Method and apparatus for computing placement costs

• US 20020157075A1
• Filed: 02/20/2002
• Published: 10/24/2002
• Est. Priority Date: 12/06/2000
• Status: Active Grant

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Ganley, Joseph L.
• Granted Patent: US 7,080,336 B2
• Time in Patent Office: Days
• US Class Current: 716/10
• 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: G06F 30/3947 global

Abstract

For a placer that partitions a region of a circuit layout into a plurality of sub-regions, some embodiments provide a method of computing placement costs. For a set of sub-regions, the method identifies a connection graph that connects the set of sub-regions. The connection graph has at least one edge that is at least partially diagonal. The method then identifies a placement cost from an attribute of the connection graph.

Claims

1. For a placer that partitions a region of a circuit layout into a plurality of sub-regions, a method of computing placement costs, the method comprising:

a) for a set of sub-regions, identifying a connection graph that connects the set of sub-regions, wherein the connection graph has at least one edge that is at least partially diagonal; and

b) identifying a placement cost from an attribute of the connection graph.

2. The method of claim 1, wherein the attribute is the length of the connection graph, and the placement cost equals the length of the connection graph.

3. The method of claim 2, wherein the length of the connection graph provides an estimate of the necessary wirelength for routing a net that has circuit elements in the set of subregions.

4. The method of claim 2, wherein the method computes placement costs of nets in the circuit-layout region, and each net represents a set of circuit elements in the circuit-layout region, the method further comprising:

before the identification of the connection graph, identifying the set of sub-regions as the set that contains the set of circuit elements of a net;

wherein the placement cost is a placement cost for the net.

5. The method of claim 4 further comprising:

from a storage structure, retrieving the attribute based on the identity of the set of sub-regions.

6. The method of claim 4 further comprising:

for each net in the circuit-layout region,

(i) identifying a set of sub-regions that contains the set of circuit elements of the net;

(ii) identifying a connection graph that connects the set of sub-regions;

(iii) identifying the length of the connection graph;

wherein some connection graphs have at least one edge that is at least partially diagonal;

identifying an overall placement cost from the identified length of each connection graph.

7. The method of claim 6, wherein the overall placement cost quantifies the quality of an initial placement configuration.

8. The method of claim 7, wherein the initial placement configuration is specified by a placer that does not account for the router'"'"'s potential diagonal wiring during routing.

9. The method of claim 1, wherein the connection graph is a Steiner tree.

10. For a placer that partitions a region of a circuit layout into a plurality of sub-regions, a computer readable medium that stores a program for computing placement costs, the program comprising:

a) a first set of instructions for identifying, for a set of sub-regions, a connection graph that connects the set of sub-regions, wherein the connection graph has at least one edge that is at least partially diagonal; and

b) a second set of instructions for identifying a placement cost from an attribute of the connection graph.

11. The computer readable medium of claim 10, wherein the attribute is the length of the connection graph, and the placement cost equals the length of the connection graph.

12. The computer readable medium of claim 11, wherein the length of the connection graph provides an estimate of the necessary wirelength for routing a net that has circuit elements in the set of sub-regions.

13. The computer readable medium of claim 11, wherein the program computes placement costs of nets in the circuit-layout region, and each net represents a set of circuit elements in the circuit-layout region, the computer program further comprising:

a third set of instructions for identifying, before the identification of the connection graph, the set of sub-regions as the set that contains the set of circuit elements of a net;

wherein the placement cost is a placement cost for the net.

14. The computer readable medium of claim 13, wherein the computer program further comprises:

a fourth set of instructions for retrieving, from a storage structure, the attribute based on the identity of the set of sub-regions.

15. The computer readable medium of claim 13, wherein the computer program further comprises:

for each net in the circuit-layout region,

(i) a fourth set of instructions for identifying a set of sub-regions that contains the set of circuit elements of the net;

(ii) a fifth set of instructions for identifying a connection graph that connects the set of sub-regions;

(iii) a sixth set of instructions for identifying the length of the connection graph;

wherein some connection graphs have at least one edge that is at least partially diagonal;

a seventh set of instructions for identifying an overall placement cost from the identified length of each connection graph.

16. The computer readable medium of claim 15, wherein the overall placement cost quantifies the quality of an initial placement configuration.

17. The computer readable medium of claim 16, wherein the initial placement configuration is specified by a placer that does not account for the router'"'"'s potential diagonal wiring during routing.

18. The computer readable medium of claim 10, wherein the connection graph is a Steiner tree.