Hierarchical routing method and apparatus that use diagonal routes

• US 20030018947A1
• Filed: 12/07/2001
• Published: 01/23/2003
• Est. Priority Date: 12/07/2000
• Status: Active Grant

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Buset, Oscar, Teig, Steven
• Granted Patent: US 7,073,150 B2
• Time in Patent Office: Days
• US Class Current: 716/7
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• CPC Class Codes: G11B 7/08582 Sled-type positioners

Abstract

Some embodiments provide a hierarchical routing method that uses diagonal routes. This method routes a net within a particular region of an integrated circuit (“IC”) layout. This net includes several pins in the region. The method initially partitions the particular IC region into a first set of sub-regions. It then identifies a first route that connects a group of first-set sub-regions that contain the net'"'"'s pins. The identified first route has an edge that is at least partially diagonal. The method next partitions the first-set sub-regions into a second set of smaller sub-regions. It then propagates the first route into the second-set sub-regions.

Claims

1. A method of routing a net within a particular region of an integrated circuit (“

IC”

) layout, the net having a plurality of pins, the method comprising;

a) partitioning the particular IC region into a first set of sub-regions;

b) identifying a first route that connects a group of first-set sub-regions containing the net'"'"'s pins, wherein the route has an route edge that is at least partially diagonal;

c) partitioning the first-set sub-regions into a second set of smaller sub-regions;

d) propagating the first route into the second-set sub-regions.

2. The method of claim 1, wherein a first set of paths exists between the first set of sub-regions, and a second set of paths exists between the second set of sub-regions, wherein the first route is defined with respect to a third set of paths that are a sub-set of the first set of paths.

3. The method of claim 2 further comprising identifying a first second-set path that represents a propagation of a particular third-set path into the second set of sub-regions.

4. The method of claim 3, wherein the particular third-set path and the first second-set path are diagonal.

5. The method of claim 3, wherein the particular third-set path is a Manhattan path and the first second-set path is a diagonal.

6. The method of claim 3, wherein the particular third-set path is a diagonal path and the first second-set path is a Manhattan path.

7. The method of claim 3 further comprising identifying a second second-set path that, along with the first second-set path, represents the propagation of the particular third-set path into the second set of sub-regions.

8. The method of claim 7, wherein the particular third-set path is diagonal, and the first and second second-set paths are diagonal.

9. The method of claim 1, wherein a first set of inter-region edges exists between the first set of sub-regions, and a second set of inter-region edges exists between the second set of sub-regions, wherein the first route is defined with respect to a third set of inter-region edges that are a sub-set of the first set of inter-region edges.

10. The method of claim 9 further comprising identifying a first second-set edge that represents a propagation of a particular third-set edge into the second set of sub-regions.

11. The method of claim 10, wherein the particular third-set edge and the first second-set edge are diagonal.

12. The method of claim 10, wherein the particular third-set edge is a Manhattan inter-region edge and the first second-set edge is a diagonal.

13. The method of claim 10, wherein the particular third-set edge is a diagonal inter-region edge and the first second-set edge is a Manhattan inter-region edge.

14. The method of claim 10 further comprising identifying a second second-set edge that, along with the first second-set edge, represents the propagation of the particular third-set edge into the second set of sub-regions.

15. The method of claim 14, wherein the particular third-set edge is diagonal, and the first and second second-set edges are diagonal.

16. The method of claim 1 further comprising:

in one of the first-set sub-regions that has been partitioned into a first group of second-set sub-regions, identifying a second route that connects the sub-regions in the first group that contain the net'"'"'s pins.

17. The method of claim 1 wherein the pins are actual and virtual pins for the net.

18. The method of claim 1, wherein a virtual pin in one of the first set of sub-regions is set to account for propagation of a higher-level route into the particular IC region.

19. The method of claim 1 further comprising defining at least one virtual pin for the net to account for propagating the first route into the second set of sub-regions.

20. A computer readable medium comprising a computer program having executable code, the computer program for routing a set of nets within a region of an integrated circuit (“

IC”

) layout, wherein each net includes a set of pins in the region, the computer program comprising;

a first set of instructions for partitioning the IC region into a first set of sub-regions, wherein a first set of paths exist between the first set of sub-regions, wherein some of the first set of paths are diagonal;

a second set of instructions for identifying, for each particular net, a first route that connects a group of first-set sub-regions containing the particular net'"'"'s pins, wherein each particular first route is defined in terms of the paths from the first path set that the first route traverses, wherein at least one of the first routes traverses at least one of the diagonal paths of the first path set;

a third set of instructions for partitioning the first-set sub-regions into a second set of sub-regions, wherein a second set of paths exist between the second set of sub-regions, wherein some of the second set paths are diagonal;

a fourth set of instructions for identifying, for each particular net, a second route that connects a group of second-set sub-regions containing the pins of the particular net, wherein at least one of the second routes traverses at least one of the diagonal paths.

21. The computer readable medium of claim 20, wherein the computer program further comprises:

a fifth set of instructions for identifying propagations of the first routes into the second set of sub-regions, wherein the propagations of the first routes are defined with respect to the second set paths, and some of the identified propagations traverse diagonal paths in the second path set.

22. The computer readable medium of claim 21, wherein the first and second sets of paths further include Manhattan paths, and some of the routes and propagations traverse some of the Manhattan paths.

23. The computer readable medium of claim 21, wherein the identified propagations are defined with respect to the second set paths that are between the second-set sub-regions of different first-set sub-regions.

24. The computer readable medium of claim 20, wherein the first route of a net that has all its pins in one of the first-set sub-regions is specified by a null set of paths.

26. The computer readable medium of claim 25, wherein the computer program further comprises:

a fifth set of instructions for identifying propagations of the first routes into the second set of sub-regions, wherein the propagations are defined with respect to the second set of inter-region edges that the propagations intersect, and some of the identified propagations intersect diagonal inter-region edges in the second edge set.

27. The computer readable medium of claim 26, wherein the first and second sets of inter-region edges further include Manhattan inter-region edges, and some of the routes and propagations intersect some of the Manhattan inter-region edges.

28. The computer readable medium of claim 26, wherein the identified propagations are defined with respect to the inter-region edges from the second set that are between the second-set sub-regions of different first-set sub-regions.

29. The computer readable medium of claim 25, wherein the first route of a net that has all its pins in one of the first-set sub-regions is specified by a null set of edges.

25. A computer readable medium comprising a computer program having executable code, the computer program for routing a set of nets within a region of an integrated circuit (“

IC”

) layout, wherein each net includes a set of pins in the region, the computer program comprising;

a first set of instructions for partitioning the IC region into a first set of sub-regions, wherein a first set of inter-region edges exist between the first set of sub-regions, wherein some of the first set of inter-region edges are diagonal;

a second set of instructions for identifying, for each particular net, a first route that connects a group of the first set of sub-regions containing the particular net'"'"'s pins, wherein each particular first route is defined in terms of the inter-region edges from the first-edge set that the particular first route intersects, wherein at least one of the first routes intersects at least one of the diagonal edges of the first-edge set;

a third set of instructions for partitioning the first set of sub-regions into a second set of sub-regions, wherein a second set of inter-region edges exist between the second set of sub-regions, wherein some of the second set inter-region edges are diagonal;

a fourth set of instructions for identifying, for each particular net, a second route that connects a group of the second-set sub-regions containing the pins of the particular net, wherein at least one of the second routes intersects at least one of the diagonal inter-region edges.