Method and apparatus for routing

• US 6,988,257 B2
• Filed: 12/31/2002
• Issued: 01/17/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): Garbowski, Leigh M.
• Assistant Examiner(s): Dimyan, Magid Y.
• Application Number:
  US10/334,690
• Publication Number:
  US 20040098695A1
• Time in Patent Office: 1,113 Days
• Field of Search: 716/13, 716 7- 9, 716/12, 716/11, 716 1- 3, 438/617, 438/130
• 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 defining a global route for a net in a region of a layout, where each net has a set of routable elements. The method partitions the region into several rectangular sub-regions. It then identifies a set of sub-regions that contain the routable elements of the net. Next, it defines a global route that connects the identified sub-regions, where the global route includes at least one non-Manhattan edge that crosses a boundary between two sub-regions at a non-vertex location.

Claims

1. A method of defining a global route for a net in a region of a layout, wherein each net has a set of routable elements, the method comprising:

a) partitioning the region into a plurality of rectangular sub-regions;

b) identifying a set of sub-regions that contain the routable elements of the net; and

c) defining a global route that connects the identified sub-regions, wherein the global route includes at least one non-Manhattan edge that crosses a boundary between two sub-regions at a non-corner vertex of the rectangular sub-regions, wherein the non-Manhattan edge is neither parallel nor orthogonal to the boundaries of the rectangular sub-regions that it crosses.

2. The method of claim 1, wherein the global route further includes at least one Manhattan edge.

3. The method of claim 1, wherein the sub-regions are Gcells.

4. The method of claim 1 further comprising partitioning the region into a plurality of Gcells, wherein several sub-regions are within each Gcell.

5. The method of claim 1, wherein defining the global route comprises performing a set of path searches to identify a set of paths that connect the identified set of sub-regions, wherein performing each path search comprises exploring expansions in non-Manhattan directions between the sub-regions.

6. The method of claim 5, wherein performing each path search further comprises exploring expansions in Manhattan directions between the sub-regions.

7. The method of claim 6, wherein the expansions in the non-Manhattan directions are along non-Manhattan edges between the sub-regions, while the expansions in the Manhattan directions are along Manhattan edges between the sub-regions.

8. The method of claim 7, wherein each edge is between two adjacent sub-regions.

9. The method of claim 8, wherein the non-Manhattan edges traverse different layers than the Manhattan edges.

10. A computer readable medium that stores a computer program for defining a global route for a net in a region of a layout, wherein each net has a set of routable elements, the computer program comprising sets of instructions for:

a) partitioning the region into a plurality of rectangular sub-regions;

b) identifying a set of sub-regions that contain the routable elements of the net; and

c) defining a global route that connects the identified sub-regions, wherein the global route includes at least one non-Manhattan edge that crosses a boundary between two sub-regions at a non-corner vertex of the rectangular sub-regions, wherein the non-Manhattan edge is neither parallel nor orthogonal to the boundaries of the rectangular sub-regions that it crosses.

11. The computer readable medium of claim 10, wherein the global route further includes at least one Manhattan edge.

12. The computer readable medium of claim 10, wherein the sub-regions are Gcells.

13. The computer readable medium of claim 10, wherein the computer program further comprises a set of instructions for partitioning the region into a plurality of Gcells, wherein several sub-regions are within each Gcell.

14. The computer readable medium of claim 10, wherein the set of instructions for defining the global route comprises a set of instructions for performing a set of path searches to identify a set of paths that connect the identified set of sub-regions, wherein performing each path search comprises exploring expansions in non-Manhattan directions between the sub-regions.

15. The computer readable medium of claim 14, wherein the set of instructions for performing each path search further comprises a set of instructions for exploring expansions in Manhattan directions between the sub-regions.

16. The computer readable medium of claim 15, wherein the expansions in the non-Manhattan directions are along non-Manhattan edges between the sub-regions, while the expansions in the Manhattan directions are along Manhattan edges between the sub-regions.

17. The computer readable medium of claim 16, wherein each edge is between two adjacent sub-regions.

18. The computer readable medium of claim 17, wherein the non-Manhattan edges traverse different layers than the Manhattan edges.