METHOD, APPARATUS, AND SYSTEM FOR ROUTING

摘要

Some embodiments of the invention provide a method of identifying global routes for nets in a region of a layout with multiple layers. In the region, each net has a set of routable elements. The method partitions each layer of the region into several sub-regions. For each net, the method then identifies a route that connects the sub-regions that contain the net's set of routable elements, where some routes have at least one non-Manhattan edge and traverse sub-regions on multiple layers. Some embodiments search for a three-dimensional global path between first and second sets of routable elements in a region of a layout that has multiple layers. These embodiments partition the region into several sub-regions. They then perform 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. During the path search, these embodiments explore expansions along Manhattan and non-Manhattan routing directions between the sub-regions on a plurality of layers. Some embodiments define a routing graph that has several of nodes on several layers, where each node represents a sub-region on a layer. In the graph, there is a set of edges between the nodes on each layer. On one layer, there is at least one set of edges that are neither orthogonal nor parallel to a set of edges on another layer. These embodiments then use the routing graph to identify routes.