Method and apparatus for searching for a global path

摘要

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.