     # The interconnection problem: A tutorial

• View
216

0

Embed Size (px)

Transcript

• THE INTERCONNECTION PROBLEM: A TUTORIAL

David W. Hightower Bell Telephone Laboratories, Inc.

Introduction

This paper represents a fairly extensive survey of the literature on the interconnection problem. The topics covered are Pin Assignment, Layering, Ordering, Wire List Determination, Spanning Trees, Rectilinear Steiner Trees, and Wire Layout. In addition, several new ideas are presented which could provide for better wire layout. Algorithms are presented in a way that makes them easy to understand, hence easy to discuss and apply. Formal statement of the algorithms can be found in the references cited.

Net List Determination

Starting Point The very beginning of the routing problem is a net list of some sort and a description of the circuit's geometry. In its most general form, the net list will be of the form shown in Figure 1.

The net list in Figure 1 denotes that some pin on component 1 (a dual in-line pack, for example) must connect to some pin on component 7. Furthermore, the gate which is selected on component 1 must be selected for net 10. In other words, nets 1 and 10 serve as inputs to the same logic

18 COMPUTER

• function. That function can be carried out by gates 2 or 3 on circuit 1 of component 1, or by gates 3 or 4 on circuit 2 of component 1. For each of the gates there is a choice of two pins. For this example, we have permutable circuits on a component, permutable gates on a circuit, and permutable pins on each gate.

As part of the routing assignment it is necessary to transform the list in Figure 1 to one like the one shown in Figure 2. The problem of transforming the general net list into a net list which specifies the particular terminals on each component which must be connected is called the pin assignment problem.

NET 1 Cl netl

CT1

CT2

C7 CT1

GT2

GT3

GT3

Glk

GT2

GT3

pn3 pnU

pn3 pnU

pn3 pnU

pn3 pnU

pnb

pnb

NET 2

etc.

Figure 1. A General Net List

NET 1 Cl - T2 C7 - T3

NET 2 e t c ,

Figure 2. Transformed Net List

Pin Assignment The pin assignment problem is the determination of which of several logically equivalent pins on a component a particular wire should connect to. Koren33 has described an interesting way to go about the assignment process. The basic idea behind Koren's algorithm is to assign pins on a component to incoming nets so that the assigned pin is the best candidate for routing in the general direction of the net.

Suppose net i can connect to any pin in the set (pj), j=l, . . . , m, of pins on the same component, and net i has k points (Ni j ) , j=l , . . . , k. Then assign a unit vector Pj, called a pin vector, to each p so that it originates at the center of

April 1974

the component and points to pj. The next step is to transform the points in the net to more realistically represent actual routing conditions. For example, in Figure 3 point (x,y) is transformed to (x\y') since (x',y') is the cell through which (x,y) would pass on its way to the target.

Next assign k vectors (Ry), j=l, . . . , k, to each transformed point in the net so that the vector originates at the center of the component and terminates at the other points in the net, (Ni j). Then compute a connection vector Ci by the following formula:

k Rjj/IRyl Ci = IR.-I

j=i y

This formula ensures that Ci will be long if the Rj j lie in the same direction and also will be long if the Rj j are short.

The assignment of nets (connection vectors) to pin vectors for a component is made so that the cyclic order of the connection vectors is the same as the cyclic order of the pin vectors. Of the k such assignments, the best one is found by maximizing

n q-PjO)

i=l

where Pj(i) is the pin vector to which net i is assigned, and n is the number of nets. Maximizing the quantity above means that less dispersion of the other points in the net will be rewarded, as will short connections. Because of this fact, Koren recommends that short connections be done before long connections when the routing process begins.

This process can also be applied to the problem of selecting circuits if there is more than one permutable circuit, and to the problem of selecting gates if there is more than one permutable gate.

Mattison has given a simple method for determining the orientation of components prior to routing.41 He assigns pin vectors in the same way as Koren, then averages the pin vectors which are permutable and assigns the resulting vector to those pins. Net vectors are also computed in the same way but then are transformed as follows:

