Algorithm to Compact a VLSI Symbolic Layout With Mixed Constraints
Original Publication Date: 1984-Oct-01
Included in the Prior Art Database: 2005-Feb-05
A popular algorithm to compact a VLSI symbolic layout is to use a graph algorithm similar to finding the 'longest-path' in a network. The algorithm assumes that the spacing constraints on the mask elements are of the lower-bound type. However, to enable the user to have close control over the compaction result, a desired symbolic layout system should allow the user to add either the equality or the upper-bound constraints on selected pairs of mask elements as well. The algorithm described herein uses a graph-theoretic approach to efficiently solve the compaction problem with mixed constraints. In the following algorithm, the first stage in compacting the layout along one axis is to map a stick diagram to a directed graph.