Method and apparatus for performing an exponential path search

• US 20040098691A1
• 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, Jacques, Etienne
• Granted Patent: US 6,996,789 B2
• Time in Patent Office: Days
• 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
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• CPC Class Codes: G06F 30/3947 global

Abstract

Some embodiments of the invention provide a method of searching for a path. The method identifies a set of source and target elements. It then performs a path search that iteratively identifying path expansions in order to identify a set of associated path expansions that connect the source and target elements. The method costs at least one expansion based on an exponential equation that has an exponent that includes a cost associated with the expansion.

Claims

1. A method of searching for a path, the method comprising:

a) identifying a set of source and target elements;

b) performing a path search that iteratively identifying path expansions in order to identify a set of associated path expansions that connect the source and target elements;

c) costing at least one expansion based on an exponential equation that has an exponent that includes a cost associated with the expansion.

2. The method of claim 1 further comprising costing each expansion based on an exponential equation that has an exponent that includes a cost associated with the expansion.

3. The method of claim 1, wherein the cost associated with the expansion is a length cost.

4. The method of claim 3, wherein the costed expansion extends a path to a particular destination, wherein the length cost is the length of the path after reaching the particular destination.

5. The method of claim 4, wherein, in the exponent, the length cost is divided by a target length cost of the path search.

6. The method of claim 5, wherein the exponent includes a multiplier that is multiplied by the length cost divided by the target length cost.

7. The method of claim 4, wherein costing the expansion further comprises costing the expansion based on an exponential equation that has an exponent that includes a congestion cost associated with the expansion.

8. The method of claim 1, wherein the cost associated with the expansion is a congestion cost.

9. The method of claim 8, wherein the costed expansion extends a path across a particular region, wherein the congestion cost is the congestion within the region if the path is extended by the expansion.

10. The method of claim 9, wherein, in the exponent, the congestion cost is divided by a capacity of the region.

11. The method of claim 10, wherein the exponent includes a multiplier that is multiplied by the congestion cost divided by the capacity.

12. The method of claim 8, wherein the method searches for a path in a space with multiple layers, wherein the costed expansion extends a path in a non-planar direction between two different layers in the space, wherein the congestion cost is the congestion of non-planar expansions between the two different layers if the path is extended by the expansion.

13. The method of claim 12, wherein the congestion cost is the congestion of non-planar expansions between the two different layers in a localized region about the expansion.

14. The method of claim 12, wherein, in the exponent, the congestion cost is divided by a capacity value.

15. The method of claim 14, wherein the exponent includes a multiplier that is multiplied by the congestion cost divided by the capacity value.

16. A method of searching for a path between first and second sets of states in a space with a plurality of states, the method comprising:

a) specifying an expansion of a path from a first state to a second state, wherein the path started from a third state in the first set;

b) identifying an estimated cost of a path that starts from the third state, traverses through the first and second states and reaches a fourth state in the second set;

c) computing a cost for the expansion based on an exponential equation that has an exponent that includes the estimated cost.

17. The method of claim 16, wherein the estimated cost is an {circumflex over (F)} cost of a best-first search.

18. The method of claim 17, wherein the estimated {circumflex over (F)} cost is a length cost.

19. The method of claim 16 further comprising:

identifying an estimated distance between at least one state and at least a second-set state;

dividing the estimated cost by the estimated distance in the exponent.

20. The method of claim 19, wherein the identified estimated distance is an estimated distance between a first-set state and the second-set states.

21. The method of claim 20 further comprising:

identifying an estimated distance between each first-set state and the second-set states;

identifying the smallest estimated distance;

wherein dividing the estimated cost by the estimated distance comprises dividing the estimated cost by the smallest estimated distance.

22. The method of claim 16,

wherein the exponential equation is a first exponential equation,

wherein computing the cost comprises multiplying the first exponential equation with a second exponential equation,

wherein the second exponential equation includes an exponent that includes the cost of a set of previously identified paths between different sets of states.

23. The method of claim 22 further comprising:

computing an estimated cost of the previously identified paths;

dividing the cost of the set of previously identified paths by the estimated cost of the previously identified paths in the exponent of the second exponential expression.

24. The method of claim 22, wherein the method is used by a router that identifies routes for nets, wherein the previously identified paths are routes previously identified by the router.

25. A method of routing a net in a design layout, the method comprising:

a) defining a first set of routes for a set of nets;

b) identifying a path that is a potential part of a route for a first net;

c) computing a cost for the path based on two components, wherein the first component is based on a cost associated with a second set of the defined routes, and the second component is an exponential expression that has an exponent that includes a cost associated with the path.

26. The method of claim 25, wherein the first component is an exponential expression that has an exponent that includes the cost associated with the second set of the defined routes.

27. The method of claim 26, wherein the first and second sets of routes are the same set of routes.

28. The method of claim 25, wherein the cost associated with the path is a length cost.

29. The method of claim 28, wherein the path is incomplete, wherein length cost is an estimated cost of the path once the path is complete.

30. The method of claim 29, wherein the path started from a particular location in the layout, the method further comprising:

identifying an estimated distance between the particular location and a destination of the path;

dividing the estimated cost by the estimated distance in the exponent.

31. The method of claim 30, wherein the layout has several locations for starting the path, wherein the method further comprises:

identifying an estimated distance between each location and a destination of the path;

identifying the smallest estimated distance;

wherein dividing the estimated cost by the estimated distance comprises dividing the estimated cost by the smallest estimated distance.

32. A method of searching for a path between first and second sets of states in a space with a plurality of states, the method comprising:

a) specifying an expansion of a path from a first state to a second state;

b) computing an increase, due to the expansion, in an exponential cost of the congestion in a region between the first and second state;

c) increasing a cost of the path by the computed increase in cost.

33. The method of claim 32, wherein the congestion is the congestion of planar paths in the region.

34. The method of claim 32, wherein the congestion is the congestion of non-planar paths in the region.

37. The method of claim 32, wherein the capacity for non-planar paths in the region.

35. A method of costing expansions identified in a path search between first and second sets of states in a space with a plurality of states, the method comprising:

a) specifying an expansion of a path from a first state to a second state, wherein the expansion is the first expansion to the second state in the path search, wherein the expansion is across a region between the first and second states;

b) assessing the expansion an exponential congestion cost that includes a base and an exponent, wherein the exponent includes a capacity of the region.

36. The method of claim 35, wherein the capacity is the capacity for planar paths in the region.