Timing driven force directed placement flow

• US 7,752,588 B2
• Filed: 12/29/2007
• Issued: 07/06/2010
• Est. Priority Date: 06/29/2005
• Status: Active Grant

• Current Assignee: Callahan Cellular LLC (Intellectual Ventures LLC)
• Original Assignee: Otrsotech LLC (Intellectual Ventures LLC)
• Inventors: Bose, Subhasis
• Primary Examiner(s): Dinh; Paul
• Application Number:
  US11/967,180
• Publication Number:
  US 20080216038A1
• Time in Patent Office: 920 Days
• Field of Search: 716 6- 11
• US Class Current: 716/122
• CPC Class Codes: G06F 2119/12 Timing analysis or timing optimisation
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

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:

generating, by a computing apparatus, a first state of a system of nodes and nets representative of an integrated circuit, wherein the first state includes first locations of one or more nodes;

applying, by the computing apparatus, a timing force on the one or more nodes;

applying, by the computing apparatus, a spreading force on the one or more nodes;

adjusting, by the computing apparatus, the first state in accordance with the timing force and the spreading force to determine second locations of the one or more nodes; and

generating, by a computing apparatus, a second placement of nodes of an integrated circuit in accordance with the determined second locations.

2. The method of claim 1, wherein the timing force is based, at least in part, on a number of paths including the one or more nodes.

3. The method of claim 2, further comprising determining the number of critical paths using a heuristic based model.

4. The method of claim 2, further comprising constructing, by the computing apparatus, a timing graph representative of one or more timing characteristics of the system, wherein the number of paths is based, at least in part, on a topological traversal of the timing graph.

5. The method of claim 1, wherein the timing force is based, at least in part, on a negative slack of the system.

6. The method of claim 1, wherein the timing force is based, at least in part, on a fan-in score of each of the one or more nodes and a fan-out score of each of the one or more nodes.

7. The method of claim 6, wherein the timing force is a product of the fan-in score and the fan-out score of each of the one or more nodes.

8. The method of claim 6, wherein a path includes the one or more nodes, wherein the fan-in score of each of the one or more nodes is a sum of fan-in scores for predecessor ones of the nodes on the path, and wherein the fan-out score of each of the one or more nodes is a sum of fan-out scores for successor ones of the nodes on the path.

9. The method of claim 8, wherein the path is a timing-critical path.

10. The method of claim 9, wherein the timing-critical path is a path having negative slack, and wherein the system includes one or more non-timing-critical paths having non-negative slack.

11. The method of claim 10, wherein the timing force for a node on a non-timing-critical path is zero.

12. The method of claim 1, wherein the timing force is based, at least in part, on a drive resistance of the one or more nodes.

13. The method of claim 12, wherein the node comprises a driver on a net.

14. The method of claim 13, wherein the net is a critical net.

15. The method of claim 1, wherein the timing force is based, at least in part, on a ratio of a drive resistance of the one or more nodes and a minimum drive resistance among all nodes of the system.

16. The method of claim 1, wherein the timing force is based, at least in part, on a path delay through a load pin of the one or more nodes.

17. The method of claim 16, wherein the timing force is further based, at least in part, on a stage delay of a driver of a load pin of the one or more nodes.

18. The method of claim 17, wherein the timing force is a product of the stage delay and the path delay.

19. The method of claim 1, wherein the timing force is based, at least in part, on a timing slack of the one or more nodes.

20. A computer readable medium having stored thereon, computer-executable instructions that, if executed by a computing apparatus, cause the computing apparatus to perform a method comprising:

generating a first state of a system of nodes and nets representative of an integrated circuit, wherein the first state includes first locations of one or more nodes;

applying a timing force on the one or more nodes;

applying a spreading force on the one or more nodes;

adjusting the first state in accordance with the timing force and the spreading force to determine second locations of the one or more nodes; and

generating a second placement of nodes of an integrated circuit in accordance with the determined second locations.

21. The computer-readable medium of claim 20, wherein the timing force is based, at least in part, on one or more of:

a number of paths including the one or more nodes;

a fan-in score of each of the one or more nodes and a fan-out score of each of the one or more nodes;

a drive resistance of the one or more nodes;

a ratio of a drive resistance of the one or more nodes and a minimum drive resistance among all nodes of the system;

a path delay through a load pin of the one or more nodes;

or

a timing slack of the one or more nodes.

22. The computer readable medium of claim 20, wherein at least some of the spreading forces correspond to spatial concentrations of at least some of the nodes.

23. The computer readable medium of claim 20, wherein at least some of the spreading forces comprise exclusion forces corresponding to predetermined layout floorplan constraints.

24. The computer readable medium of claim 20, wherein the method further comprises the computing apparatus to apply an attractive force on on the one or more nodes.

25. The computer readable medium of claim 20, wherein the method further comprises applying a viscous damping force on on the one or more nodes.

26. A system comprising:

a processor; and

a computer-readable medium coupled to the processor by way of a bus, the computer-readable medium having stored thereon, computer-executable instructions that, if executed by the processor, cause the system to perform a method comprising;

generating a first state of a system of nodes and nets representative of an integrated circuit, wherein the first state includes first locations of one or more nodes;

applying a timing force on the one or more nodes;

applying a spreading force on the one or more nodes;

adjusting the first state in accordance with the timing force and the spreading force to determine second locations of the one or more nodes; and

generating a second placement of nodes of an integrated circuit in accordance with the determined second locations.

27. The system of claim 26, wherein the timing force is based, at least in part, on one or more of:

a number of paths including the one or more nodes;

a fan-in score of each of the one or more nodes and a fan-out score of each of the one or more nodes;

a drive resistance of the one or more nodes;

a ratio of a drive resistance of the one or more nodes and a minimum drive resistance among all nodes of the system;

a path delay through a load pin of the one or more nodes;

or

a timing slack of the one or more nodes.

28. The system of claim 26, wherein at least some of the spreading forces correspond to spatial concentrations of at least some of the nodes.

29. The system of claim 26, wherein at least some of the spreading forces comprise exclusion forces corresponding to predetermined layout floorplan constraints.

30. The system of claim 26, wherein the instructions further include instructions that, if executed by the processor, cause the system to apply an attractive force on on the one or more nodes.

31. The system of claim 26, wherein the instructions further include instructions that, if executed by the processor, cause the system to apply a viscous damping force on on the one or more nodes.