Methods and systems for placement and routing

• US 8,332,793 B2
• Filed: 05/18/2007
• Issued: 12/11/2012
• Est. Priority Date: 05/18/2006
• Status: Active Grant

• Current Assignee: Callahan Cellular LLC (Intellectual Ventures LLC)
• Original Assignee: Otrsotech LLC (Intellectual Ventures LLC)
• Inventors: Bose, Subhasis
• Primary Examiner(s): DOAN, NGHIA M
• Application Number:
  US12/301,456
• Publication Number:
  US 20090254874A1
• Time in Patent Office: 2,034 Days
• Field of Search: 716/108, 716113-114, 716/119, 716/122, 716/134
• US Class Current: 716/114
• CPC Class Codes: G06F 30/39 Circuit design at the physical level physical level design for reconfigurable circuits G06F30/347

Abstract

Techniques for placement of integrated circuit elements include global placement, detailed placement, timing closure, and routing. The integrated circuit is described by a netlist specifying interconnections of morphable devices. The detailed placement uses, for example, Simultaneous Dynamical Integration, wherein the morphable-devices correspond to nodes influenced by forces, including timing forces. The timing forces are derived, for example, from a timing graph; path delay; slack; and drive resistance of the elements. The timing closure uses timing-driven buffering and timing-driven resizing to reduce maximum delay and/or transition time, and/or to fix hold time. Nets having high capacitance and/or fanout, and timing critical nets are preferentially processed. Timing-driven buffering applies buffering solutions to segments of route trees, combines solutions of adjoining segments, and prunes sets of solutions. Timing-driven resizing morphably replaces selected elements with upsized versions thereof.

Claims

1. A method, comprising:

evolving over time, by a computing apparatus, a system of equations representative of motion of a first state of first locations of a plurality of nodes and a plurality of nets and approximating a continuous evolution of state variables over time, resulting, at least in part, from a plurality of forces on the nodes and the nets, to determine a second state of second locations of the nodes and the nets, wherein the nodes and the nets are representative of a circuit netlist of elements of an integrated circuit, wherein the plurality of forces include viscous damping, attractive, and spreading forces, and wherein the state variables describe at least a mass of each node;

modifying, by the computing apparatus after said evolving, magnitudes of one or more of the plurality of forces of at least one of the nodes, and the mass of at least one of the nodes based, at least in part, on a resource usage of the nodes and the nets, to adjust the second state to a third state of third locations; and

modifying, by the computing apparatus, the third state to a fourth state of fourth locations based, at least in part, on a timing of the third state by;

replacing a first driver of at least one of the nets with a second driver, wherein the first driver and the second driver have different drive strengths;

or

inserting a buffer driving the at least one of the nets;

or

both.

2. The method of claim 1, further comprising sorting, by the computing apparatus, the plurality of the nets, prior to said modifying the third state to a fourth state, according to timing criticality.

3. The method of claim 1, wherein said modifying the third state to a fourth state is performed based, at least in part, on one or more of capacitance of at least one of the nets, fanout of at least one of the nets, timing criticality of at least one of the nets, maximum delay of at least one of the nets, or transition time of at least one of the nets.

4. The method of claim 1, wherein said modifying the third state to a fourth state comprises said replacing the first driver of the at least one of the nets with the second driver, and wherein the method further comprises, prior to said modifying the third state to a fourth state:

determining, by the computing apparatus, a plurality of replacement forms of the first driver;

attempting, by the computing apparatus, placement of at least some of the replacement forms to determine placeable ones of the replacement forms; and

selecting, by the computing apparatus, the second driver from the placeable replacement forms.

5. The method of claim 4, further comprising sorting, by the computing apparatus, the placeable replacement forms based at least in part on respective timing scores of the placeable replacement forms.

6. The method of claim 5, wherein the respective timing scores of the placeable replacement forms are determined based at least in part on said attempting placement.

7. The method of claim 4, further comprising sorting, by the computing apparatus, prior to said attempting placement, the replacement forms based at least in part on respective timing scores of the replacement forms.

8. The method of claim 1, wherein said modifying the third state to a fourth state includes inserting a tree of buffers to drive at least one of the nets.

9. The method of claim 1, wherein said modifying the third state to a fourth state includes inserting a clock tree into the third state.

10. The method of claim 9, wherein said inserting a clock tree comprises inserting the clock tree based at least in part on a maximum clock skew of a network of clocks of the third state.

11. The method of claim 9, wherein said inserting a clock tree comprises inserting the clock tree based at least in part on a maximum latency of a network of clocks of the third state.

12. The method of claim 1, further comprising generating, by the computing apparatus, a placement of the elements of the integrated circuit in accordance with the determined fourth locations.

13. The method of claim 1, wherein the state variables further describe a position and a velocity of each node.

