Piecewise linear cost propagation for path searching

• US 20020100009A1
• Filed: 11/30/2001
• Published: 07/25/2002
• Est. Priority Date: 12/01/2000
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Kao, Russell, Xing, Zhaoyun
• Granted Patent: US 6,665,852 B2
• Time in Patent Office: Days
• US Class Current: 716/12
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

The problem of searching for a low cost path from a source location to a target location through a traversable region partitioned into a plurality of tiles is solved using source and target cost functions. Each tile in the traversable region is defined by boundary segments. The source cost function provides a cost for traversing from the source location to the boundary segment in question. The target cost function provides a cost for traversing from the boundary segment in question to the target location. The target cost function is estimated, and the source cost function is calculated. A path cost function is determined by adding the source and target cost functions. If the target location is a tile, then the target cost may be estimated using a convex hull of the target tile and the boundary segment in question. To facilitate the cost function calculations, multiple forms of cost function propagation between segments are disclosed.

Claims

20-1. The product of claim 34,

wherein the at least one computer readable medium is selected from the set of a disk, tape or other magnetic, optical, or electronic storage medium and a network, wireline, wireless or other communications medium.

21. A method of propagating cost from entry segment of a tile to an exit segment of the tile, the method comprising:

determining the relative orientation of the entry and exit segments;

performing a first type of cost function propagation if the entry and exit boundary segments have a first relative orientation; and

performing a second type of cost function propagation if the entry and exit boundary segments have a second relative orientation.

22. The method of claim 21 wherein a propagation cost for the tile is not explicitly calculated.

23. The method of claim 21 wherein the first orientation is perpendicular and the second orientation is parallel.

24. The method of claim 21 wherein the first type of cost function propagation comprises finding a linear minimum convolution of the cost function of the exit boundary segment.

25. The method of claim 21 wherein the first type of cost function propagation comprises:

finding a linear minimum convolution of the cost function of the exit boundary segment using a first directional weight value; and

calculating the source cost of the exit boundary segment using the linear minimum convolution and a second directional weight value.

26. The method of claim 21 wherein the second type of cost function propagation comprises finding the minimum of a sum of expressions, the expressions including a function determined in part by a first directional weight, a function determined in part by a second directional weight and the cost function of the entry segment, wherein the minimum is found by evaluating the expressions at knot points and not by evaluating every value of the continuous expressions.

27. The method of claim 21 wherein the cost function is a source cost function for use in calculating a path from a source location to a target location through a traversable region including the tile.

28. The method of claim 27 wherein the path to be calculated is a lowest cost path from the source to the target.

29. A method as recited in claim 28 wherein the cost is based at least in part on distance and the lowest cost path is a shortest path.

30. A method as recited in claim 27 wherein the path includes a route from a first location of an integrated circuit to a second location of the integrated circuit.

31. A method as recited in claim 30 wherein the path is a conducting via between substantially equivalent potential terminals at such first and second locations.

32. A method of calculating a cost of a path from a source to a tile exit boundary segment, the path crossing a boundary of the tile at a tile entry boundary segment, the method comprising:

providing an entry source cost, the entry source cost providing a cost from the source to the entry boundary segment;

calculating an exit source cost, the exit source cost providing a cost from the source to the exit boundary segment, the exit source cost depending in part on the entry source cost, the exit source cost being calculated without explicitly determining a propagation cost across the tile from the entry boundary segment to the exit boundary segment.

33. A computer program product encoded in computer readable media for propagating cost from an entry segment of a tile to an exit segment of the tile, the product comprising:

first instructions, executable by an information processing system for determining the relative orientation of the entry and exit segments;

second instructions, executable by an information processing system for performing a first type of cost function propagation if the entry and exit boundary segments have a first relative orientation; and

third instructions, executable by an information processing system for performing a second type of cost function propagation if the entry and exit boundary segments have a second relative orientation.

1. A method of processing information for finding a low cost path from a source to a target through a traversable region partitioned into a plurality of tiles, each tile being defined by a plurality of boundary segments, the method comprising:

estimating a target cost function providing the cost to the target from an exit boundary segment of a tile;

calculating a source cost function from the source to the exit boundary segment; and

calculating a path cost function from the source cost and the target cost.

2. The method of claim 1 further comprising:

assigning an initial source cost function for the exit boundary segment of a tile before calculating the source cost function before estimating the target cost function;

determining the minimum of the initial source cost function and the calculated source cost function as the source cost function after calculating the source cost function;

determining a minimum of the path cost function after calculating the path cost function; and

prioritizing the exit boundary segment with other boundary segments based on the minimum of the path cost after determining a minimum of the path cost function.

3. The method of claim 1 wherein the target is referenced as a point location within a tile, and the estimating the target cost function comprises calculating a Manhattan distance from exit boundary segment points to the target location.

4. The method of claim 1 wherein target is a tile, and the estimating the target cost function comprises:

selecting a boundary segment of the target tile;

propagating a cost function from the exit boundary segment to the selected target boundary segment; and

repeating the selecting and the propagating until all boundary segments of the target tile have been selected.

5. The method of claim 1 wherein target is a tile, and the estimating the target cost function comprises:

finding a convex hull of the exit boundary segment and the target tile;

