Method and apparatus for routing sets of nets

• US 6,886,149 B1
• Filed: 10/31/2002
• Issued: 04/26/2005
• Est. Priority Date: 01/22/2002
• Status: Active Grant

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Caldwell, Andrew
• Primary Examiner(s): Siek, Vuthe
• Application Number:
  US10/286,584
• Time in Patent Office: 908 Days
• Field of Search: 716 12- 15
• US Class Current: 716/129
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18

Abstract

Some embodiments of the invention provide a method of routing a set of nets. The method specifies a first order for the set of nets. It then routes the nets according to the specified first order. The method then specifies a second order for the set of nets, where the second order has the fewest possible number of differences with the first order. The method then routes the nets according to the specified second order.

Claims

1. A method of routing a set of nets, the method comprising:

a) specifying a first order for the set of nets, wherein an order is a specific sequence of nets to be routed in succession of each other, wherein each net has a position in the specific sequence of nets;

b) routing the nets according to the specified first order;

c) using a least-discrepancy search (“

LDS”

) to specifying a second order for the set of nets, wherein the LDS-specified second order has the fewest possible number of differences with the first order, wherein a difference is calculated for every net whose position in the second order differs from said net'"'"'s position in the first order; and

d) routing the nets according to the specified second order.

2. The method of claim 1 further comprising:

a) using the least-discrepancy search to specify a third order for the set of nets, wherein the third order has the next fewest possible number of differences with the first order; and

b) routing the nets according to the specified third order.

3. The method of claim 2 further comprising, after routing the nets according to the second order but before routing the nets according to the third specified order, identifying a set of orders for the set of nets, wherein each order in the identified set of orders has the same number of differences with the first order as the second order.

4. The method of claim 3 further comprising:

routing the nets according to each of the orders in the identified set of orders.

5. The method of claim 4, wherein identifying the set of orders comprises iteratively identifying each order in the set and routing the nets at each particular iteration according to the order for the particular iteration.

6. The method of claim 5, wherein the routing the nets according to at least some of the orders results in a complete routing solution that includes a route for each net, the method further comprising:

after at least each particular routing that results in a complete solution, determining whether the particular routing solution is better than any of the prior complete routing solutions examined, and if so, storing the particular routing solution.

7. The method of claim 6, wherein the set of orders is a first set of orders, the method further comprising:

identifying a second set of orders for the set of nets, wherein each order in the identified second set of orders has the same number of differences with the first order as the third order; and

routing the nets according to each of the orders in the identified second set of orders.

8. The method of claim 7 further comprising:

identifying a third set of orders for the set of nets, wherein each order in the identified second set of orders has one more difference with the first order than the number of differences between the first and third orders; and

routing the nets according to each of the orders in the identified third set of orders.

9. The method of claim 8 further comprising:

iteratively identifying additional sets of orders for the set of nets, wherein at each iteration the number of differences between the orders in the set and the first order is more than the number of differences between the orders in the set from the previous iteration and the first order;

at each iteration, identifying a routing solution for at least one order in the iteration; and

terminating the iterative identification of additional order sets once the number of differences between the orders in the next iteration and the first order reaches a certain value.

10. The method of claim 9 further comprising:

iteratively identifying additional sets of orders for the set of nets, wherein at each iteration the number of differences between the orders in the set and the first order is more than the number of differences between the orders in the set from the previous iteration and the first order;

at each iteration, identifying a routing solution for at least one order in the iteration; and

terminating the iterative identification of additional order sets once the number of differences between the orders in the last iteration and the first order reaches a certain value.

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

a) specifying a first order for the set of nets, wherein an order is a specific sequence of nets to be routed in succession of each other, wherein each net has a position in the specific sequence of nets;

b) routing the nets according to the specified first order;

c) using a least-discrepancy search (“

LDS”

) to specifying a second order for the set of nets, wherein the LDS-specified second order has the fewest possible number of differences with the first order, wherein a difference is calculated for every net whose position in the second order differs from said net'"'"'s position in the first order; and

d) routing the nets according to the specified second order.

12. The computer readable medium of claim 11, wherein the computer program further comprises sets of instructions for:

a) using the least-discrepancy search to specify a third order for the set of nets, wherein the third order has the next fewest possible number of differences with the first order; and

b) routing the nets according to the specified third order.

13. The computer readable medium of claim 12, wherein the computer program further comprises instructions for identifying, after routing the nets according to the second order but before routing the nets according to the third specified order, a set of orders for the set of nets, wherein each order in the identified set of orders has the same number of differences with the first order as the second order.

14. The computer readable medium of claim 13, wherein the computer program further comprises a set of instructions for routing the nets according to each of the orders in the identified set of orders.

15. The computer readable medium of claim 14, wherein the set of instructions for identifying the set of orders comprises a set of instructions for iteratively identifying each order in the set and routing the nets at each particular iteration according to the order for the particular iteration.

16. The computer readable medium of claim 15, wherein the routing of the nets according to at least some of the orders results in a complete routing solution that includes a route for each net, the computer program further comprises instructions for determining, after at least each particular routing that result in a complete solution, whether the particular routing solution is better than any of the prior complete routing solutions examined, and if so, storing the particular routing solution.

17. The computer readable medium of claim 16, wherein the set of orders is a first set of orders, the computer program further comprising sets of instructions for:

identifying a second set of orders for the set of nets, wherein each order in the identified second set of orders has the same number of differences with the first order as the third order; and

routing the nets according to each of the orders in the identified second set of orders.

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

identifying a third set of orders for the set of nets, wherein each order in the identified second set of orders has one more difference with the first order than the number of differences between the first and third orders; and

routing the nets according to each of the orders in the identified third set of orders.

19. The computer readable medium of claim 18, wherein the computer program further comprises sets of instructions for:

iteratively identifying additional sets of orders for the set of nets, wherein at each iteration the number of differences between the orders in the set and the first order is more than the number of differences between the orders in the set from the previous iteration and the first order;

at each iteration, identifying a routing solution for at least one order in the iteration; and

terminating the iterative identification of additional order sets once the number of differences between the orders in the next iteration and the first order reaches a certain value.

20. The computer readable medium of claim 18, wherein the computer program further comprises sets of instructions for:

iteratively identifying additional sets of orders for the set of nets, wherein at each iteration the number of differences between the orders in the set and the first order is more than the number of differences between the orders in the set from the previous iteration and the first order;

at each iteration, identifying a routing solution for at least one order in the iteration; and

terminating the iterative identification of additional order sets once the number of differences between the orders in the last iteration and the first order reaches a certain value.