Patent US5666290A successfully refreshed from Google Patents.
US5666290A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Interactive time-driven method of component placement that more directly constrains critical paths using net-based constraints
Assignee: Philips Semiconductors Inc
•
Filing: 1995-12-27
•
Granted: 1997-09-09
•
Expires: 2015-12-27
Abstract
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.
Inventors
- 👤 Ying-Meng Li
- 👤 Sunil Ashtaputre
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 17:51
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/32; G06F30/33; G06F30/3308; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
282 words
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.
Claim 2
Independent Claim
282 words
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.
Claim 3
Dependent Claim
62 words
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.
Claim 4
Dependent Claim
23 words
The method of claim 2 wherein the distribution of the assigned weight values decreases linearly from the peak value to the minimum value.
Claim 5
Dependent Claim
17 words
The method of claim 2 wherein the distribution of the assigned weight values is convex in nature.
Claim 6
Dependent Claim
80 words
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.
Claim 7
Dependent Claim
28 words
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.
Claim 8
Dependent Claim
151 words
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.
Claim 9
Dependent Claim
79 words
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.
Claim 10
Dependent Claim
108 words
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.
Claim 11
Dependent Claim
45 words
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 .
Claim 12
Dependent Claim
33 words
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.
Claim 13
Dependent Claim
20 words
The method of claim 11 wherein said step of estimating total wire length is performed using an approximate Steiner Tree.
Claim 14
Dependent Claim
103 words
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.
Claim 15
Dependent Claim
42 words
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.
Claim 16
Dependent Claim
61 words
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.
Claim 17
Dependent Claim
14 words
The method of claim 1 or 5 wherein the default weight value is one.
Claim 18
Dependent Claim
91 words
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.
Claim 19
Dependent Claim
15 words
The method of claim 1 wherein the initial placement is performed using a mincut algorithm.
Claim 20
Dependent Claim
27 words
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.
Claim 21
Dependent Claim
36 words
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.
Claim 22
Dependent Claim
34 words
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.
Claim 23
Independent Claim
105 words
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.
Claim 24
Independent Claim
105 words
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.
References Cited (Backward Citations)
US5113352A
Cited
US5218551A
Cited
US5367469A
Cited
US5402357A
Cited
US5237514A
Cited
US5397749A
Cited
US5513124A
Cited
US5521837A
Cited
US5461576A
Cited
US5544071A
Cited
US5475607A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-09-08 | 2001-03-10 | 2001-09-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-09-08 | 2005-03-10 | 2005-09-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-09-08 | 2009-03-10 | 2009-09-09 | $7700.00 | Window Closed / Lapsed |