LP method and apparatus for identifying route propagations

• US 6,883,154 B2
• Filed: 01/05/2002
• Issued: 04/19/2005
• Est. Priority Date: 01/19/2001
• Status: Expired due to Term

• Current Assignee: Cadence Design Solutions, Inc.
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Buset, Oscar
• Primary Examiner(s): Siek, Vuthe
• Assistant Examiner(s): Liu, Andrea
• Application Number:
  US10/040,953
• Publication Number:
  US 20030043827A1
• Time in Patent Office: 1,200 Days
• Field of Search: 716/7
• 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 provide an LP method that identifies route propagations. In some embodiments, this method is used by a router that hierarchically defines routes for nets within a region of a design layout. The router (1) partitions the region into a first set of sub-regions, and (2) for each particular net, identifies a route that traverses a set of the first-set sub-regions. In some embodiments, the invention'"'"'s method partitions the first set of sub-regions into a second set of smaller sub-regions. It then identifies a plurality of propagation possibilities for propagating each route into the second set of smaller sub-regions of the first set sub-regions. The method next formulates a linear-programming (“LP”) problem based on the identified propagation possibilities. The method then solves the LP problem. In some embodiments, the formulated LP problem is an integer-linear-programming (“ILP”) problem, and solving the ILP problem returns integer solutions that specify one propagation permutation for each route in each first-set sub-region traversed by the route. In other embodiments, solving the LP problem returns real-numbered solutions. In some of these embodiments, the method converts the real-number solutions into integer solutions that specify one identified propagation permutation for each route in each first-set sub-region traversed by the route.

Claims

1. For a router that hierarchically defines routes for nets within a region of a design layout, the router (i) partitioning the region into a first set of sub-regions and (ii) for each particular net identifying a route that traverses a set of the first-set sub-regions, a method of propagating the routes comprising:

a) partitioning the first set of sub-regions into a second set of smaller sub-regions;

b) identifying a plurality of propagation permutations for propagating each route into the second set of smaller sub-regions of the first set sub-regions;

c) formulating a linear-programming (“

LP”

) problem based on the identified propagation permutations;

d) solving the LP problem to propagate the routes into the second set of smaller sub-regions.

2. The method of claim 1 wherein formulating an LP problem includes using the propagation possibilities to specify an objective function.

3. The method of claim 2, wherein the objective function minimizes the overall wirelength necessary for routing the identified propagation permutations.

4. The method of claim 2,

a) wherein identifying for each particular route a plurality of propagation permutations comprises:

identifying a plurality of propagation configurations in each incident first set sub-region traversed by the first route, wherein each propagation configuration in each incident sub-region includes a unique combination of propagation permutations for each path of the particular route that is incident on the incident sub-region;

computing the cost of each identified propagation configuration; and

b) wherein the objective function is specified by using each propagation configuration and the cost of each propagation configuration.

5. The method of claim 4,

a) wherein each net includes a set of pins;

b) wherein identifying the propagation permutations further comprises;

for each particular identified propagation configuration in each particular first set sub-region, identifying a particular pin configuration that accounts for the particular propagation configuration in the particular first set sub-region;

c) wherein computing the cost for each particular propagation configuration comprises using the propagation configuration'"'"'s pin configuration to compute a cost of a route necessary for routing the pin configuration; and

d) wherein the objective function includes the routing cost of each propagation configuration.

6. The method of claim 1 wherein formulating an LP problem includes specifying a number of constraints.

7. The method of claim 6, wherein one of the constraints is to select only one propagation configuration.

8. The method of claim 6,

wherein identifying the plurality of propagation permutations comprises identifying sets of propagation permutations for propagating each route in each sub-region traversed by the route;

and

wherein formulating the LP problem comprises specifying a propagation-consistency constraint that solving the LP problem results in a consistent values for the sets of propagation permutations identified for each route in each sub-region traversed by the route.

9. The method of claim 6, wherein one of the constraints is a capacity constraint that ensures that areas between the second set of sub-regions are not overcongested.

