Method and apparatus for constraint graph based layout compaction for integrated circuits

Abstract

The present layout compaction technique compacts circuit elements in two dimensions of a circuit layout with reduced computational requirements. A circuit layout representation is converted to a constraint graph representation in a reference direction. An orthogonal constraint graph is also constructed. A critical path subgraph is constructed based upon the reference and orthogonal constraint graphs, where one or more critical paths are chosen as the longest paths between the source and sink vertices of the reference constraint graph. Further, each vertex in the constraint graph is converted to an input vertex for each incoming shear edge and an output vertex for each outgoing shear edge. Jogging edges are created between each input and output vertices in the critical path subgraph. Weight values are assigned to each shear and jogging edge. An optimal cutset is determined, which comprises a substantially minimum or substantially maximum cutset based on the sum of weights of the edges of the constraint graph subgraph. The critical path is reduced, where removing a shear edge denotes moving a corresponding circuit element by a certain amount and removing a jogging edge denotes a jog insertion of a flexible element by breaking the element into multiple elements and inserting a jog. The reference and orthogonal directions are swapped and the procedure is repeated for the orthogonal direction. The entire process is iterated for both dimensions until the one or more critical paths are no longer reduceable so that an optimal compaction solution is achieved in two dimensions.