Method and apparatus for routing

• US 20040098696A1
• Filed: 12/31/2002
• Published: 05/20/2004
• Est. Priority Date: 11/18/2002
• Status: Active Grant

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Jacques, Etienne, Teig, Steven, Caldwell, Andrew, Frankle, Jonathan
• Granted Patent: US 7,003,752 B2
• Time in Patent Office: Days
• US Class Current: 716/129
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

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.

Claims

1. A method of routing nets in a region of a layout with multiple layers, the method comprising:

a) defining a routing graph that has a plurality of nodes on plurality of layers, wherein each node represents a sub-region on a layer, wherein a set of edges exist 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;

b) using the routing graph to identify routes.

2. The method of claim 1,

wherein defining the routing graph comprises partitioning each layer into a plurality of sub-regions;

wherein using the routing graph comprises identifying, for each net, a route that connect 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.

3. The method of claim 2, wherein each edge connects two sub-regions, wherein some edges are non-Manhattan edges.

4. The method of claim 3, wherein some edges are Manhattan edges.

5. The method of claim 4, 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.

6. The method of claim 5, wherein performing the path search comprises:

a) specifying source and target sets;

b) identifying the start of at least one path;

c) 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.

7. The method of claim 1, wherein some of the edges are Manhattan edges while other edges are non-Manhattan edges, wherein the non-Manhattan edges are on different layers than the Manhattan edges.

8. The method of claim 7,

wherein defining the routing graph comprises partitioning each layer into a first set of sub-regions and partitioning the region into a second set of sub-regions;

wherein the edges exist between the first-set sub-regions.

9. The method of claim 8, wherein a set of non-planar edges exist between first-set sub-regions on different layers.

10. The method of claim 9, wherein each second-set sub-region includes a plurality of first-set sub-regions, wherein at least some non-planar edges are between first-set sub-regions that are in the same second-set sub-region.

11. The method of claim 9, wherein each second-set sub-region includes a plurality of first-set sub-regions, wherein at least some non-planar edges are between first-set sub-regions that are in different second-set sub-regions.

12. The method of claim 8, wherein the non-Manhattan edges include a first set of non-Manhattan edges on a first layer and a second set of non-Manhattan edges on a second layer, wherein the first set of non-Manhattan edges do not include an edge between each pair of first-set sub-regions that are adjacent in the direction of the first-set edges on the first layer, and the second set of non-Manhattan edges do not include an edge between each pair of second-set subregions that are adjacent in the direction of the second-set edges on the second layer.

13. The method of claim 12, wherein the first layer is a fourth wiring layer, the second layer is a fifth wiring layer, and the first and second sets of non-Manhattan edges are ±

45°

edges.

14. The method of claim 1, wherein using the routing graph comprises embedding routes in the routing graph.

30. The computer readable medium of claim 9, wherein each second-set sub-region includes a plurality of first-set sub-regions, wherein at least some non-planar edges are between first-set sub-regions that are in the same second-set sub-region.

31. The computer readable medium of claim 9, wherein each second-set sub-region includes a plurality of first-set sub-regions, wherein at least some non-planar edges are between first-set sub-regions that are in different second-set sub-regions.

32. The computer readable medium of claim 8, wherein the non-Manhattan edges include a first set of non-Manhattan edges on a first layer and a second set of non-Manhattan edges on a second layer, wherein the first set of non-Manhattan edges do not include an edge between each pair of first-set sub-regions that are adjacent in the direction of the first-set edges on the first layer, and the second set of non-Manhattan edges do not include an edge between each pair of second-set sub-regions that are adjacent in the direction of the second-set edges on the second layer.

33. The computer readable medium of claim 12, wherein the first layer is a fourth wiring layer, the second layer is a fifth wiring layer, and the first and second sets of non-Manhattan edges are ±

45°

edges.

15. A multi-layer routing graph that represents a region of a multi-layer layout, the routing graph comprising:

a) a plurality of nodes on plurality of layers, wherein each node represents a sub-region on a layer,

b) a set of edges exist 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.

16. The routing graph of claim 15, wherein some edges are Manhattan edges and some are non-Manhattan edges.

17. The routing graph of claim 16, wherein the non-Manhattan edges are on different layers than the Manhattan edges.

18. The routing graph of claim 15 further comprising a set of non-planar edges exist between nodes on different layers.

19. The routing graph of claim 18 further comprising a plurality of Gcells, wherein each Gcell includes a plurality of nodes on a plurality of layers, wherein at least some non-planar edges are between nodes that are in the same Gcell.

20. The routing graph of claim 18 further comprising a plurality of Gcells, wherein each Gcell includes a plurality of nodes on a plurality of layers, wherein at least some non-planar edges are between nodes that are in different Gcells.

21. The routing graph of claim 17, wherein the non-Manhattan edges include a first set of non-Manhattan edges on a first layer and a second set of non-Manhattan edges on a second layer, wherein the first set of non-Manhattan edges do not include an edge between each pair of first-set sub-regions that are adjacent in the direction of the first-set edges on the first layer, and the second set of non-Manhattan edges do not include an edge between each pair of second-set sub-regions that are adjacent in the direction of the second-set edges on the second layer.

22. A computer readable medium that stores a computer program for routing nets in a region of a layout with multiple layers, the computer program comprising sets of instructions for:

a) defining a routing graph that has a plurality of nodes on plurality of layers, wherein each node represents a sub-region on a layer, wherein a set of edges exist 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;

b) using the routing graph to identify routes.

24. The computer readable medium of claim 22,

wherein the set of instructions for defining the routing graph comprises a set of instructions for partitioning each layer into a plurality of sub-regions;

wherein the set of instructions for using the routing graph comprises a set of instructions for identifying, for each net, a route that connect 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.

25. The computer readable medium of claim 24, wherein each edge connects two subregions, wherein some edges are non-Manhattan edges.

26. The computer readable medium of claim 25, wherein some edges are Manhattan edges.

27. The computer readable medium of claim 22, wherein some of the edges are Manhattan edges while other edges are non-Manhattan edges, wherein the non-Manhattan edges are on different layers than the Manhattan edges.

28. The computer readable medium of claim 27,

wherein the set of instructions for defining the routing graph comprises a set of instructions for partitioning each layer into a first set of sub-regions and partitioning the region into a second set of sub-regions;

wherein the edges exist between the first-set sub-regions.

29. The computer readable medium of claim 28, wherein a set of non-planar edges exist between first-set sub-regions on different layers.