Tunneling as a boundary congestion relief mechanism

• US 7,921,393 B2
• Filed: 12/29/2007
• Issued: 04/05/2011
• 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: Furnish, Geoffrey Mark, Bose, Subhasis, LeBrun, Maurice J.
• Primary Examiner(s): Dinh; Paul
• Application Number:
  US11/967,185
• Publication Number:
  US 20080216025A1
• Time in Patent Office: 1,193 Days
• Field of Search: 716 1- 5, 716 7- 13, 716/110, 716/119, 716/122, 716/126
• US Class Current: 716/110
• CPC Class Codes: G06F 2119/12 Timing analysis or timing optimisation
• CPC Class Codes: G06F 30/39 Circuit design at the physical level physical level design for reconfigurable circuits G06F30/347
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Simultaneous Dynamical Integration modeling techniques are applied to global placement of elements of integrated circuits as described by netlists specifying interconnection of morphable-devices. Solutions to a system of coupled ordinary differential equations in accordance with Newtonian mechanics are approximated by numerical integration. A resultant time-evolving system of nodes moves through a continuous location space in continuous time, and is used to derive placements of the morphable-devices having one-to-one correspondences with the nodes. Nodes under the influence of net attractive forces, computed based on the interconnections between the morphable devices, tend to coalesce into well-organized topologies. Nodes are also affected by spreading forces determined by density fields that are developed based on local spatial node population.

Claims

1. A method comprising:

creating, by a computing apparatus, an initial state of nodes and nets representative of a circuit netlist of elements of a region of an integrated circuit, wherein the initial state includes first locations of one or more of the nodes, and wherein the nodes are represented by state variables comprising position, velocity, and mass;

generating, by the computing apparatus, a system of equations representative of motion of the nodes and nets resulting, at least in part, from one or more forces on the nodes and nets;

evolving, by the computing apparatus, the system over time to determine second locations of one or more of the nodes;

generating, by the computing apparatus, a placement of the elements of the integrated circuit in accordance with the determined second locations; and

reducing, by the computing apparatus, congestion by transiting one or more of the nodes through one or more obstructed areas of the region.

2. The method of claim 1, wherein said reducing congestion comprises moving one of the nodes from a first position to a second position.

3. The method of claim 2, further comprising evaluating, by a computing apparatus, the second position based, at least in part, on a position constraint of the region.

4. The method of claim 2, further comprising determining, by the computing apparatus, whether the second position is within a predetermined statistical window.

5. The method of claim 1, wherein the one or more forces comprise a first set of one or more forces, and wherein said reducing congestion comprises:

moving a candidate node to a snapped position;

calculating a magnitude of a second set of one or more forces acting on the candidate node at the snapped position;

calculating a magnitude of a third set of one or more forces that would act on the candidate node at a speculative position; and

selectively moving the candidate node to the speculative position based, at least in part, on a difference between the magnitude of the second set of one or more forces and the magnitude of the third set of one or more forces.

6. The method of claim 5, further comprising applying, by the computing apparatus, one or more biasing factors to the third set of one or more forces prior to said selectively moving.

7. The method of claim 1, further comprising determining, by the computing apparatus, locations of the one or more of the nodes based, at least in part, on a density of the nodes.

8. The method of claim 1, wherein the one or more obstructed areas comprise one or more locations of the region not available for placement of one or more of the nodes.

9. The method of claim 1, wherein one or more of the nodes correspond to a particular type of the elements.

10. The method of claim 9, wherein the particular type is a combinational type.

11. The method of claim 9, wherein the particular type is a sequential type.

12. A non-transitory 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:

creating an initial state of nodes and nets representative of a circuit netlist of elements of a region of an integrated circuit, wherein the initial state includes first locations of one or more of the nodes, and wherein the nodes are represented by state variables comprising position, velocity, and mass;

generating a system of equations representative of motion of the nodes and nets resulting, at least in part, from one or more forces on the nodes and nets;

evolving the system over time to determine second locations of one or more of the nodes;

generating a placement of the elements of the integrated circuit in accordance with the determined second locations; and

reducing congestion by transiting one or more of the nodes through one or more obstructed areas of the region.

13. The non-transitory computer-readable medium of claim 12, wherein the one or more forces comprise a first set of one or more forces, and wherein said reducing congestion comprises:

moving a candidate node to a snapped position;

calculating a magnitude of a second set of one or more forces acting on the candidate node at the snapped position;

calculating a magnitude of a third set of one or more forces that would act on the candidate node at a speculative position; and

selectively moving the candidate node to the speculative position based, at least in part, on a difference between the magnitude of the second set of one or more forces and the magnitude of the third set of one or more forces.

14. The non-transitory computer-readable medium of claim 13, wherein the computer-executable instructions, if executed by a computing apparatus, further cause the computing apparatus to perform an operation of applying one or more biasing factors to the third set of one or more forces prior to said selectively moving.

15. The non-transitory computer-readable medium of claim 14, wherein at least one of the biasing factors is based, at least in part, on a distance between the snapped position and the speculative position.

16. The non-transitory computer-readable medium of claim 14, wherein at least one of the biasing factors is based, at least in part, on a timing criticality of the candidate node.

17. 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, if executed by the processor, cause the system to perform a method comprising;

creating, by a computing apparatus, an initial state of nodes and nets representative of a circuit netlist of elements of a region of an integrated circuit, wherein the initial state includes first locations of one or more of the nodes, and wherein the nodes are represented by state variables comprising position, velocity, and mass;

generating, by the computing apparatus, a system of equations representative of motion of the nodes and nets resulting, at least in part, from one or more forces on the nodes and nets;

evolving, by the computing apparatus, the system over time to determine second locations of one or more of the nodes;

generating, by the computing apparatus, a placement of the elements of the integrated circuit in accordance with the determined second locations; and

reducing congestion by transiting one or more of the nodes through one or more obstructed areas of the region.

18. The system of claim 17, wherein said reducing congestion comprises moving one of the nodes from a first position to a second position, and wherein the method further comprises evaluating the second position based, at least in part, on a position constraint of the region.

19. The system of claim 17, wherein the one or more forces comprise a first set of one or more forces, and wherein said reducing congestion comprises:

moving a candidate node to a snapped position;

calculating a magnitude of a second set of one or more forces acting on the candidate node at the snapped position;

calculating a magnitude of a third set of one or more forces that would act on the candidate node at a speculative position; and

selectively moving the candidate node to the speculative position based, at least in part, on a difference between the magnitude of the second set of one or more forces and the magnitude of the third set of one or more forces.