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

• US 6,301,693 B1
• Filed: 12/16/1998
• Issued: 10/09/2001
• Est. Priority Date: 12/16/1998
• Status: Expired due to Term

• Current Assignee: Synopsys Incorporated
• Original Assignee: Synopsys Incorporated
• Inventors: Naylor, William C., Sha, Lu, Donelly, Ross
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): Garbowski, Leigh Marie
• Application Number:
  US09/216,632
• Time in Patent Office: 1,028 Days
• Field of Search: 716/1, 716/2, 716/4, 716/5, 716/6, 716/8, 716/9, 716/10, 716/18, 716/11, 703/2
• US Class Current: 716/114
• CPC Class Codes: G06F 2119/06 Power analysis or power optimisation
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

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.

Claims

1. A method of placing cells within a netlist, said method comprising the steps of:

a) receiving a netlist describing a circuit to be fabricated on a substrate within a chip area, said netlist comprising a plurality of cells having an initial cell placement and having wire connections between said plurality of cells; and

b) determining a cell placement of said plurality of cells using iterations of a non-linear optimization process including an objective function that is differentiable and continuous but is not quadratic in terms of wire length of said wire connections, said objective function including a delay objective function for measuring the worst path signal delay through said netlist in terms of each cell placement and including a wire length objective function for minimizing said wire length of said wire connections, wherein said non-linear optimization process utilizes the conjugate-gradient.

2. A method as described in claim 1 wherein said non-linear optimization process comprises the steps of:

b1) smoothing said objective function according to a variable, alpha, to produce a smoothed function;

b2) computing a negative gradient of said smoothed function;

b3) searching, from a starting point, along said smoothed function in a direction of said negative gradient to determine a current solution;

b4) revising said variable alpha; and

b5) repeating steps b1) through b4) a number of times and returning a solution wherein said starting point of step b3), for each respective iteration of step b3), is a solution determined in a last iteration of step b3).

3. A method as described in claim 2 wherein said delay objective function is based on wire parameters that include half-perimeter wire length computations involving a log_sum_exp( ) function that is smoothed based on said smoothing variable, alpha.

4. A method as described in claim 2 wherein said step b2) is computed based on a reverse breadth-first traversal through said netlist computing partial derivatives of said delay objective function with respect to individual cells.

5. A method as described in claim 1 wherein said delay objective function is calculated by a forward breadth-first static timing calculation through said netlist.

6. A method as described in claim 1 wherein said delay objective function includes stage delay computations that are based on wire capacitance and wire resistance, said wire capacitance being based on half-perimeter wire length computations and said wire resistance being based on manhattan distance wire length computations.

7. A method as described in claim 1 wherein said delay objective function includes stage delay computations that are based on Elmore-Rubenstein-Penfield (ERP).

8. A method as described in claim 1 wherein said delay objective function includes stage delay computations that are based on Asymptotic Waveform Expansion (AWE).

9. A method as described in claim 1 wherein said delay objective function includes stage delay computations and further comprising the step of performing automatic cell sizing by basing said stage delay computations on cell sizing within said delay objective function.

10. A method as described in claim 1 wherein said delay objective function includes stage delay computations and further comprising the step of approximating the effects of automatic buffer insertion within said stage delay computations to reduce said worst path signal delay.

11. A method as described in claim 1 further comprising the step of deriving said worst path signal delay using automatic buffer insertion, and wherein said step of deriving said worst path signal delay using automatic buffer insertion is approximated using the equation:

