Timing driven placement

• US 5,218,551 A
• Filed: 04/30/1990
• Issued: 06/08/1993
• Est. Priority Date: 04/30/1990
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Norman, Reini J., Han, San Y., Wilk, Ralph W., McMillan, Roger I., Agrawal, Bhuwan, Hutt, Joseph Jr., Kurtzberg, Jerome M., Bello, Stephen E., Donath, Wilm E., Price, Cyril A.
• Primary Examiner(s): Trans, Vincent N.
• Application Number:
  US07/516,944
• Time in Patent Office: 1,135 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

The invention is a method of designing an integrated circuit in which the steps of designing the circuit are optimized by a formal hierarchy. This method, called Timing Driven Placement, of designing an integrated circuit avoids detailed optimization which consumes enormous computational resources. It organizes physical and logical characteristics of the design so that those characteristics can be optimized with respect to the physical design of the circuit. The characteristics are optimized and the resulting circuit to location assignment is placed and wired with a conventional automated process. The method optimizes the global placement into precincts of logic segments of the circuit design with respect to the segment placement effect on circuit timing and wireability. The method then migrates individual circuits within particular segments to other segments to improve both the individual segment and overall circuit timing and wireability. Finally, the method transfers circuit assignment to logic segment and logic segment assignment to physical location information to a conventional process for final detailed circuit placement and wiring.

Claims

1. A method for determining placement of circuit elements, comprising the steps of:

describing a circuit in a formal hierarchy, said formal hierarchy describing block placement in said circuit;

generating path equations, said path equations representing delays on global nets determining slack from said formal hierarchy and said path equations;

optimizing said slack;

placing a plurality of blocks in a circuit according to said optimization of said slack.

2. A method for determining placement of circuit elements as in claim 1, wherein said formal hierarchy description:

describes said circuit in logical block form, said logical block form containing a plurality of logical blocks interconnected by a plurality of nets;

describes a physical space within which to design an integrated circuit;

partitions said logical block form into a plurality of segments, each of said segments containing a plurality of logical blocks, each of said segments connected to other segments by global nets;

partitions said physical space into a plurality of precincts; and

randomly assigns each of said segments to one of said precincts.

3. A method for determining placement of circuit elements as in claim 2, wherein:

each of said path equations includes a plurality of terms, said terms list a plurality of segments attached to a common global net to estimate capacitance associated with said common global net; and

said plurality of terms are minimized, said term minimization retaining a signal term when at least two terms have an identical plurality of said segments.

4. A method for determining placement of circuit elements as in claim 3, wherein:

said list of segments has a first segment designated as a driver segment; and

said term minimization retains a single term when at least two terms have an identical plurality of said segments and said drivers are identical.

5. A method for determining placement of circuit elements as in claim 2, wherein:

each of said path equations include a plurality of terms, said terms list a plurality of segments attached to a common global net to estimate capacitance associated with said common global net;

said plurality of terms are minimized; and

said minimized terms are used to calculate an arrival time for each of said path equations, sorting said path equations with respect to said arrival time, and eliminating said equations having said arrival time greater than a user defined limit.

6. A method for determining placement of circuit elements as in claim 2, wherein said slack optimization comprises:

evaluating said slack as a cost function, said cost function efficiently evaluating timing and wiring changes in said circuit design; and

modifying said circuit placement to minimize said cost function.

7. A method for determining placement of circuit elements as in claim 6, wherein said minimization of said cost function comprises:

modifying said circuit placement when said modification lowers said cost function; and

having a probability greater than zero of modifying said circuit placement when said modification raises said cost function.

8. A method for determining placement of circuit elements, comprising the steps of:

describing said circuit in logical form, said logical block form containing a plurality of logical blocks interconnected by a plurality of nets;

describing a physical space within which to design an integrated circuit;

partitioning said logical block form into a plurality of segments, each of said segments containing a plurality of logical blocks, each of said segments connected to other segments by global nets;

partitioning said physical space into a plurality of precincts;

randomly assigning each of said segments to one of said precincts;

generating path equations, said path equations representing delays on said global nets as a function of said segments assignment to said precincts;

determining slack from said path equations;

