Browse Prior Art Database

# Layout Compaction Algorithm With Multiple Grid Constraint

IP.com Disclosure Number: IPCOM000102629D
Original Publication Date: 1990-Dec-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 5 page(s) / 172K

IBM

Lee, JF: AUTHOR

## Abstract

As ground rules become more complex with technology, we need to consider the compaction problem with multiple grid constraints, which is a mixed integer problem. A new polynomial time algorithm is developed.

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

Layout Compaction Algorithm With Multiple Grid Constraint

As ground rules become more complex with technology, we
need to consider the compaction problem with multiple grid
constraints, which is a mixed integer problem.  A new polynomial time
algorithm is developed.

Graph-based layout compactors become powerful tools, because
they can be adapted to complex technology rules and design
constraints.  One type of design constraint often encountered when
compacting a cell is the grid constraint. That is, selected objects
need to be placed on the grid. The reasons behind this constraint:
(1) The pin positions of macro cells are often required on the wiring
grids, so that the global routers (1) can wire up these macro cells.
(2) Keeping wires on grid can improve the porosity of the cell.  The
compaction problem with grid constraints turns out to be a mixed
integer problem.  An algorithm dealing with one grid constant is
given in (2).  Different mask levels in general have different sets
of ground rules.  So we may encounter the situations that we have to
deal with several grids.  In this article, we will present an
algorithm to solve the compaction problem when multiple grids need to
be considered.

Ground rule constraints of VLSI circuits are typically
specified in terms of minimum and maximum seperation between
different circuit components, which generates a set of constraint
equations xi - xj / l(ij) among the positions {x} of components.
These equations can be represented by a directed graph, G = (V,E),
called the constraint graph, in which the nodes are components or
groups of components, and edges are constraints.  Nodes are labelled
with components' positions, while the edges are labelled with the
spacing l(ij).  The compaction is then the problem of finding xi such
that the minimum cell span is obtained.

In the case of multiple grids, we have several grid constants
d(1), d(2).., and the positions of some nodes need to be integer
multiples of these grid constants.  Such nodes are called grid nodes
to distinguish from the rest of nodes which will be called non-grid
nodes.  We shall make the assumption that the least common multiple
(LCM) of grid constants d(1), d(2) ... exists:
D = LCM (d(1), d(2).. ) = d(1) d(2)../GCD (d(1), d(2).. )      (1)

Here GCD is the greatest common divisor.  In reality, all the
ground rules are expressed in terms of the basic mask resolution
unit, r, which is a common divisor of d(1), d(2)..., so our
assumption about the existence of LCM is valid.  A node may consist
of several circuit components, which move together during the
compaction.  Such a grid node is required simultaneously on several
grids, d(il), d(i2), ..., which means that the node's position xi
must be an integer multiple of the least common multiplier:
D(i) = LCM (d(il), d(i2)..) (2) Since {d(il), d(i2), ...}  is a
subset of {d(i), ...}, D is an integer multiple of D(i).

...