Methods, systems, and articles of manufacture for implementing physical design using force models with custom connectivity

• US 9,043,742 B1
• Filed: 03/15/2013
• Issued: 05/26/2015
• Est. Priority Date: 03/15/2013
• Status: Expired due to Fees

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: McCracken, Thaddeus C.
• Primary Examiner(s): Ngo, Brian
• Application Number:
  US13/842,890
• Time in Patent Office: 802 Days
• Field of Search: 716/118, 716/119, 716/123, 716/126, 716/135
• US Class Current: 716/123
• CPC Class Codes: G06F 2119/14 Force analysis or force optimisation, e.g. static or dynamic forces
• 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

Abstract

Disclosed are methods, systems, and articles of manufactures for implementing physical designs by using multiple force models to iteratively morph a layout decomposition. In addition to attractive force model(s) or repulsive force model(s), the physical implementation also uses a containment force model for grouping multiple design blocks or for confining a node of a cell within the boundary of a container. Another aspect is directed at deriving a first force model at the first hierarchical level from a second force model at the second hierarchical level by directly modifying the second model based at least in part on characteristic(s) of the first hierarchical level and of the second hierarchical level. In a design with multiple hierarchies, a cell-based force model is also used to ensure child nodes of a parent cell stay within a close proximity of the parent node of the parent cell.

Claims

1. A computer implemented method for implementing physical designs using one or more force models, comprising:

using at least one processor to perform a process, the process comprising;

identifying a first set of cells representing a physical design area of an electronic design, wherein the at least one processor partitions the physical design area into the first set of cells, and the first set of cells are non-overlapping and need no overlap resolution;

determining one or more force models using at least the first set of cells, wherein at least one force model of the one or more force models is used to exert force on one or more nodes of a cell; and

anchoring a first cell in the first set of cells by using a containment force model of the one or more force models to exert one or more forces on at least a part of the first cell.

2. The computer implemented method of claim 1, in which the process further comprises:

identifying incomplete conductivity information for the electronic design; and

generating a placement layout or a floorplan by using one or more force models to iteratively morph the first set of cells.

3. The computer implemented method of claim 2, in which the act of generating a placement layout or the floorplan is iteratively performed until one or more convergence criteria are satisfied.

4. The computer implemented method of claim 1, in which the process further comprises:

reconfiguring the conductivity for the first set of cells to have a substantially uniform degree.

5. The computer implemented method of claim 1, in which the act of determining the one or more force models comprises:

identifying one or more characteristics of elements of a graph that is constructed by using at least the first cell.

6. The computer implemented method of claim 5, in which the act of identifying the one or more characteristics of the elements of the graph comprise determining whether the elements of the graph are constructed by using Voronoi cells.

7. The computer implemented method of claim 5, in which the act of determining the one or more force models further comprises:

identifying a first node connected to a second node in the graph based at least in part upon conductivity information; and

determining one or more attractive force models for the first node.

8. The computer implemented method of claim 7, in which the one or more attractive force models comprise at least one of a cell-based attractive force model and a cell attractive force model.

9. The computer implemented method of claim 8, in which the cell-based attractive force model adds a plurality of child nodes to a parent cell in the first set of cells at a higher hierarchical level and models attractive forces between at least some of the plurality of child nodes and a parent node of the parent cell.

10. The computer implemented method of claim 8, in which the cell attractive force model for a cell depends on an attractive weight of another cell.

11. The computer implemented method of claim 10, the process further comprising:

determining the attractive weight of the another cell based at least in part upon an iteratively evolving area of the another cell.

12. The computer implemented method of claim 5, in which the act of determining the one or more force models further comprises:

identifying a third node in the graph; and

determining one or more repulsive force models for the third node.

13. The computer implemented method of claim 10, in which the one or more repulsive force models comprise a containment force model.

14. The computer implemented method of claim 1, in which the act of anchoring the first cell in the first set of cells by using the containment force model further comprises:

determining the containment force model for a first node of the first cell.

15. The computer implemented method of claim 14, in which the act of anchoring the first cell in the first set of cells by using the containment force model further comprises:

identifying the first node of the first cell;

identifying boundary of a containment for the first node; and

