Browse Prior Art Database

Wire Routing With Path History Dependent Penalty Functions

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

Publishing Venue

IBM

Related People

Linsker, R: AUTHOR

Abstract

When routing interconnection wires on a circuit board, it is useful to be able to route each wire so as to minimize a penalty function that may be nonlinear in the number of occurrences of each penalty type along the path. Examples include routing subject to a crosstalk (adjacency) constraint, wherein one may wish to penalize adjacency only when it exceeds a threshold, and not otherwise, and routing subject to minimum and maximum wire length constraints. It is further useful to be able to near-minimize the number of wires involved in illegal (within-plane) crossings even if one thereby increases the total number of crossings on the board. These improvements are achieved as follows. Suppose we want to charge more for the nth link, satisfying some condition m on a path being mazerouted, than for the first.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 23% of the total text.

Page 1 of 5

Wire Routing With Path History Dependent Penalty Functions

When routing interconnection wires on a circuit board, it is useful to be able to route each wire so as to minimize a penalty function that may be nonlinear in the number of occurrences of each penalty type along the path. Examples include routing subject to a crosstalk (adjacency) constraint, wherein one may wish to penalize adjacency only when it exceeds a threshold, and not otherwise, and routing subject to minimum and maximum wire length constraints. It is further useful to be able to near-minimize the number of wires involved in illegal (within- plane) crossings even if one thereby increases the total number of crossings on the board. These improvements are achieved as follows. Suppose we want to charge more for the nth link, satisfying some condition m on a path being mazerouted, than for the first. (For example, we are getting close to a crosstalk limit.) A mazerouter algorithm does not save information on all possible paths to the present point, and then assign a different cost for the new link depending on the number of links (satisfying condition m) already traversed by each of these paths. We can, however, ask how many links (satisfying m) that wire contained on its previous routing (i.e., on the prior pass of an iterative mazerouting). If that number is too large, we know the wire is 'at risk'; therefore, we propose increasing the per-link penalty (for condition m) for the present routing of that wire. That is, the previous- pass experience is used as a guide in choosing the new per-link penalty, even though the penalty per link (satisfying m) is constant for all such links traversed on a given path routing. We now consider several specific problems. Minimizing the number of wires to be manually embedded (routed) or to be wired as discrete wires: Suppose we want to near-minimize FGLOBAL = S f( x(j) ) (sum over j), where x(j) is the number of crossings involving wire j; and suppose f(x) is concave downward. That is, we would rather have one wire with n crossings than have n crossings each involving a different wire pair. [For example, the former may be less costly to embed manually, and will require fewer discrete wires running outside the printed interconnection planes if they cannot be manually embedded by the designer.] For each connection i, route so as to minimize the path cost function c(i) = S a( x(j;old) ) $ x(i with j). Here x(j;old) is the number of crossings for connection j from the previous iterative pass; and x(i with j) is the number of times i crosses j on the present iterative pass. The sum is over all paths j. This is implemented using a mazerouter algorithm as follows: When routing path i, suppose we are considering a trial move that would cross some path j. Look up x(j;old). If it is large (i.e., j was a 'bad' wire, with many crossings, on the previous pass), then a( x(j; old) ) is small. That is, a small penalty is incurred when a 'bad' wire...