Hier archical pitchmaking compaction method and system for integrated circuit design

• US 5,381,343 A
• Filed: 05/26/1992
• Issued: 01/10/1995
• Est. Priority Date: 05/26/1992
• Status: Expired due to Term

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Bamji, Cyrus, Varadarajan, Ravi
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): Wieland, Susan
• Application Number:
  US07/889,831
• Time in Patent Office: 959 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491
• US Class Current: 716/122
• CPC Class Codes: G06F 30/398 Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] optical proximity correction [OPC] design processes G03F1/36

Abstract

A hierarchical pitchmatching compactor is provided that maintains hierarchical structure, design rule correctness, and circuit integrity of a symbolic layout while globally compacting the layout without excessive computational or data handling requirements, even for layouts of substantial size. The compactor achieves this result by taking advantage of the regularity of the layout, to reduce the number of constraints in the linear programming problem to a minimum level. This minimal problem, called the minimum design, can be drastically smaller than the original minimization problem for layouts of practical interest. This technique is implemented by means of a computer program that operates on the original symbolic layout of an integrated circuit to produce an automatically compacted layout as the data output.

Claims

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.

2. The method for compacting of claim 1 further comprising a first step of:

digitizing the integrated circuit layout in order to convert a physical layout to a coordinate layout representation suitable for computer implementation.

3. The method of claim 1 wherein the step of minimizing the geometrical area of the normalized circuit layout is performed using linear programming methods to solve the minimum sets of primitive loop, intracell, and intercell constraints.

4. A compaction system for minimizing 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 a interface, the system comprising:

processor means for executing programmed instructions, and for storing and retrieving data;

program memory means connected to the processor means for storing program instruction steps for execution by the processor means;

layout coordinate memory means connected to the processor means for storing data relating to layout coordinates of the circuit layout to be compacted, from which the processor means extracts data relating to cell interconnections and relative placements between cells contained in the circuit layout;

normalized layout memory means connected to the processor means for storing layout coordinates resulting from normalization of the circuit layout by the processor means wherein all cell interconnections are defined by abutment from which the processor means extracts data relating to the interconnections and relative placements between cells contained in the normalized circuit layout;

interface graph memory connected to the processor means for storing interface graph representations of normalized layout cells as determined by the processor means from the stored layout coordinates of the normalized circuit layout;

primitive loop memory means connected to the processor means for receiving and storing data generated by the processor means from the interface graph representations stored in the interface graph memory means relating to relationships between the relative placements of a plurality of cells contained in the normalized circuit layout;

intracell constraint memory means connected to the processor means for storing a list of design rule constraints related to electrical interaction and geometrical spacing relationships between elements within the cells;

intercell constraint memory means connected to the processor means for storing constraints describing abutment relationships across interfaces between cells for preserving abutment and design rule enforcement across cell boundaries; and

compacted coordinate memory means for storing compacted coordinates resulting from solving a minimized set of constraints stored in the primitive loop memory means, the intracell constraint memory means, and the intercell constraint memory means, by the processor in accordance with executed program instructions stored in the program memory means.

5. A computer implemented method for compacting the geometrical area of an integrated circuit layout by removing geometrical regularities in the circuit layout, wherein the method comprises the steps:

defining the circuit layout by a system of equations;

factoring the equations into classes, each class of equation representing a type of constraint applied to the circuit layout;

minimizing the equations of each class into a minimum set of equations;

simultaneously solving the minimum set of equations; and

recreating the circuit layout in compacted form from solutions to the minimum set of equations.

6. The method of claim 5, wherein the step of factoring the equations into classes comprises factoring the equations into at least three independent classes including primitive loop constraint equations, intracell constraint equations and intercell constraint equations.