Method and apparatus for placing circuit modules

• US 7,055,120 B2
• Filed: 01/13/2002
• Issued: 05/30/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): Garbowski, Leigh M.
• Application Number:
  US10/046,858
• Publication Number:
  US 20020069397A1
• Time in Patent Office: 1,598 Days
• Field of Search: 716 1- 14
• US Class Current: 716/113
• 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 a net in a region of a circuit layout, said placement for a routing operation, the method comprising:

before said routing operation, selecting a net from a plurality of nets in said region;

for the selected net, computing a delay cost that accounts for potential diagonal wiring for said routing operation;

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:

for each net in said plurality of nets, computing a delay cost that accounts for potential diagonal wiring for said routing operation;

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 computing the delay cost for each net comprises:

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

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 has a linear relationship to the net'"'"'s wirelength cost.

7. The method of claim 5, wherein for at least one net, the delay cost has a non linear relationship to the net'"'"'s wirelength cost.

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

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

measuring the distance (D) between two opposing corners 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 said at least one diagonal wiring direction specified by the wiring model.

9. The method of claim 5,

wherein each net comprises a plurality of circuit elements:

and

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:

partitioning the region into a plurality of sub-regions;

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;

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

11. The method of claim 3, wherein the placement cost is the 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 potential diagonal wiring for said routing operation.

13. The method of claim 12 further comprising:

for a net in said circuit-layout region, said net comprising at least one circuit module, modifying a position of said circuit module; and

after said modification, computing a delay cost associated with said position that accounts for potential diagonal wiring for said routing operation.

14. The method of claim 1, wherein the electronic design automation process includes said routing operation, wherein said routine operation comprises 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.

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:

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;

identifying a delay cost from an attribute of the connection graph; and

identifying a placement cost from said computed delay cost.

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 that contains a net comprising said set of circuit elements;

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 said identified set of sub-regions.

20. The method of claim 18 further comprising:

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

21. The method of claim 18 further comprising:

for each net in the circuit-layout region,

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

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

identifying the delay cost from an attribute 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.