US 6,662,348 B1 · Non-linear optimization system and method for wire length and density within an automatic electronic circuit placer

Abstract

A computer implemented process for automatic creation of integrated circuit (IC) geometry using a computer. The present invention includes a general unconstrained non-linear optimization method to generate coarse placement of cells on a 2-dimensional silicon chip or circuit board. In one embodiment, the coarse placer can also be used to automatically size cells, insert and size buffers, and aid in timing driven structuring of the placed circuit. The coarse placer is used in conjunction with other automatic design tools such as a detailed placer and an automatic wire router. A master objective function (MOF) is defined which evaluates a particular cell placement. A non-linear optimization process finds an assignment of values to the function variables which minimizes the MOF. The MOF is a weighted sum of functions which evaluate various metrics. An important metric for consideration is the density metric, which measures how well, spread out the cells are in the placement. Other component functions are wire-length, which measures total linear wire-length, delay, which measures circuit timing, and power, which measures circuit power consumption. The barrier metric penalizes placements with cells outside the allowed placement region. A conjugate-gradient process utilizes both the MOF and its gradient to determine a next cell placement. The gradient is the vector of partial derivatives of the MOF with respect to all variables. The non-linear optimization process calls the MOF and gradient function subroutines and uses the results to minimize the MOF.

Claims32

Dependent claims

A method of placing cells within a netlist describing a physical integrated circuit that is to be fabricated on a substrate within a chip area, said netlist comprising a plurality of cells having an initial cell placement and wire connections between said plurality of cells, said method comprising the steps of:

a) determining a function of cell placement of said plurality of cells wherein said function is continuous and differentiable;
and
b) performing multiple iterations of an automatic placer process to determine a final cell placement of said plurality of cells, said final cell placement simultaneously minimizing said function, wherein said automatic placer process utilizes a conjugate-gradient optimization process.

A computer system comprising:

a processor coupled to a bus;
and
a memory coupled to said bus, said memory containing instructions for implementing a processor controlled method of placing cells within a netlist that describes a physical integrated circuit that is to be fabricated on a substrate within a chip area, said netlist comprising a plurality of cells having an initial cell placement and wire connections between said plurality of cells, said method comprising the steps of:
a) determining a function of cell placement of said plurality of cells wherein said function is continuous and differentiable;
and
b) performing multiple iterations of an automatic placer process to determine a final cell placement of said plurality of cells, said final cell placement simultaneously minimizing said function, wherein said automatic placer process utilizes a conjugate-gradient optimization process.

3 more elements

Dependencies are inferred from the claim text.

Non-linear optimization system and method for wire length and density within an automatic electronic circuit placer

Life of this patent

Non-linear optimization system and method for wire length and density within an automatic electronic circuit placer

Life of this patent

Abstract

Claims32