determining a repulsive force between the boundary and the first node, wherein the repulsive force is inversely proportional to a distance between the first node and the boundary.

16. The computer implemented method of claim 15, in which the act of determining the repulsive force between the boundary and the first node comprises:

identifying an edge along the boundary of the containment for the first node; and

determining the repulsive force based at least in part upon the distance and a mass of the first node, and a mass of the edge.

17. The computer implemented method of claim 1, in which process further comprises:

determining a common modifier for both an attractive force model and a repulsive force model, wherein the act of determining the common modifier comprises;

identifying a first value of the common modifier;

operating on the first set of cells using the attractive force model or the repulsive force model without using the containment force model for a number of iterations; and

iteratively modifying the first value of the common modifier by using at least a characteristic of a cell in the first set of cells in each iteration of the number of iterations.

18. The computer implemented method of claim 7, the act of determining the one or more attractive force models for the first node comprising:

identifying the second node that is connected to the first node;

determining a first attractive force model of the one or more attractive force model based at least in part upon an edge weight of an edge connecting the first node and the second node; and

identifying or determining a summation of forces on the first node by using at least the first attractive force model.

19. The computer implemented method of claim 7, the act of determining the one or more attractive force models for the first node comprising:

identifying a force directed placement result for a first set of cells;

identifying or determining a first point of the first set of cells as a first fictitious node for the first set of cells;

identifying the force directed placement result for a second set of cells; and

identifying or determining a force model of the one or more attractive force models by using the fictitious node.

20. The computer implemented method of claim 19, wherein the first set of cells reside on a first hierarchy of the electronic design, the second set of cells reside on a second hierarchy of the electronic design, and the first hierarchy is at a higher hierarchical level than the second hierarchy.

21. The computer implemented method of claim 7, the act of determining the one or more attractive force models for the first node comprising:

identifying or determining the graph for at least the first cell; and

identifying or determining a second attractive force model of the one or more attractive force model based at least in part upon an attractive weight of a vertex for the first cell.

22. The computer implemented method of claim 21, wherein the second attractive force model is identified or determined based at least further in part upon one or more characteristics of the first cell and a neighboring cell of the first cell.

23. The computer implemented method of claim 1, the process further comprising:

identifying or determining a first attractive weight of a first node of a first cell in the first set of cells;

identifying or determining one or more force models by using at least the first attractive weight;

identifying or determining a force directed placement result for the electronic design by using at least the one or more force models; and

identifying or determining a second set of cells based at least in part upon the force directed placement result.

24. The computer implemented method of claim 23, the process further comprising:

modifying the first attractive weight of the first node of the first cell in the first set of cells; and

determining whether or not a convergence criterion is satisfied.

25. The computer implemented method of claim 12, the act of determining the one or more repulsive force models for the third node comprising:

identifying or determining an effect of a repulsive force;

identifying an adjacent node neighboring the third node; and

identifying or determining a first repulsive force model between the adjacent node and the third node based at least in part upon the effect and respective characteristics of the third node and the adjacent node.

26. The computer implemented method of claim 1, further comprising:

identifying or determining a first initial value for a first constant;

identifying or determining a second initial value for a second constant;

identifying or determining a result ant layout portion by at least performing force directed placement with the first initial value and the second initial value without using the containment force model; and

identifying or determining a geometric characteristic of the layout portion.

27. The computer implemented method of claim 26, further comprising:

identifying or determining a second value for the second constant based at least in part upon the geometric characteristic; and

identifying or determining a candidate value for the second constant by at least performing the force directed placement for a number of times without using the containment force model.

28. The computer implemented method of claim 27, further comprising:

identifying or determining a final value for the second constant by at least reducing the candidate value by a factor based at least in part upon one or more attributes of the containment force model.

29. The computer implemented method of claim 1, the process further comprising:

identifying or determining a first plurality of cells representing a first decomposition of the physical design area of the electronic design;

identifying or determining a first graph for the physical design area using at least the first plurality of cells; and

identifying a common modifier for both an attractive force model and a repulsive force model for the physical design area.

30. The computer implemented method of claim 29, the process further comprising:

identifying or creating a second graph representing a second decomposition of the physical design area of the electronic design.

