Method and apparatus for routing

• US 7,003,752 B2
• Filed: 12/31/2002
• Issued: 02/21/2006
• Est. Priority Date: 11/18/2002
• Status: Expired due to Fees

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Caldwell, Andrew, Frankle, Jonathan, Jacques, Etienne
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): TAT, BINH C
• Application Number:
  US10/335,093
• Publication Number:
  US 20040098696A1
• Time in Patent Office: 1,148 Days
• Field of Search: 716 1- 18
• 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 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.

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

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

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

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

6. 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.

7. The method of claim 6,

wherein defining the three dimensional 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.

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

9. The method of claim 8, 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.

10. The method of claim 8, 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.

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

12. The method of claim 11, 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.

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

19. The three dimensional routing graph of claim 7 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.

14. 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.

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

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

17. The three dimensional routing graph of claim 14 further comprising a set of non-planar edges exist between nodes on different layers.

18. The three dimensional routing graph of claim 17 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 three dimensional routing graph of claim 16, 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.

21. 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.

22. The computer readable medium of claim 21, wherein each edge connects two sub-regions, wherein some edges are non-Manhattan edges.

23. The computer readable medium of claim 22, wherein some edges are Manhattan edges.

24. The computer readable medium of claim 21, 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.

25. The computer readable medium of claim 24,

wherein the set of instructions for defining the three dimensional 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.

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

27. The computer readable medium of claim 26, 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.

28. The computer readable medium of claim 26, 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.

29. The computer readable medium of claim 25, 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.

30. The computer readable medium of claim 29, 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.