10. A method of routing nets within a particular region of an integrated circuit (“

IC”

) layout, each net having a set of pins, the method comprising;

a) partitioning the particular IC region into a first set of sub-regions;

b) for each particular net, identifying a route that connects a set of sub-regions containing the particular net'"'"'s pins;

c) partitioning the sub-regions into a second set of smaller sub-regions;

d) identifying a plurality of propagation permutations for propagating each route into the second set of smaller sub-region;

e) formulating a linear-programming (“

LP”

) problem based on the identified propagation permutations; and

f) solving the LP problem to select one identified propagation permutation for each route in each sub-region traversed by the route.

11. The method of claim 10, wherein a plurality of paths exist between the first set of sub-regions, each particular route is defined with respect to the paths traversed by the particular route, and the paths include diagonal paths.

12. The method of claim 11, wherein a plurality of paths exist between the second set of sub-regions, wherein a plurality of the paths between the second set of sub-regions are diagonal, wherein some of the identified propagation permutations traverse the diagonal paths between the second set of smaller sub-regions.

13. The method of claim 12, wherein some of the diagonal paths traversed by the identified propagation permutations are for propagating diagonal paths of routes between the first set of sub-regions.

14. The method of claim 12, wherein some of the diagonal paths traversed by the identified propagation permutations are for propagating Manhattan paths of routes between the first set of sub-regions.

15. The method of claim 10, wherein a plurality of edges exist between the first set of sub-regions, each particular route is defined with respect to the edges intersected by the particular route, and the edges include diagonal edges.

16. The method of claim 15, wherein a plurality of edges exist between the second set of sub-regions, wherein a plurality of the edges between the second set of sub-regions are diagonal, wherein some of the identified propagation permutations intersect the diagonal edges between the second set of smaller sub-regions.

17. The method of claim 16, wherein some of the diagonal edges intersected by the identified propagation permutations are for propagating diagonal edges of routes between the first set of sub-regions.

18. The method of claim 16, wherein some of the diagonal edges intersected by the identified propagation permutations are for propagating Manhattan edges of routes between the first set of sub-regions.

19. The method of claim 10, wherein the formulated LP problem is an integer-linear-programming (“

ILP”

) problem, and the solving of the ILP problem returns integer solutions that specify one propagation permutation for each route in each first-set sub-region traversed by the route.

20. The method of claim 10, wherein the solving of the LP problem returns real-numbered solutions, wherein the method further comprises converting the real-number solutions into integer solutions that specify one identified propagation permutation for each route in each first-set sub-region traversed by the route.

21. The method of claim 10, wherein the method identifies a first route for a first net, said first route having a plurality of paths incident on a plurality of sub-regions in the first set, wherein, for the first route, each propagation permutation in each particular incident sub-region includes one propagation possibility for each of the first-route'"'"'s paths that are incident on the particular sub-region.

22. For a router that hierarchically defines routes for nets within a region of a design layout, the router (i) partitioning the region into a first set of sub-regions and (ii) for each particular net identifying a route that traverses a set of the first-set sub-regions, a computer readable medium comprising a computer program having executable code, the computer program for propagating the routes, the computer program comprising:

a) a first set of instructions for partitioning the first set of sub-regions into a second set of smaller sub-regions;

b) a second set of instructions for identifying a plurality of propagation permutations for propagating each route into the second set of smaller sub-regions of the first set sub-regions;

c) a third set of instructions for formulating a linear-programming (“

LP”

) problem based on the identified propagation permutations; and

d) a fourth set of instructions for solving the LP problem to propagate the routes into the second set of smaller sub-regions.

23. The computer readable medium of claim 22 wherein the third set of instructions includes a fifth set of instructions for using the propagation possibilities to specify an objective function.

24. The computer readable medium of claim 23,

a) wherein the second set of instructions includes:

a sixth set of instructions for identifying a plurality of propagation configurations in each incident first set sub-region traversed by the first route, wherein each propagation configuration in each incident sub-region includes a unique combination of propagation permutations for each path of the particular route that is incident on the incident sub-region;