31. The computer implemented method of claim 30, the process further comprising:

reducing the common modifier for the physical design area to form a reduced common modifier based at least in part upon a first number of nodes in the first graph and a second number of nodes in the second graph.

32. The computer implemented method of claim 31, the process further comprising:

modifying the first force model for the physical design area by replacing the common modifier in the first force model by the reduced common modifier.

33. An article of manufacture comprising a non-transitory computer readable storage medium storing thereupon a sequence of instructions which, when executed by at least one processor or at least one processor core, causes the at least one processor or the at least one processor core to perform a method for implementing physical designs using one or more force models, the method comprising:

at least one processor performing a process, the process comprising;

identifying a first set of cells representing a physical design area of an electronic design, wherein the at least one processor partitions the physical design area into the first set of cells, and the first set of cells are non-overlapping and need no overlap resolution;

determining one or more force models using at least the first set of cells at least one force model of the one or more force models is used to exert force on one or more nodes of a cell; and

anchoring a first cell in the first set of cells by using a containment force model of the one or more force models to exert one or more forces on at least a part of the first cell.

34. The article of manufacture of claim 33, the process further comprising:

identifying incomplete conductivity information for the electronic design; and

generating a placement layout or a floorplan by using one or more force models to iteratively morph the first set of cells.

35. The article of manufacture of claim 33, the process further comprising:

reconfiguring the conductivity for the first set of cells to have a substantially uniform degree.

36. The article of manufacture of claim 33, in which the act of determining the one or more force models comprises:

identifying one or more characteristics of elements of a graph that is constructed by using at least the first cells, wherein the act of identifying the one or more characteristics of the elements of the graph comprise determining whether the elements of the graph are constructed by using Voronoi cells.

37. The article of manufacture of claim 36, in which the act of determining the one or more force models comprises:

identifying a first node connected to a second node in the graph based at least in part upon conductivity information; and

determining one or more attractive force models for the first node, in which the one or more attractive force models comprise at least one of a cell-based attractive force model and a cell attractive force model.

38. The article of manufacture of claim 36, in which the act of anchoring the first cell in the first set of cells by using the containment force model comprises:

determining the containment force model for a first node of the first cell;

identifying the first node of the first cell;

identifying boundary of a containment for the first node; and

determining a repulsive force between the boundary and the first node, wherein the repulsive force is inversely proportional to a distance between the first node and the boundary.

39. A system for implementing physical designs using one or more force models, comprising:

a computing system that comprises at least one processor having at least one core and is to;

identify a first set of cells representing a physical design area of an electronic design, wherein the at least one processor partitions the physical design area into the first set of cells, and the first set of cells are non-overlapping and need no overlap resolution;

determine one or more force models using at least the first set of cells at least one force model of the one or more force models is used to exert force on one or more nodes of a cell; and

anchor a first cell in the first set of cells by using a containment force model of the one or more force models to exert one or more forces on at least a part of the first cell.

40. The system of claim 39, wherein the computing system is further to:

identify incomplete conductivity information for the electronic design; and

generate a placement layout or a floorplan by using one or more force models to iteratively morph the first set of cells.

41. The system of claim 39, wherein the computing system is further to:

reconfigure the conductivity for the first set of cells to have a substantially uniform degree.

42. The system of claim 39, in which the computing system that is to determine the one or more force models is further to:

identify one or more characteristics of elements of a graph that is constructed by using at least the first cells, wherein the act of identifying the one or more characteristics of the elements of the graph comprise determining whether the elements of the graph are constructed by using Voronoi cells.

43. The system of claim 42, in which the computing system that is to determine the one or more force models is further to:

identify a first node connected to a second node in the graph based at least in part upon conductivity information; and

determine one or more attractive force models for the first node, in which the one or more attractive force models comprise at least one of a cell-based attractive force model and a cell attractive force model.

44. The system of claim 42, in which the computing system that is to anchor the first cell is further to:

determine the containment force model for a first node of the first cell;

identify the first node of the first cell;

identify boundary of a containment for the first node; and

determine a repulsive force between the boundary and the first node, wherein the repulsive force is inversely proportional to a distance between the first node and the boundary.