Interactive time-driven method of component placement that more directly constrains critical paths using net-based constraints

• US 5,666,290 A
• Filed: 12/27/1995
• Issued: 09/09/1997
• Est. Priority Date: 12/27/1995
• Status: Expired due to Fees

• Current Assignee: VLSI Technology, Inc. (Koninklijke Philips N.V.)
• Original Assignee: VLSI Technology, Inc. (Koninklijke Philips N.V.)
• Inventors: Li, Ying-Meng, Ashtaputre, Sunil
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): GARBOWSKI, LEIGH M
• Application Number:
  US08/579,381
• Time in Patent Office: 622 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491
• US Class Current: 716/113
• CPC Class Codes: G06F 30/33 Design verification, e.g. functional simulation or model checking
• CPC Class Codes: G06F 30/3308 using simulation
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A method of optimizing the placement of components of an integrated circuit to ensure that all circuit paths will meet their timing criteria, as well as to minimize area and total wire length is disclosed. The method employs a non-constant net weighting distribution along critical paths to encourage a mincut algorithm to place components so that path lengths are minimized as well as the entire nets coupled to paths. The magnitude of weights assigned are commensurate with the slack the path has with respect to its maximum delay constraint, as well as the level of method iteration. Any nets not deemed critical are assigned a minimum capacitance constraint to prevent them from becoming critical as a function of actual placement. Weights assigned to capacitively constrained nets are inversely proportional to the difference between the maximum capacitance allowed and the estimated capacitance of the current placement. A novel manner of estimating the propagation delay along the interconnect of the critical path is implemented. A novel weighting of driver/buffer pairs ensure that the most sensitive nets of the pairs are kept short.

Claims

1. A method for optimizing the placement of components of an integrated circuit, the components interconnected by nets to form paths wherein each of the nets couples an output of one of the components to one or more inputs of one or more of the components, and wherein each of the paths comprises one or more segments, each of the segments of one of the paths comprising one of the components and the net coupled to the output of the component, each of the segments of one of the paths coupled by a branch of its net to an input of one of the components comprising a next segment in the path, said method comprising the steps of:

identifying one or more of the paths as critical;

imposing a maximum delay constraint on each of the critical paths;

performing an initial placement of the components which becomes the current placement;

for each of the critical paths;

estimating a path delay for the critical path based on the current placement; and

assigning weight values to each of the nets which form part of the segments of the critical path, said assigned weight values having a non-constant distribution based on location of the segment in the critical path of which each net is a part;

assigning a default weight value to each of the nets not previously assigned a weight;

applying a mincut algorithm to find a placement of the components that minimizes total weight of the nets crossing a cut line, the weight minimized placement becoming the current placement; and

iterating said method from said step of estimating path delays through said step of applying a mincut algorithm until the components are optimally placed.

2. The method of claim 1 wherein the non-constant distribution of weight values assigned to the nets forming part of the segments of one of the critical paths decreases continuously from a peak value assigned to the net of the center-most segment of the critical path to a minimum value assigned to the nets of the two outer-most segments of the critical path.

3. The method of claim 2 wherein the distribution of the assigned weight values decreases linearly from the peak value to the minimum value.

4. The method of claim 2 wherein the distribution of the assigned weight values is convex in nature.

5. The method of claim 1, wherein at least one of said iterations of said method further comprises the steps of:

constraining one or more of the nets with a maximum capacitance value; and

for each of the nets constrained by a maximum capacitance value;

estimating total capacitance of the net based on the current placement; and

assigning a weight value to the net that is inversely proportional to the difference between the maximum capacitance value and the estimated total capacitance.

6. The method of claim 5 wherein any of the nets having multiple assigned weight values is deemed to be assigned the maximum of the multiple assigned weight values.

7. The method of claim 1 or 5 wherein said step of estimating a path delay further comprises the steps of:

determining delay (D_S) for each of the segments of the critical path in accordance with D_S =D_i +S·

C_in +S·

