Method and apparatus for identifying a group of routes for a set of nets

• US 20040098693A1
• 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, Frankle, Jonathan
• Granted Patent: US 7,093,221 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 identifying a group of routes for a set of nets. The group of routes includes one route for each net in the set of nets. The method identifies a set of routes for each net. It then iteratively selects one identified route for each net. During each iteration, the method selects the identified route that least increases a tracking cost that accounts for each of the previously selected routes.

Claims

1. A method of identifying a group of routes for a set of nets, wherein the group of routes includes one route for each net in the set of nets, the method comprising:

a) identifying a set of routes for each net;

b) iteratively selecting one identified route for each net,

c) during each iteration, selecting the identified route that least increases a tracking cost that accounts for each of the previously selected routes.

2. The method of claim 1, wherein the cost is an exponential tracking cost.

3. The method of claim 2, wherein the method identifies routes within a region of an integrated circuit (“

IC”

) layout, wherein the exponential tracking cost includes a congestion component that exponentially accounts for congestion caused by the selected routes within the IC-layout region.

4. The method of claim 3, wherein the exponential tracking cost includes a length component that exponentially accounts for length of selected routes.

5. The method of claim 2, wherein the exponential tracking cost includes a length component that exponentially accounts for length of selected routes.

6. The method of claim 1, wherein the method identifies routes within a region of an integrated circuit (“

IC”

) layout, wherein the tracking cost includes a congestion component that accounts for congestion caused by the selected routes within the IC-layout region.

7. The method of claim 6, wherein the tracking cost includes a length component that accounts for length of selected routes.

8. The method of claim 1, wherein the cost is a tracking cost that includes a length component that accounts for length of selected routes.

9. The method of claim 1, wherein each route of each particular net has an associated frequency parameter that is based on a frequency of occurrence of the route in the set for the particular net, the method further comprising sorting the nets based on the associated frequency parameters.

10. The method of claim 9, wherein sorting the nets comprises sorting the nets based on the maximum values of the frequency parameters.

11. A computer readable medium that stores a computer program for identifying a group of routes for a set of nets, wherein the group of routes includes one route for each net in the set of nets, the computer program comprising sets of instructions:

a) identifying a set of routes for each net;

b) iteratively selecting one identified route for each net,

c) during each iteration, selecting the identified route that least increases a tracking cost that accounts for each of the previously selected routes.

12. The computer readable medium of claim 11, wherein the cost is an exponential tracking cost.

13. The computer readable medium of claim 12, wherein the computer program identifies routes within a region of an integrated circuit (“

IC”

) layout, wherein the exponential tracking cost includes a congestion component that exponentially accounts for congestion caused by the selected routes within the IC-layout region.

14. The computer readable medium of claim 13, wherein the exponential tracking cost includes a length component that exponentially accounts for length of selected routes.

15. The computer readable medium of claim 12, wherein the exponential tracking cost includes a length component that exponentially accounts for length of selected routes.

16. The computer readable medium of claim 11, wherein the computer program identifies routes within a region of an integrated circuit (“

IC”

) layout, wherein the tracking cost includes a congestion component that accounts for congestion caused by the selected routes within the IC-layout region.

17. The computer readable medium of claim 16, wherein the tracking cost includes a length component that accounts for length of selected routes.

18. The computer readable medium of claim 11, wherein the cost is a tracking cost that includes a length component that accounts for length of selected routes.

19. The computer readable medium of claim 11, wherein each route of each particular net has an associated frequency parameter that is based on a frequency of occurrence of the route in the set for the particular net, the computer program further comprising a set of instructions for sorting the nets based on the associated frequency parameters.

20. The computer readable medium of claim 19, wherein the set of instructions for sorting the nets comprises a set of instructions for sorting the nets based on the maximum values of the frequency parameters.