Method and apparatus for routing a set of nets

• US 7,107,564 B1
• Filed: 01/31/2002
• Issued: 09/12/2006
• Est. Priority Date: 06/03/2001
• Status: Expired due to Fees

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Caldwell, Andrew
• Primary Examiner(s): Kik, Phallaka
• Application Number:
  US10/066,060
• Time in Patent Office: 1,685 Days
• Field of Search: 716/13, 716/14, 716/9, 716/10, 716/4
• US Class Current: 716/129
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

One embodiment of the invention is a method of specifying routes for a group of nets. The method identifies different routing solutions for the group of nets. It then selects the best routing solution.

Claims

1. A method for specifying a topological routing solution for a group of nets, said routing solution being one route for each net, comprising:

a) initially identifying a set of initial routing solutions for each net in the group of nets, wherein each of a plurality of the initial set of routing solutions has a plurality of topological routes, wherein each topological route is a route that represents a set of geometric routes that are morphable into one another; and

b) specifying a best topological routing solution from said initially identified sets of topological routing solutions for the nets, wherein the best routing solution has one route for each net in the group of nets.

2. The method of claim 1, wherein all of the identified routing solutions includes a route for each of the nets in the group of nets.

3. The method of claim 1, wherein at least one of the identified routing solutions includes a route for each of the nets in the group of nets.

4. The method of claim 1, wherein some of the routing solutions include a route for some but not all of the nets in the group.

5. The method of claim 4, wherein at least one routing solution includes a route for all nets in the group.

6. The method of claim 1, wherein specifying the best topological routing solution comprises:

a) for each routing solution, computing a metric cost that quantifies quality of the routing solution;

b) selecting the routing solution that has a metric cost that is a best computed metric cost.

7. The method of claim 6, wherein each routing solution includes a route for each net in a set of nets of the group of nets, wherein computing the metric cost for each particular routing solution comprises:

a) computing the metric cost for each route in the particular routing solution; and

b) computing the metric cost for the particular routing solution from the metric cost of each route in the particular routing solution.

8. The method of claim 7, wherein the metric cost includes a length of the route.

9. The method of claim 7, wherein the metric cost of each route includes a length of the route.

10. The method of claim 6 further comprising:

a) specifying a metric-cost threshold before identifying the routing solutions;

b) wherein selecting the routing solution with the best metric cost includes selecting the routing solution that has a metric cost better than other computed metric costs and better than the metric-cost threshold.

11. The method of claim 1, wherein specifying the best topological routing solution comprises selecting the best routing solution that is identified by examining a particular maximum number of routes.

12. A method for specifying a topological routing solution for a group of nets, said routing solution being one route for each net, comprising:

a) initially identifying a set of initial routing solutions for each net in the group of nets, wherein each of a plurality of the initial set of routing solutions has a plurality of topological routes, wherein each topological route is a route that represents a set of geometric routes that are morphable into one another; and

b) specifying a best topological routing solution from said initially identified sets of routing solutions for the nets, wherein the best topological routing solution has one route for each net in the group of nets;

wherein when none of the routing solutions has a metric cost better than a metric-cost threshold, the method further comprising;

a) incrementing the metric-cost threshold;

b) identifying a plurality of routing solutions for the nets in the group of nets;

c) computing the metric cost for each routing solution; and

d) selecting the routing solution that has the metric cost better than other computed metric costs and better than the metric-cost threshold.

13. The method of claim 12 wherein the best metric cost is an optimal metric cost of an optimal routing solution or is a metric cost within a predetermined percentage of the optimal metric cost of the optimal routing solution.

14. A computer program embedded on a computer readable medium, the computer program for specifying a topological routing solution for a group of nets, said routing solution being one route for each net, the computer program comprising sets of instructions for:

a) initially identifying a set of initial routing solutions for each net in the group of nets, wherein each of a plurality of the initial set of routing solutions has a plurality of topological routes, wherein each topological route is a route that represents a set of geometric routes that are morphable into one another; and

b) specifying a best topological routing solution from said initially identified sets of topological routing solutions for the nets, wherein the best routing solution has one route for each net in the group of nets.

15. The computer program of claim 14, wherein all of the identified routing solutions include a route for each of the nets in the group of nets.

16. The computer program of claim 14, wherein at least one of the identified routing solutions includes a route for each of the nets in the group of nets.

17. The computer program of claim 14, wherein some of the routing solutions include a route for some but not all of the nets in the group.

18. The computer program of claim 17, wherein at least one routing solution includes a route for all nets in the group.

19. The computer program of claim 14, wherein said set of instructions for specifying the best topological routing solution comprises sets of instructions for:

a) computing, for each routing solution, a metric cost that quantifies quality of the routing solution; and

b) selecting the routing solution that has a best metric cost.

20. The computer program of claim 19, wherein said set of instructions for computing, for each routing solution, the metric cost that quantifies the quality of the routing solution comprises sets of instructions for:

a) computing a metric cost for each route in each routing solution; and

b) computing the metric cost for each routing solution from the metric cost of each route in the routing solution;

wherein each routing solution includes a route for each net in a set of nets of the group of nets.

21. The computer program of claim 20, wherein the metric cost includes a length of the route.

22. The computer program of claim 20, wherein the metric cost of each route includes a length of the route.