Methods and Systems for Placement

• US 20070150846A1
• Filed: 03/09/2007
• Published: 06/28/2007
• 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, LeBrun, Maurice, Furnish, Geoffrey
• Granted Patent: US 7,653,884 B2
• Time in Patent Office: Days
• US Class Current: 716/122
• 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 placement of elements of integrated circuits as described by netlists specifying interconnection of 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 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 populations. The forces are optionally selectively modulated as a function of simulation time. The placements of the devices are compatible with various design flows, such as standard cell, structured array, gate array, and field-programmable gate array.

Claims

1. A method comprising:

integrating continuous coupled simultaneous ordinary differential equations of motion to at least approximate a continuous evolution of state variables over time;

describing nodes of a continuous dynamic system using the equations of motion and the state variables, the nodes corresponding to at least some aspects of a circuit netlist; and

determining a spatial arrangement of circuit elements corresponding to the continuous evolution and in accordance with the circuit netlist.

2. The method of claim 1, wherein the continuous dynamic system corresponds to an analogous physical system having a plurality of forces and the state variables include position and velocity.

3. The method of claim 2, further wherein the state variables further include mass.

4. The method of claim 2, further wherein the position and the velocity state variables describing at least some of the nodes include components corresponding to each available dimension in an implementation architecture the circuit netlist is compatible with.

5. The method of claim 2, further wherein one or more of the forces are damping, attractive, or spreading forces.

6. The method of claim 2, further wherein at least some of the forces are attractive forces, each attractive force acting solely between a respective portion of the nodes interconnected by a respective net that is represented by the circuit netlist.

7. The method of claim 2, further wherein magnitudes of at least some of the forces are selectively modulated to affect the spatial arrangement, the modulation being with respect to time as modeled by the continuous evolution.

8. The method of claim 7, wherein the selective modulation is at least in part performed in accordance with at least one of:

a predetermined criteria;

a manual procedure;

an automatic procedure;

a semi-automatic procedure; and

intervention of a human operator.

9. The method of claim 2, wherein at least some of the forces correspond to at least one of:

layout heuristics;

interconnections in the netlist; and

placement constraints.

10. The method of claim 2, wherein the nodes are an abstract representation of the circuit elements.

11. The method of claim 2, wherein the nodes are a reduced representation of the circuit elements.

12. The method of claim 2, wherein the nodes have a one-to-one correspondence to the circuit elements.

13. The method of claim 1, wherein the integrating is implemented at least in part using at least one of:

analog integration techniques wherein at least some of the state variables are truly continuous;

digital integration techniques wherein at least some of the state variables are pseudo-continuous;

digital integration techniques wherein at least some of the state variables are represented using finite-approximations; and

digital integration techniques wherein at least some of the state variables are represented using floating-point numbers.

14. The method of claim 1, wherein the integrating is performed at least in part using at least one of:

a Runge-Kutta integrator;

a predictor-corrector integrator; and

a leap-frog integrator.

15. The method of claim 1, wherein the integrating is stopped in accordance with at least one of:

a predetermined criteria;

a manual procedure;

an automatic procedure;

a semi-automatic procedure; and

intervention of a human operator.

16. The method of claim 1, further comprising legalizing the spatial arrangement in accordance with a predetermined criteria.

17. The method of claim 1, wherein the spatial arrangement is a cell placement specifying locations of cells with respect to a circuit layout, the circuit netlist representing at least the cells and interconnect between the cells.

18. The method of claim 17, further wherein one or more of the cells are at least standard cells, elements of structured array tiles, macro elements, elements of field-programmable gate arrays, or elements of mask-programmable gate arrays.

19. The method of claim 17, further wherein the cell placement is a global placement specifying an initial approximate placement of the cells.

20. The method of claim 17, further comprising performing a detailed placement of the cells.

21. A computer readable medium having a set of instructions stored therein which when executed by a processing device causes the processing device to perform procedures comprising:

integrating continuous coupled simultaneous ordinary differential equations of motion to at least approximate a continuous evolution of state variables over time, the state variables including at least position and velocity;

describing nodes of a continuous dynamic system using the equations of motion and the state variables, the continuous dynamic system being an analogous physical system of a circuit netlist, the continuous dynamic system having a plurality of forces and the nodes corresponding to at least some aspects of the circuit netlist; and

determining a spatial arrangement of circuit elements corresponding to the continuous evolution and in accordance with the circuit netlist.

