Method and apparatus for searching for a three-dimensional global path
First Claim
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.
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.
-
Citations
36 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
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. - 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 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. - View Dependent Claims (28, 29, 30, 31, 32, 33, 34, 35, 36)
-
Specification