Minimizing path delay in a machine by compensation of timing through selective placement and partitioning

• US 5,237,514 A
• Filed: 12/21/1990
• Issued: 08/17/1993
• Est. Priority Date: 12/21/1990
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Curtin, James J.
• Primary Examiner(s): Trans, Vincent N.
• Application Number:
  US07/632,454
• Time in Patent Office: 970 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491
• US Class Current: 716/113
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A method for minimizing cycle time to improve machine performance is described. The approach prioritizes placement and partitioning decisions based on the criticality of paths and their constituent net segments. It provides an initial coarse approximation to a final more optimum configuration by iteratively improving on it through the use of deterministic techniques. The method optimizes placement by means of heuristic algorithms that are based on a cost function that is dependent on net segment and path criticality.

Claims

1. A computer implemented method for minimizing path delay and optimizing cycle time of a circuit design, said circuit design having a plurality of blocks connected to each other by interblock net segments, said method comprising the steps of:

a) measuring path criticality as a function of path slack;

b) cataloguing said paths comprised of net segments contained in nets attached to a placed block for determining all the paths affected by a selected block placement;

c) developing an acceptance factor based on the most critical path in said nets, whereby said path criticality acceptance factor is based on the ratio of said path slack to said machine cycle time; and

d) interconnecting the blocks comprising said circuit design in accord with said improved net segments configuration, thereby achieving an optimized circuit design.

2. The computer implemented method for minimizing path delay and optimizing cycle time of a circuit design as recited in step c) of claim 1, wherein said critical acceptance factor is based on the relative position of a path within said path slack criticality as defined in said ascendency list.

3. A method for optimizing path delay and machine cycle time as recited in claim 1, whereby the cost function acceptance criteria is a function of the combined effect of global criticality and local composite weighting of all said paths in the nets affected by a selected block placement.

4. A method for optimizing delay and machine cycle time as in claim 3, wherein said cost function is the combined effect of global criticality and local composite weighting of all said net segments int he nets affected by a selected block placement.

5. A computer implemented method for minimizing path delay and optimizing cycle time of a circuit design based on global considerations, said circuit design having a plurality of blocks connected to each other by interblock net segments, said method comprising the steps of:

a) measuring net segment criticality as a function of net segment slack;

b) cataloguing said net segments contained in nets attached to a placed block for determining all said net segments affected by a selected block placement;

c) developing an acceptance factor based on the most critical net segment in said nets, whereby said net segment criticality acceptance factor is based on the ratio of said net segment slack to said machine cycle time; and

d) interconnecting the blocks comprising said circuit design in accord with said improved net segments configuration, thereby achieving an optimized circuit design.

6. The computer implemented method for minimizing path delay and optimizing cycle time of a circuit design as recited in step c) of claim 5, whereby said critical acceptance factor is based on the relative position of a net segment within said net segment slack criticality as defined in said ascendency list.

7. A computer implemented method for minimizing path delay and optimizing cycle time of a circuit design, said circuit design having a plurality of blocks connected to each other by interblock net segments, said method comprising the steps of:

a) determining the delay of each of said net segments interconnecting said blocks and prioritizing said net segments in accordance to a predetermined criterion for criticality;

b) achieving an initial coarse approximation to a final optimum configuration based on said net segment criticality;

c) improving said coarse approximation to the final optimum configuration by assigning a cost function to said net segments as a function of said net segment criticality;

d) using said cost function to achieve by heuristic means an improved net segment configuration over the initial coarse approximation; and

e) interconnecting the blocks comprising said circuit design in accord with said improved net segments configuration, thereby achieving an optimized circuit design.

8. The computer implemented method for minimizing path delay and optimizing cycle time of a circuit design as recited in step c) of claim 7, whereby improving said initial placement is achieved by improving electrical parameters of the most critical said net segments.

9. The computer implemented method for minimizing path delay and optimizing cycle time of a circuit design as recited in step c) of claim 7, whereby improving said initial placement is achieved by improving timing parameters of the most critical said net segments.

10. The computer implemented method for minimizing path delay and optimizing cycle time of a circuit design as recited in step c) of claim 7, whereby configuring all said net segments is achieved by evaluating the hierarchical criticality of all paths and net segments that comprise a given net.

11. The computer implemented method for minimizing path delay and optimizing cycle time of a circuit design as recited in step c) of claim 7, whereby said initial placement is achieved by random means.

12. The computer implemented method for minimizing path delay and optimizing cycle time of a circuit design as in step a) of claim 7, whereby block placement priorities are adjusted to reflect the selection of selected net segments as partition boundaries, whereby adjustments to the path slack are altered by the choice of a block as a boundary partition as a driver or receiver, and whereby the reapportionment of said path slack is achieved by adjusting the original equipartition rule to account for a partition boundary net segment which is many times larger than the net segment within said partition.

