Method and apparatus for placing circuit modules

• US 20020069397A1
• Filed: 01/13/2002
• Published: 06/06/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,055,120 B2
• Time in Patent Office: Days
• US Class Current: 716/12
• 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

Some embodiments of the invention are placers that use diagonal lines in calculating the costs of potential placement configurations. For instance, some embodiments estimate the delay cost of a placement configuration by accounting for the potential use of diagonal wiring in the layout. Some of these embodiments derive the delay cost from an estimate of the wirelength needed to route the nets in the region.

Claims

1. For an electronic design automation process that uses a wiring model that includes diagonal wiring directions, a method of placing circuit modules in a region of a circuit layout, wherein said circuit-layout region includes a plurality of nets, and each net has a set of circuit elements, the method comprising:

a) selecting a net;

b) for the selected net, computing a delay cost that accounts for potential diagonal wiring during routing;

c) identifying a placement cost from the computed delay cost.

2. The method of claim 1, wherein the placement cost equals the delay cost.

3. The method of claim 1 further comprising:

a) for each net, computing a delay cost that accounts for potential diagonal wiring during routing;

b) identifying the placement cost from the computed delay costs.

4. The method of claim 3, wherein the placement cost equals the sum of the delay costs.

5. The method of claim 3, wherein each net represents a set of circuit elements in the circuit-layout region, wherein computing the delay cost for each net comprises:

a) computing a wirelength estimate for each net, wherein the wirelength estimates are computed by accounting for diagonal wiring during routing;

b) computing the delay cost for each net from the computed wirelength estimate for the net.

6. The method of claim 5, wherein for at least one net, the delay cost is computed from the net'"'"'s wirelength cost based on a linear relationship.

7. The method of claim 5, wherein for at least one net, the delay cost is computed from the net'"'"'s wirelength cost based on a non-linear relationship.

8. The method of claim 5, wherein the routing model specifies at least one diagonal routing direction, wherein computing the wirelength estimate for each net comprises:

a) identifying a bounding box that encloses the set of circuit elements of the net;

b) measuring the distance (D) between two opposing comers of the bounding box by using the following equation, D=[L−

{S (cos A/sin A)}]+S/sin A,

wherein L is the longest side of the bounding box, S is the shortest side of the bounding box, and A is an angle of one of the diagonal routing directions specified by the wiring model.

9. The method of claim 5,

wherein computing the wirelength estimate for each net comprises:

identifying a connection graph that connects the circuit elements of the net;

identifying the length of the connection graph;

wherein some of the connection graphs include at least one edge that is at least partially diagonal.

10. The method of claim 5 further comprising:

a) partitioning the region into a plurality of sub-regions;

b) wherein computing the wirelength estimate for each net comprises;

identifying the set of sub-regions that contain the net'"'"'s circuit elements; and

identifying the length of a set of interconnect lines that traverses the identified set of sub-regions;

c) wherein some of the identified interconnect lines are at least partially diagonal.

11. The method of claim 3, wherein the placement metric quantifies the placement cost of an initial placement configuration.

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

13. The method of claim 12 further comprising:

a) modifying the position of at least one circuit module in the circuit-layout region; and

b) after said modification, computing a delay cost that accounts for potential diagonal wiring during routing.

14. The method of claim 1, wherein the electronic design automation process uses a router that uses diagonal wiring to route the nets in the circuit-layout region.

15. The method of claim 14, wherein the router also uses Manhattan wiring to route the nets in the circuit-layout region.

17. The method of claim 16, wherein the attribute is the length of the connection graph, and the delay cost is derived from the length of the connection graph.

18. The method of claim 16, wherein the method computes delay 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 delay cost is a placement cost for the net.

19. The method of claim 18 further comprising:

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

20. The method of claim 18 further comprising:

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

21. The method of claim 18 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 delay cost from an attributed of the connection graph identified for the net;

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

identifying an overall placement cost from the identified delay cost of each net.

22. The method of claim 16, wherein the connection graph is a Steiner tree.

16. 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 delay cost from an attribute of the connection graph.