Method and apparatus for searching for a three-dimensional global path

• US 20040098680A1
• 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,047,513 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 three-dimensional global path between first and second sets of routable elements in a region of a layout that has multiple layers. The method partitions the region into several sub-regions. It then performs a path search to identify a path between a first set of sub-regions that contains the first-set elements and a second set of sub-regions that contain a second-set element. When the method performing the path search, it explores expansions along Manhattan and non-Manhattan routing directions between the sub-regions on a plurality of layers.

Claims

1. A method of searching for a three-dimensional global path between first and second sets of routable elements in a region of a layout that has multiple layers, the method comprising:

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

b) performing a path search to identify a path between a first set of sub-regions that contains the first-set elements and a second set of sub-regions that contain a second-set element,

c) wherein performing the path search comprises exploring expansions along Manhattan and non-Manhattan routing directions between the sub-regions on a plurality of layers.

2. The method of claim 1, wherein partitioning the region comprises partitioning each layer of the layout into a plurality of sub-regions, wherein the sub-regions are reachable along different routing directions on different layers.

3. The method of claim 2, wherein the sub-regions are reachable along Manhattan directions on some layers, and are reachable along diagonal directions on other layers.

4. The method of claim 2, wherein performing the path search further comprises exploring non-planar expansions between sub-regions on different layers.

5. The method of claim 4, wherein exploring non-planar expansions comprises identifying on one layer a first sub-regions that is reachable from a second sub-region on another layer.

6. The method of claim 5, wherein the layers of the first and second sub-regions have diagonal routing directions that are not parallel.

7. The method of claim 6, wherein the diagonal routing directions of the first and second sub-regions are orthogonal.

8. The method of claim 7, wherein the first and second sub-regions are not directly overlapping sub-regions.

9. The method of claim 8, wherein the sub-regions are a first group of sub-regions, wherein partitioning the region further comprises partitioning the region into a second group of sub-regions, wherein each second-group sub-region includes a plurality of first-group sub-regions, wherein the first and second sub-regions are in the same second-group sub-region.

10. The method of claim 8, wherein the sub-regions are a first group of sub-regions, wherein partitioning the region further comprises partitioning the region into a second group of sub-regions, wherein each second-group sub-region includes a plurality of first-group sub-regions, wherein the first and second sub-regions are in different second-group sub-regions.

11. The method of claim 1, wherein exploring expansions 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.

12. The method of claim 11 further comprising:

wherein each path terminates in a sub-region;

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

13. A method of specifying a path in a region of a layout that has multiple layers, wherein one layer has a first preferred routing direction and another layer has a second preferred routing direction, wherein the first and second preferred routing directions are neither orthogonal nor parallel to each other, the method comprising:

a) identifying first and second sets of elements to connect by a path;

b) identifying a set of path expansions between the two sets, wherein at least one of the path expansions is a via expansion between the two layers with the first and second preferred routing directions.

14. The method of claim 13, wherein identifying the set of path expansions 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.

15. The method of claim 14, wherein iteratively identifying the set of expansions comprises iteratively identifying a set of expansions about a current lowest-cost path until identifying a path that connects the two sets.

16. The method of claim 14 further comprising:

specifying a plurality of nodes in a graph that represents the layout region;

wherein each path terminates on a node;

wherein identifying an expansion about a path comprises identifying nodes that are reachable from the path'"'"'s terminating node.

17. The method of claim 16, wherein the graph has one layer corresponding to each layer of the layout, wherein the nodes are specified in each layer of the graph, wherein nodes are reachable along different routing directions on different layers, wherein at least some of these different routing directions are neither parallel nor orthogonal to each other.

18. The method of claim 17, wherein nodes are reachable along Manhattan directions on some layers, and are reachable along diagonal directions on other layers.

19. The method of claim 14 further comprising:

partitioning the region into a plurality of sub-regions;

wherein each path terminates in a sub-region;

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

20. The method of claim 19, wherein partitioning the region comprises partitioning each layer of the layout into a plurality of sub-regions, wherein the sub-regions are reachable along different routing directions on different layers, wherein at least some of these different routing directions are neither parallel nor orthogonal to each other.

21. The method of claim 20, wherein the sub-regions are reachable along Manhattan directions on some layers, and are reachable along diagonal directions on other layers.

22. The method of claim 21, wherein identifying reachable sub-regions comprises identifying on one layer a first sub-regions that is reachable from a second sub-region on another layer, wherein the layers of the first and second sub-regions have diagonal routing directions that are not parallel.

23. The method of claim 22, wherein the diagonal routing directions of the first and second sub-regions are orthogonal.

24. The method of claim 23, wherein the first and second sub-regions are not directly overlapping sub-regions.

25. The method of claim 23, wherein the sub-regions are a first set of sub-regions, wherein partitioning the region 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 the first and second sub-regions are in the same second-set sub-region.

26. The method of claim 23, wherein the sub-regions are a first set of sub-regions, wherein partitioning the region 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 the first and second sub-regions are in different second-set sub-regions.

27. A computer readable medium that stores a computer program for searching for a three-dimensional global path between first and second sets of routable elements in a region of a layout that has multiple layers, the computer program comprising sets of instructions for:

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

b) performing a path search to identify a path between a first set of sub-regions that contains the first-set elements and a second set of sub-regions that contain a second-set element,

c) wherein performing the path search comprises exploring expansions along Manhattan and non-Manhattan routing directions between the sub-regions on a plurality of layers.

28. The computer readable medium of claim 27, wherein the set of instructions for partitioning the region comprises a set of instructions for partitioning each layer of the layout into a plurality of sub-regions, wherein the sub-regions are reachable along different routing directions on different layers.

29. The computer readable medium of claim 28, wherein the sub-regions are reachable along Manhattan directions on some layers, and are reachable along diagonal directions on other layers.

30. The computer readable medium of claim 28, wherein the set of instructions for performing the path search further comprises a set of instructions for exploring non-planar expansions between sub-regions on different layers.

31. The computer readable medium of claim 30, wherein the set of instructions for exploring non-planar expansions comprises a set of instructions for identifying on one layer a first sub-regions that is reachable from a second sub-region on another layer.

32. The computer readable medium of claim 31, wherein the layers of the first and second sub-regions have diagonal routing directions that are not parallel.

33. The computer readable medium of claim 32, wherein the diagonal routing directions of the first and second sub-regions are orthogonal.

34. The computer readable medium of claim 33, wherein the first and second sub-regions are not directly overlapping sub-regions.

35. The computer readable medium of claim 34, wherein the sub-regions are a first group of sub-regions, wherein the set of instructions for partitioning the region further comprises a set of instructions for partitioning the region into a second group of sub-regions, wherein each second-group sub-region includes a plurality of first-group sub-regions, wherein the first and second sub-regions are in the same second-group sub-region.

36. The computer readable medium of claim 34, wherein the sub-regions are a first group of sub-regions, wherein the set of instructions for partitioning the region further comprises a set of instructions for partitioning the region into a second group of sub-regions, wherein each second-group sub-region includes a plurality of first-group sub-regions, wherein the first and second sub-regions are in different second-group sub-regions.