A system for hierarchical constraint graph generation and graph compaction for symbolic layout

The authors present a novel approach to and system for graph oriented layout compaction for large symbolic layout designs. Hierarchical compaction is performed by first generating geometrical interfaces for compacted subcells which are used as rigid nodes in graphs at higher hierarchical levels. Among other things, technology independency is achieved by defining constraint graphs for leaf cells (contacts, transistors etc.) for each different technology, which can be instantiated (hierarchically or flat) in the constraint graphs of more complex cells (invertor, fulladder, etc.). Further reduction of the complexity of graph generation and compaction is achieved by setting only local constraints in the graphs, which requires an iterative graph-generation/compaction scheme. The compaction algorithm performs a bidirectional breadth-first search through the graph to position layout edges in the critical path and distribute slack