Browse Prior Art Database

Positive Cycle Detection Algorithm for Layout Compactor

IP.com Disclosure Number: IPCOM000111439D
Original Publication Date: 1994-Feb-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 4 page(s) / 113K

Publishing Venue

IBM

Related People

Lee, J: AUTHOR

Abstract

Disclosed is an algorithm for detecting positive cycles on the constraint graph. This algorithm allows the user to locate quickly an offending constraint during the layout compaction.

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

Positive Cycle Detection Algorithm for Layout Compactor

      Disclosed is an algorithm for detecting positive cycles on the
constraint graph.  This algorithm allows the user to locate quickly
an offending constraint during the layout compaction.

      A one-dimensional layout compactor converts loose IC layouts
into tight ground rule clean layouts with compaction performed
alternatively in the x- and y-direction.  For the compaction in each
direction, a constraint graph G=(V,E) was constructed through
detailed design rule analysis.  Nodes in V represent the edge
positions of layout shapes, while arcs in E represent the constraint
equations derived from the ground rules.  For compaction in the x-
direction, nodes are sorted in a left-to-right order, and arcs, E
sub r , are partitioned into   E  sub r , a set of right-directed
arcs, and E, a set of left-directed arcs.  E  sub r representing all
the minimum spacing rules, forms a single-source acrylic spanning
subgraph, while E  sub r , representing the maximum spacing rules,
contains much fewer arcs.

      Tarjan [1]  describes an O(|V| |E|) algorithm to locate a
positive cycle in a general graph.  Liao and Wong [2]  describe a
longest path algorithm for compaction, and show that there will be
positive cycles in the constraint graph if the algorithm does not
converge within |E| + 1 iterations, which corresponds to a time
complexity of O(|E  sub r | | E|).  Reference [3]  then uses this
result to locate all positive cycles with a complexity of O(E|  sup 2
|E|).  For the special case of constraint graph, the cycle detection
algorithm in [3]  is more efficient than Tarjan's algorithm, since
|Esub 1| < < min(|Esub r|, |V|).  However, since E sub 1 grows with
the size of the layout, |E sub 1| can still be a big number.  This
leads to a long run-time of algorithm [3]  for large IC layouts.

      The proposed algorithm is based on the labeling method.  For
each node, a position label is used to store the longest path length.
In addition, a parent pointer, PR, is assigned to each node to keep
track of the node's immediate predecessor in the longest path.
Initially, all the position labels of nodes except the source node
are set to (need formula) and all PR pointers are set to NIL.  Then
an iteration loop, consisting of alternative passes through  E sub r
and Esub 1, is used to search for the longest paths.  After each
right and left passes, a routine Search-cycle is used to determine
whether there are cycles on the PR-graph, which is the subgraph
constructed from arcs (PR(i),i).  It can be shown that cycles on
PR-graphs all have positive cycle lenghts.  If a positive cycle is
found or the longest path search converges, the iteration loop is
terminated.  The proposed algorithm is given as follows:

Algorithm Compaction(G)

1 Set (need formula)

2 Repeat

3  Set converge = true

4  Breadth-first-search(E,{x}, converge)

5  For each arc(i,j) in E do labeling...