a seventh set of instructions for computing the cost of each identified propagation configuration; and

b) wherein the fifth set of instructions includes an eight set of instructions for using each propagation configuration and the cost of each propagation configuration to specify the objective function.

25. The computer readable medium of claim 24,

a) wherein each net includes a set of pins;

b) wherein the second set of instructions includes;

a ninth set of instructions for identifying, for each particular identified propagation configuration in each particular first set sub-region, a particular pin configuration that accounts for the particular propagation configuration in the particular first set sub-region;

c) wherein the seventh set of instructions comprises a tenth set of instructions for using the propagation configuration'"'"'s pin configuration to compute a cost of a route necessary for routing the pin configuration; and

d) wherein the objective function includes the routing cost of each propagation configuration.

26. The computer readable medium of claim 25, wherein the third set of instructions includes a fifth set of instructions for specifying a number of constraints.

27. A computer readable medium comprising a computer program having executable code, the computer program for routing nets within a particular region of an integrated circuit (“

IC”

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

a) partitioning the particular IC region into a first set of sub-regions;

b) for each particular net, identifying a route that connects a set of sub-regions containing the particular net'"'"'s pins;

c) partitioning the sub-regions into a second set of smaller sub-regions;

d) identifying a plurality of propagation permutations for propagating each route into the second set of smaller sub-region;

e) formulating a linear-programming (“

LP”

) problem based on the identified propagation permutations; and

f) solving the LP problem to select one identified propagation permutation for each route in each sub-region traversed by the route.

28. The computer readable medium of claim 27, wherein a plurality of paths exist between the first set of sub-regions, each particular route is defined with respect to the paths traversed by the particular route, and the paths include diagonal paths.

29. The computer readable medium of claim 28, wherein a plurality of paths exist between the second set of sub-regions, wherein a plurality of the paths between the second set of sub-regions are diagonal, wherein some of the identified propagation permutations traverse the diagonal paths between the second set of smaller sub-regions.

30. The computer readable medium of claim 29, wherein some of the diagonal paths traversed by the identified propagation permutations are for propagating diagonal paths of routes between the first set of sub-regions.

31. The computer readable medium of claim 29, wherein some of the diagonal paths traversed by the identified propagation permutations are for propagating Manhattan paths of routes between the first set of sub-regions.

32. The computer readable medium of claim 27, wherein a plurality of edges exist between the first Set of sub-regions, each particular route is defined with respect to the edges intersected by the particular route, and the edges include diagonal edges.

33. The computer readable medium of claim 32, wherein a plurality of edges exist between the second set of sub-regions, wherein a plurality of the edges between the second set of sub-regions are diagonal, wherein some of the identified propagation permutations intersect the diagonal edges between the second set of smaller sub-regions.

34. The computer readable medium of claim 33, wherein some of the diagonal edges intersected by the identified propagation permutations are for propagating diagonal edges of routes between the first set of sub-regions.

35. The computer readable medium of claim 33, wherein some of the diagonal edges intersected by the identified propagation permutations are for propagating Manhattan edges of routes between the first set of sub-regions.

36. The computer readable medium of claim 27, the formulated LP problem is an integer-linear-programming (“

ILP”

) problem, and the set of instructions for solving of the ILP problem returns integer solutions that specify one propagation permutation for each route in each first-set sub-region traversed by the route.

37. The computer readable medium of claim 27, wherein the set of instructions for solving of the LP problem returns real-numbered solutions, wherein the program includes a set of instructions for converting the real-number solutions into integer solutions that specify one identified propagation permutation for each route in each first-set sub-region traversed by the route.

38. The computer readable medium of claim 27, wherein the program identifies a first route for a first net, said first route having a plurality of paths incident on a plurality of sub-regions in the first set, wherein, for the first route, each propagation permutation in each particular incident sub-region includes one propagation possibility for each of the first-route'"'"'s paths that are incident on the particular sub-region.