13. A method for optimizing delay and machine cycle time as in claim 7, whereby said prioritizing of said net segments is based in the combined effect of criticality and associativity, wherein said net segments are considered in order of their critical position in an ascendency list and are segregated into a plurality of subsets based on said associativity, and wherein subset linkage is achieved in a hierarchical structure through the first appearance of said net segments whose source and destination blocks reside in at least one of previously unconnected said subsets.

14. A computer implemented method for minimizing path delay and optimizing cycle time of a circuit design, said circuit design having a plurality of blocks connected to each other by interblock net segments, said method comprising the steps of:

a) generating a set of path delay equations for all machine paths in terms of block delays and interblock net segment connections;

b) generating a path delay slack by subtracting the total functional block delay of said path from the cycle time requirement;

c) expressing the set of said path delay slacks for all machine paths, such that each of said path delay slack is comprised of a summation of net segment delay factors defined in terms of source and destination tags of said net segments;

d) estimating an initial net segment slack by applying equipartition rule;

e) extracting the smallest delay value of multiple path net segments from a list of multiple values for all multi-use "pinned" net segments and using said smallest value as a singular value for said multiple path net segments;

f) ordering all said net segments in ascending slack value;

g) accounting for associativity among said net segments by establishing growth centers of said net segments to achieve net coagulation; and

h) interconnecting the blocks comprising said circuit design in accord with said improved net segments configuration, thereby achieving an optimized circuit design.

15. The computer implemented method for minimizing path delay and optimizing cycle time of a circuit design as recited in step b) of claim 14, which includes the additional steps of:

h) ordering said set of path delay slacks in ascending slack values for each of said machine paths; and

i) prioritizing said set of path delay slacks by long paths followed by short paths.

16. The computer implemented method for minimizing path delay and optimizing cycle time of a circuit design as recited in step e) of claim 14, whereby extracting the smallest delay value for multi-path net segments is followed by:

substituting the newly calculated smallest values for multi-path net segments into said equations of all paths containing said multi-paths net segments; and

recalculating the "free" said net segments of said paths by subtracting said newly calculated smallest value from the path slack and reapportioning the remaining slack among said "free" net segments by equipartition rule.

17. The computer implemented method for minimizing path delay and optimizing cycle time of a circuit design as recited in steps f) and g) of claim 14, whereby partition boundaries that are compatible with timing requirements of each said net segment are obtained by means of nested hierarchy.

18. The computer implemented method for minimizing path delay and optimizing cycle time of a circuit design as recited in claim 17, whereby said nested hierarchy is based upon the first net coagulation between two previously independent groups of said net segments.

19. A computer implemented method for minimizing path delay and optimizing cycle time of a circuit design based on local considerations, said circuit design having a plurality of blocks connected to each other by interblock net segments, said method comprising the steps of:

a) measuring path criticality as a function of path slack;

b) cataloguing said paths comprised of net segments contained in nets attached to a placed block for determining all the paths affected by a selected block placement;

c) indexing all said net segments contained in each in said nets by assigning a composite weight generated by a code based on path criticality, whereby the assigned indexed weight for each net segment in said nets is likewise a function of path criticality such that the highest indexed weight is assigned to the net segment contained in the most critical path;

d) developing an acceptance factor based on said composite weight, whereby composite weight is a function of path criticality of each net segment in said net, and whereby said composite weight is defined by a code containing said indexed weight for each said net segment in said net; and

e) interconnecting the blocks comprising said circuit design in accord with said improved net segments configuration, thereby achieving an optimized circuit design.

20. A method for optimizing path delay and machine cycle time as recited in claim 19, whereby the cost function acceptance criteria is a function of the combined effect of global criticality and local composite weighting of all said paths in the nets affected by a selected block placement.

21. A method for optimizing delay and machine cycle time as in claim 20, whereby said cost function is the combined effect of global criticality and local composite weighting of all said net segments in the nets affected by a selected block placement.

22. A computer implemented method for minimizing path delay and optimizing cycle time of a circuit design based on local considerations, said circuit design having a plurality of blocks connected to each other by interblock net segments, said method comprising the steps of:

a) measuring net segment criticality as a function of net segment slack;

b) cataloguing said net segments contained in nets attached to a placed block for determining all the net segments affected by a selected block placement;

c) indexing all said net segments contained in each said nets by assigning a composite weight generated by a code based on net segment criticality, whereby said assigned indexed weight of each said net segment in said nets is likewise a function of net segment criticality, and such that the highest indexed weight is assigned to the net segment deemed most critical;

d) developing an acceptance factor based on said composite weight, whereby said composite weight is a function of the criticality of each said net segment in said net and whereby said composite weight is defined by a code containing said indexed weights for each said net segment in said net; and

e) interconnecting the blocks comprising said circuit design in accord with said improved net segments configuration, thereby achieving an optimized circuit design.