A hierarchical graph oriented compaction system for symbolic layout

A new graph-oriented compaction system is presented for large symbolic layout designs. True hierarchical compaction is performed by first generating geometrical interface for compacted subcells which are used in graphs at higher hierarchical levels. Among other things, technology independence is achieved by defining constraint graphs for leaf cells (contacts, transistors, etc.) for each different technology, which can be instantiated in the constraint graphs of more complex cells (invertor, full adder, 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