Method and apparatus for pre-computing and using multiple placement cost attributes to quantify the quality of a placement configuration within a partitioned region

• US 6,988,256 B2
• Filed: 12/15/2000
• Issued: 01/17/2006
• Est. Priority Date: 12/06/2000
• Status: Expired due to Fees

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Ganley, Joseph L.
• Primary Examiner(s): THOMPSON, ANNETTE M
• Application Number:
  US09/739,589
• Publication Number:
  US 20040123260A1
• Time in Patent Office: 1,859 Days
• Field of Search: 716/7, 716/2, 716/18, 716/10
• US Class Current: 716/113
• CPC Class Codes: G06F 2111/06 Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA]
• 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
• CPC Class Codes: G11B 7/08582 Sled-type positioners

Abstract

One embodiment of the invention is a recursive partitioning method that places circuit elements in an IC layout. This method initially defines a number of partitioning lines that divide an IC region into several sub-regions (also called slots). For a net in the region, the method then identifies the set of sub-regions (i.e., the set of slots) that contain the circuit elements (e.g., the pins or circuit modules) of that net. The set of sub-regions for the net represents the net'"'"'s configuration with respect to the defined partitioning lines. Next, the placement method identifies attribute or attributes of a connection graph that models the net'"'"'s configuration with respect to the partitioning lines. The connection graph for each net provides a topology of interconnect lines that connect the slots that contain the net'"'"'s circuit elements. According to some embodiments of the invention, the connection graph for each net can have edges that are completely or partially diagonal.

Claims

1. For a placer that places circuit modules in integrated-circuit (“

IC”

) layouts, the placer using a set of partitioning lines, that define a plurality of slots, to partition an IC layout region into a plurality of sub-regions corresponding to said slots, a method of pre-computing costs of placing circuit modules in an IC-layout region, the method comprising;

a) selecting a first group of said slots;

b) computing a first attribute of a set of one or more interconnect lines necessary for connecting the first group of said slots, wherein computing the first attribute comprises calculating the length of said set of interconnect lines;

c) computing a second attribute of the set of interconnect lines, wherein said second attribute comprises the number of bends in said set of interconnect lines; and

d) storing the computed attributes in a storage structure for later use by said placer during a placement operation.

2. The method of claim 1 wherein the bends are diagonal bends.

3. The method of claim 1, wherein a plurality of line paths exist between said slots, wherein computing the first attribute comprises identifying the line paths used by said set of interconnect lines.

4. The method of claim 1, wherein a plurality of edges exist between said slots, wherein computing the first attribute comprises identifying the edges intersected by said set of interconnect lines.

5. The method of claim 1 further comprising:

e) computing a third attribute of the set of interconnect lines; and

f) storing the computed third attributes in the storage structure.

6. The method of claim 1 further comprising:

e) selecting a second group of said slots different from said first group;

f) computing first and second attributes of a set of one or more interconnect lines connecting the second group of said slots;

g) storing the computed attributes in the storage structure.

7. For an electronic design automation (“

EDA”

) application that performs placement operations, a method of pre-computing costs of placing circuit elements within an integrated-circuit (“

IC”

) layout, the method comprising;

a) defining a partitioning grid having a plurality of slots, said partitioning grid for partitioning a region of an IC layout during a placement operation;

b) for each combination of said slots, defining at least one connection graph that models the topology of interconnect lines necessary for connecting the combination of said slots;

c) computing multiple attributes for each of said connection graphs, wherein one of said attributes comprises the number of bends in each connection graph of a plurality of said connection graphs;

d) storing the computed attributes in a storage structure for later use by said EDA application during said placement operation.

8. The method of claim 7, wherein the connection graphs are Steiner trees.

9. The method of claim 7, wherein the connection graphs are minimum spanning trees.

10. The method of claim 7, wherein computing multiple attributes of each connection graph comprises calculating the length of each graph.

11. The method of claim 7, wherein the bends are diagonal bends.

