Method and apparatus for routing
AssigneeCadence Design Systems, Inc.
InventorsSteven Teig, Jonathan Frankle, Etienne Jacques, Andrew Caldwell
Life of this patent
Estimating the term…
Abstract
Some embodiments of the invention provide a method of routing nets in a region of a layout with multiple layers. The method defines a routing graph that has several of nodes on plurality of 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. The method uses this routing graph to identify routes.
Claims30
A method of defining global routes for nets in a region of a layout with multiple layers, the method comprising:
- a) defining a three dimensional routing graph that has a plurality of nodes on a plurality of layers, wherein each node represents a sub-region on a layer, wherein a set of edges exists between the nodes on each layer, wherein a set of edges on one layer are neither orthogonal nor parallel to a set of edges on another layer, wherein defining the three dimensional routing graph comprises partitioning each layer into a plurality of sub-regions;
- wherein using the three dimensional routing graph comprises identifying, for each net, a route that connects the sub-regions that contain the net's set of routable elements, wherein some of the routes traverse along edges that are neither orthogonal nor parallel to each other;
- and
- b) using the three dimensional routing graph to identify global routes within said region.
A three dimensional global routing graph that represents a region of a multi-layer layout, the three dimensional global routing graph comprising:
- a) a plurality of nodes on a plurality of layers, wherein each node represents a sub-region on a layer;
- and
- b) a set of edges existing between the nodes on each layer, wherein a set of edges on one layer are neither orthogonal nor parallel to a set of edges on another layer,
- wherein the three dimensional global routing graph is for defining global routes that connect nodes representing sub-regions on a layer within said region.
A computer readable medium that stores a computer program for defining global routes for nets in a region of a layout with multiple layers, the computer program comprising sets of instructions for:
- a) defining a three dimensional routing graph that has a plurality of nodes on a plurality of layers, wherein each node represents a sub-region on a layer, wherein a set of edges exists between the nodes on each layer, wherein a set of edges on one layer are neither orthogonal nor parallel to a set of edges on another layer, wherein defining the three dimensional routing graph comprises partitioning each layer into a plurality of sub-regions;
- wherein using the three dimensional routing graph comprises identifying, for each net, a route that connects the sub-regions that contain the net's set of routable elements, wherein some of the routes traverse along edges that are neither orthogonal nor parallel to each other;
- and
- b) using the three dimensional routing graph to identify global routes within said region.
Dependencies are inferred from the claim text.