Method and apparatus for computing placement costs

• US 7,080,336 B2
• Filed: 02/20/2002
• Issued: 07/18/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): Dinh, Paul
• Application Number:
  US10/079,270
• Publication Number:
  US 20020157075A1
• Time in Patent Office: 1,609 Days
• Field of Search: 716 1- 18
• US Class Current: 716/122
• 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 placing a set of circuit elements in the circuit layout, the method comprising:

a) for a set of sub-regions that contain the circuit elements, identifying a connection graph during a placement operation that connects the set of sub-regions, wherein the connection graph has at least one edge that is at least partially diagonal;

b) identifying a placement cost from an attribute of the connection graph, wherein the placement cost specifies a cost for the placement of the circuit elements; and

using the placement cost during a placement operation to identify a placement for the circuit elements, wherein the placement specifies positions in the circuit layout for the circuit elements.

2. The method of claim 1, wherein the attribute is a 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 a length of a route for routing a net that is defined to include the circuit elements in the set of sub-regions.

4. The method of claim 2, wherein a net is defined to include the 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 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, wherein the circuit layout region comprises a set of nets, wherein each net is defined to include a set of circuit elements, the method 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 placer works in conjunction with a router that uses a wiring model that allows routing in at least one diagonal direction, wherein the initial placement configuration is specified by a placer that does not account for 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 placing a set of circuit elements in the circuit layout, the program comprising:

a) a first set of instructions for identifying during a placement operation, for a set of sub-regions that contain the circuit elements, 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;

b) a second set of instructions for identifying a placement cost from an attribute of the connection graph, wherein the placement cost specifies a cost for the placement of the circuit elements; and

c) a third set of instructions for using the placement cost during a placement operation to define a position in the circuit layout for the circuit elements.

11. The computer readable medium of claim 10, wherein the attribute is a 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 a length of a route for routing a net that is defined to include the circuit elements in the set of sub-regions.

13. The computer readable medium of claim 11, wherein a net is defined to include the 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 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 circuit layout region comprises a set of nets, wherein each net is defined to include a set of circuit elements, the computer program further comprising:

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 placer works in conjunction with a router that uses a wiring model that allows routing in at least one diagonal direction, wherein the initial placement configuration is specified by a placer that does not account for potential diagonal wiring during routing.

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