Method and apparatus for routing

• US 7,171,635 B2
• Filed: 12/31/2002
• Issued: 01/30/2007
• Est. Priority Date: 11/18/2002
• Status: Expired due to Fees

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Frankle, Jonathan
• Primary Examiner(s): Siek; Vuthe
• Assistant Examiner(s): TAT, BINH C
• Application Number:
  US10/334,689
• Publication Number:
  US 20040098694A1
• Time in Patent Office: 1,491 Days
• Field of Search: 716 1- 18
• US Class Current: 716/129
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Some embodiments of the invention provide a method of identifying global routes for nets in a region of a layout with multiple layers, where each net has a set of routable elements. The method partitions each layer of the region into several sub-regions. For each net, the method then identifies a route that connects the sub-regions that contain the net'"'"'s set of routable elements. Some of the identified routes have at least one non-Manhattan edge and traverse sub-regions on multiple layers.

Claims

1. A method for identifying global routes for nets in a region of a layout with multiple layers, wherein each net has a set of routable elements, the method comprising:

a) partitioning each layer of the region into a plurality of sub-regions; and

b) for each net, identifying a global route that connects the sub-regions that contain the net'"'"'s set of routable elements, wherein some of the routes have at least one non-Manhattan edge and traverse sub-regions on multiple layers, wherein identifying the route for a net comprises performing at least one path search that explores planar path expansions on at least one layer and non-planar path expansions between the layers in order to identify a segment of the route, wherein performing the path search comprises;

i) specifying source and target sets;

ii) identifying the start of at least one path;

iii) iteratively identifying a set of expansions about previously identified paths until identifying a path that connects the source and target sets, wherein the identified path is the segment of the route, wherein each expansion is from one sub-region to another, wherein some expansions are along planar Manhattan directions, some expansions are along planar non-Manhattan directions, and some expansions are along non-planar directions.

2. The method of claim 1, wherein the sub-regions are Gcells.

3. The method of claim 1, wherein the sub-regions are regions within Gcells.

4. The method of claim 1, wherein the sub-regions are a first set of sub-regions, wherein the method further comprises partitioning the region into a second set of sub-regions, wherein each second-set sub-region includes a plurality of first-set sub-regions, wherein at least some non-planar expansions are between first-set sub-regions that are in the same second-set sub-region.

5. The method of claim 1, wherein the sub-regions are a first set of sub-regions, wherein the method further comprises partitioning the region into a second set of sub-regions, wherein each second-set sub-region includes a plurality of first-set sub-regions, wherein at least some non-planar expansions are between first-set sub-regions that are in different second-set sub-regions.

6. A computer readable medium storing a computer program that identifies global routes for nets in a region of a layout with multiple layers, wherein each net has a set of routable elements, the computer program comprising sets of instructions for:

a) partitioning each layer of the region, into a plurality of sub-regions; and

b) for each net, identifying a global route that connects the sub-regions that contain the net'"'"'s set of routable elements, wherein some of the routes have at least one non-Manhattan edge and traverse sub-regions on multiple layers, wherein identifying the route for a net comprises performing at least one path search that explores planar path expansions on at least one layer and non-planar path expansions between the layers in order to identify a segment of the route, wherein performing the path search comprises;

i) specifying source and target sets;

ii) identifying the start of at least one path;

iii) iteratively identifying a set of expansions about previously identified paths until identifying a path that connects the source and target sets, wherein the identified path is the segment of the route, wherein each expansion is from one sub-region to another, wherein some expansions are along planar Manhattan directions, some expansions are along planar non-Manhattan directions, and some expansions are along non-planar directions.

7. The computer readable medium of claim 6, wherein the sub-regions are Gcells.

8. The computer readable medium of claim 6, wherein the sub-regions are regions within Gcells.

9. The computer readable medium of claim 6, wherein the sub-regions are a first set of sub-regions, wherein the computer program further comprises a set of instructions for partitioning the region into a second set of sub-regions, wherein each second-set sub-region includes a plurality of first-set sub-regions, wherein at least some non-planar expansions are between first-set sub-regions that are in the same second-set sub-region.

10. The computer readable medium of claim 6, wherein the sub-regions are a first set of sub-regions, wherein the computer program further comprises a set of instructions for partitioning the region into a second set of sub-regions, wherein each second-set sub-region includes a plurality of first-set sub-regions, wherein at least some non-planar expansions are between first-set sub-regions that are in different second-set sub-regions.