LP method and apparatus for identifying routes

• US 6,915,501 B2
• Filed: 01/05/2002
• Issued: 07/05/2005
• Est. Priority Date: 01/19/2001
• Status: Expired due to Fees

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Buset, Oscar, Teig, Steven
• Primary Examiner(s): Whitmore, Satcy A.
• Application Number:
  US10/040,948
• Publication Number:
  US 20020166105A1
• Time in Patent Office: 1,277 Days
• Field of Search: 716 12- 14
• US Class Current: 716/130
• 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 identities routes. In some embodiments, this method is used by a router that defines routes for nets within a region of a design layout. Each net has a set of pins in the region. The method partitions the region into a set or sub-regions. For each particular net, the method identifies a set or route. Each route for a net traverses the sub-regions that contain the net'"'"'s pins. Each route includes a set of route edge, and each route edge connects two sub-regions. Also, some of the identified routes have route edges that are at least partially diagonal. The method formulates a linear-programming (“LP”) problem based on the identified sets of routes for the nets. The method then solves the LP problem to identify one route for each net. 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 route for each net. 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 route for each net.

Claims

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

a) partitioning the design region into a first set of sub-regions, wherein a plurality of inter-sub-region edges exist between the sub-regions, and wherein a plurality of the inter-sub-region edges are diagonal;

b) for each particular net, identifying a set of routes, wherein each route in the route set identified for a particular net traverses a set of sub-regions containing the particular net'"'"'s pins, wherein each route includes a set of route edges, and each route edge connects two sub-regions, and wherein routes are defined with respect to the inter-sub-region edges;

c) formulating a linear-programming (“

LP”

) problem based on the identified routes, wherein formulating an LP problem includes using the identified routes to specify an objective function to optimize; and

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

2. The method of claim 1, wherein the objective function includes a component for overall length of the routes for the nets, and solving the LP problem includes searching for a solution to the objective function that reduces the overall-length component.

3. The method of claim 1, wherein the objective function includes a component for the expected number of vias for the routes for the nets, and solving the LP problem includes searching for a solution to the objective function that minimizes the via-number component.

4. The method of claim 1, wherein

the objective function includes a congestion-component that quantifies the congestion of the inter-sub-region edges, and

solving the LP problem includes:

measuring the congestion of the inter-sub-region edges for each solution considered by the objective function;

identifying a solution that reduces the congestion of the inter-sub-region edges.

5. The method of claim 1, wherein formulating an LP problem includes specifying at least one congestion constraint regarding the congestion of the inter-sub-region edges between the sub-regions.

6. The method of claim 1, wherein some of the inter-sub-region edges share common regions with other inter-sub-region edges, wherein formulating an LP problem includes specifying that the capacity of the common regions be properly shared among the inter-sub-region edges.

7. The method of claim 6, wherein specifying at least one includes requiring that only one route be selected for each net.

8. The method of claim 7, 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 route for each net.

9. A computer readable medium comprising a computer program having executable code, the computer program for routing a net within a particular region of a design layout, the net having a plurality of pins, the computer program comprising:

a) a first set of instructions for partitioning the design region into a first set of sub-regions, wherein a plurality of paths exist between the sub-regions, and wherein a plurality of the paths are diagonal paths, and wherein some of the paths share common regions with other paths;

b) a second set of instructions for identifying, for each particular net, a set of routes, wherein each route in the route set identified for a particular net traverses a set of sub-regions containing the particular net'"'"'s pins, wherein each route includes a set of route edges, and each route edge connects two sub-regions, and wherein the routes are defined with respect to the paths between sub-regions;

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

LP”

) problem based on the identified routes, wherein the third set of instructions includes a fifth set of instructions for using the identified routes to specify an objective function to optimize, and wherein the third set of instructions further includes a sixth set of instructions for specifying that the capacity of common regions be properly shared among paths; and

d) a fourth set of instructions solving the LP problem to identify one route for each net.

10. The computer readable medium of claim 9, wherein

the objective function includes a congestion-component that quantifies the congestion of the paths, and

the fourth set of functions includes:

a seventh set of instructions for measuring the congestion of the paths for each solution considered by the objective function;

an eighth set of instructions for identifying a solution that reduces the congestion of the paths.

11. The computer readable medium of claim 9, wherein the third set of instructions further includes a seventh set of instructions for specifying a congestion constraint regarding the congestion of the paths between the sub-regions.

12. A method of routing nets within a particular region of a design layout, each net having a set of pins, the method comprising:

a) partitioning the design region into a first set of sub-regions, wherein a plurality of paths exist between the sub-regions, and wherein a plurality of the paths are diagonal paths;

b) for each particular net, identifying a set of routes, wherein each route in the route set identified for a particular net traverses a set of sub-regions containing the particular net'"'"'s pins, wherein each route includes a set of route edges, and each route edge connects two sub-regions, and wherein the routes are defined with respect to the paths between the sub-regions;

c) formulating a linear-programming (“

LP”

) problem based on the identified routes, wherein formulating an LP problem includes using the identified routes to specify an objective function to optimize; and

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

13. The method of claim 12, wherein

the objective function includes a congestion-component that quantifies the congestion of the paths, and

solving the LP problem includes:

measuring the congestion of the paths for each solution considered by the objective function;

identifying a solution that reduces the congestion of the paths.

14. The method of claim 12, wherein formulating an LP problem includes specifying a congestion constraint regarding the congestion of the paths between the sub-regions.

15. The method of claim 12, wherein some of the paths share common regions with other paths, wherein formulating an LP problem includes specifying that the capacity of common regions be properly shared among the paths.

16. The method of claim 15, wherein specifying at least one constraint includes requiring that only one route be selected for each net.

17. The method of claim 16, 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 route for each net.

18. A computer readable medium comprising a computer program having executable code, the computer program for routing a net within a particular region of a design layout, the net having a plurality of pins, the computer program comprising:

a) a first set of instructions for partitioning the design region into a first set of sub-regions, wherein a plurality of inter-sub-region edges exist between the sub-regions, and wherein a plurality of the inter-sub-region edges are diagonal;

b) a second set of instructions for identifying, for each particular net, a set of routes, wherein each route in the route set identified for a particular net traverses a set of sub-regions containing the particular net'"'"'s pins, wherein each route includes a set of route edges, and each route edge connects two sub-regions, and wherein the routes are defined with respect to the inter-sub-region edges;

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

LP”

) problem based on the identified routes, wherein the third set of instructions includes a fifth set of instructions for using the identified routes to specify an objective function to optimize; and

d) a fourth set of instructions solving the LP problem to identify one route for each net.

19. The computer readable medium of claim 18, wherein

the objective function includes a congestion-component that quantifies the congestion of the inter-sub-region edges, and

the fourth set of instructions includes

a sixth set of instruction for measuring the congestion of the inter-sub-region edges for each solution considered by the objective function;

a seventh set of instructions for identifying a solution that reduces the congestion of the inter-sub-region edges.

20. The computer readable medium of claim 18, wherein the third set of instructions includes a sixth set of instructions for specifying a congestion constraint regarding the congestion of the inter-sub-region edges between the sub-regions.

21. The computer readable medium of claim 18, wherein some of the inter-sub-region edges share common regions with other inter-sub-region edges, wherein the third set of instructions further includes a sixth set of instructions for specifying that the capacity of the common regions be properly shared among the inter-sub-region edges.