Algorithms for circuit layout compaction of building blocks

Compaction is the CAD tool used to pack rough sketches or symbolic diagrams to produce error free IC layouts. With the ever increasing complexity of VLSI circuitry, the building block approach becomes very important for custom VLSI design.

A graph-theoretic compaction algorithm is developed for the compaction of symbolically specified layouts of building block LSI's. The layout area is reduced by minimizing the pitch in each dimension separately. The algorithm is capable of handling mixed constraints; i.e., the constraints arising from design rule requirements (lower-bound type), and the User defined constraints (equality and upper-bound type).