Let Vi be the net vector for net i computed as described above, then set Vj=l if it exits the right side of the component, Vi=-1 if it exits the left side and V=0 otherwise. Then compute the number X=Vi#Pi, Where Vj is the net vector for net i and Pi is the pin vector for the pin to which net i is assigned, If X

• areas and a better pin assignment program is needed, then Oestreicher's data structure, applied only to the pin assignment problem, could prove very valuable in keeping track of the many options available for pin assignment. The result would be close to an exhaustive solution which is not unreasonable for many PC boards. This algorithm is discussed further in the section on Cellular Routers.

THE OPPOSITE PIN TRANSFORMATION (OPT) FOR VER T ICAL CONNECTIONS. THE ORIGIN IS THE CENTER OF THE SELECTED (LOWER) CHIP. (x,y) IS A PIN LOCATION ON THE EXTERNAL CHIP, (',') IS THE TRANSFORMED LOCATION.

o

o

-10 -5

-5

)Jx,y)

o

o

o

UV)

o

o

o

10

Figure 3. Opposite Pin Transformation

External Pin Assignment Akers4 has suggested an approach to the external pin assignment problem which tries to eliminate crossovers when the external pins are connected to their assigned component terminals by straight lines. The approach is illustrated by Figure 4. From an external pin a line segment is "swung" and the first candidate that it hits is assigned to it.

Figure 4. External Pin Assignment

Figure 5. 34 Cells Used to Route Pins ABC

Unfortunately connections are not made with straight lines, so that if the pins are perturbed slightly as in Figure 5a, then this assignment algorithm gives poor results, as shown in Figure 5b.

Brown's approach9 to the external pin assignment problem seems to have promise. This approach is to construct a candidate list for each net which needs a pin. The list contains those pins which could be reasonably assigned to the net. The nets are then sorted so that the net with the fewest candidates is at the top. The top net is assigned the best pin in its list, that pin is taken away from all other candidate lists, the nets are re-sorted, and the process continues until all pins have been assigned. The best candidate for a net is the one that gives the least increase in total net wire length. Figure 6 gives an example based on the setup of Figure 5. Figure 7 shows the final result of this assignment algorithm.

In assignment problems, the idea of assignment based on the notion of freedom (actually lack of freedom) of the elements to be assigned can be very useful. In particular, the author has found a very valuable application of that principle to a type of partitioning problem.29 The principle can also be applied to the ordering problem as discussed under 'Ordering," below.

After external pins are assigned, it is wise to go back into placement, with the external pins acting as components whose positions are frozen. Traditionally, external pins are assigned after placement, and therefore never take a part in placement. But it is fairly obvious that external pins should play an important role in placement.

Excellent results were achieved on the Golem B Project at the Weizmann Institute35 by assigning all external pins before placement began. The approach was to do placement of daughter boards on the mother board, external pin assignment on the daughter boards, and routing on the mother board simultaneously. Then placement of the com-

i i /

A o

B Q

c o

20 COMPUTER

• A o

B o

1 2

C o

D o

E o

F o

G o

4 5

H o

7

8

3 6

c, {A, B.C.D}

C2= {A , B, C, D}

c3= { C , D } c4= {c, D.E.F.G}

3 C 1 B 2 A 6 D

C5 = { c , D , E,F, G}

c6 - { D , E } C7 {F, G, H }

c8 = { F . G . H }

4 E 5+ F 7 H 8 G

Figure 6. "Best Candidate" Pin Assignment

ponents on the daughter boards proceeded very smoothly, with the external pins acting as anchors or seeds. This approach has a great deal of merit.

The Transformed Net List After pin assignment and external pin assignment, the net list is transformed to one which gives the component and terminal for each point in the net as in Figure 2. Further, the net list can be specified in terms of actual (x,y) locations of the points on the circuit. The next problem is connecting the points. But before they can be connected, we should determine the best way to go about that job, i.e., "What is the best order to do the connections?", and "Which connections should be attempted if there are more than two points in the net?" When we have answered these questions, we will have the wire list.

Wire List Determination

A net list is a list of the points that are electrically common; a wire list is a list of connections that should be made. For example, the wire list in Figure 8 displays the connections that should be attempted and the order in which they should be attempted d