$\mathrm{delay}<br><br>\left(x\right)=\begin{array}{cc}\mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(0\le <br><br>x\le <br><br>T\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{then},& \left({\mathrm{ax}}^2+\mathrm{bx}+c\right)\\ \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(x\ge <br><br>T\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{then},& \left(\mathrm{dx}+e\right)\end{array}$

where T is a threshold delay value and a, b, c, d and e are constants.

12. A method as described in claim 1 further comprising the step of computing delay estimates through a gate structure using buffer tree rebalancing and wherein said delay estimates are used in said delay objective function.

13. A method as described in claim 12 wherein buffer tree rebalancing is modeled by the tree-depth relationship:

$1=\underset{i}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>(1/\left(2^{\left(\mathrm{di}/T\right)}\right)$

where di is the delay from input to output and where the summation is performed over all outputs, i.

14. A method as described in claim 12 wherein said buffer tree rebalancing is modeled by additional variables associated with the wire to be buffered and a forward traversal is used.

15. A method as described in claim 12 wherein stage delay to the output, di, of said buffer tree rebalancing is modeled using equation:

$\mathrm{di}=\frac{T}{\log <br><br>\text{\hspace{1em}<br><br>}<br><br>\left(2\right)}<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{i}{\mathrm{log\_sum}<br><br>\mathrm{\_exp}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\frac{\log <br><br>\text{\hspace{1em}<br><br>}<br><br>\left(2\right)}{T}\times <br><br>\mathrm{vi}\right)-\mathrm{vi}.$

16. A method as described in claim 12 wherein said buffer tree rebalancing is modeled using the relationship:

$\mathrm{Ain}=T/\log <br><br>\text{\hspace{1em}<br><br>}<br><br>\left(2\right)\times <br><br>\mathrm{log\_}<br><br>\underset{i}{\mathrm{sum}}<br><br>\mathrm{\_exp}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\left(\log <br><br>\text{\hspace{1em}<br><br>}<br><br>\left(2\right)/T\right)\times <br><br>\mathrm{Ai}\right))$

wherein Ai represents required times and i represents outputs.

17. A method as described in claim 1 wherein said delay objective function includes stage delay computations and further comprising the step of estimating the effects of timing-driven-synthesis optimizations and wherein said stage delay computations approximate said effects of timing-driven synthesis optimizations.

18. A method as described in claim 17 wherein said timing-driven synthesis optimization is modeled by the tree-depth relationship:

$1=\underset{i}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>(1/\left(2^{\left(\mathrm{di}/T\right)}\right)$

where di is the delay from input to output and where the summation is performed over all inputs, i.

19. A method as described in claim 17 wherein said timing-driven synthesis is modeled by additional variables and a reverse traversal is used.

20. A method as described in claim 17 wherein stage delay to the output, di, of said timing-driven synthesis is modeled using equation:

$\mathrm{di}=\frac{T}{\log <br><br>\text{\hspace{1em}<br><br>}<br><br>\left(2\right)}<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{i}{\mathrm{log\_sum}<br><br>\mathrm{\_exp}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\frac{\log <br><br>\text{\hspace{1em}<br><br>}<br><br>\left(2\right)}{T}\times <br><br>\mathrm{vi}\right)-\mathrm{vi}.$

21. A method as described in claim 17 wherein said timing-driven synthesis optimizations are modeled using the relationship:

$\mathrm{Aout}=T/\log <br><br>\text{\hspace{1em}<br><br>}<br><br>\left(2\right)\times <br><br>\mathrm{log\_}<br><br>\underset{i}{\mathrm{sum}}<br><br>\mathrm{\_exp}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\left(\log <br><br>\text{\hspace{1em}<br><br>}<br><br>\left(2\right)/T\right)\times <br><br>\mathrm{Ai}\right))$

wherein Ai represents arrival times and i represents inputs.

22. A method as described in claim 1 wherein said objective function further includes a density objective function for penalizing uneven cell distributions of said cell placements.

23. A method as described in claim 22 wherein said step b), in solving said density objective function, comprises the steps of:

b1) defining a field of discrete grid points within said chip area;

b2) determining, for each cell, spatial potentials effecting grid points near each cell;

b3) determining a summed potential for each grid point of said chip area by summing the spatial potential contributions from all cells for each grid point; and

b4) determining a result of said density objective function by determining an error, at each grid point, between its summed potential and an average potential.

24. A system comprising:

a processor coupled to a bus

a memory coupled to said bus and wherein said memory contains instructions that when executed implement a method of placing cells within a netlist, said method comprising the steps of;

a) receiving a netlist describing a circuit to be fabricated on a substrate within a chip area, said netlist comprising a plurality of cells having an initial cell placement, an initial cell sizing and wire connections between said plurality of cells; and

b) determining an optimized cell placement and cell sizing of said cells of said netlist using iterations of a non-linear optimization process that performs simultaneous cell placement and cell sizing wherein said non-linear optimization process minimizes an objective function that is differentiable and continuous but is not quadratic in terms of wire lengths of said wire interconnections, said objective function including a wire length objective function and a delay objective function having terms defined with respect to cell placement and cell sizing.

25. A system as described in claim 24 wherein said non-linear optimization process comprises the steps of:

b1) smoothing said objective function according to a variable, alpha, to produce a smoothed function;

b2) computing a negative gradient of said smoothed function;

b3) searching, from a prior solution, along said smoothed function in a direction of said negative gradient to determine a current solution;

b4) revising said variable alpha; and

b5) repeating steps b1) through b4) a number of times to arrive at a solution.

26. A system as described in claim 25 wherein cell size is an exponential transform of an associated variable which is given by the relationship:

27. A system as described in claim 25 wherein said delay objective function is calculated by a forward breadth-first static timing calculation through said netlist.

28. A system as described in claim 25 wherein said delay objective function is based on wire parameters that include half-perimeter wire length computations involving a log_sum_exp( ) function that is smoothed based on said smoothing variable, alpha.

29. A system as described in claim 25 wherein said delay objective function includes stage delay computations that are based on wire capacitance and wire resistance, said wire capacitance being based on half-perimeter wire length computations and said wire resistance being based on manhattan distance wire length computations.