Method and apparatus for searching for a three-dimensional global path
First Claim
1. A method of searching for a three-dimensional global route 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; and
b) performing a path search to identify a global route path between a first set of sub-regions that contains the first-set elements and a second set of sub-regions that contains 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.
1 Assignment
0 Petitions
Accused Products
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.
172 Citations
36 Claims
-
1. A method of searching for a three-dimensional global route 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; and b) performing a path search to identify a global route path between a first set of sub-regions that contains the first-set elements and a second set of sub-regions that contains 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A method of specifying a global route 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 global route path; and 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, c) wherein the set of path expansions define the global route path between the first and second sets of elements. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26)
-
-
27. A computer readable medium that stores a computer program for searching for a three-dimensional global route 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; and b) performing a path search to identify a global route 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. - View Dependent Claims (28, 29, 30, 31, 32, 33, 34, 35, 36)
-
Specification