Method and apparatus for searching for a global path

• US 20040098698A1
• Filed: 12/31/2002
• Published: 05/20/2004
• Est. Priority Date: 11/18/2002
• Status: Active Grant

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Frankle, Jonathan
• Granted Patent: US 7,010,771 B2
• Time in Patent Office: Days
• 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 searching for a global path between first and second sets of routable elements in a region of a layout. The method partitions the region into several rectangular sub-regions. It then identifies a set of sub-regions that contain the two sets of elements. Next, it performs a path search to identify a set of path expansions between a sub-region that contains a first-set element and a sub-region that contains a second-set element. When the method performs the path search, it explores expansions along non-Manhattan directions between the sub-regions.

Claims

1. A method of searching for a global path between first and second sets of routable elements in a region of a layout, the method comprising:

a) partitioning the region into a plurality of rectangular sub-regions;

b) identifying a set of sub-regions that contain the two sets of elements;

c) performing a path search to identify a set of path expansions between a sub-region that contains a first-set element and a sub-region that contains a second-set element, wherein performing the path search comprises exploring expansions along non-Manhattan directions between the sub-regions.

2. The method of claim 1, wherein each expansion is along an edge that connects two sub-regions, wherein at least some edges are non-Manhattan edges.

3. The method of claim 2, wherein some edges are Manhattan edges.

4. The method of claim 3, wherein the layout has multiple layers, and the non-Manhattan edges are on different layers than the Manhattan edges.

5. The method of claim 1, wherein performing the path search comprises:

a) identifying the start of at least one path;

b) iteratively identifying a set of expansions about previously identified paths until identifying a path that connects the two sets.

6. The method of claim 5 further comprising:

wherein each path terminates in a sub-region;

wherein identifying an expansion about a path comprises identifying sub-regions that are reachable from the path'"'"'s terminating sub-region.

7. The method of claim 6, wherein some sub-regions are reachable along Manhattan directions, and some sub-regions are reachable along non-Manhattan directions.

8. The method of claim 1, wherein each expansion is across an edge that is between two sub-regions, wherein at least some edges are non-Manhattan edges.

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

10. The method of claim 1 further comprising partitioning the region into a plurality of Gcells, wherein each Gcell contains several sub-regions.

11. The method of claim 1, wherein the rectangular sub-regions are squares.

12. The method of claim 11, wherein all the square sub-regions have the same size.

13. A computer readable medium storing a computer program for searching for a global path between first and second sets of routable elements in a region of a layout, the computer program comprising sets of instructions for:

a) partitioning the region into a plurality of rectangular sub-regions;

b) identifying a set of sub-regions that contain the two sets of elements;

c) performing a path search to identify a set of path expansions between a sub-region that contains a first-set element and a sub-region that contains a second-set element, wherein performing the path-search comprises exploring expansions along non-Manhattan directions between the sub-regions.

14. The computer readable medium of claim 13, wherein each expansion is along an edge that connects two sub-regions, wherein at least some edges are non-Manhattan edges.

15. The computer readable medium of claim 14, wherein some edges are Manhattan edges.

16. The computer readable medium of claim 15, wherein the layout has multiple layers, and the non-Manhattan edges are on different layers than the Manhattan edges.

17. The computer readable medium of claim 13, wherein each expansion is across an edge that is between two sub-regions, wherein at least some edges are non-Manhattan edges.

18. The computer readable medium of claim 13, wherein the sub-regions are Gcells.

19. The computer readable medium of claim 13, wherein the computer program further comprises a set of instructions for partitioning the region into a plurality of Gcells, wherein each Gcell contains several sub-regions.

20. The computer readable medium of claim 13, wherein the rectangular sub-regions are squares.