LP method and apparatus for identifying route propagations

• US 20030043827A1
• Filed: 01/05/2002
• Published: 03/06/2003
• Est. Priority Date: 01/19/2001
• Status: Active Grant

• Current Assignee: Cadence Design Solutions, Inc.
• Original Assignee: Cadence Design Solutions, Inc.
• Inventors: Teig, Steven, Buset, Oscar
• Granted Patent: US 6,883,154 B2
• Time in Patent Office: Days
• US Class Current: 370/408
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• CPC Class Codes: G06F 30/3953 detailed
• CPC Class Codes: G11B 7/08582 Sled-type positioners

Abstract

The invention is directed towards routing method and apparatus. Some embodiments provide a routing method that uses diagonal routes. This method routes several nets within a region of a circuit layout. Each net includes a set of pins in the region. The method initially partitions the region into several sub-regions. For each particular net in the region, the method then identifies a route that connects the sub-regions that contains a pin from the set of pins of the particular net. Some of the identified routes have edges that are at least partially diagonal.

Claims

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

IC”

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

a) partitioning the particular IC region into a plurality of sub-regions, wherein the sub-regions have the same shape; and

b) identifying a route that connects a set of sub-regions containing the pins of the net, wherein the route has a route edge that is at least partially diagonal.

2. The method of claim 1, wherein identifying the route includes identifying the set of sub-regions that contains the pins of the net.

3. The method of claim 2, wherein identifying the route further includes using the identified set of sub-regions to retrieve the route from a storage structure.

4. The method of claim 1, wherein all the sub-regions have the same size.

5. The method of claim 1, wherein each sub-region is a four-sided sub-region.

6. The method of claim 1, wherein a plurality of paths exist between the sub-regions, wherein a plurality of the paths are diagonal paths, wherein the route traverses at least one of the diagonal paths.

7. The method of claim 6 wherein identifying the route comprises identifying the paths between the sub-regions used by the route.

8. The method of claim 7, wherein a plurality of the paths are Manhattan paths, wherein the route traverses at least one of the Manhattan paths.

9. The method of claim 1, wherein a plurality of inter-region edges exist between the sub-regions, wherein a plurality of the inter-region edges between the sub-regions are diagonal inter-region edges, wherein the route intersects at least one of the diagonal inter-region edges.

10. The method of claim 9, wherein identifying the route comprises identifying the inter-region edges between the sub-regions intersected by the route.

11. The method of claim 10, wherein a plurality of the inter-region edges between the sub-regions are Manhattan inter-region edges, wherein the route intersects at least one of the Manhattan inter-region edges.

12. The method of claim 1 further comprising:

a) computing a cost for the route;

b) determining whether to embed the route based on the computed cost.

13. The method of claim 1, wherein the IC region is the layout of the entire IC.

14. The routing method of claim 1, wherein the IC region is a portion of the layout of the entire IC.

15. A method of 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 method comprising;

partitioning the IC region into several sub-regions;

for each particular net in the region,

identifying each sub-region that contains a pin from the set of pins of the particular net, and

identifying a route that connects the identified sub-regions for the particular net;

wherein some of the identified routes have route edges that are at least partially diagonal.

16. The method of claim 15,

wherein a plurality of paths exist between the sub-regions, and a plurality of the paths are diagonal paths,

wherein identifying the route for each particular net comprises identifying the paths used by a set of interconnect lines connecting the sub-regions identified for the particular net,

wherein some of the interconnect lines traverse some of the diagonal paths.

17. The method of claim 16, wherein a plurality of the paths are Manhattan paths, wherein some of the interconnect lines traverse some of the Manhattan paths.

18. The method of claim 16 further comprising embedding each route by storing the identity of the paths used by each route.

19. The method of claim 15,

wherein a plurality of inter-region edges exist between the sub-regions, and a plurality of the inter-region edges are diagonal,

wherein identifying the route for each particular net comprises identifying the inter-region edges intersected by a set of interconnect lines connecting the sub-regions identified for the particular net,

wherein some of the interconnect lines intersect some of the diagonal inter-region edges.

20. The method of claim 19, wherein a plurality of the inter-region edges are Manhattan edges, wherein some of the interconnect lines intersect some of the Manhattan inter-region edges.

21. The method of claim 19 further comprising embedding each route by storing the identity of the inter-region edge intersected by each route.

22. The method of claim 15 further comprising:

for each particular net in the region, identifying a set of route that connects the identified sub-regions for the particular net;

computing costs for the identified routes;

selecting one identified route for each net based on the computed costs;

embedding the selected route for each net in the region.

23. A computer readable medium comprising a computer program having executable code, the computer program for routing a net within a particular region of an integrated circuit (“

IC”

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

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

b) a second set of instructions for identifying a route that connects a set of sub-regions containing the pins of the net, wherein the route has a route edge that is at least partially diagonal.

24. The computer readable medium of claim 23,

wherein a plurality of paths exist between the sub-regions, and a plurality of the paths are diagonal,

wherein the second set of instructions includes a third set of instructions for identifying the paths between the sub-regions used by the route;

wherein the route traverses at least one of the diagonal paths.

25. The computer readable medium of claim 23,

wherein a plurality of inter-region edges exist between the sub-regions, and a plurality of the inter-region edges are diagonal,

wherein the second set of instructions includes a third set of instructions for identifying the inter-region edges between the sub-regions intersected by the route;

wherein the route traverses at least one of the diagonal inter-region edges.

26. The computer readable medium of claim 23 further comprising:

a) a third set of instructions for computing a cost for the route;

b) a fourth set of instructions for determining whether to embed the route based on the computed cost.