Method and apparatus for pre-computing routes

• US 7,139,994 B2
• Filed: 01/07/2002
• Issued: 11/21/2006
• 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: Teig, Steven, Chao, Heng-Yi, Ganley, Joseph L.
• Primary Examiner(s): Whitmore, Stacy A.
• Assistant Examiner(s): TAT, BINH C
• Application Number:
  US10/041,957
• Publication Number:
  US 20030088844A1
• Time in Patent Office: 1,779 Days
• Field of Search: 716 1- 18, 257207-211
• 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 a method of pre-computing routes for nets in a region of an integrated circuit (“IC”) layout. The method initially defines a set of partitioning lines for partitioning the region into a plurality of sub-regions during a routing operation. For a particular set of potential sub-regions, the method then identifies a set of routes that traverse the particular set of potential sub-regions, where at least one of the identified routes has at least one diagonal edge. The method then stores the identified routes.

Claims

1. A method of pre-computing routes for nets, the method comprising:

a) prior to performing a routing operation, defining a set of partitioning lines for partitioning a region of an integrated circuit (“

IC”

) layout into a plurality of sub-regions, during the routing operation;

b) for a set of potential sub-regions, identifying a set of at least two routes that traverse the potential set of sub-regions, wherein at least one of the routes has at least one diagonal edge; and

c) storing the identified routes, wherein said stored routes are for use during the routing operation.

2. The method of claim 1, wherein a plurality of paths exist between the sub-regions defined by the set of partitioning lines, wherein a plurality of the paths are diagonal paths, wherein at least one of the routes traverses some of the diagonal paths.

3. The method of claim 2 wherein identifying the routes comprises identifying the paths between the sub-regions used by each route.

4. The method of claim 3, wherein a plurality of the paths are Manhattan paths, wherein at least one of the routes traverses some of the Manhattan paths.

5. The method of claim 1, wherein a plurality of edges exist between the sub-regions defined by the set of partitioning lines, wherein a plurality of the edges between the sub-regions are diagonal edges, wherein at least one of the routes intersects at least one of the diagonal edges.

6. The method of claim 5, wherein identifying the routes comprises identifying the edges between the sub-regions intersected by each route.

7. The method of claim 6, wherein a plurality of the edges between the sub-regions are Manhattan edges, wherein at least one of the routes intersects at least one of the Manhattan edges.

8. The method of claim 7 further comprising:

a) for each particular set of potential sub-regions from a group of potential-sub-region sets, identifying a set of routes that traverse the particular set of potential sub-regions, wherein some of the routes have diagonal edges; and

b) storing the identified routes.

9. The method of claim 8, wherein the group of sets includes all possible sets of sub-regions including sets with zero or one sub-region, wherein the identified sets of routes for sets of sub-regions with zero or one sub-region are empty.

10. The method of claim 8, wherein the group of sets includes all combinations of two or more sub-regions.

11. For a router that uses a set of partitioning lines to partition an integrated-circuit (“

IC”

) layout region into a plurality of sub-regions, wherein a plurality of routing paths exist between the sub-regions, a method of pre-computing routes for connecting said sub-regions, the method comprising;

for each particular combination of two or more sub-regions, identifying at least one route for connecting the particular combination of said sub-regions, said identifying performed before a routing operation;

identifying the routing paths used by each identified route, wherein some of the identified routing paths are diagonal; and

storing the identified routing paths for each identified route in a storage structure, wherein said stored routing paths are for use during the routing operation.

12. The method of claim 11, wherein some of the routing paths are horizontal.

13. The method of claim 11, wherein some of the routing paths are Manhattan.

14. The method of claim 13, wherein the Manhattan routing paths are defined with respect to a first grid, and wherein the diagonal routing paths are defined with respect to a second grid.

15. The method of claim 11, wherein the set of partitioning lines includes intersecting lines that form a partitioning grid.

16. For a router that uses a set of partitioning lines to partition an integrated-circuit (“

IC”

) layout region into a plurality of sub-regions, wherein a plurality of edges exist between said sub-regions, a method of pre-computing routes for connecting said sub-regions, the method comprising;

for each particular combination of at least two of said sub-regions,

identifying at least one routing graph for connecting the particular combination of said sub-regions, wherein said identifying is performed before a routing operation;

identifying the edges intersected by each routing graph identified for the particular combination of said sub-regions,

wherein some of the identified edges are diagonal; and

storing the identified edges for each routing graph identified for the particular combination of said sub-regions in a storage structure, wherein said stored edges are for use during the routing operation.

17. The method of claim 16, wherein some of the edges are horizontal.

18. The method of claim 16, wherein some of the edges are Manhattan.

19. The method of claim 18, wherein the Manhattan edges are defined with respect to a first grid, and wherein the diagonal edges are defined with respect to a second grid.

20. A method of pre-computing routes, the method comprising:

a) prior to performing a routing operation, defining a set of partitioning lines for partitioning a region of an integrated circuit (“

IC”

) layout into a plurality of sub-regions, during the routing operation, wherein a plurality of ±

45°

diagonal edges and a plurality of Manhattan edges exist between the sub-regions;

b) for a set of potential sub-regions, identifying a set of at least two routes that traverse the potential set of sub-regions, wherein at least one of the routes utilizes at least one diagonal edge and one Manhattan edge; and

c) storing the identified routes, wherein said stored routes are for use during the routing operation.

21. A method of pre-computing routes, the method comprising:

a) defining a set of partitioning lines for partitioning a region of an integrated circuit (“

IC”

) layout into a plurality of sub-regions, during the routing operation said defining performed before the routing operation, wherein a plurality of ±

45°

diagonal paths and a plurality of Manhattan paths exist between the sub-regions;

b) for a set of potential sub-regions, identifying a set of at least two routes that traverse the potential set of sub-regions, wherein at least one of the routes utilizes at least one diagonal path and one Manhattan path; and

c) storing the identified routes, wherein said stored routes are for use during the routing operation.