14. The method of claim 1, further comprising creating, by the computing apparatus, the first state of the nodes and the nets representative of the circuit netlist of elements of the integrated circuit.

15. A non-transitory computer-readable medium having stored thereon, computer-executable instructions configured to cause the computing apparatus, in response to execution of the instructions by the computing apparatus, to perform operations comprising:

evolving over time, by the computing apparatus, a system of equations representative of motion of a first state of first locations of a plurality of nodes and a plurality of nets and approximating a continuous evolution of state variables over time, resulting, at least in part, from a plurality of forces on the nodes and the nets, to determine a second state of second locations of the nodes and the nets, wherein the nodes and the nets are representative of a circuit netlist of elements of an integrated circuit, wherein the plurality of forces include viscous damping, attractive, and spreading forces, and wherein the state variables describe at least a mass of each node;

modifying, by the computing apparatus after said evolving, magnitudes of one or more of the plurality of forces of at least one of the nodes, and the mass of at least one of the nodes based, at least in part, on a resource usage of the nodes and the nets, to adjust the second state to a third state of third locations; and

modifying, by the computing apparatus, the third state to a fourth state of fourth locations based, at least in part, on a timing of the third state by;

replacing a first driver of at least one of the nets with a second driver, wherein the first driver and the second driver have different drive strengths;

or

inserting a buffer driving the at least one of the nets;

or

both.

16. The non-transitory computer-readable medium of claim 15, wherein the computer-executable instructions, if executed by the computing apparatus, further cause the computing apparatus to perform an operation of sorting the plurality of the nets, prior to said modifying the third state to a fourth state, according to timing criticality.

17. The non-transitory computer-readable medium of claim 15, wherein said modifying the third state to a fourth state is performed based, at least in part, on one or more of capacitance of at least one of the nets, fanout of at least one of the nets, timing criticality of at least one of the nets, maximum delay of at least one of the nets, or transition time of at least one of the nets.

18. The non-transitory computer-readable medium of claim 15, wherein said modifying the third state to a fourth state comprises said replacing the first driver of the at least one of the nets with the second driver, and wherein the computer-executable instructions, if executed by a computing apparatus, further cause the computing apparatus to perform, prior to said modifying the third state to a fourth state,

determining a plurality of replacement forms of the first driver;

attempting placement of at least some of the replacement forms to determine placeable ones of the replacement forms; and

selecting the second driver from the placeable replacement forms.

19. A system, comprising:

a processor; and

a non-transitory computer-readable medium coupled to the processor by way of a bus, the non-transitory computer-readable medium having stored thereon, computer-executable instructions that enable the system, in response to execution of the instructions, to;

evolve over time a system of equations representative of motion of a first state of first locations of a plurality of nodes and a plurality of nets and approximating a continuous evolution of state variables over time, resulting, at least in part, from a plurality of forces on the nodes and the nets, to determine a second state of second locations of the nodes and the nets, wherein the nodes and the nets are representative of a circuit netlist of elements of an integrated circuit, wherein the plurality of forces include viscous damping, attractive, and spreading forces, and wherein the state variables describe at least a mass of each node; and

modifying, by the computing apparatus after said evolving, magnitudes of one or more of the plurality of forces of at least one of the nodes, and the mass of at least one of the nodes based, at least in part, on a resource usage of the nodes and the nets, to adjust the second state to a third state of third locations; and

modify the third state to a fourth state of fourth locations based, at least in part, on a timing of the third state by;

replacing a first driver of at least one of the nets with a second driver, wherein the first driver and the second driver have different drive strengths;

or

inserting a buffer driving the at least one of the nets;

or

both.

20. The system of claim 19, wherein the computer-executable instructions enable the system to modify the third state to the fourth state by replacing the first driver of the at least one of the nets with the second driver, and wherein the computer-executable instructions further enable the system, in response to execution of the instructions by the system, to:

determine a plurality of replacement forms of the first driver;

attempt placement of at least some of the replacement forms to determine placeable ones of the replacement forms; and

select the second driver from the placeable replacement forms.

21. The system of claim 19, wherein the computer-executable instructions further enable the system, in response to execution of the instructions by the system, to modify the third state to the fourth state based at least in part on the timing of the third state by inserting a tree of buffers to drive the at least one of the nets.

22. The system of claim 19, wherein the computer-executable instructions further enable the system, in response to execution of the instructions by the system, to modify the third state to the fourth state based at least in part on the timing of the third state by inserting a clock tree into the third state, wherein the clock tree comprises one or more levels of clock selector logic gates.

23. The system of claim 19, wherein the computer-executable instructions further enable the system, in response to execution of the instructions by the system, to modify the third state to the fourth state based at least in part on the timing of the third state by inserting a clock tree into the third state, wherein the clock tree comprises one or more levels of clock gating logic gates.