Method and apparatus for routing

• US 20040098695A1
• 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: Teig, Steven, Caldwell, Andrew, Frankle, Jonathan, Jacques, Etienne
• Granted Patent: US 6,988,257 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 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;

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-vertex location.

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 search to identify a set of paths that connect the identified set of sub-region, 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 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;

c) performing a set of path searches to identify a set of paths that connect the identified set of sub-region, wherein performing each path search comprises exploring expansions in non-Manhattan directions between identified sub-regions;

d) defining the global route based on the set of paths.

15. 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 search to identify a set of paths that connect the identified set of sub-region, wherein performing each path search comprises exploring expansions in non-Manhattan directions between the sub-regions.

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

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

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

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

11. 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;

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-vertex location.

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

13. The computer readable medium of claim 11, wherein the sub-regions are Gcells.

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