Browse Prior Art Database

Procedure for Connecting N Points with Near Minimum Cost

IP.com Disclosure Number: IPCOM000045561D
Original Publication Date: 1983-Apr-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 5 page(s) / 19K

Publishing Venue

IBM

Related People

Donath, WE: AUTHOR

Abstract

Physical design of electrical packages requires interconnection of n point nets. Each wiring configuration can be evaluated and assigned a cost. This article describes a routing method for obtaining configurations of best or near-best cost.

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

Page 1 of 5

Procedure for Connecting N Points with Near Minimum Cost

Physical design of electrical packages requires interconnection of n point nets. Each wiring configuration can be evaluated and assigned a cost. This article describes a routing method for obtaining configurations of best or near- best cost.

In the early stages of the automatic routing of electrical networks, a 'global phase' is used to determine the paths of the electrical connections, where the wiring tracks are grounded into'channel segmental, which consist of a number of wiring tracks, and many distinct nets can use the same channel segment. When engaged in the routing of a single net, a cost is associated with the use of each channel segment, which is a function of among other things, how many other nets use the same segment. The routing of a net can be modeled as the following graph problem:
1) There exist a set of nodes V with non-directed edges G (G is

a subset of V x V), and for each edge g (i,j) in G we have an associated cost c (i,j).
2) Let N be a set of 'pins' a,b,c... etc., where a pin x is

typically a single vertex in V, but in general it is a

sub-tree of (V,G) - i.e., it consists of a vertex set v(x) in V

and a routing r(x) in G, where (v,r) form a complete tree

(i.e., if i and j are both in v, there exist a set of edges

in r, which form a path over the nodes of v from i to j).
3) A network is routed if we associate with the net N a generalized

pin (v(N), R(N)) such that the net N is included in

v(N). The cost of the routing C(R(N)) rs C(R(N)) = Sum

(g(i,j) in R) c(i,j).
4) The problem is to find a routing R such that C(R(N)) is a

near minimum.

This problem is NP-complete in the general case of many pins; however, a heuristic algorithm is described herein which yields an optimum solution when N < = 3, and hopefully generates otherwise good solutions. The method is a generalized mazerunner.

Essentially, for each vertex x of N, a 'mouse' is run on the basis of minimum cost. When some mouse of pin x (x in N) reaches some pin y (other than x) in N, and when there are more than two mice on the net, then the two mice of x and y are joined in a double mouse of x y; when any double mouse makes a 'junction' with some other mouse or when only two mice are left and they make a 'junction' (to be defined more precisely later), then the pins belonging to the contacting mice joined together by the routing, and the joined pins are replaced by a single generalized pin and the routing as determined from the joined mice. When only one pin is left in the net, then the routing is complete.

To be more precise of what is meant by a 'mouse', a mouse from pin x generates from each vertex t in V the following:
1) Status S(t,x) of node t with respect to pin x - which can

have the following values:

1

Page 2 of 5

not reached (S(t,x) = 0)

surface of the mouse (S(t,x) = s)

evaluated (S(t,x) = e)
2) The Cost C(t,x) is defined if, and only if, S(t,x)

is not equal to 0.
3) The direction D(t,x...