optimizing said slack, said slack optimization interchanging a plurality of segments between said assigned precincts, said slack optimization utilizing said path equations to measure said slack, said measurement expressed in a cost function, said cost function efficiently evaluating timing and wiring changes in said circuit design from said segment interchanges, said slack optimization minimizing said cost function, said slack optimization indicating a final assignment of said segments to said precincts when said slack is optimized; and

placing said segments into said precincts indicated by said final assignment.

9. A method for determining placement of circuit elements as in claim 8, wherein;

said evaluation of said wiring changes measures cut cost and precinct cost of said element placement.

10. A method for determining placement of circuit elements comprising the steps of:

assigning logic blocks to a plurality of segments, said segments interconnected by a plurality of nets;

calculating slack associated with said plurality of nets;

selecting a plurality of critical nets based on slack;

evaluating a plurality of logic block moves between said segments for each of said critical nets, said evaluation determining a new net slack for each of said moves;

selecting a move for each critical net which provides the largest improvement in slack; and

making said selected block move when said new net associated with said block move has a larger slack than said critical net slack.

11. A method for determining placement of circuit elements comprising the steps of:

assigning logic blocks to a plurality of precincts, said precincts interconnected by a plurality of nets;

calculating slack associated with each of said plurality of nets;

identifying a plurality of critical nets based on said slack;

evaluating a plurality of logic block moves between precincts for each of said critical nets, said evaluation determining a new slack for each of said moves;

selecting a block move for each critical net which provides the largest improvement in slack; and

making said selected block move when said new net associated with said block move has a larger slack than said critical net slack.

12. A method for determining placement of circuit elements comprising the steps of:

assigning logic blocks to a plurality of precincts, said precincts interconnected by a plurality of nets;

calculating slack associated with each of said plurality of nets;

sorting said plurality of nets by a slack;

evaluating a plurality of logic block moves between precincts for each of said plurality of nets to determine capacitance and wiring cost;

selecting a block move for each net which provides the lowest cost; and

making said selected block move when said capacitance associated with said move is not increased on a critical net.

13. A method for determining placement of circuit elements as in claim 12, wherein aid wiring cost comprises:

cut cost and precinct cost.

14. A method for determining placement of circuit elements comprising the steps of:

assigning logic blocks of said circuit elements to a plurality of precincts forming a circuit;

optimizing said logic block placement within said precincts;

optimizing said precinct placement in said circuit to enhance wiring, said precinct placement optimization overlapping precinct edges.

15. A method for determining placement of circuit elements comprising the steps of:

assigning logic blocks of said circuit elements to a plurality of precincts, said precincts interconnected by a plurality of nets, said nets interconnect a plurality of logic blocks, said precincts forming a circuit;

optimizing said logic block placement within said precincts, said optimization placing logic blocks associated with critical nets within said precincts; and

optimizing said precinct placement in said circuit to enhance wiring, said precinct placement optimization overlapping precinct edges.

16. A method for determining placement of circuit elements, comprising the steps of:

describing said circuit elements in logical block form, said logical block form containing a plurality of logical blocks interconnected by a plurality of nets;

describing a physical space within which to design an integrated circuit;

partitioning said logical block form into a plurality of segments, each of said segments containing a plurality of logical blocks, each of said segments connected to other segments by global nets;

calculating slack associated with said plurality of global nets;

selecting a plurality of critical nets from said global based on slack;

evaluating a plurality of logic block moves between said segments for each of said critical nets, said evaluation determining a new net slack for each of said moves;

selecting a move for each critical net which provides the largest improvement in slack;

making said selected block move when said new net associated with said block move has a larger slack than said critical net slack.

partitioning said physical space into a plurality of precincts;

initially assigning each of said segments to one of said precincts;

generating path equations, said path equations representing delays on said global nets as a function of said segments assignment to said precincts;

determining slack from said path equations;

optimizing said slack, said optimization interchanging a plurality of segments between said assigned precincts, said optimization utilizing said path equations to measure said slack, said measurement being expressed in a cost function, said cost function efficiently evaluating timing and wiring changes in said circuit design, said optimization minimizing said cost function, said optimization indicating a final assignment of said segments to said precincts when said slack is optimized;

