Patent ID: 7171635

Claim:
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.