Patent Document ID: 5381343
Application ID: 07889831
Patent Flag: 1

Claim One:
1. A computer implemented method for compacting the geometrical area of an integrated circuit layout including a plurality of cells, each cell including at least one circuit element, each cell interconnected with at least one other cell across an interface, the method comprising the steps of: normalizing the circuit layout such that all cell interconnections are defined by abutment with other cells in a single level layout; generating interface graphs of the normalized circuit layout, wherein each cell within the circuit layout is represented by a node and relative placements of interconnected cells are represented by edges connecting the nodes representing the cells; generating a minimum set of primitive loop constraints, each primitive loop constraint representing a relationship between relative placements of a plurality of nodes of the interface graphs; generating a minimum set of intracell constraints, each intracell constraint describing electrical interactions and geometrical spacing relationships between elements within a cell; generating a minimum set of intercell constraints, each intercell constraint describing an abutment relationship between cells, for preserving electrical connectivity and design rule enforcement across cell interfaces; minimizing the geometrical area of the normalized circuit layout by simultaneously solving the minimum sets of primitive loop, intracell and intercell constraints; reconstructing the normalized integrated circuit layout by reversing the generation of the interface graphs using the solutions to the minimum sets of primitive loop, intracell and intercell constraints: and denormalizing the reconstructed normalized integrated circuit layout to produce the compacted integrated circuit layout.