Published on

07-Apr-2017View

216Download

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 during the wire layout phase: first a connection from net 5, then a connection from net 3, etc. The problem now is to construct the wire list given a net list. Note that there are two aspects to a wire list: a set of connections and an order. To determine the set of connections, we use the concepts of minimum spanning trees and the traveling salesman problem.

Minimum Spanning Trees Wire length has a definite effect on routing performance. Therefore, a good way of arriving at a set of connections is by finding the minimum spanning tree through the points in the net. The resulting tree is really a set of pairs of nodes. The router will try to connect each pair of nodes and if successful will connect the net with the least possible amount of wire assuming Steiner points are not allowed. If Steiner points are allowed,

April 1974

A o

B C O > J E Q

F o

* 3 * 6

5

G H

Figure 7. Final Assignment (24 Cells for D.E,F)

the set of connections given by the minimum spanning tree gives the best chance of finding good Steiner trees. This point is discussed further in the section on "Net Layout."

The Traveling Salesman Problem If the points in a net must be connected by a chain, then the problem of which connections to attempt is equivalent to the traveling salesman problem. Shen Lin of Bell Labs has described an algorithm38 for solving the traveling salesman problem. Lin's algorithm finds the true solution to problems with fewer than 14 cities (in 1.75 sees on the IBM 7094). For larger problems his algorithm will yield the optimal solution after k iterations with probability

P = 1 1-2

n 10

where n is the number of cities. Clearly the larger k is, the more likely the computed tour is optimal. Each iteration takes less than 30n3 microseconds on the IBM 7094. For large problems (n>30), Lin uses a reduction technique to reduce the running time. For a 100-city problem, his estimates show that a tour having a probability of 0.54 of being optimal can be found in less than 100 minutes.

Define a p-optimal tour to be a tour such that its length cannot be reduced if any p links in the tour are replaced by p links not in the tour. The basic approach used in the algorithm is to find k 3-optimal tours and choose the shortest of the k tours.

For large problems, after finding a given number of tours, say r of them, the set I is computed so that

I = n T, i = l

11 32 1U lh 32 26

16 29 36 16 56 19

X2 y2 Net #

10 i*9 16 U2 93 9U

12 22 60 19 1*2 55

5 3 2 5 7 1

Figure 8. Wire List Based on Length

where Tj is the set of links in the ith tour i.e., I is the set of links common to all r tours. This set of links is used to reduce the size of the problem. For example, if two links are in I which connect to city j , then city j can be removed from the problem.

Lin gives results of several experiments in particular, the results of a 105-city problem. Computation time for a 3-opt tour without reduction for this problem was 35 seconds. With reduction, the problem was reduced to an 81-city problem and the time for a 3-opt tour was 23.8 seconds. Total computation time was 476 seconds, with a final tour length of 23,096. (The conjectured optimum tour is 23,082.)

Layering

Layering is the assignment of routing planes to connections before routing begins. The idea behind layering is that it should be possible to utilize routing space more effectively if conflicting wires are not routed on the same plane.

Abel1 has worked on the layering problem extensively and derived some clever methods for layering. His conclusion, however, was that no layering method is significantly superior to all other layering methods. He uses an interference measure to derive a graph which can be "colored" using his technique for coloring a graph with insufficient colors. This interference concept is discussed below in the section on "Ordering."

The main problem with layering is that deciding once and for all before routing begins where a connection should go neglects the fact that small perturbations in early routes may get magnified in later routes. As a result, routes which do not seem to conflict when there are few routes on the plane may seriously conflict with many routes on the surface. Also, layering neglects the fact that two routes which at one point in time may seem to conflict end up not conflicting because of the lack of interference around them. These points are illustrated in Figure 9.

The point is that once routing is under way, all of the orderliness and theory that existed before routing began

-A

B;

THESE ROUTES DO NOT INTERFERE IF THERE ARE NO ROUTES WHICH PROHIBIT A,A1 FROM GOING AROUND ,'.

B*-

B -C

INITIALLY IT LOOKS AS THOUGH ,' DOES NOT INTERFERE WITH C , C BUT BECAUSE OF A, A' , IT REALLY DOES.

Figure 9. "Interference" isdifficult to measure.

falls apart. It would seem, then, that a layering scheme as good as any is to do to as many routes on one layer as will fit, then as many routes on the next layer as will fit, etc.15'19

The overriding principle behind good routing seems to be to get the nets in with as little metal as possible. There are, of course, tradeoffs: a path can be a little longer to avoid a via, etc., but generally, it is path length that is critical. In any event, the value of layering is questionable. However, if you decide that layering is essential to your problem, then I suggest you read Abel's paper. He has some solid ideas on the layering problem. Akers4 also has a discussion of the layering problem. He uses an approach based on the number of straight-line intersections for each connection. Ordering

Ordering means deciding the ord...