Browse Prior Art Database

Soft Constraints for Layout Compaction

IP.com Disclosure Number: IPCOM000109620D
Original Publication Date: 1992-Sep-01
Included in the Prior Art Database: 2005-Mar-24
Document File: 4 page(s) / 220K

Publishing Venue

IBM

Related People

Burns, JL: AUTHOR [+2]

Abstract

Disclosed are the idea of soft constraints and an algorithm to implement them on the one-dimensional layout compactor, a Computer-Aided Design software tool. One dimensional compaction approaches often get stuck at sub-optimal solutions when there are two-dimensional deadlocks. Soft constraints are introduced as a way to prevent deadlocks.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 37% of the total text.

Soft Constraints for Layout Compaction

       Disclosed are the idea of soft constraints and an
algorithm to implement them on the one-dimensional layout compactor,
a Computer-Aided Design software tool.  One dimensional compaction
approaches often get stuck at sub-optimal solutions when there are
two-dimensional deadlocks.  Soft constraints are introduced as a way
to prevent deadlocks.

      The layout compaction approach (1) is widely adopted by design
communities to handle complex technology and design requirements.
Because the two-dimensional compaction problem is NP-hard (2), the
only practical solution is the one-dimensional approach in which the
layout is compacted alternately in the x and y directions.  Of
course, one-dimensional compaction does not always give the best
layout.  As an example, Fig. 1(a) shows four rectangle circuit
symbols A, B, C, D, and one wire connecting C and D.  Assume that
symbols are not allowed to overlap.  Then symbols A and B form a
two-dimensional deadlock [3].  If we do x-compaction first, then
symbol B will slide below symbol A and a 20x24 layout (Fig. 1(b)), is
produced after the y-compaction.  However, the best layout is 20x16
(Fig. 1(c)), in which symbol B is placed to the right of symbol A and
the bottom of symbol C.  To achieve this best layout with a
one-dimensional compaction approach, we need a mechanism  to keep
symbol B to the right of symbol A during x-compaction.  In this
article we introduce a new type of constraint, called a soft
constraint, to serve this purpose.

      Before giving a definition for soft constraint, we first review
the popular one-dimensional compaction approach in which a constraint
graph  is generated to represent minimum and maximum constraints.
These are hard constraints derived from the ground rules.  In what
follows, we shall consider the x-constraint graph, G=(V, E) (y-
direction is the same) where V is a set of nodes that represents the
center positions xi of the symbols, and E is a set of edges that
represents spacing weights, xj - xi / wij.  Nodes xj and xi are the
head and the tail of the edge.  Two special nodes, L and R, denote
the left and right boundaries of the cell.  Nodes are sorted in a
left to right order.  A minimum constraint xj - xi / wij is
represented by a right-directed edge of weight wij, while a maximum
constraint is represented by a left-directed edge.  A longest path
algorithm (4) will yield a solution with a minimum cell size, R-L, if
there is no positive cycle in G.

      A soft constraint is defined as a user-specified constraint,
which needs to be satisfied if and only if its inclusion into the
constraint graph does not create positive cycles or increase the cell
size.  Just like a hard constraint, a soft constraint will be
assigned a weight to specify the preferred spacing, and there are two
types of soft constraints: soft minimum and maximum constraints.
Since several soft constraints sometimes can...