placing said segments into said precincts indicated by said final assignment;

moving at least one logic block on a net between precincts connected by the net, said movement improving slack associated with said net, and

moving at least one logic block between precincts when said move does not increase capacitance on said net and when said move improves precinct wiring.

17. A system for placing circuit elements, comprising:

a database means for storing a description of a circuit, said description containing placement information of a plurality of logic blocks within said circuit, said logic blocks interconnected by nets;

a logical partitioning means for separating said plurality of logic blocks into a plurality of segments, said segments interconnected by global nets;

a path equation generation means for generating path equations representing delays on said global nets;

a slack determining means for determining slack from said path equations and said circuit description;

a global placement means for optimizing said slack; and

a circuit migration means for physically placing said plurality of logic blocks in said circuit.

18. A system for placing circuit elements, as in claim 17, wherein said path equation generation means:

generates a plurality of terms, said terms list a plurality of segments attached to a common global net to estimate capacitance associated with said common global net; and

minimizes said plurality of terms, said term minimization retaining a single term when at least two terms have an identical plurality of said segments.

19. A system for placing circuit elements, as in claim 17, wherein said path equation generation means:

generates a plurality of terms, said terms list a plurality of segments attached to a common global net to estimate capacitance associated with said common global net, said list of segments having a first segment designated as a driver segment; and

minimizes said plurality of terms, said term minimization retaining a single term when at least two terms have an identical plurality of said segments and said drivers are identical.

20. A system for placing circuit elements, as in claim 17, wherein said logical partition means:

calculates slack associated with said plurality of global nets;

selects a plurality of critical nets based on slack;

evaluates a plurality of logic block moves between said segments for each of said critical nets, said evaluation determines a new net slack for each of said moves;

selects a move for each critical net which provides the largest improvement in slack; and

makes said selected move when said new net associated with said block move has a larger slack than said critical net slack.

21. A system for placing circuit elements, as in claim 17, wherein:

said database storage means stores an assignment of logic blocks to a plurality of precincts, said precincts interconnected by a plurality of nets;

said circuit migration means calculates slack associated with each of said plurality of nets;

said circuit migration means selects a plurality of critical nets based on said slack;

said circuit migration means evaluates a first plurality of logic block moves between said plurality of precincts for each of said critical nets, said evaluation determines a new net slack for each of said moves;

said circuit migration means selects a logic block move for each critical net which provides the largest improvement in slack; and

said circuit migration means makes said selected move when said new net associated with said selected move has a larger slack than said critical net slack.

22. A system for placing circuit elements, as in claim 17, wherein said circuit migration means:

sorts said plurality of nets by slack;

evaluates a second plurality of logic block moves between precincts for each of said plurality of nets to determine capacitance, timing cost, and wiring cost;

selects a block move for each net which provides the lowest wiring cost; and

makes said selected block move when said capacitance on critical nets associated with said move is not increased.

23. A system for placing circuit elements, comprising:

a data base storage means for storing an assignment of logic blocks to a plurality of precincts, said precincts interconnected by a plurality of nets;

a calculating means for calculating slack associated with each of said plurality of nets;

a first selection means for selecting a plurality of critical nets based on said slack;

an evaluation means for evaluating a plurality of logic block moves between said plurality of precincts for each of said critical nets, said evaluation determines a new net slack for each of said moves;

a second selection means for selecting a logic block move for each critical net which provides the largest improvement in slack; and

a movement means for making said selected move when said new net associated with said selected move has a larger slack than said critical net slack.

24. A system for placing circuit elements, comprising:

a data base storage means for storing an assignment of logic blocks to a plurality of precincts, said precincts interconnected by a plurality of nets;

a calculating means for calculating slack associated with each of said plurality of nets;

a sorting means for sorting said nets by slack;

an evaluation means for evaluating a plurality of logic block moves between precincts for each of said plurality of nets to determine capacitance, timing cost, and wiring cost;

a selection means for selecting a block move for each net which provides the lowest wiring cost; and

a movement means for making said selected block move when said capacitance on critical nets associated with said move is not increased.