Method and apparatus for routing groups of paths

• US 7,069,530 B1
• Filed: 01/31/2002
• Issued: 06/27/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): Siek, Vuthe
• Assistant Examiner(s): Bowers, Brandon
• Application Number:
  US10/066,095
• Time in Patent Office: 1,608 Days
• Field of Search: 716 12- 14, 716/8, 716/10
• 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 identifying a set of paths between a set of source routable elements of a net and a set of target routable elements of the net. The set of paths has to have a minimum acceptable number of paths. The method specifies a first total cost. It then performs a first depth-first search to identify the set of paths, where each path has a cost that does not exceed the first total cost, and each path includes a set of expansions from the set of routable-element sources to the set of routable-element targets. If the search cannot find the acceptable number of paths, it increments the total cost and performs a second depth-first search to identify the set of paths, where each path has a cost that does not exceed the incremented total cost.

Claims

1. A method of routing a net by identifying a set of paths between a set of source routable elements of a net and a set of target routable elements of the net, wherein the set of paths has to have a minimum acceptable number of paths, the method comprising:

a) identifying a set of an acceptable number of at least two paths between the set of source routable elements and the set of target routable elements, said identifying comprising;

1) specifying a first total cost;

2) performing a first depth-first search to identify the set of at least two paths that each have a cost that does not exceed the first total cost, wherein each path in the set includes a set of expansions from the set of routable-element sources to the set of routable-element targets;

3) if the search cannot find the acceptable number of paths, incrementing the total cost and performing a second depth-first search to identify the set of paths that each have a cost that does not exceed the incremented total cost, wherein the acceptable number of paths is at least two paths; and

b) when the acceptable number of paths is identified, using one of the paths to define a route for the net.

2. The method of claim 1, wherein the set of source routable elements includes one routable element.

3. The method of claim 1, wherein the set of source routable elements includes more than one routable element.

4. The method of claim 1, wherein the set of source routable elements include the routed routable elements.

5. The method of claim 1, wherein the set of source routable elements further include elements on the routes between the routed routable elements.

6. The method of claim 1, wherein the set of target routable elements includes one routable element.

7. The method of claim 1, wherein the set of target routable elements includes more than one routable element.

8. The method of claim 1, wherein the set of target routable elements include the routed routable elements.

9. The method of claim 1, wherein the set of target routable elements further include elements on the routes between the routed routable elements.

10. The method of claim 1, wherein the first total cost equals the distance between the set of source and target elements according to a particular interconnect-line model.

11. The method of claim 1, wherein the routable elements are pins of the nets.

12. The method of claim 1, wherein the routable elements are ports of the nets.

13. The method of claim 1, wherein the method is used by a topological router that defines a plurality of topological items for defining each path, the method further comprising:

defining each expansion to traverse from one topological item to another topological item.

14. The method of claim 1, wherein the depth-first search is an A* search.

15. The method of claim 1, wherein performing a first depth-first search comprises:

a) identifying a first set of path expansions from the source sel to the target set, wherein each path expansion has a cost;

b) individually examining the first-set expansions until the acceptable number of paths is identified or until all first-set expansions have been examined without identifying the acceptable number of paths;

c) wherein individually examining a particular first-set expansion includes determining whether a second set of expansions exists from the particular expansion to the target set such that the costs of the particular expansion and the second set of expansions do not exceed the first total cost.

16. The method of claim 15 further comprising:

when a second set of expansions exists for a particular first-set expansion, identifying the particular first-set expansion and the second set of expansions as a path between the source and target sets.

17. The method of claim 16, wherein determining whether a second set of expansions exists for a particular first-set expansion comprises:

a) selecting one of the second-set expansions, wherein the selected second-set expansion has a destination;

b) identifying a third set of path expansions from the destination of the selected second-set expansion to the target set;

c) individually examining the third-set expansions until the acceptable number of paths is identified or until all third-set expansions have been examined without identifying the acceptable number of paths;

d) wherein individually examining a particular third-set expansion includes determining whether a fourth set of expansions exists from the particular third-set expansion to the target set such that the costs of the particular first and third expansions and the fourth set of expansions do not exceed the first total cost.

18. The method of claim 17 further comprising:

when no fourth set of expansions exists for any third-set expansion, examining another first-set expansion.

19. The method of claim 1, wherein the first-set expansions are not examined in a particular order.

20. The method of claim 1, wherein the first-set expansions are examined in a particular order.