Hierarchical pitchmatching compaction using minimum design

A new hierarchical compactor capable of compacting and pitchmatching hierarchically defined layouts is described. The hierarchical compactor can handle most input hierarchies, including multilevel hierarchies, over the cell routing and cell rotations and reflections. The compactor simultaneously compacts the contents of all the cells of the layout hierarchy maintaining the hierarchy of the input layout as well as the pitchmaking and abutment constraints between the cells. The hierarchical compactor automatically factors out the regularity in the layout and performs almost all of its operations on a minimum design. This novel and unique formulation of the hierarchical compaction problem enables compaction time to be a function of the irregularity rather than the size of the layout