Method and apparatus for costing routes of nets

• US 6,892,369 B2
• Filed: 12/31/2002
• Issued: 05/10/2005
• 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
• Primary Examiner(s): Siek, Vuthe
• Application Number:
  US10/335,086
• Publication Number:
  US 20040098692A1
• Time in Patent Office: 861 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 costing routes for a set of nets. The method identifies at least one route for each net, where each route has a particular length. It also identifies an estimated route length for each net. It then computes a cost that includes an exponential expression for each net. Each net'"'"'s exponential expression includes a base and an exponent. The exponent of each net'"'"'s exponential expression includes the length of the net'"'"'s route divided by the estimated route length for the net.

Claims

1. A method of costing routes for a set of nets in an integrated circuit (“

IC”

) layout, the method comprising;

a) identifying at least one route for each net in the IC layout, wherein each route has a particular length;

b) identifying an estimated route length for each net; and

c) computing a routing cost of the IC layout that includes an exponential expression for each net, wherein each net'"'"'s exponential expression includes a base and an exponent, wherein the exponent of net'"'"'s exponential expression includes the length of the net'"'"'s route divided by the estimated route length for the net.

2. The method of claim 1, wherein the exponent of each net'"'"'s exponential expression further includes an importance factor that adjusts the result of the division of the net'"'"'s route length by the net'"'"'s estimated route length to reflect the importance of the net.

3. The method of claim 2, wherein at least two nets have different importance factors.

4. The method of claim 2, wherein the importance factor of a net is multiplied by the estimated route length of the net in the exponent of the net'"'"'s exponential expression.

5. The method of claim 2, wherein the importance factor of a net is multiplied by the length of the net'"'"'s route in the exponent of the net'"'"'s exponential expression.

6.The method of claim 1, wherein computing the routing cost comprises summing the exponential expressions.

6. The method of claim 1, wherein identifying at least one route for each net comprises:

a) identifying a set of routes for each net; and

b) selecting one route for each net from the identified set of routes for the net.

9. The method of claim 1, wherein the nets are nets within a region of the integrated circuit layout.

7. The method of claim 7 further comprising;

a) examining different combination of routes of the nets; and

b) for each combination of routes, computing a routing cost of the IC layout that includes an exponential expression for each net, wherein each net'"'"'s exponential expression includes a base and an exponent, wherein the exponent of each net'"'"'s exponential expression includes the length of the net'"'"'s route in the combination divided by the estimated route length for the net.

8. The method of claim 8 further comprising selecting the combination of routes that results in the lowest computed routing cost of the IC layout.

10. A computer readable medium that stores a computer program for costing routes for a set of nets in an integrated circuit (“

IC”

) layout, the computer program comprising sets of instructions for;

a) identifying at least one route for each net in the IC layout, wherein each route has a particular length;

b) identifying an estimated route length for each net; and

c) computing a routing cost of the IC layout that includes an exponential expression for each net, wherein each net'"'"'s exponential expression includes a base and an exponent, wherein the exponent of net'"'"'s exponential expression includes the length of the net'"'"'s route divided by the estimated route length for the net.

11. The computer readable medium of claim 11, wherein the exponent or each net'"'"'s exponential expression further includes an importance factor that adjusts the results of the division of the net'"'"'s route length by the net'"'"'s estimated route length to reflect the importance of the net.

15. The computer readable medium claim 11, wherein the set for computing the routing cost comprises a set of instructions for summing the exponential expressions.

16. The computer readable medium of claim 11, wherein the set of instructions for identifying at least one route for each net comprises sets of instructions for:

a) identifying a set of routes for each net; and

b) selecting one route for each net from the identified set of routes for the net.

19. The computer readable medium of claim 11, wherein the nets are nets within a region of the integrated circuit layout.

12. The computer readable medium of claim 12, wherein at least two nets have different importance factors.

13. The computer readable medium of claim 12, wherein the importance factor of a net is multiplied by the estimated route length of the net in the exponent of the net'"'"'s exponential expression.

14. The computer readable medium of claim 12, wherein the importance factor of a net is multiplied by the length of the net'"'"'s route in the exponent of the net'"'"'s exponential expression.

17. The computer readable medium of claim 17, wherein the computer program further comprises sets of instructions for;

a) examining different combination of routes of the nets; and

b) for each combination of routes, computing a routing cost of the IC layout that includes an exponential expression for each net, wherein each net'"'"'s exponential expression includes a base and an exponent, wherein the exponent of each net'"'"'s exponential expression includes the length of the net'"'"'s route in the combination divided by the estimated route length for the net.

18. The computer readable medium of claim 18, wherein the computer program further comprises a set of instructions for selecting the combination of routes that results in the lowest computed routine cost of the IC layout.