Method and apparatus for costing routes of nets

• US 20040098692A1
• 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 6,892,369 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 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, the method comprising:

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

b) identifying an estimated route length for each net;

c) computing a cost 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 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 cost comprising summing the exponential expressions.

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

a) identifying a set of routes for each net;

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

8. The method of claim 7 further comprising:

a) examining different combination of routes of the nets;

b) for each combination of routes, computing a cost 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.

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

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

11. A computer readable medium that stores a computer program for costing routes for a set of nets, the computer program comprising sets of instructions for:

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

b) identifying an estimated route length for each net;

c) computing a cost 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 divided by the estimated route length for the net.

12. The computer readable medium of claim 11, 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.

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

14. 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.

15. 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.

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

17. 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;

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

18. 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;

b) for each combination of routes, computing a cost 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.

19. 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 cost.

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