Interactive time-driven method of component placement that more directly constrains critical paths using net-based constraints
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
22 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21)
-
-
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.
-
Specification