Probabilistic routing method and apparatus

• US 6,952,815 B2
• Filed: 01/13/2002
• Issued: 10/04/2005
• 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): WHITMORE, STACY
• Application Number:
  US10/047,978
• Publication Number:
  US 20030088845A1
• Time in Patent Office: 1,360 Days
• Field of Search: 716/2, 716/12, 716/13, 716/14
• 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 net and each particular edge, identifies an edge-intersect probability that specifies the probability that a set of potential routes for the particular net will intersect the particular edge, and (2) uses the identified edge-intersect probabilities to identify routes for the nets. A potential route for a particular net traverses the set of sub-regions that contain the particular net'"'"'s set of pins.

In other embodiments, the method partitions the region into several sub-regions that have a number of paths between them. The method (1) for each particular net and each particular path, identifies a path-use probability that specifies the probability that a set of potential routes for the particular net will use the particular path, and (2) uses the identified path-use probabilities to identify routes for the nets.

Claims

1. A method of routing a plurality of nets in a region of an integrated circuit (“

IC”

) 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 particular net, identifying an edge-intersect probability for each particular edge that specifies the probability that a set of potential routes for the particular net will 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; and

c) using the identified edge-intersect probabilities to identify routes for the nets.

2. The method of claim 1, wherein, for each particular net, the edge-intersect probability for each particular edge 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.

3. The method of claim 2, wherein identifying the edge-intersect probabilities for each particular net comprises:

a) identifying the set of sub-regions that contain each particular net'"'"'s pins;

b) based on each particular net'"'"'s identified set of sub-regions, retrieving the particular net'"'"'s edge-intersect probabilities from a storage structure.

4. The computer readable medium of claim 2, wherein the set of instructions for identifying the edge-intersect probabilities for each particular net comprises sets of instructions for:

a) identifying the set of sub-regions that contain each particular net'"'"'s pins;

b) based on each particular net'"'"'s identified set of sub-regions, retrieving the particular net'"'"'s edge-intersect probabilities from a storage structure.

5. The method of claim 1, wherein identifying the edge-intersect probabilities comprises:

for each particular net;

a) identifying the set of potential routes for the particular net;

b) for each particular edge, computing the number of potential routes of the particular net that intersect the particular edge;

c) dividing the computed number of each particular edge by the number of potential routes of the particular net.

6. The method of claim 5, wherein identifying the set of potential routes for each particular net comprises retrieving the set of routes from a storage structure.

7. The method of claim 5, wherein identifying the set of potential routes for each particular net comprises generating the set of routes after partitioning the IC region.

8. The method of claim 1 further comprising:

for each particular edge, computing a sum of the probabilities identified for the particular edge for all the nets;

using the summed probabilities for the edges to predict congestion of the edges;

routing the nets based on the predicted congestion of the edges.

9. The method of claim 1, wherein using the identified probabilities to identify routes for the nets comprises:

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

b) based on the predicted congestion, identifying routes for nets.

10. The method of claim 1, wherein using the identified probabilities to identify routes for the nets comprises:

a) using the edge-intersect probabilities to derive an edge-intersect cost for each edge;

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

LP”

) problem;

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

11. The method of claim 10, 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.

12. The method of claim 10, wherein solving the LP problem results in a real-number solution for each net, wherein using the identified probabilities to identify routes for the nets further comprises converting the real-numbered solutions to integer solutions that specify only one route for each net.

13. A method of routing a plurality of nets in a region of an integrated circuit (“

IC”

) 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 particular net, identifying a path-use probability for each particular path that specifies the probability that a set of potential routes for the particular net will 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; and

c) using the identified path-use probabilities to identify routes for the nets.

14. The method of claim 13, for each particular net, the path-use probability for each particular path 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.

15. The method of claim 14, wherein identifying the path-use probabilities for each particular net comprises:

a) identifying the set of sub-regions that contain each particular net'"'"'s pins;

b) based on each particular net'"'"'s identified set of sub-regions, retrieving the particular net'"'"'s path-use probabilities from a storage structure.

16. The method of claim 13, wherein identifying the path-use probabilities comprises:

for each particular net;

a) identifying the set of potential routes for the particular net;

b) for each particular path, computing the number of potential routes of the particular net that use the particular path;

c) dividing the computed number of each particular path by the number of potential routes of the particular net.

17. The method of claim 16, wherein identifying the set of potential routes for each particular net comprises retrieving the set of routes from a storage structure.

18. The method of claim 16, wherein identifying the set of potential routes for each particular net comprises generating the set of routes after partitioning the IC region.

19. The method of claim 13 further comprising:

for each particular path, computing a sum of the probabilities identified for the particular path for all the nets;

using the summed probabilities for the paths to predict congestion of the paths;

routing the nets based on the predicted congestion of the paths.

20. The method of claim 13, wherein using the identified probabilities to identify routes for the nets comprises:

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

b) based on the predicted congestion, identifying routes for nets.

21. The method of claim 13, wherein using the identified probabilities to identify routes for the nets comprises:

a) using the path-use probabilities to derive an path-use cost for each path;

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

LP”

) problem;

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

22. A computer readable medium that stores a computer program for routing a plurality of nets in a region of an integrated circuit (“

IC”

) layout, each net having a set of pins in the region, the computer program comprising sets of instructions for;

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

b) for each particular net, identifying an edge-intersect probability for each particular edge that specifies the probability that a set of potential routes for the particular net will 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; and

c) using the identified edge-intersect probabilities to identify routes for the nets.

23. The computer readable medium of claim 22, wherein, for each particular net, the edge-intersect probability for each particular edge 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.

24. A computer readable medium that stores a computer program for routing a plurality of nets in a region of an integrated circuit (“

IC”

) layout, each net having a set of pins in the region, the computer program comprising sets of instructions for;

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

b) for each particular net, identifying a path-use probability for each particular path that specifies the probability that a set of potential routes for the particular net will 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; and

c) using the identified path-use probabilities to identify routes for the nets.

25. The computer readable medium of claim 24, wherein, for each particular net, the path-use probability for each particular path 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.

26. The computer readable medium of claim 25, wherein the set of instructions for identifying the path-use probabilities for each particular net comprises sets of instructions for:

a) identifying the set of sub-regions that contain each particular net'"'"'s pins;

b) based on each particular net'"'"'s identified set of sub-regions, retrieving the particular net'"'"'s path-use probabilities from a storage structure.