Method and apparatus for routing

• US 7,013,450 B2
• Filed: 01/14/2002
• Issued: 03/14/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, Buset, Oscar
• Primary Examiner(s): Garbowski, Leigh M.
• Application Number:
  US10/047,982
• Publication Number:
  US 20030056187A1
• Time in Patent Office: 1,520 Days
• Field of Search: 716 1- 2, 716/4, 716 7- 18
• US Class Current: 716/129
• 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/3953 detailed
• CPC Class Codes: G11B 7/08582 Sled-type positioners

Abstract

Some embodiments of the invention provide a method of routing several nets in a region of a design layout. Each net includes a set of pins in the region. In some embodiments, the method partitions the region into several sub-regions that have a number of edges between them. The method (1) for each particular edge, identifies an edge-intersect cost based on a set of potential routes for the nets that intersect the particular edge, and (2) selects routes for the nets based on the computed edge-intersect costs. A potential route for a particular net traverses the set of sub-regions that contain the particular net'"'"'s set of pins. Also, different embodiments identify different edge-intersect costs. For instance, the edge-intersect cost of a particular edge (1) can be the number of routes that intersect the particular edge, (2) can be a edge-intersect probability that equals the number of routes that intersect the particular edge divided by the total number of routes, or (3) can be a cost derived from the edge-intersect probability. Other embodiments might define other edge-intersect costs. In other embodiments, the method partitions the region into several sub-regions that have a number of paths between them. The method next (1) for each particular path, identifies a path-use cost based on a set of potential routes for the nets that use the particular path, and (2) selects a route for each net based on the computed path-use costs. Different embodiments identify different path-use costs. For instance, the path-use cost of a particular path (1) can be the number of routes that use the particular path, (2) can be a path-use probability that equals the number of routes that use the particular path divided by the total number of routes, or (3) can be a cost derived from the path-use probability. Other embodiments might define other path-use costs.

Claims

1. A method of routing a plurality of nets in a region of a design layout, each net having a set of pins in the region, the method comprising:

a) partitioning the region into several sub-regions, wherein a plurality of edges exist between said sub-regions,

b) for each combination of a particular edge and a particular net, identifying an edge-intersect cost based on the number of potential routes for the particular net that intersect the particular edge, wherein a potential route for a particular net traverses the set of sub-regions that contain the particular net'"'"'s set of pins, wherein at least one particular net includes at least two potential routes; and

c) selecting routes for nets based on the computed edge-intersect costs.

2. The method of claim 1, wherein the cost for each combination of a particular edge and a particular net equals the number of potential routes that intersect the particular edge.

3. The method of claim 1, wherein identifying the cost for each combination of a particular edge and a particular net comprises:

identifying an edge-intersect probability that equals the number of potential routes of the particular net that intersect the particular edge divided by the number of potential routes of the particular net.

4. The method of claim 3, wherein the cost for each combination of a particular edge and a particular net equals the edge-intersect probability for the combination.

5. The method of claim 3, wherein identifying the cost for each combination of a particular edge and a particular net further comprises:

deriving the cost for the combination from the edge-intersect probability for the combination.

6. The method of claim 1, wherein selecting routes for nets comprises:

a) using the edge-intersect costs to predict congestion of the edges;

b) based on the predicted congestion, selecting a route for each net nets.

7. The method of claim 1, wherein selecting routes for nets comprises:

a) using the potential routes and the edge-intersect costs to formulate a linear-programming (“

LP”

) problem;

b) solving the LP problem to identify one route for each net.

8. The method of claim 7, wherein the LP problem is an integer linear programming (“

ILP”

) problem, and solving the ILP problem results in an ILP solution that specifies one route for each net.

9. The method of claim 7, wherein solving the LP problem results in a real-number solution for each net, wherein selecting routes for nets further comprises converting the real-numbered solutions to integer solutions that specify only one route for each net.

10. A method of routing a plurality of nets in a region of a design layout, each net having a set of pins in the region, the method comprising:

a) partitioning the region into several sub-regions, wherein a plurality of paths exist between said sub-regions,

b) for each combination of a particular path and a particular net, identifying a path-use cost based on the number of potential routes of the particular net that use the particular path, wherein a potential route for a particular net traverses the set of sub-regions that contain the particular net'"'"'s set of pins, wherein at least one particular net includes at least two potential routes; and

c) selecting routes for the nets based on the computed path-use costs.

11. The method of claim 10, wherein the cost for each combination of a particular path and a particular net equals the number of potential routes of the particular net that use the particular path.

12. The method of claim 10, wherein identifying the cost for each combination of a particular path and a particular net comprises:

identifying a path-use probability that equals the number of potential routes of the particular net that use the particular path divided by the number of potential routes of the particular net.

13. The method of claim 12, wherein the cost for each combination equals the path-use probability for the combination.

14. The method of claim 12, wherein identifying the cost for each combination of a particular path and a particular net further comprises:

deriving the cost for the particular path from the path-use probability for the particular path.

15. The method of claim 10, wherein selecting routes for nets comprises:

a) using the path-use costs to predict congestion of the paths;

b) based on the predicted congestion, selecting a route for each net.

16. The method of claim 10, wherein selecting routes for nets comprises:

a) using the potential routes and the path-use costs to formulate a linear-programming (“

LP”

) problem;

b) solving the LP problem to identify one route for each net.

17. The method of claim 16, wherein the LP problem is an integer linear programming (“

ILP”

) problem, and solving the ILP problem results in an ILP solution that specifies one route for each net.

18. The method of claim 16, wherein solving the LP problem results in a real-number solution for each net, wherein selecting routes for nets further comprises converting the real-numbered solutions to integer solutions that specify only one route for each net.