Piecewise linear cost propagation for path searching

Details Piecewise linear cost propagation for path searching Piecewise linear cost propagation for path searching

2001-11-30

2003-12-16

Siek, Vuthe (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000, C716S030000, C716S030000, C716S030000

Reexamination Certificate

active

06665852

ABSTRACT:

BACKGROUND
1. Field
The present invention relates to path search techniques and, more particularly, to systems and methods to aid routing around obstacles such as for integrated circuit (e.g., VLSI) routing.
2. Description of the Related Art
There are many important practical applications for path searching. The classic, student's example is the traveling salesman searching for an efficient path to visit a list of locations. Some search methods are useful to plan the movement of a robot across a room around obstacles such as furniture or the movement of a robot arm through space around obstacles. One practical and currently very important engineering application of path searching is found in the semiconductor and electronics arts. Path searching and routing techniques are typically employed for layout of conductive traces. Other practical applications are well known.
The classical path searching problem and current techniques can be understood in the context of searching for a shortest path from a source point or location to a target point or location through clear space of a routing region (two-dimensional or otherwise) around various obstacles in the routing region. More specifically, assume that inside a rectangular routing region there are several rectilinear obstacles. The space not occupied by the obstacles may be called clear space. For any given two points inside the clear space, the minimum cost path search problem is to find the path with the minimum cost (e.g., the shortest path or by some other measure) inside the clear space that connects them.
Computational efficiency of path search and routing techniques is important, particularly for complex routing problems such as those presented by modern semiconductor technology and applications such as VLSI routing. Existing approaches to solving this problem typically suffer from at least one, and sometimes all of the following disadvantages: (i) complexity, (ii) overlong computational time, (iii) failure to achieve an optimal path when multiple paths exist, (iv) failure to find a path when one exists. The semiconductor routing industry, for example, is constantly looking to improve techniques for solving this problem to mitigate or eliminate the above disadvantages.
SUMMARY
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 a discovered method of and system for 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. In embodiments described herein, 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.
It has been discovered that a cost function may be propagated across tiles or cells of a clear space decomposition. For example, in a two-dimensional realization, a cost function may be propagated from one edge of a tile or cell to another, even without explicitly calculating a value for a propagation cost across the tile. In a realization suitable for rectilinear tiles described herein, techniques are provided for propagation of a piecewise linear function from one edge of a tile to (1) a parallel-oriented edge or (2) a perpendicular-oriented edge. By propagating cost functions and searching for least cost paths based on the propagated costs, some realizations in accordance with the present invention provide efficient routing or path planning.
For example, in VLSI design, shortest path routing solutions attempt to connect two or more geometries with a shortest possible wire length. One way to solve this problem is to use tile expansion. Non-used tiles can be stored in a data structure suitable for tile operations such as searching, tile insertion, and tile deletion. For any given pair of source and target geometries, the routing is successful if there is a sequence of clear tiles connecting them. For any given tile, there may be several neighboring tiles and an efficient search technique is important. Our approach employs minimum cost function propagation and propagates the minimum cost function across tiles by hopping from one piece of shared tile boundary segment to another piece of shared tile boundary segment. Based on this propagation scheme, searching methods such as A* search can be used to find the target tile. After searching, a least cost path can be traced backwards from the passing segments.
It has been further discovered that some aspects of a cost function propagation technique can be implemented using an efficient algorithm for linear minimum convolution (LMC). While applications of the efficient algorithm are not limited to shortest path routing problems in VLSI, some realizations are particularly advantageous given the computational scale of such routing problems. As described in greater detail herein, an efficient routing algorithm may be implemented based on the discovered LMC implementations.
In general, the linear minimum convolution problem can be described as follows: assume f(x) is a piecewise linear function defined over the interval, [a, b]. At any given point (x,f(x)), a symmetric vertical cone is attached. The area covered by all cones is open at the top and the area's boundary is a piecewise linear function that is called linear minimum convolution.
A straightforward LMC implementation takes a number of steps that is quadratic in terms of number of knot points of the piecewise linear function. In contrast, the discovered techniques provide an implementation that takes a number of steps that is linear in the number of knot points. Accordingly, computational efficiency can be enhanced for realizations of the described cost function propagation technique or of realizations of path search and/or routing algorithms that employ the discovered linear minimum convolution implementation.
The foregoing is a summary and thus contains, by necessity, simplifications, generalizations and omissions of detail. Consequently, those skilled in the art will appreciate that the foregoing summary is illustrative only and that it is not intended to be in any way limiting of the invention. Other aspects, inventive features, and advantages of the present invention, as defined solely by the claims, may be apparent from the detailed description set forth below.


REFERENCES:
patent: 6324675 (2001-11-01), Dutta et al.
Arnold, M. H. and Scott, W. S., “An Interactive Maze Router with Hints,” 25th ACM/IEEE Design Automation Conference, 1988, Paper 41.4, pp. 672-676.
Tsai, Chia-Chun et al., “An H-V Alternating Router,” IEEE Transactions on Computer-Aided Design, vol. 11, No. 8, Aug. 1992, pp. 976-991.
Margarino, A. et al., “A Tile-Expansion Router,” IEEE Transactions on Computer-Aided Design, vol. CAD-6, No. 4, Jul. 1987, pp. 507-517.
Liu, Le-Chin E. et al., “Chip-Level Area Routing,” International Symposium on Physical Design, Proceedings of the 1998 International Symposium on Physical, Monterey, CA, 1998, ACM Press, NY, NY pp. 197-204.
Cong, Jason et al, “An Implicit Connection Graph Maze Routing Algorithm for ECO Routing,” ACM SIGDA proceedings 1999, Session 3B: Routing, 5 pp.; [online] Downloaded from the Internet May 14, 2002, URL: <http://www.sigda.org/Archives/ProceedingsArchives/Iccad99/pdffiles/03b 2.pdf>.
Dion, J. and Monier, L.M., “Contour: A Tile-based Gridless Router,” WRL Research Report 95/3, Digital Western Research Laboratory, Palo Alto, CA, Mar. 1995, 30 pp. [online] Downloaded from t

Affiliated with

Also associated with

Rating

Piecewise linear cost propagation for path searching does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Piecewise linear cost propagation for path searching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Piecewise linear cost propagation for path searching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3128913