Synopsys, Inc.

William C Naylor

Ross Alexander Donelly

Lu Sha

Ronald A Miller

Yiu-Chung Wong

Jason R Woolever

Michael Fu

A detailed placement process which optimizes cell placement with up to one hundred percent densities in a linear run time. The output from a conjugate-gradient coarse placement process is input to the detailed placement process. A dynamic programming technique is used to optimize cell placement by swapping cells between two or more rows. The search space is pruned beforehand. A greedy cleanup phase using an incremental row placer is used. Thereby, the detailed placement process handles congestion driven placements characterized by non-uniform densities expeditiously and efficiently.

Detailed placer for optimizing high density cell placement in a linear runtime

A method and system for the simultaneous placement of large and small cells in an electronic circuit. A coarse placement using well known methods may provide an initial placement of cells. Cells meeting a size criteria may be selected for further processing. An optimum cell orientation may be determined. An optimum axis of movement for separation may be determined. Overlapping cells may be separated and their positions may be optimized in both horizontal and vertical directions. Any cell moved from its initial placement may be fixed so as not to be moved during subsequent placements. This process may be repeated for cells meeting a new, generally smaller, size criteria. A well known detailed placement process may finalize a design. In this novel manner, large and small cells may be automatically simultaneously placed, deriving speed and quality advantages over prior art methods.

Simultaneous placement of large and small cells in an electronic circuit

A method and system of constrained optimization with linear constraints to remove overlap among cells of an integrated circuit. A coarse placement using well known methods may provide an initial placement of cells. Overlapping cells are separated. Any cell moved to its initial placement may be fixed so as not to be moved during subsequent placements. A plurality of linear inequalities representing allowable placements of a plurality of cells of a layout is generated. An objective function measuring cell movement subject to the constraints of the plurality of inequalities is minimized. The objective function minimizes cell movement from the initial cell placement. In this novel manner, large and small cells may be automatically simultaneously placed, deriving speed and quality advantages over prior art methods.

Constrained optimization with linear constraints to remove overlap among cells of an integrated circuit

A computer implemented process for the automatic creation of integrated circuit (IC) geometry including a multiple pass process flow using multiple passes of direct timing driven placement after a first pass of non-direct timing driven placement. First, a high level description of the circuit design may be synthesized. Next, a non-direct timing driven placement process may place the design. Then the placed design may be routed. Alternatively, routability may be estimated. After routing, a modified design may be resynthesized. The resynthesized design may then be placed according to a direct timing driven placement process. This sequence may be repeated several times.

Multiple pass optimization for automatic electronic circuit placement

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.

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

A method and system for the quick placement of electronic circuits using orthogonal one dimensional placements. All circuits of a design may be placed in a linear dimension to obtain a first placement. Next, those same circuits may be placed in a second linear dimension, orthogonal to the first dimension, in order to obtain a second placement. Finally, a two dimensional placement for the circuits may be created by selecting for each circuit element a first coordinate from the first placement and a second coordinate from the second placement.

Quick placement of electronic circuits using orthogonal one dimensional placements

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.

Growing community of inventors

San Jose, CA, United States of America

William C Naylor