22. The computer readable medium of claim 21, wherein the state variables further include mass.

23. The computer readable medium of claim 21, wherein the position and velocity state variables describing at least some of the nodes include components corresponding to each available dimension in an implementation architecture the circuit netlist is compatible with.

24. The computer readable medium of claim 21, wherein one or more of the forces are damping forces.

25. The computer readable medium of claim 21, wherein one or more of the forces are attractive forces.

26. The computer readable medium of claim 25, further wherein each attractive force acts solely between a respective portion of the nodes interconnected by a respective net that is represented by the circuit netlist.

27. The computer readable medium of claim 21, wherein one or more of the forces are spreading forces.

28. The computer readable medium of claim 21, wherein magnitudes of at least some of the forces are selectively modulated to affect the spatial arrangement, the modulation being with respect to time as modeled by the continuous evolution.

29. The computer readable medium of claim 21, wherein at least some of the forces correspond to at least one of:

layout heuristics;

interconnections in the netlist; and

placement constraints.

30. The computer readable medium of claim 21, wherein the nodes are an abstract representation of the circuit elements.

31. The computer readable medium of claim 21, wherein at least some of the nodes are a reduced representation of the circuit elements.

32. The computer readable medium of claim 31, further wherein at least some of the nodes have a one-to-one correspondence to a second portion of the circuit elements.

33. The computer readable medium of claim 21, wherein at least some of the nodes have a one-to-one correspondence to the circuit elements.

34. The computer readable medium of claim 21, wherein the procedures further comprise legalizing the spatial arrangement in accordance with a predetermined criteria.

35. The computer readable medium of claim 21, wherein the spatial arrangement is a cell placement specifying locations of cells with respect to a circuit layout, the circuit netlist representing at least the cells and interconnect between the cells.

36. The computer readable medium of claim 21, wherein the spatial arrangement is a global cell placement specifying initial approximate locations of cells with respect to a circuit layout.

37. The computer readable medium of claim 36, wherein the procedures further comprise performing a detailed placement of the cells.

38. The computer readable medium of claim 21, wherein the integrating is in accordance with an adaptive timestep that is automatically varied subject to maintenance of an accuracy norm.

39. The computer readable medium of claim 38, wherein centered-differencing in the integrating is maintained by computing approximated values for the state variables at a half-step time value at each point when the adaptive timestep is adjusted.

40. The computer readable medium of claim 39, wherein the computing of the approximated values is performed using Runge-Kutta integration.

41. The computer readable medium of claim 21, wherein at least part of at least one of the integrating, the describing, and the determining are performed for at least part of an integrated circuit design of a licensee under license from a licensor.

42. A method comprising:

integrating continuous coupled simultaneous ordinary differential equations of motion to at least approximate a continuous evolution of state variables over time, the state variables including at least position, velocity, and mass;

describing nodes of a continuous dynamic system using the equations of motion and the state variables, the continuous dynamic system being an analogous physical system of a circuit netlist having a plurality of circuit elements, the continuous dynamic system having a plurality of forces and the nodes corresponding to at least some aspects of the circuit netlist; and

determining a spatial arrangement of the circuit elements corresponding to the continuous evolution and in accordance with the circuit netlist.

43. The method of claim 42, wherein the position and velocity state variables describing at least some of the nodes include components corresponding to each available dimension in an implementation architecture the circuit netlist is compatible with.

44. The method of claim 42, further wherein one or more of the forces are damping, attractive, or spreading forces.

45. The method of claim 42, wherein magnitudes of at least some of the forces are selectively modulated to affect the spatial arrangement, the modulation being with respect to time as modeled by the continuous evolution.

46. The method of claim 42, wherein at least part of at least one of the integrating, the describing, and the determining are performed for at least part of an integrated circuit design of a licensee under license from a licensor.

47. A system comprising:

means for integrating continuous coupled simultaneous ordinary differential equations of motion to at least approximate a continuous evolution of state variables over time;

means for describing nodes of a continuous dynamic system using the equations of motion and the state variables, the nodes corresponding to at least some aspects of a circuit netlist; and

means for determining a spatial arrangement of circuit elements corresponding to the continuous evolution and in accordance with the circuit netlist.

48. The system of claim 47, wherein the continuous dynamic system is an analogous physical system having a plurality of forces and the state variables include position, velocity, and mass.

49. The system of claim 48, further comprising means for formulating a gridded mass density scalar field.