12. The method of claim 7, wherein the partitioning grid having a plurality of edges between said slots, wherein computing multiple attributes of each connection graph comprises identifying the edges intersected by each graph.

13. The method of claim 12, wherein said partitioning grid having a particular structure, wherein said edges are defined based on a wiring model for the IC layout and on the structure of the partitioning grid.

14. The method of claim 7, wherein the partitioning grid having a plurality of interconnect-line paths between said slots, wherein computing multiple attributes of each connection graph comprises identifying the paths used by each graph.

15. The method of claim 14, wherein said partitioning grid having a particular structure, wherein said interconnect-line paths are defined based on a wiring model for the IC layout and on the structure of the partitioning grid.

16. The method of claim 7, wherein the partitioning grid having a plurality of interconnect-line paths between said slots, wherein computing multiple attributes of each connection graph comprises calculating the length of each graph and identifying the paths used by each graph.

17. The method of claim 7, wherein the partitioning grid having a plurality of edges between said slots, wherein computing multiple attributes of each connection graph comprises calculating the length of each graph and identifying the edges intersected by each graph.

18. The method of claim 7, wherein the partitioning grid is formed by a set of partitioning lines.

19. The method of claim 18, wherein the partitioning lines are horizontal and vertical lines.

20. For an electronic design automation (“

EDA”

) application that performs placement operations, a method of pre-computing costs of placing circuit elements within an integrated-circuit (“

IC”

) layout, the method comprising;

a) defining a partitioning grid having a plurality of slots, said partitioning grid for partitioning, during a placement operation, a region of an IC layout into a plurality of sub-regions corresponding to said slots;

b) for each combination of said slots, identifying at least one connection graph that models the topology of interconnect lines necessary for connecting the combination of said slots;

c) computing the length and number of bends in each of said connection graphs;

d) storing the length of a connection graph identified for each combination of said slots, wherein when more than one connection graph is defined for a particular combination of said slots, the method storing the length of a short connection graph that has less than a first predetermined number of bends.

21. The method of claim 20 further comprising:

for each combination of said slots that has more than one identified connection graph, storing the length of a short connection graph that has less than a second predetermined number of bends, when none of the connection graphs for the particular combination of said slots have less than the first predetermined number of bends.

22. A method of placing circuit modules in a region of an integrated circuit (“

IC”

) layout, said IC layout having a plurality of circuit elements, wherein a plurality of nets represent interconnections between said circuit elements, each net defined to include a set of circuit elements, the method comprising;

a) partitioning the IC region into several sub-regions;

b) selecting a net;

c) identifying the set of sub-regions containing the circuit elements of the selected net;

d) retrieving from a storage structure multiple pre-computed attributes of a set of one or more interconnect lines necessary for connecting the identified set of sub-regions;

e) computing a placement cost of said net within said region by using the retrieved attributes;

f) changing the position of a circuit element of the net from one sub-region to another;

g) identifying a new set of sub-regions that contain the circuit elements of the net;

h) retrieving multiple pre-computed attributes of a different set of interconnect lines necessary for connecting the identified new set of sub-regions; and

i) computing a new placement cost of said net within said region by using the attributes retrieved for the different set of interconnect lines, wherein said retrieved attributes include the number of bends in said different set of interconnect lines.

23. A method of placing circuit modules in a region of an integrated circuit (“

IC”

) layout, said IC layout having a plurality of circuit elements, wherein a plurality of nets represent interconnections between said circuit elements, each net defined to include a set of circuit elements, the method comprising;

a) partitioning the IC-layout region into several sub-regions;

b) for each particular net, identifying the set of sub-regions containing the circuit elements of the particular net;

c) for each particular net, retrieving multiple pre-computed attributes of a connection graph that models the topology of interconnect lines needed to connect the identified set of sub-regions of the particular net, wherein the connection graph is either a Steiner tree or a minimum spanning tree;

d) computing a placement cost for the IC layout within said region by using the retrieved attributes, wherein said retrieved attributes include the number of bends in a plurality of said connection graphs.