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

• US 7,093,221 B2
• Filed: 12/31/2002
• Issued: 08/15/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, Frankle, Jonathan
• Primary Examiner(s): Siek, Vuthe
• Assistant Examiner(s): Dimyan, Magid Y.
• Application Number:
  US10/335,087
• Publication Number:
  US 20040098693A1
• Time in Patent Office: 1,323 Days
• Field of Search: 716/4, 716 12- 15
• 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 global routes for a set of nets in an integrated circuit (“

IC”

) layout, wherein the group of global routes includes one global route for each net in the set of nets, the method comprising;

a) identifying a plurality of global routes for each net in the IC layout;

b) iteratively selecting one global route from the identified plurality of global routes for each net, wherein selecting one global route during each iteration comprises selecting one global route from the identified plurality of global routes that least increases a metric score that tracks a cost for each of the previously selected global routes; and

c) specifying the group of global routes for the set of nets based on the iteratively selected global route for each net.

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

3. The method of claim 2, wherein the method identifies global 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 global 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 global routes.

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

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

IC”

) layout, wherein the metric score includes a congestion component that accounts for congestion caused by the selected global routes within the IC-layout.

7. The method of claim 6, wherein the metric score includes a length component that accounts for length of selected global routes.

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

9. The method of claim 1, wherein each global route of each particular net has an associated frequency parameter that is based on a frequency of occurrence of the global 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 computer program for identifying a group of global routes for a set of nets in an integrated circuit (“

IC”

) layout, wherein the group of global routes includes one global route for each net in the set of nets, the computer program comprising sets of instructions for;

a) identifying a plurality of global routes for each net in the IC layout;

b) iteratively selecting one global route from the identified plurality of global routes for each net, wherein selecting one global route during each iteration comprises selecting one global route from the identified plurality of global routes that least increases a metric score that tracks a cost for each of the previously selected global routes; and

c) specifying the group of global routes for the set of nets based on the iteratively selected global route for each net.

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

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

IC”

) layout, wherein the exponential tacking cost includes a congestion component that exponentially accounts for congestion caused by the selected global 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 global 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 global routes.

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

IC”

) layout, wherein the metric score includes a congestion component that accounts for congestion caused by the selected global routes within the IC-layout.

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

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

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

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