Method and apparatus for pre-computing and using placement costs within a partitioned region for multiple wiring models

• US 6,910,198 B2
• Filed: 12/15/2000
• Issued: 06/21/2005
• Est. Priority Date: 12/06/2000
• Status: Expired due to Term

• 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): Garbowski, Leigh M.
• Application Number:
  US09/739,580
• Publication Number:
  US 20020124231A1
• Time in Patent Office: 1,649 Days
• Field of Search: 716 1- 2, 716 7- 14
• US Class Current: 716/122
• 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 of 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 an electronic-design-automation placer that uses a set of partitioning lines, that define a plurality of slots, to partition an integrated-circuit (“

IC”

) layout region into a plurality of sub-regions corresponding to said slots, a method of pre-computing placement costs for multiple wiring models, the method comprising;

a) for each combination of said slots, identifying at least one connection graph that is based on a first wiring model and that represents the topology of interconnect lines necessary for connecting the combination of said slots according to the first wiring model;

b) for each combination of said slots, identifying at least one connection graph that is based on a second wiring model and that represents the topology of interconnect lines necessary for connecting the combination of said slots according to the second wiring model;

c) computing an attribute of each identified connection graph; and

d) storing the computed attributes in a storage structure.

3. The method of claim 1, wherein the connection graphs are minimum spanning trees.

4. The method of claim 1, wherein computing said attribute comprises calculating the length of each graph.

5. The method of claim 1, wherein computing said attribute comprises calculating the number of bends in each graph.

6. The method of claim 5, wherein the bends are diagonal bends.

7. The method of claim 1, wherein a plurality of interconnect-line paths exist between said slots, wherein computing the attribute comprises identifying the interconnect line paths used by each connection graph.

8. The method of claim 7, wherein a first set of interconnect-line paths exist between said slots when the first wiring model is used, and a second set of interconnect-line paths exist between said slots when the second wiring model is used.

9. The method of claim 1, wherein a plurality of edges exist between said slots, wherein computing the attribute comprises identifying the edges intersected by each connection graph.

10. The method of claim 9, wherein a first set of edges exist between said slots when the first wiring model is used, and a second set of edges exist between said slots when the second wiring model is used.

2. The method of claim wherein the connection graphs are Steiner trees.

11. 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) selecting a first wiring model from a set of at least two wiring models, each wiring model providing a wiring direction for each layer of said IC layout, wherein the first wiring model includes a wiring direction that is not available on any layer of at least one other wiring model in the set of wiring model;

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

c) selecting a net;

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

e) retrieving, from a storage structure, a pre-computed attribute of a set of one or more interconnect lines that are necessary for connecting the identified set of sub-regions, wherein said set of interconnect lines are based on the first wiring model.

12. The method of claim 11, wherein the retrieved attribute represents the placement cost of said net within said region.

13. The method of claim 11, further comprising computing the placement cost of said net from said retrieved attribute.

14. The method of claim 11, further comprising:

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, from the storage structure, a pre-computed attribute of a different set of interconnect lines necessary for connecting the identified new set of sub-regions, wherein said different set of interconnect lines are based on the first wiring model.

15. 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) selecting a first wiring model from a set of at least two wiring models, each wiring model providing a wiring direction for each layer of said IC layout, wherein the first wiring model includes a wiring direction that is not available on any layer of at least one other wiring model in the set of wiring mode;

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

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

d) for each particular net, retrieving a pre-computed attribute of a connection graph that is based on the first wiring model, and that represents the topology of interconnect lines needed to connect the identified set of sub-regions of the particular net;

e) computing a placement cost for the IC layout within said region by using the retrieved attributes.

16. The method of claim 15 further comprising:

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

g) for each particular net that includes the particular circuit element, identifying a new set of sub-regions that contain the circuit elements of the particular net;

h) for each particular net that includes the particular circuit element, retrieving a pre-computed attribute of a new connection graph that is based on the first wiring model, and that represents the topology of interconnect lines necessary for connecting the identified new set of sub-regions for the particular net;

i) computing a delta placement cost based on the retrieved attributes of the new connection graphs.

17. The method of claim 15, wherein the connection graphs are Steiner trees.

18. The method of claim 15, wherein the connection graphs are minimum spanning trees.