Browse Prior Art Database

Wire Routing Subject to Constraints

IP.com Disclosure Number: IPCOM000043049D
Original Publication Date: 1984-Jul-01
Included in the Prior Art Database: 2005-Feb-04
Document File: 5 page(s) / 21K

Publishing Venue

IBM

Related People

Linsker, R: AUTHOR

Abstract

A conventional maze router for wire placement in an array finds the path of lowest cost between two points or regions. If one is required to find a path of minimum cost C subject to the constraint that some other nonnegative function g (whose value depends on the path) not exceed the value g0, the conventional methods do not suffice. This is because one does not know, at an intermediate stage of the maze run, whether one needs to make the 'sacrifice' of accepting a higher-cost route to a given intermediate state, in order to insure reaching the target with an allowed g value. An improvement is provided by a modification of the usual mazerunner algorithm that optimizes a general cost function subject to one or more constraints of this type. Strategies for reducing run time and storage requirements are also provided.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 24% of the total text.

Page 1 of 5

Wire Routing Subject to Constraints

A conventional maze router for wire placement in an array finds the path of lowest cost between two points or regions. If one is required to find a path of minimum cost C subject to the constraint that some other nonnegative function g (whose value depends on the path) not exceed the value g0, the conventional methods do not suffice. This is because one does not know, at an intermediate stage of the maze run, whether one needs to make the 'sacrifice' of accepting a higher-cost route to a given intermediate state, in order to insure reaching the target with an allowed g value. An improvement is provided by a modification of the usual mazerunner algorithm that optimizes a general cost function subject to one or more constraints of this type. Strategies for reducing run time and storage requirements are also provided. Some applications to wire routing on chips and higher-level packages include minimization of an arbitrary cost function subject to the constraints of: . maximum distance for which two wires may run in

tandem, either in adjacent wire tracks on a plane, or

in adjacent planes (crosstalk constraint);

. maximum wire length (e.g., owing to timing

considerations); and/or

. a prescribed maximum number of vias, or of wire

bends, for a given wire. A conventional mazerunner algorithm can be described as follows. Label the source point A as the 'current point' ('CP'). Assign trial scores to all points in a 'neighborhood' of the CP. The score increment is given by a specified cost function which is nonnegative. The score may be a number or a sequence of numbers with lexicographic ordering understood. In the latter case, (s1,...,sn) is 'less than' (t1,...,tn) if (si=ti for all i < k) and (sk < tk), for some k=1,..., n. Accept a trial score at a point if it is lower than any score previously assigned to that point. When a trial score is accepted, record the direction from which the point was entered resulting in that score. Choose as the next CP a point whose score is the smallest among all points that have not yet been made the CP; proceed until the score of a CP first equals that of a terminal point
B. If the CP list becomes exhausted, there is no path from A to B.

Backtrack from B to A using the directional information that has been saved. The resulting path is a lowest-cost path connecting source and target. Cost minimization subject to a constraint g < g0 requires a different approach. Suppose a point has been reached with score SC1 and g-value g1 by some path. It may subsequently be reached by a different path with values (SC2,g2). If SC2 < SC1 but g2 > g1, and if one keeps the SC2 value (as in the usual algorithms), the resulting path to the target might have g-value greater than g0, and thus be unacceptable. There is no way, in such a case, to know whether the 'sacrifice' of keeping the higher score SC1 (with the lower g-value) is worth making at an intermediate stage of the maze run. The fo...