# US 2002/0100009 A1 · Piecewise linear cost propagation for path searching

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2002/0100009 A1
- Document ID: US20020100009A1
- Status: Published application
- Kind: A1
- Application number: 09/998,558
- Filed: 2001-11-30
- Published: 2002-07-25
- Earliest claimed: 2000-12-01
- Assignees: Sun Microsystem, Inc.
- Inventors: Zhaoyun Xing; Russell Kao
- Web page: https://patentgrep.com/patent/US20020100009A1

## CPC

- G06F 30/394: Routing (G06F30/396 takes precedence)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 5)

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.

### Claim 7 (depends on 6)

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

### Claim 8 (depends on 6)

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.

### Claim 9 (depends on 8)

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.

### Claim 10 (depends on 6)

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.

### Claim 11 (depends on 10)

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

### Claim 12 (depends on 1)

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.

### Claim 13 (depends on 12)

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

### Claim 14 (depends on 12)

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.

### Claim 15 (depends on 12)

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.

### Claim 16 (depends on 12)

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.

### Claim 17 (depends on 1)

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

### Claim 18 (depends on 1)

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

### Claim 19 (depends on 18)

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

### Claim 20 (depends on 1)

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.

### Claim 20 (depends on 34)

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.

### Claim 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.

### Claim 22 (depends on 21)

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

### Claim 23 (depends on 21)

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

### Claim 24 (depends on 21)

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.

### Claim 25 (depends on 21)

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.

### Claim 26 (depends on 21)

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.

### Claim 27 (depends on 21)

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.

### Claim 28 (depends on 27)

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

### Claim 29 (depends on 28)

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.

### Claim 30 (depends on 27)

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.

### Claim 31 (depends on 30)

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.

### Claim 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.

### Claim 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.

### Claim 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.

### Claim 35 (depends on 34)

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.

### Claim 36 (depends on 34)

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

### Claim 38 (depends on 34)

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.

### Claim 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.

### Claim 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.

### Claim 41 (depends on 40)

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.

### Claim 42 (depends on 41)

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.
