Browse Prior Art Database

Detection of Overconstraints in IC Layout Compaction

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

Publishing Venue

IBM

Related People

Burns, JL: AUTHOR [+2]

Abstract

Disclosed is an algorithm for detecting illegal component configurations during IC layout compaction. An illegal configuration results in a so-called overconstraint, or posit cycle. The disclosed algorithm determines, in a single execution, the layout components and design rules that comprise each overconstraint. This information can then be used to correct the layout.

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

Detection of Overconstraints in IC Layout Compaction

       Disclosed is an algorithm for detecting illegal component
configurations during IC layout compaction.  An illegal configuration
results in a so-called overconstraint, or posit cycle.  The disclosed
algorithm determines, in a single execution, the layout components
and design rules that comprise each overconstraint.  This information
can then be used to correct the layout.

      Layout compactors map loose layouts into dense, manufacturable
layouts (1).  Most compactors employ the one-dimensional,
constraint-based formulation (2) in which the layout is compacted in
a sequence of pitch-minimization iterations in alternating
directions. In each iteration, the layout is mapped into a constraint
graph G = (V, E).  Each component maps to a vertex v e V; each
spacing or size requirement maps to an edge (constraint) e e E.  In a
horizontal compaction, the edge set E can be partitioned into two
subsets EF and EB, consisting of constraints of the form xj - xi >
lij and xi - xj > - uji, respectively.  Here, lij and uji are
typically nonnegative integers, xi is the x-coordinate of some
element, and xj is the x-coordinate of a second element further to
the right.

      The minimum pitch of the layout is found by performing a
longest-path analysis on G.  The longest path does not exist,
however, if G contains one or more directed cycles of net positive
weight.  A positive cycle (overconstraint) indicates that there is no
realizable placement of the corresponding layout elements.  The graph
in the figure has two cycles, one of which is positive.  A practical
compactor must have a mechanism for detecting the vertices and edges
in any positive cycles that are present, so that the user can remove
the overconstraints by altering the layout.

      The disclosed algorithm is based on the longest-path algorithm
of Liao and Wong (3).  Liao and Wong's algorithm (denoted the LW
algorithm) is the basic form of the longest-path algorithm used,
e.g., in the PSI (4) and SLS (5) compactors.

      Two facts have been exploited to enhance the efficiency of the
disclosed algorithm.  First, when the LW algorithm terminates due to
an overconstraint, all constraints in EF are satisfied but at least
one in EB is not (3).  Second, most graphs have             The
subset of constraints in EB which remain unsatisfied when the LW
algorithm terminates is denoted Eb.  At least one of the constraints
in Eb belongs to a positive cycle.  However, some of the constraints
in Eb may indeed be satisfiable.  The disclosed algorithm analyzes
each constraint in Eb in turn to determine whether it is satisfiable.
If so, it is allowed to remain in G.  If not, it is removed from
G and the other vertices and constraints in the corresponding
positive cycle are reported.

      Consider constraint (n,m) e Eb with weight -enm .  As shown in
the figure, vertex n is at its tail and ver...