C_W +D_RC wherein D_i is intrinsic delay through the component of the segment, S is effective resistance of the component of the segment, C_in is summation of all input capacitance coupled to the net of the segment, C_W is total capacitance presented to the output of the component of the segment by the net of the segment, and D_RC is propagation delay along the branch of the net of the segment which couples the component of the segment to the component of the next segment of the path; and

summing the delays D_S for all of the segments of the path.

8. The method of claim 7 wherein the step of assigning weight values to each of the nets which are part of the segments of the critical path further comprises the step of computing the slack for the critical path in accordance with SLACK=D_C -D_I, wherein D_C is the maximum delay constraint imposed on the critical path and D_I is a summation of D_i +S·

C_in for each of the segments of the path.

9. The method of claim 8 wherein the step of assigning weight values to each of the nets which are part of the segments of the critical path further comprises the step of calculating a term weight (W_T), said step of calculating a term weight further comprising the steps of:

setting W_T =(max [D_L -SLACK/2;

5])·

(max [10-i_L ;

1]) when D_L >

SLACK/2, wherein D_L is a summation of S·

C_W +D_RC for each of the segments of the critical path and i_L is a current iteration level of the mincut algorithm; and

setting W_T =1 when D_L ≦

SLACK/2.

10. The method of claim 9 wherein the weight value assigned to the net of the centermost segment of each critical path is 2W_T, and the weight values assigned to the nets of the centermost segments of each critical path is W_T.

11. The method of claim 7 wherein said step of estimating a path delay further comprises the step of estimating total wire length of the net of each segment based on the current placement.

12. The method of claim 11 wherein said step of estimating total wire length is performed using an approximate Steiner Tree.

13. The method of claim 7 wherein the step of estimating a path delay further comprises the step of estimating D_RC for each segment of the critical path in accordance with D_RC =r·

D (L/(D+L)) (C_W +C_in), wherein r is unit length resistance of the branch coupling the segment with the next segment of the critical path, D is the length of the branch, L is the total length of the net of the segment, C_W is total capacitance of the net of the segment and C_in is total input capacitance coupled to the net of the segment.

14. The method of claim 13 wherein D is estimated as a rectilinear distance between a coordinate position of the output pin of the component of the segment and a coordinate position of the input pin of the component of the next segment.

15. The method of claim 14 wherein L is estimated using a bounding box which encompasses coordinate positions of input pins of all components coupled to the net of the segment and the coordinate position of the output pin of the component of the segment, L being estimated as a sum of the width and the height dimensions of the bounding box.

16. The method of claim 1 or 5 wherein the default weight value is one.

17. The method of claim 1 or 5, wherein at least one of said iterations of said method further comprises the steps of:

identifying driver/buffer pairs; and

for each driver/buffer pair, assigning a weight value to a net coupling an output of the driver to an input of the buffer and a weight value to a net coupled to an output of the buffer, wherein the weight value assigned to the net driven by the driver is relatively much greater than the weight value assigned to the net driven by the buffer.

18. The method of claim 1 wherein the initial placement is performed using a mincut algorithm.

19. The method of claim 1 wherein the initial placement is performed to optimize initial placement of components while optimizing total overall length of all of the nets.

20. The method of claim 1, wherein said non-constantly assigned weight values are highest at one end of said critical path, and continuously decrease to a minimum weight value at the opposite end of said critical path.

21. The method of claim 1, wherein said non-constantly assigned weight values are highest in the center segment or segments of said critical path, and are relatively lower towards each end of said critical path.

22. A method for optimizing the placement of components of an integrated circuit comprising the steps of:

identifying at least one path of segments including components coupled by nets on said integrated circuit as critical;

assigning weight values to the nets which form part of the segments of said critical path, wherein;

said weight values are non-constant;

said weight values are assigned based in part upon the location of the segment in the critical path of which each net is a part; and

applying a mincut method to find a placement of said components that minimizes the total weight of the nets that cross cut lines.