selecting a boundary segment of the target tile not on the convex hull;

propagating a cost function from the exit boundary segment to the selected target boundary segment; and

repeating the selecting and the propagating at least until all boundary segments of the target tile not on the convex hull have been selected.

6. The method of claim 5 wherein the propagating the cost function comprises:

determining the relative orientation of the exit and target boundary segments;

performing a first type of source cost function propagation if the exit and target boundary segments have a first relative orientation; and

performing a second type of source cost function propagation if the exit and target boundary segments have a second relative orientation.

7. The method of claim 6 wherein the first orientation is perpendicular and the second orientation is parallel.

8. The method of claim 6 wherein the first type of cost function propagation comprises finding a linear minimum convolution of the cost function of the exit boundary segment.

9. The method of claim 8 wherein the linear minimum convolution of the cost function of the exit boundary segment is found using a first directional weight value, and wherein the method further comprises calculating the source cost of the exit boundary segment using the linear minimum convolution and a second directional weight value.

10. The method of claim 6 wherein the second type of cost function propagation comprises finding the minimum of a sum of expressions, the expressions including a function determined in part by a first directional weight, a function determined in part by a second directional weight and the cost function of the entry segment.

11. The method of claim 10 wherein finding of the minimum of the sum includes evaluating the expressions only at knot points.

12. The method of claim 1 wherein the calculating the source cost function comprises:

determining the relative orientation of the entry and exit boundary segments;

performing a first type of source cost function propagation if the entry and exit boundary segments have a first relative orientation; and

performing a second type of source cost function propagation if the entry and exit boundary segments have a second relative orientation.

13. The method of claim 12 wherein the first orientation is perpendicular and the second orientation is parallel.

14. The method of claim 12 wherein the first type of cost function propagation comprises finding a linear minimum convolution of the cost function of the exit boundary segment.

15. The method of claim 12 wherein the first type of cost function propagation comprises:

finding the linear minimum convolution of the cost function of the exit boundary segment using a first directional weight value; and

calculating the source cost of the exit boundary segment using the found linear minimum convolution and a second directional weight value.

16. The method of claim 12 wherein the second type of cost function propagation comprises finding the minimum of a sum of expressions, the expressions including a function determined in part by a first directional weight, a function determined in part by a second directional weight and the cost function of the entry segment, wherein the minimum is found by evaluating the expressions only at knot points and not by evaluating every value of the continuous expressions.

17. The method of claim 1 wherein the calculating the path cost function comprises adding the target cost function and the source cost function.

18. The method of claim 1 wherein the cost is based at least in part on distance.

19. The method of claim 18 wherein the low cost path is a shortest path from the source to the target.

20. The method of claim 1 wherein the path includes a route from a first location of an integrated circuit to a second location of the integrated circuit.

35. The product of claim 34 comprising first computer program instructions for propagating a cost from a first boundary segment to a second boundary segment, wherein the first computer program instructions are called by the software module for estimating the target cost function and by the software module for calculating the source cost function.

36. The product of claim 34 wherein the product is for providing an ability to route an integrated circuit design to an information processing system.

38. The product of claim 34 wherein the at least one computer readable medium comprises at least one of a data storage medium and a data transmission medium, the data storage medium including at least one of the group consisting of a disk, tape, a compact disc and a digital video disc, and the data transmission medium including at least one of the group consisting of a wireline network and a wireless network.

34. A computer program product encoded in at least one computer readable medium for processing information for finding a low cost path from a source to a target through a traversable region partitioned into a plurality of tiles, each tile being defined by a plurality of boundary segments, the computer program product comprising:

a software module for estimating a target cost function providing the cost to the target from an exit boundary segment of a tile; and

a software module for calculating a source cost function from the exit boundary segment to the source; and

a software module for calculating a path cost function from the source cost and the target cost.

39. A method comprising the step of providing an information processing system in which a processor and a plurality of software modules are configured for processing information for finding a low cost path from a source to a target through a traversable region partitioned into a plurality of tiles, each tile being defined by a plurality of boundary segments, wherein the plurality of software modules include a first software module for estimating a target cost function providing the cost to the target from an exit boundary segment of a tile, a second software module for calculating a source cost function from the exit boundary segment to the source;

and a third software module for calculating a path cost function from the source cost and the target cost.

40. A method of estimating a least cost of a path from any point on a piecewise linear curve to a tile outlined by a plurality of boundary segments, the method comprising:

finding a convex hull of the piecewise linear curve and the boundary segments of the tile;

selecting a boundary segment of the tile not on the convex hull;

propagating a cost function from the piecewise linear curve to the selected boundary segment; and

repeating the selecting and the propagating at least until all boundary segments of the not on the convex hull have been selected.

41. The method of claim 40 wherein the piecewise linear curve is a segment, and the propagating the cost function comprises:

determining the relative orientation of the segment and the selected boundary segment;

performing a first type of source cost function propagation if the segment and selected boundary segment have a first relative orientation; and

performing a second type of source cost function propagation if the segment and selected boundary segment have a second relative orientation.

42. The method of claim 41 wherein the first type of cost function propagation comprises finding the linear minimum convolution of the cost function of the segment using a first directional weight value.