Browse Prior Art Database

Improved Longest Path Algorithm for Layout Compaction

IP.com Disclosure Number: IPCOM000105569D
Original Publication Date: 1993-Aug-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 4 page(s) / 113K

Publishing Venue

IBM

Related People

Lee, JF: AUTHOR

Abstract

A software algorithm is disclosed for the IC layout compactor. This algorithm achieves a better computational efficiency over the popular LW algorithm lbracket 1 rbracket .

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

Improved Longest Path Algorithm for Layout Compaction

      A software algorithm is disclosed for the IC layout compactor.
This algorithm achieves a better computational efficiency over the
popular LW algorithm lbracket 1 rbracket .

      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.  The compaction in each
direction is a two-step process:  (1)First, a constraint graph
G=(V,E) was constructed through detailed design rule analysis, and
(2) the constraints are then solved with graph-based compaction
algorithms.  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, are partitioned into E
sub r , a set of right-directed arcs, and E sub l , a set of
left-directed arcs.  E sub r, representing all the minimum spacing
rules, forms a single-source acyclic spanning subgraph, while E sub
r, representing the maximum spacing rules, contains much fewer arcs.

      LW algorithm lbracket 1 rbracket uses the longest path method
to solve the constraint equations.  Since E sub r  is a single-source
acyclic spanning subgraph, the labeling method combined with a
breadth-first search is used to calculate the position of a node,
say,V sub i (X) , as the longest path length from the source node to
that node in E sub r . This constitutes one right pass in LW
algorithm.  However, these position labels may not satisfy the
constraints in E sub l . So a left pass follows, in which each arc in
E sub l  is examined, and the positions are updated accordingly if
new longest paths are found by adding a left-directed arc.  To find V
sub i (X)  satisfying all constraints in G, LW algorithm executes
consecutive right and left passes through E sub r  and E sub l ,
until the solution converges.  During each right pass, at most one
path segment consisting of right-directed arcs is added to the
longest path, while during each left pass, at most one left-directed
arc is added.  If G does not contain positive cycle, then LW
algorithm converges when the number of passes reaches L= max lbrace L
sub  i rbrace +1 where L sub i  is the minimum number of
left-directed arcs in the longest paths from the source node V sub 0
to node V sub i .

      The proposed compaction algorithm will use the breadth-first
search for both E sub r  and E sub l .  Since E sub l  may contain
many nodes with no ancestor, the breadth-first search procedure in LW
algorithm needs to be generalized.  The breadth-first search uses a
queue, Q , to keep track of the search order for nodes to be visited.
For E sub r , Q starts naturally from the single source node.  For E
sub l , we need to incorporate all the nodes with no ancestor into Q,
(See Line 1 in procedure BreadthfirstSearch),...