UPPER BOUNDS	PAGE 77

Chapter 4
Upper bounds

An upper bound in the VLSI model of computation is proved by the existence of an admissible communication graph achieving a given performance level. This chapter details four constructions, two solving the Fourier transform problem and two solving the sorting problem. Of the two graphs solving each problem, one is based on the shuffle-exchange interconnection pattern, and one is based on the square mesh. The shuffle-exchange designs are fast but large: the Fourier transform circuit operates in time T~ O(?og27’/) and area A = 0(N2/log1”2N); the sorting circuit has T= 0(’log3i\9 and the same area. The mesh designs for both problems are relatively slow and small, T = O(N1”2loglog N) and A = 0(N log2N). All four designs are nearly optimal under the AT2 metric, and the mesh designs are nearly optimal under any AT2X metric, for 0 < x < 1.

The constructions are described in a top-down fashion, starting with a discussion of the basic algorithms, the bitonic sort and the fast Fourier transform (FFT). In Section 4.1, these algorithms are defined as networks consisting of 0(’N log N) or more cells each capable of performing a two-element sort or a two-element Fourier transform. Section 4.2 discusses the way in which a network construction leads to a recirculation algorithm that uses only 0(’N) cells. Section 4.3 gives two VLSI imp leinentations of the FFT algorithm, one for a mesh-based recirculation network, one for a shLlflle-exchange-based recirculation network. These two networks are used to implement the bitonic sorting algorithm in Section 4.4. Section 4.5 develops approximations to the actual size and speed of the VLSI implementations of sorting and FFT circuits, comparing these to their asymptotic performance measures.
PAGE	78	A COMPLEXITY ThEORY FOR VLSI
4.1	AlgorithmS

Both the bitonic sort and the fast Fourier transform are often described as large networks of fairly simple cells. The FF1’ network will be discussed first, since its construction is the simpler of the two.

An N-element FF1 network [Cochran 671 is built from a total of ½N log N multiply-add cells. Figures 4-1 and 4-2 illustrate the recursive construction of an N-element network from N/2 cells and two N/2-element networks. Figure 4-3 is the 8-element FF1 network that results from this method of construction.

The basis of the recursive construction is the two-element FF1’ network composed of a single multiply-add cell. A cell marked k produces as outputs
   Y0=X0+a~’~Xj	(4.1)
and
     y1 =X0 — a’Xj,	(4.2)

where X~ and X1 are its two input values (here a is an N-th root of unity, as defined in Subsection 1.2.1). The exponent of a is parameterized since different cells have different values for k. The construction of Figure 4-2 defines the way in which cells are assigned values for their parameter k. In this construction, networks and subnetworks are also parameterized: a (k)-FFT network is built from an N/2-element (0)-FFT network and an N/2-element (N/4)-FFT network.

The outputs of an N-element (O)-FFT network are the N outputs of the discrete

Fourier transform. However, these outputs appear in “bit-reversed” order [Cochran

67]. That is, if the output indices are expressed as (log iV)-bit binary numbers, then

each output appears in the position denoted by reading its index in reversed order.

For example, the fifth output of an 8-element FF1, Y4, appears in position

(001)2 = 1, since the binary representation of its index is (100)2.

It is now time to examine sorting networks. The N-element bitonic sorting network [Batcher 68] is built of ½A1(’log N)(’log N + 1) comparison-exchange cells,
UPPER BOUNDS
PAGE 79
xo	xi
‘(0 = Xo + CZ~ X1
	‘(1	X0— ~k x~
Figure 4-1: Multiply-add cell or 2-element FF1’ network.
Figure 4-2: Recursive from
construction of an N-element (k)-FFT network ‘/2N(log N) multiply-add cells.
interconnected as shown in Figures 4-4 through 4-7. A comparison-exchange cell is a two-input, two-output device that compares the values of its two inputs, sending the larger toward the point of its arrow. As indicated in Figure 4-6, a sorting network is defined in a doubly-recursive fashion, from two smaller sorting networks and one bitonic merger. Note that a bitonic merger is topologically identical to the FFT network of Figure 4-2, since it has the same recursive construction, from N/2 cells and two half-sized networks.
	‘(0	‘(i
6 0 0
N—I
Yo
0	0
0
YN2
Yl
0	0	0
PAGE 80
A COMPLEXITY THEORY FOR VLSI
X6 X7
Yip

The term bitonic seems to have been coined by Batcher [Batcher 68], by analogy with monotonic. A bitonic sequence is the concatenation of two monotonic sequences, one increasing and the other decreasing. In the article cited above, Batcher also makes a distinction between a “bitonic sorter” (his name for a bifonic merger) and the complete bitonic sorting network. In an effort to avoid confusion between these two networks, Batcher’s distinction is not observed here.

Y0 = MIN (X0 ,X) Y = MAX(X01X )
xo	X1	X2	X3 X4 X5
Y0 Y4 Y2 Y6 Yi Y~ Y3 Figure 4-3: An 8-element FF1’ network.
xo	xi
Figure 4-4: Comparison-exchange cell or 2-element sorting network.
UPPER BOUNDS
PAGE 81
	0	X1 0 0 0	xN/2,	XN,2	Xp4/2 + I	X N-I
N,2_ ELEMENT BITONIC	
MERGER	
Figure 4-5: Recursive construction of an N-element bitonic merger.

The bases for the recursions of Figures 4-5 and 4-6 are formed trivially by the single comparison-exchange cell of Figure 4-4, which may be considered either a two-element bitonic merger or a two-element sorting network. The arrow inside a sorting network indicate the “direction” of its sorting process: the larger input elements move toward the point of the arrow, following Knuth’s notation ([Knuth 73], p. 237). The direction of these arrows is critical in the construction, for one of the two N/2-element sorting networks of Figure 4-6 must produce its outputs in ascending order, while the other must produce a descending sequence.

The action of a sorting network can be described in an intuitive fashion [Stone 71]. The graph of the outputs of the left-hand N/2-element sorting network may be visualized as 1, for its rightmost outputs are the largest. Similarly, the graph of the outputs of the right-hand N/2-element sorting network looks like \. The inputs to the N-element bitonic merger are thus a bitonic sequence A. Just inside of the N-element bitonic merger, the two arms of the A are interleaved to form an x. The
N,’2 - ELEMENT BITONIC	
MERGER	
1

‘(N /2
0	0 0
‘(N/2_I	a	a	a	‘(N
PAGE 82
A COMPLEXITY THEORY FOR VLSI
XN/?+, o a a XN
	1
	0	YN_I

Figure 4-6: Construction of an N-element bitonic sorting network from
two N/2-element bitonic sorting networks and
one N-element bitonic merger.

comparison-exchange cells are able to pick apart the top and bottom halves of this x into a A and a V both of which are bitonic sequences. The A is passed to the left and the V is sent to the right. Since all elements of the A are less than any element of the V the outputs of the two N/2-element bitonic mergers look like / and / and can be immediately combined into a fully sorted sequence I.

Note that there are two distinct ways of forming an ascending sorting network (...÷) from a descending sorting network (i—). One way is to “flip” the network along a vertical axis, so that the rightmost and’largest output becomes the leftmost output. This is the approach used on page 237 of [Knuth 73]. The other way, chosen by Stone [Stone 71] and adopted here, is to reverse the directions of all the comparison-exchange cells inside a descending sorting network. Figure 4-7 shows the eight-element sorting network obtained from the construction of Figure 4-6, using this
0
y
	X1 0 0 0	XN,2..,
	I	I
XN/z

1
I N,2... ELEMENT BITONIC SORTER —
N/2-ELEMEm BITONIC

SORTER
N - ELEMENT BITONIC MERGER
YO
Yl
0
0
I
UPPER BOUNDS
PAGE 83
Yip

type of descending sorter. The two methods of reversal give distinct networks. In particular, the top row of an eight-element sorting network built using Knuth’s approach has comparison-exchange cell directions (—p ~— —+ i—), while the top row of Figure 4-7 is (—i +- ~- —+). The virtue of the latter approach is that it has a more
x0 x1 x2 x3 x4 x5 x6 x7
	YO V	Y2	Y3	Y~ ‘(5 ‘(6

Figure 4-7: An 8-element bitonic sorting network.
PAGE 84	A COMPLEXITY THEORY FOR VLSI

obvious mapping onto the shuffle-exchange pattern, as will be seen in Subsection

4.4.1.

4.2	Recirculation aIgor~thms

The sorting and FF1 networks described in the previous section could be implemented directly in VLsI, although this would be grossly inefficient. During the course of a computation, each cell is active only once, producing just one pair of i’esults.

There are two ways to boost the efficiency of sorting and FF1 networks, pipelining and recirculation. The pipelining approach introduces a row of registers between each row of cells in Figures 4-3 and 4-7. A new problem can be fed into the top row of the network as soon as the previous problem inputs have emerged from that row. Since a pipelined design solves many problems simultaneously, it can solve a series of problems more quickly than a non-pipelined design. However, the pipelined design is no faster at solving a single problem, and thus does not have a better time performance under the ground rules of this thesis. (An interesting extension to the VLSI model of computation would explore different notions of time performance. For example, solution time might be defined as the time between successve problem solutions, under the assumption that the circuit is always being fed with new problems.)

The second method of increasing efficiency, recirculation, uses one row of cells many times during the solution of a single problem. During each stage of the computation, this row simulates the action of one of the rows in the complete network. The inputs needed by the row as it simulates the (k + Dst row of the network are obtained from the outputs of the kili stage of computation. A recirculation network is used to handle this data flow. The structure of this network is important. If its connectivity is not precisely right, the data will have to circulate more than once through the row before it reaches the correct cell. As shown in Subsections 4.3.3 and 4.4.1, the shuffle-exchange pattern is an ideal recirculation
UPPER BOUNDS	PAGE 85

network: one pass through the network is sufficient between each stage of a FF1 or hitonic sort algorithm. The mesh pattern is not nearly so well suited to these algorithms, but it does require much less silicon area, as shown later in this chapter.

4.3	VLSI imp’ementations of the FFT

This section is divided into four parts. The first part shows how an N-element FF11’ can be performed on a row of N multiply-add cells, using a mesh-type recirculation network. The resulting algorithm is essentially identical to one proposed for the the Illiac IV computer [Stevens 71].

The second subsection examines the problem of implementing a multiply-add cell in VLsI. A construction is proposed, and its area-time performance is analyzed. This leads to area and time results for a complete mesh-based FF1 circuit.

The construction of Subsection 4.3.3 uses a different recirculation network based on the shuffle-exchange graph. Area and time results for this FF1 circuit are developed in Subsection 4.3.4, after the problem of embedding the shuffle-exchange graph in the plane has been solved.

4.3.1	PerformingtheFFTonamesh

The square mesh interconnection pattern takes its name from its appearance when drawn in its most compact form, as in Figure 4-8. In a mesh with N = cells, an interior cell i connects “horizontally” to cells i—i and i+ I, and “vertically” to cells i~~n and i-i-n. Note that there are no end-around connections, so that nodes on the periphery of the mesh have fewer than four neighbors. Figure 4-8 shows the row-major indexing scheme for the cells in a mesh that is implicit in the definition given above for cell connectivity.

The precise functionality of the cells in the mesh will be developed in the next subsection, in keeping with a top-down approach to the description of the
PAGE 86
A COMPLEXITY THEORY FOR VLSI
~-RT~1-t~J-c~:’

Figure 4-8: A 16-cell mesh drawn in its most compact form.

constructions. At the present level of detail, cells may be thought of as message-driven processors. Each cell can create a new message from the information contained in its registers, addressing it to any other cell in the network. Each cell can also forward messages along the shortest path to their destinations. Finally, each cell can receive messages addressed to it, and update its registers appropriately.

To understand the way in which an F~F1’ can be performed on a mesh, it is best to visualize the mesh in the linearized form of Figure 4-9. In this representation, the horizontal connections are still quite short, but the vertical connections have been lengthened dramatically (they must skip over N 1/2~1 intervening cells). Of course, the VLSI circuit will not be laid out in this fashion, as the vertical connections would waste a lot of area.
Figure 49: A 16-cell mesh drawn in linear form.
UPPER BOUNDS	PAGE 87

There is a natural correspondence between the Unear form of the N-cell mesh and the iV-element FFT network. Each of the N columns of cells in the FF11’ network corresponds to one of the N cells in the mesh; the interconnections between rows of cells in the FFT network correspond to data movement among the cells in the mesh (a “recirculation”). The comments made so far apply to any recirculation algorithm on any recirculation network: what makes the N-cell mesh correspond nicely to the N-element FF11’ network is the fact that each recirculation can be mapped efficiently onto either the horizontal or vertical interconnections of the mesh. Referring to the 16-element FF1 network of Figure 4-10, the interconnection pattern between each pair of rows consists of connections between columns whose indices differ by a power of 2. Similarly, in Figure 4-9, connections exist between cells whose indices differ by a power of 2.

The actions performed by cell 0 of a /6-cell mesh performing a 16-element FF1 can be described with reference to Figures 4-9 and 4-10. Initially, the 16 inputs to the FF1 are stored one per cell: cell i contains input X~. Looking at the top of column 0 of the FF1’ network, cell 0 receives input A’8 from cell 8, and does a multiply-add step with coefficient a0 on this new value and its original input X0. It keeps one of its two outputs, sending the other back to cell 8. Moving to the second row of cells in the FF1’ network, cell 0 receives a value from cell 4, does a multiply-add step, and returns a modified value to cell 4. Next, cell 0 receives a value from cell 2, and returns a modified value to that cell. Finally, cell 1 sends a value to cell 0, for use in its last multiply-add step. The FF1 computation is complete after this multiply-add step.

The actions of cell 0 in the FF1 algorithm are anomalous in the sense that no other cell performs a multiply-add step during the simulation of every row of the FF1 network. In fact, only half of the cells participate in each stage of the computation. In the first row of the /6-element example of Figure 4-10, the participating cells all have four-bit binary indices of the form (Ocba)2. That is, only the first eight cells perform the first multiply-add step, and the outputs of the other
PAGE 88
A COMPLEXITY THEORY FOR VLSI
Figure 4-10: A 16-element FF1’ network.

eight cells will be ignored. Moving to the second row of the H-”l’ network, only cells with binary indices of the form (d0ba)2 do a multiply-add step. In the third and fourth row, cells with indices (dc0a)2 and (dcb0)2 participate in the multiply-add step, respectively.
xo xi x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15
“4 ‘~‘l2 ‘~‘2 ‘~‘l 0 ‘~‘6 ‘E’14 ‘~‘i ‘~‘~ Y5 b~13 Y3 ‘~‘~ ~ y y
UPPER BOUNDS	PAGE 89

The actions of cell 0 are also anomalous because it does not have to act as an intermediary in the routing of data values from one cell to another. Most routings on the mesh do involve intermediate cells. For example, the top row of the FF1’ network of Figure 4-10 involves a distance-8 routing: the data from cell 8 reaches cell 0 by way of cell 4, passing over two vertical interconnections. Note that all distance-8 routings can be performed (in parallel) by way of one intermediate cell at distance 4 from the sender and the receiver.

On an N = n2 cell mesh, both distance 1 and distance n routings are called unit distance routes because they can be accomplished over horizontal or vertical connections with no intermediate cells. A unit distance route takes time tR.

The total time taken by the data movement during an FFT can be evaluated in terms of the number of unit distance routes performed. In the case of the 16-element FF1 of Figure 4-10, the top row’s distance-S routing takes two unit distance routes (2tR). After the first multiply-add step, there is another distance-8 routing followed by a distance-4 routing, taking time 3tR. After the second multiply-add step, there is a distance-4 routing and a distance-2 routing, which also takes time 3tR. The third multiply-add step is followed by a distance-2 and a distance-i routing, for another 3tR units of time. The fourth multiply-add step is followed by a (superfluous) distance-I routing. The total routing time in the computation of a 16-element FF1 is thus l2tR.

In the general case of an N-cell mesh performing an N-element FF1’, cell indices can be represented as (log N)-bit binary numbers. There are log N rows in the FF1 network, the kt/z of which is simulated by a multiply-add step in cells with a zero bit in the ((log N) — k)t/z bit of their index. A distance-(’N/2 k) routing is pertbrmed before and after this multiply-add step. A summation of the time contributions of all rows k of the FF1 network will give the total amount of routing time. Similarly, the amount of time taken by the multiply-add computations can also be evaluated in terms of t~, the time taken by a single multiply-add step. This line of reasoning leads to the following lemma.
PAGE 90	A COMPLEXITY THEORY FOR VLSI

Lemma 1: An N-element FF1’ can be performed on an N-cell square mesh in time T = O(N “2tR + (log N)t~ví), if a unit-distance route takes time tR and a multiply-add step takes time M~

Proof There are log N rows in an N-element FF1 network. The cells of the mesh simulates row k of the network by performing two distance-(N/2 k) routings and one multiply-add step. When k <(‘log N)/2, the mesh’s vertical interconnections should be used to perform the routings in minimal time. Otherwise, the horizontal connections should be used.

The total time for the FF1 is thus

T = ~ (2(N/2 ky1y 1/2 tR + t~) + ~ (2(N/2 k)1 + t~1),	(4.3)
	1<k<(log N)/2	(log N)/2<k<!og N

so that
	T = 4(N 1/2 — 1)tR + (log N)t~i. 0	(4.4)

This completes the description of the way in which the FF1 algorithm can be performed on mesh connections. The next subsection gives a VLsI implementation of a multiply-add cell. A mesh composed of N of these cells can compute an FF1’ in the manner described above.

4.3.2 The multiply-add cell

Each multiply-add cell in a mesh implementation of the FF1 must perform two functions. First, it must be able to perform a multiply-add step on two (‘log M,)-bit numbers A’0 and X1, computing
	Y0 _—X0 + a3X1	(4.5)

and
	Y1 =X0-a~X1.	(4.6)

Here, a1 is the power of a used in the jth stage of the FF1’ computation. Each multiply-add cell uses a different list of a~ values, corresponding to the computations performed in its column of the FF1 network. A multiply-add step takes time t~1, in the terminology of Lemma 1.
UPPER BOUNDS	PAGE 91

Second, each cell must be able to send and receive messages (data values) to and from its immediate neighbors in the mesh. Such a transmission is called a unit-distance route and takes time tR in the terminology of the previous subsection.

By the result of Lemma 1, the time performance of an N-cell square mesh will be affected much more strongly by 1R than by tM.

This observation suggests that a bit-serial method be used in the multiply-add computation to save area. Also, a bit-parallel routing method should be used to minimize tR.

Figure 4-11 shows the structure of a multiply-add cell that does bit-serial camp utation but has bit-parallel computation paths to and from its immediate neighbors. There will be N such cells in a complete mesh, arranged in a square pattern. Each cell is O(log N) units wide by O(log N) units long, so that N nodes occupy O(log 2N) area. Note that there are log iVi wires in each of the parallel communication paths, so that a (log iVf)-bit word can be transmitted to a neighbor in a single operation. However, it will take O(log N) time to get a word out of a transceiver and into the arithmetic circuits, since there is only a serial data path between these two elements. (Recall that log M = O(’log N) by assumption U4 of Chapter 2.)

There are four control wires for the vertical (resp. horizontal) transceiver, telling it to transmit data in parallel upwards (to the right) or downwards (to the left), or else to shift data serially into or out of the arithmetic circuit. The internal structure of a transceiver is shown in Figure 4-12. The circles are logic nodes forming a shift register that can be accessed either serially (shift in, shift out) or in parallel (up, down). The large triangular drivers must be able to send a signal down an O(’log N) unit wire. Hence they have area O(log N). Since the entire transceiver must fit in an O(log N) by O(’log N) unit area, these drivers must be oriented vertically, as indicated in Figure 4-12.
PAGE 92
A COMPLEXITY THEORY FOR VLSI
LOG M

TRANSCEIVER AND

SHIFT REGISTER “H”
LOG M

~_____~RANSCEI~R AND

..........,L__.0.1SHIF~REGISTER ‘IV”
CONTROL
ARITHMETIC AND
0 (LOG M)
CONTROL
CIRCUITS
o (LOG M).
LOG M
•1
Figure 4-11: Multiply-add cell for the mesh.

Lemma 2: The multiply-add cell of Figures 4-11 and 4-12 has a routing time tR = 0(loglog N), exclusive of the time it takes to shift data into and out of the transceivers (the shifting time will be included with tM).

Proof The delay of a driver of area 0(log N) is 0(loglog N), by assumption U5 of Chapter 2. 0

The total routing time for an N-element FF1 computation is thus O(N”2tR) = 0(’N1”2loglogN). This time bound could be improved to 0(N2) if a few more assumptions were added to the upper bound model of computation. As
LOG M
DATA
CONTROL ~
DATA
DATA
UPPER BOUNDS
PAGE 93
Figure 4-12: Transceiver for the mesh.

noted in the proof of Lemma 2, the factor of 0(loglog N) arises from the delay of the drivers: each has 0(loglog N) stages of amplification. Such amplification is necessary beecause the outputs of the arithmetic and control circuitry are obtained from minimal-sized transistors. However, there is no need for much gain in the data paths from one transceiver to the next. This observation suggests the following construction for a transceiver. Its drivers, receivers and shift registers could be built entirely from 0(’log N)-area transistors.2 The scaled drivers would work with 0(1)

2Even though it is quite feasible to “scale” circuitry in this way, the concept was not included in the upper bound model of computation in order to keep it as simple as possible. Changing the model to allow scaled logic nodes would entail changes in the definition of self-timed regions, since an otherwise-legal logic node might be too large to fit in a self-timed region.
	0	0	0
DATA AND
CONTROL
5
BIT 0
BIT I
	0	0	0
BIT (LOGM)-I
PAGE 94	A COMPLEXITY TFIEORY FOR VLSI

delay, reducing the unit-distance routing time tR to 0(1) time units. The multiply-add time t1~ would be increased slightly, since there would be 0(loglog N) stages of amplification between the outputs of the arithmetic and control circuitry and the inputs of the transceivers. However, if these stages were individually clocked, the amplifier would have a throughput of one bit per time unit and only 0(loglog N) delay. The additional delay would be insignificant in comparison to the 0(log N) time units required to shift the data in and out of the arithmetic circuitry.

The arithmetic and control circuits of the multiply-add cell are shown in Figure

4-13.	This circuitry can be thought of as a microcoded processor having a control program of 0(log N) instructions that are each 0(log N) bits wide. Each instruction has three fields: a timer word to indicate the number of clock cycles that the current instruction should persist, an a~ value to be used by the arithmetic unit, and a control field for the transceivers and the multiplexers in the upper right hand corner. As will be seen below, no instruction will persist for more than O(N1”2loglog N) units of time, so that an O(log N)-bit timing word will be sufficiently long.

The arithmetic unit has three serial data inputs and two serial outputs labelled a1, A’0, X1, Y0 and Y1. It implements equations (4.5) and (4.6), producing )‘~ and Y~ from X0 and ajXj in a bit-serial fashion.

The Appendix gives a control program for cell 0 in an N-cell mesh computing an N-element FF1. Initially, input X~ to the FF1 is contained in the shift register “V” of cell i’s vertical transceiver. After log N stages of computation, output Y should be in the horizontal transceiver “II” of cell i. The comments in the right hand margin of the control program indicate which instructions differ in the programs for cells other than cell 0. The program for cell 0 is unique in two ways: it participates in each stage of the computation by producing valid )~ and Y1 values from valid A’0 and A’1 values, and it uses the same value of a1 in each stage of the computation (only half of the cells participate in each stage of the computation, and many use several different a~ values).
UPPER BOUNDS
PAGE 95
T
0(I)
(To TRANSCEIVER “H”)
(TO TRANSCEIVER’V)
O(LOG N)
0	(LOG N)
•1
Figure 4-13: Arithmetic and control circuits.
PAGE 96
A COMPLEXITY THEORY FOR VLSI
As intimated in the control program for cell 0, the actual computation of the multiply-add step takes 0(log2M) 0(log2N) time. Figure 4-14 shows a small arithmetic unit with this performance, one that fits into an 0(1) by 0(log N) unit area.
x0
Y0
Yl
XI
Figure 4-14: An arithmetic unit for an FF1’ circuit

The multiplier box of figure 4-14 forms the mod M product a3 x1 from the bit-serial inputs x1 and a~. Its bit-serial output is used in two places. Along one path, it is negated then added mod M to x0 to form the bit-serial output y~. The other path leads to another bit-serial adder that produces y0.

The most complicated portion of this construction is the mod Al multiplier. It consists of 2Flog Mi carry-save adders that form the product a~xj. This 2Flog Mi-bit result is then multiplied by 1/M, with sufficient precision to maintain Flog Mi bits of accuracy to the right of the radix point The bits to the left of the radix point are discarded, and the ones to the right are multiplied by M to form the flog Mi-bit result a~ x1 mod M.

The multiplier thus has three sets of carry-save adders and storage for two constants, 1/M and M. The first constant can be expressed as a 21 log Mi-bit scaled integer, to obtain the necessary accuracy for the second multiplication step. The
UPPER BOUNDS	PAGE 97

other constant is, of course, a [log Mi-bit integer. The total amount of hardware in the multiplier is 0(log Al,) 0(’log N), since a cell of a carry-save adder can be built from 0(1,) gates. Total time for the three multiplication steps is 0(log N,), since each involves only 0(log iV~9 = 0(log N) bits.

A more realistic construction for the multiplier would use only two multiplication steps. The constants a1 and i/Al could be multiplied in advance and stored as a single 2[log Mi-bit number. The mod Al multiplication of a1 by x1 could then be ierformed by multiplying x1 by a1/Al, then multiplying the fractional part of the result by Al.

It is very easy to design the mod 1VI adder and negater. Addition can be performed with a bit-serial adder whose output is compared with Al in a bit-serial comparator. If the sum is greater than iVI, then Al can be subtracted from it in a bit-serial subtracter. The entire process takes only 0(log iVi) = 0(?og N) time and 0(’log N) hadware. The negater is even simpler. Its input is subtracted from Al in a bit-serial subtracter. Once again, 0(’log N) time and area is sufficient. (This negater produces an erroneous result if its input is zero; however the “excess Al” will be removed by the adder connected to its output in Figure 4-14.)

A more realistic circuit for the addition portion of the arithmetic unit would combine the negation step with the following addition step, saving 0(log N) time and area.

The overall performance of the multiply-add cell is described by- the lemma below, which summarizes the preceding discussion.
Lemma 3: The multiply-add cell of Figures 4-11 through 4-14 has a multiply-add time i~ = 0(log N,) and area A = 0(log AT,).

We are now in a position to prove the following theorem about the performance of the complete mesh-based FF1 circuit.
PAGE 98	A COMPLEXiTY THEORY FOR VLSI

Theorem 4: An N-element FF1 can be performed in 0(N log N) area and 0(N 1,”2 loglog N,.) time on N multiply-add cells arranged in a square mesh.

Proof By Lemma 1, an N-element FF11’ can be performed in time

T = 0(N “2,)tR + (log N,)IAf) on an AT-cell mesh. The unit routing time for this

structure, tR, is 0(’loglog N,) by Lemma 4-12. Lemma 3 gives M = 0(log N,). Thus

T = 0(iV t,”2 loglog N).

The total area is 0(N log 2A9 since there are N cells of 0(log2N,) area each. 0

The following corollaries state the combined area-time performance of the mesh-based FF1 circuit.

Corollary 5: AT2 = 0(’N2log2Nloglog2N) for the N-element FFT. Corollary 6: AT2X = 0(N” +x~0g2N~Og~og2XN,) for the N-element FF1.

Note that the FF1 circuit of this subsection is very nearly optimal under the AT2 metric developed in Chapter 3, for it is at niost 0(loglog2N,~ from the optimal AT2 ~(N2log2N) of Theorem 11. It is also nearly optimal under the AT2X metric, since it is 0(loglog2XN) from the optimal value of AT2X.

Also note that the total multiply-add time of (‘log I~,T,)t~~,f is completely dominated by the routing time N”2tR. There is thus no incentive to improve the multiply-add circuitry, for such improvements will not affect the asymptotic performance of the complete FF1 circuit.

The next subsection shows how an FF1 can be computed using a circuit built around a shuffle-exchange pattern recirculation network.

4.3.3 The FFT on shuffle-exchange connections

The shuffle-exchange pattern is a natural choice for a recirculation network solving the FFT [Stone 71]. This subsection revises Stone’s FF11’ circuitry to apply it
UPPER BOUNDS	PAGE 99

to the VLSI model of computation. 111 contrast to the mesh-based construction of the previous section, only one routing step need b~ made between multiply-add steps. Circuits based on the shuffle-exchange pattern are thus faster than mesh-based ones, since the performance of the mesh is limited by its routing time. 1-lowever, the area-time tradeoff results of Chapter 3 imply that shuffle-exchange circuits must be much larger than mesh-based ones, to counterbalance their improved time performance.

The shuffle-exchange graph is defined on N = 2N nodes numbered from 0 1o N— 1. Each node has two incoming and two outgoing edges. The outgoing edges for node i connect to node (2i+ [2i/NL~) mod N (a shuffle connection), and to node i~1 (an exchange connection). Here ~ represents the bitwise exclusive-or operation which, in this case, complements the least significant bit of 1. Exaniples of shuffle-exchange graphs have appeared earlier in this thesis, in Figures 2-3 and 3-4. An 8-node shuffle-exchange graph is drawn below in Figure 4-15.

The following subsection treats the problem of embedding the shuffle-exchange graph in the plane, according to the embedding rules of Chapter 3. The current subsection examines the way in which an FF1 can be performed on N/2 cells connected in a shuffle-exchange pattern. (Note that this subsection’s construction solves an N-element FFT on N/2 cells, not on N cells as in the mesh-based construction.)

The FF1 algorithm was defined in Section 4.1 as a network of ½N(log N) cells, each performing one multiply-add step. As we saw in Subsection 4.3.1, the recursive construction of the FF1 network lends itself to a mesh-based implementation in which each of N cells did the work of all the cells in one of the N columns. As it stands, the FF1 network is not’ suited for implementation on a shuffle-exchange pattern, for there is a different pattern of data movement between each row of the network.

However, the cells in each row of an FF1 network can be rearranged so that the interconnections between each row form the same pattern, a “perfect shuffle” [Pease
PAGE 100
A COMPLEXITY THEORY FOR VLSI
68, Stone 711. Figure 4-16 illustrates this rearrangement of Figure 4-10, the 8-element FF1’ network. Note that all cells lie in N/2 columns, and that a multiply-add step occurs in each row of each column.

The linear representation of the shuffle-exchange graph (Figure 4-15) bears the same relationship to the rearranged FF1 graph of Figure 4-16 as the linear representation of the mesh (Figure 4-9) does to the 1-’Fi graph of Figure 4-10. Each row of the FF1’ graph corresponds to one stage in the computation on the linear network, that is, to one multiply-add step and one or more passes through the recirculation network.

The rearranged FFT network is ideal for implementation on N/2 multiply-add cells connected in a shuffle-exchange fashion. Each cell corresponds to two nodes in the shuffle-exchange graph. Cell i has all the connections of nodes 21 and 21+1 in the N-node shuffle-exchange graph (see Figure 4-15). The “exchange” connections of the two nodes are thus internal to the cell, but two “shuffle” connections emanate from the cell. For example, one of the outputs of cell 2 in a 4-cell shuffle-exchange pattern (N =8) goes to cell 0, while the other output goes to cell 1.

CELLS

NODES:

The computation of an N-element FF1’ on an N/2-cell shuffle-exchange recirculation network can be described explicitly with reference to Figures 4-15 and

4-16.	Initially, each cell contains two of the N inputs: cell i contains inputs X21 and in its registers X(~ and X1. During each of the log N stages of computation,
Figure 4-15: A 16-node shuffle-exchange graph, laid out in a linear fashion. Exchange connections are internal to the cells.
UPPER BOUNDS
PAGE 101
each cell performs a multiply-add step on X0 and X1, sends the results Y0 and Y1 out over its “shuffle” output connections, and receives new values A’0 and X1 from its “shuffle” inputs.

The following lemma summarizes the behavior of the shuffle-exchange-based
FF1 algorithm.
xo xi x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15
~‘4 ‘I’12 “2 ‘~1O ~‘6 ‘~‘l4

Figure 4-16: A rearranged 16-element FF1 network.
PAGE 102	A COMPLEXITY THEORY FOR VLSI

Lemma 7: An N-element FF1’ can be performed on an i’//2-cell shuffle-exchange network in time T = O((log N,hR + (log N,~t11), if a routing step takes time 1R and a multiply-add step takes time ~

A multiply-add cell for the shuffle-exchange network can be built along the lines of Subsection 4.3.2’s construction. Three modifications are necessary, however.

First, there is no reason to provide parallel data paths between cells. Bit-serial connections take up much less area, and are fast enough to keep the multiply-add circuitry busy almost all the time. This was not the case in the mesh construction:

multiply-add time was completely dominated by routing time.

A second modification to the multiply-add cell changes its aspect ratio from O(log N~ by O(log N,) to 0(1) by 0(log2N). The reason for this modification will become apparent in the next subsection, when the shuffle-exchange connections are embedded in the plane.

Finally, the drivers for the Y0 and Y1 outputs must be able to handle wires that are 0 (N/log N) units long (this is the length of the shuffle connections in the embedding developed in the next subsection).

These three modifications lead to the multiply-add cell shown in Figure 4-17. Note that the control program must bestored in an 0(1) by 0(log2N) bit array, to fit in the required aspect ratio. This means that 0(iog N,) time must elapse between instructions (see the Appendix) so that a new instruction can be shifted in.

The following lemma describes the time performance of the shuffle-exchangebased FFT circuit.

Lemma 8: An N-element FF1 can be performed on iV/2 cells interconnected in a shuffle-exchange recirculation pattern in time T = 0(log 2~)~

Proof A total of log N routing steps and log N multiply-add steps are necessary. The Lime taken by a single multiply-add step is the same as it was for the meshbased construction, t~1 O(log2N). Total multiply-add time is thus 0(log2N).
PAGE 103
0 (LOG2 N)
o	(LOG N)

(TO OTHER MULTIPLY-ADD CELLS)
Figure 4-17: Multiply-add cell for a shuffle-exchange network:

Total routing time is also O(log2N), since there are O(log N) routing steps each involving log M = O(log N) bit-serial data transfer operations. These transfers occur at unit bandwidth, so that the transmission of one word takes 0(’log N) time. Additionally, there is an O(log N) delay in the drivers, for the wires between cells are O(N/log N) units long. (The delay of a driver-wire-reciever circuit is the logarithm of the length of the wire, by assumption U5.)

Note that the time performance of this circuit is optimal: faster multipliers and/or faster instruction loading would not help. - The same time performance would be observed if each of the N cells merely sent O(log N) bits of data to another cell, and repeated the process O(log N) times. This observation, coupled with
UPPER BOUNDS
	0(l)	-I
PAGE 104	A COMPLEXITY THEORY FOR VLSI

Chapter 3’s area-time tradeoff for the DFT, leads to the first theorem in the following section.

4.3.4 Area bounds for the shuffle-exchange graph

This subsection presents upper and lower bounds on the area of a shuffle-exchange graph, when it is embedded in the plane according to the rules of Chapter

2.

Theorem 9: At least ~2(N24og2N) units of area are required to embed a shuffle-exchange graph in the plane under Assumptions Li through L8.

Proof Under the lower bound model of computation, a communication graph with N unit area nodes could compute an N-element FF1 in time T = 0(log2N), if the nodes are connected in the shuffle-exchange pattern. Each node could do a multiply-add step in 0(log i’~ time, the time it takes to shift a word into or out of a node in bit-serial fashion).

Since any communication graph computing the FF1’ must satisfy AT2 = Q(’N2log2N) by Theorem 11, this particular graph must have area A = ~N2/log2N,). 0.

Corollary 10: The average length of the edges in a planar embedding of the shuffle-exchange graph is ~N/log2N).

Proof Each node of a shuffle-exchange graph has degree four, so there are 0(N) edges in an N-node graph. The nodes themselves take up only 0(N) area, so the total area of ~2(N 2/log 2N) must be due to the edges alone. 0

The following theorem is a constructive upper bound for embedding the shuffle-exchange graph in the plane. It is optimal to within a factor of 0(log3”2N), judging from the result of the preceding theorem. Closing the remaining gap between the upper and lower bounds is an open research problem.3

3Reccntly, Dan Hoey and Charles Leiserson of C-MU [Hoey 80] have produced an O(N 2/log N) embedding of the shuffle-exchange graph, narrowing the gap between the upper and lower area bounds to 0(log N).
UPPER BOUNDS	PAGE 105

Theorem 11: A shuffle-exchange recirculation network for N/2 cells can be laid out in 0(N2/log 1”2iv) area, if each cell occupies an 0(1) by 0(log 2N,) rectangle.

Prooj? preliminary remarks. As described in the circuit construction of Subsection 4.3.3, cell number i corresponds to two nodes in an iV-node shuffle-exchange graph, nodes 2i and 2i+ 1. Placing two cells into one node in this way has the advantage that exchange connections are local to the nodes. The remainder of the proof deals with the problem of arranging the nodes to minimize the length of the ~hufflc connections.

If node indices are expressed as binary numbers of log N bits each, a shuffle connection exists between nodes 1 and (‘21+ L2i/NJ) mod N. Note that this last functional form corresponds to an end-around left shift. Shuffle connections thus connect nodes with the same number of ‘1 ‘bits in the binary representation of their indices.

This observation suggests a partition of the N/2 cells into log N equivalence classes, or neighborhoods. Cell I and cell j are in the same equivalence class if I and] have the same number of ‘1’ bits in their binary representation. Let Bk denote the set of cells with k ‘1 ‘bits.

It is easy to verify that shuffle connections link cells in Bk only with other cells in Bk and with cells in Bk~/ and Bk+i. Consider the even-numbered node in cell I of class Bk, that is, node 21. Its shuffle connection must be to another node with exactly k ‘1’ bits in its index. The only nodes of that type are the even-numbered nodes in class Bk and the odd-numbered nodes in class Bk~/. A symmetrical argument shows that the odd-numbered nodes in Bk connect to odd-numbered nodes in 8k and to even-numbered nodes in Bk+,.

Clustering cells by their neighborhoods helps limit the length of the wires implementing the shuffle connections. Unfortunately, the neighborhoods are rather large, for there are only logNneighborhoods and N/2 cells.
PAGE 106
A COMPLEXITY THEORY FOR VLSI
The construction. Place the cells in one long horizontal line, grouping them by neighborhood. Orient the cells so that the connections to even-numbered nodes point upwards if they are in even-numbered equivalence classes, downwards otherwise. As indicated in Figure 4-17, the shuffle connections have been localized into (log N) +1 disjoint regions, one for each gap in the sequence (B0, B1, . . . B~q0g N) —
	1	I
B1	B2
Figure 4-18: Embedding of the shuffle-exchange connections
(N= 16).
The shuffle connections for (Bk, Bk+J) can be laid out in a rectangular region O(/Bk/ + /Bk+ 1D wide and O(/Bk/ + /Bk+ 1/) deep. The width is due to the 0(1) width of the /Bk/ -i- /Bk+ // cells involved in the shuffle connections of this neighborhood. The depth comes from the /Bk/ + /Bk+ ~,/ wires implementing the connections. Each wire is assigned one unit of depth, so that it can run an appropriate horizontal distance without interference.
CONNECTIONS
CONNECTIONS
	I   I	_~___j	j	II

B0
The number of cells in Bk is easily counted. It is just the number of cell indices
UPPER BOUNDS	PAGE 107

that have k 1’ bits in their binary representation. There are N/2 cells, and ~‘logA9—1 bits in each cell index, so that

(logt’/— l’~
	Bk= ~	k 1.	(4.7)

The largest Bk is thus B~~og iv)/2j’ which has size 0 (N/log 1”2N). The largest neighborhood is (B[~ogNy2j ~Bj~~l001\.~9/2j +1), which may contain wires as long as 0 (N/log 1”2A9.

The entire layout fits in a rectangular legion 0(’N,~ wide and 0(’N/log ~“2N,) deep. The width of the layout is due to the cell width. The depth is mostly due to the size of the largest neighborhood, since cell depth is asymptotically negligible by comparison. 0

Theorem 12: An N-element FF1 can be performed in A = 0(N 2/log l/2~y,~ and T = 0(log2iV~) using a circuit based on the shuffle-exchange recirculation pattern.

Proof Immediate from Lemmas 8 and 11. 0

The [ollowing corollaries indicate that the shuffle-exchange-based FF1 circuit is nearly nearly optimal under the AT2 metric, for it is only 0(log3”21\9 from the optimal performance of AT2 = f2(N2log2N,.). 1-lowever, this same circuit is far from optimal under the AT2X metric for x <1, since it is 0(N1 xlog2x 1”2N,) from the optimal AT 2x = Q(’iVt + Xlog 2xjy,~ 4

Corollary 13: AT2 = 0(’N21og7”2i\9 for the N-element FF1’ on a shuffle-exchange-based circuit of Theorem 12.

Corollary 14: AT2X = 0(N2log4X~~”2N) for the N-element FF1’ on a shuffle-exchange-based circuit of Theorem 12.

The discussion of Fourier transformation methods is now complete. The next section deals with sorting on the mesh and the shuffle-exchange connections.

4Recently, Preparata and Vuillemin [Pieparata 79J have devised a layout that ou~erfoçms the shuffle-exchange-based FFi design described above. Their layout has an area of O(N /Iog zi\~) and would take O(log 2N~ time to compute a Fourier transform, if the multiply-add cell of this thesis were used a its implementation. Their construction is thus within a constant factor of the lower bound on AT2 cost.
PAGE 108	A COMPLEXITY THEORY FOR VLSI

4.4	VLSi implementations of sorting

Before reading this section, the reader is advised to review the description of the bitonic sorting network contained in the latter part of Section 4.1.

Subsection 4.4.1 describes the bitonic sorting algorithm as it applies to a VLSI circuit with N/2 comparison-exchange cells connected by a shuffle-exchange recirculation network. The construction of the comparison-exchange cell is covered in Subsection 4.4.2. Finally, Subsection 4.4.3 gives a VLSI implementation of the bitonic sort on N cells in a mesh pattern.

4.4.1	Sorting on shuffle-exchange connections

The shuffle-exchange connections are nearly as well-suited for sorting as they are for Fourier transformation: This should not be surprising, for the N-element bitonic sorting network is very similar to the N-element FF11’ network.

The same approach used to perform an FF1 on iV/2 cells with shuffle-exchange interconnections can be used to perform a bitonic sort, as shown by Stone [Stone 71]. This subsection adapts his circuits to the VLSI model of computation.

The time taken to sort N elements on a shuffle-exchange-based circuit is bounded by the following lemma.

Lemma 15: An N-element sort can be performed on N/2 cells interconnected with a shuffle-exchange recirculation network in time T =0 ((log 2N)IR + (log 2N)tc), if it takes tR units of time to perform a routing step and tc units of time to perform a comparison-exchange step.

Proof Refer to Figures 4-4 through 4-7 for the construction of the hitonic sorting network. The bottom half of Figure 4-6 forms an N-element bitonic merger, which is isomorphic to an N-element FF1’ network. The reader may verify this by comparing the bottom three rows of Figure 4-5 with Figure 4-2.

Note that successive rows of these networks specify distance N/2, i’J/4, . . . , 1
UPPER BOUNDS	PAGE 109

routings. By Lemma 8, these bottom rows can be simulated in time O(’(’logN,)t~ + (iogN)t~), where the comparison time tC takes the place of’ the multiply-add time tM of the FF1 algorithm.

The top half of the bitonic sorting network is formed recursively from two half-sized sorting networks. As in the case of the full-sized network, the last (log N,)—] rows of these half-sized networks can be specified by a geometrically decreasing set of roLitings: distance 7V14, N/8, ..., 1. Note that these two networks are contained side-by-side in the last (log N,~—1 rows of an N-element Fourier transform network. Again by analogy with the Fourier transform circuit, a total of 0~”(log N)tR + (log N,)tc) time is sufficient to simulate these rows on a shuffle-exchange network, if a null comparison-exchange is performed after the (seemingly unnecessary) distance N/2 routing of the first step of’ the FF1 algorithm. Actually, this routing is not unnecessary, for it does result in a net movement of data among the cells, in preparation for the distance N/4 routing.

Continuing with the recursive constfuction of the bitonic sorting network, the top halves of the two half-sized sorting networks are themselves formed of four quarter-sized sorting networks. The routings of the last (logN)—2 rows of these quarter-sized networks are distance N/8, N/16, .. ., 1. Once again, the FF1’ algorithm can be used to simulate these routings in 0((log N)tR + (log N)tc time, if two null comparison-exchanges are followed by (log N) —2 comparison-exchange steps.

The recursive construction is complete at a depth of (log Nj—i. The last network

in the construction is a 4-sorter formed of two 2-sorters and one 4-merger. The 2-

sorters are identical to 2-mergers, so the entire construction may be visualized as

N/2 2-mergers above N/4 4-mergers above N/8 8-mergers above. . . one N-merger.

Each of the (log N) levels of mergers can be simulated in 0((log T\9tR + (log N~)tc)
time, for total time 0(’(iog 2N,~tR + (log 2N,)t~). 0

The preceding lemma has perhaps obscured the simplicity of the sorting process on a shuffle-exchange network. A sort consists of log2N passes through the network,
PAGE 110	A COMPLEXITY TFIEORY FOR VLSI

where a (possibly null) comparison-exchange operation intervenes between each pass. The operations required of a cell are thus very simple. During each stage of computation it must do one of three things: a null comparison-exchange,

Yl 4—XI
	(4.8)
a “~—“ comparison-exchange,

Y1 ~— max(X1, X2)
	~T2 ;nin(X1, X2),	(4.9)
or a “—p” comparison-exchange,

Y1 ~— ,nin(X1, K,)
	max(X1, X2). (4.10)
The next subsection describes the construction of a comparison-exchange cell that is capable of performing these operations.

4.4.2 The comparison-exchange cell

Figure 4-19 illustrates a construction of a comparison-exchange cell that can fit into either an 0(log N) by 0(log N) area or into an 0(1) by 0(’log 2N) area.

The serial comparator logic at the top of the figure can be built with 0(j) gates in a straightforward manner, as long as the inputs are presented most-significant bit first [Moravec 79]. This logic is responsible for putting the larger or smaller of the two inputs X1 and X2 onto the output lines Y1 and Y2 the “direction” of the comparison-exchange is dictated by the two-bit state vector stored in the shift registers below. For concreteness, the state-vector assignment may be specified as

Ibliows:
	00	Y1 X1,	~-	(4.11)
	10	Y1 ~— tnax(1X1, X2), Y2 ~— min(X1, X2), and	(4.12)
	ii	~	~— min(X1, X2), Y2 ..- max(X1, X2).	(4.13)

Since the sorting algorithm is complete after log2N passes through a shuffle-
UPPER BOUNDS	PAGE 111

CONTROL

PROGRAM

(2 LOG2 N BITS)

2[~~
COMPARATOR

~TOL~YOXIY

Figure 449: The comparison-exchange cell.

exchange based recirculation network, 2log2N bits of state vector suffice to define all operations of the comparison-interchange cell. The shift registers holding the state vector should be clocked once every ~ time units, if t~ is defined (as in the previous subsection) as the time taken for a comparison-exchange step. The value of t~ 0(log N), since each bit of the inputs is sent to one of the outputs after 0(1) delay. (Note that this performance is possible only if the most-significant bits of the inputs are sent first.)

The discussion above is summarized by the following lemma and theorem.

Lemma 16: The comparison-exchange cell of Figure 4-19 has a comparison-exchange time t~. of 0(log N) and an area of 0(log 2N). Its aspect ratio may be either square or 0(1) by 0(log 2iv) depending on how the shift registers are “folded.”

Theorem 17: An N-element sort can be performed in 0(N24og1~”2N) area and 0(log3N) time on N/2 comparison-exchange cells arranged in a shuffle-exchange pattern.

Proof By Lemma 15, an N-element sort can be done in time T= 0((log2N)t~ + (log2N)t~) on N/2 cells connected in a shuffle-exchange
PAGE 112	A COMPLEXY~1 THEORY FOR VLSI

pattern. The unit routing time tR is the same as it was in the FF1 circuit of Lemma 8, since the words still have 0(log iV) bits. Thus 1R = 0(log N), and t~ = 0(log N) by the preceding Lemma. Finally, the embedding of Subsection 4.3.4 may be used to give an area bound of 0(1N2/log “2N~). 0

The following corollaries are immediate.

Corollary 18: AT2 = 0(N21og11”2N,) for an N-element sort performed on N/2 comparison-exchange cells connected with a shuffle-exchange recirculatic ti network.

Corollary 19: AT2X = 0(N2log6X~/’21V) for an N-element sort performed on N/2 comparison-exchange cells connected with a shuffle-exchange recirculation network.

The shuffle-exchange-based sorting circuit is thus nearly optimal under the AT2 metric. It is only 0(log7”2,) from the optimal performance of AT2 = ~2~’N2log2N~. However, this same circuit is far from optimal under the AT2X metric (unless x = i), for it is 0(Nl_xlog4~_~/2N) from the optimal AT2X = (N~~log2’N).

4.4.3	Sorting on mesh connections

This subsection shows how the bitonic sorting algorithm can be used to sort N elements on N comparison-exchange cells arranged in a mesh. The same approach is used as in the other recirculating constructions of this thesis: each stage of computation on the N cells corresponds to one row of the bitonic sorting network. Since there are 0(log2N) rows in the sorting network, a total of 0(log2N) comparison-exchange steps must be performed. However, the total number of unitdistance routing steps is variable, depending on the way in which the data is distributed among the cells during the course of the computation.

To minimize the number of routing steps, the cells should be indexed in “shuffled row-major order” [Thompson 77]. In this scheme, a cell Is given the n-bit binary index b,, b~~2 l~1 b,,~2 — / —2 n/2— 2 3 b~/2 3~ . . b~~2 + 3b3 b,,~2 + 2b2 b,~2 + ~ b1 if its natural “row-major” index would be b~~21b,12b,1_3. . . b,~2+3b,~2+2
UPPER BOUNDS
PAGE 113
b,v2 b,~2_j b,v2_2b,v2_3... b3b2b1 (think of printing each of the hits of a row-major index on a playing card, then “shuffling” the top half of the deck b,~ b~ — / — _3 ..~ 1~n/2 +3 ~~n/2 +2 n/2 + ~ with the bottom half b,~2 b,~,21 b,.L,/2 —2 b~2_3... b3b2b1). Figure 4-20 illustrates the row-major and shuffled row-major indexing of a mesh with N 16 cells. Note that the cell in the lower left corner has row-major index L2w = 11002 and hence shuffled row-major index lOjo = 10102.

Figure 4-20: Row-major and shuffled row-major indexing schemes
for the 16-cell mesh.

The shuffled row-major indexing scheme has two important properties for sorting algorithms. First of all, it is similar to the row-major indexing scheme in that it is simple to move data between pairs of cells whose indices differ only in the kth bit. In general, 2~ horizontal or vertical routes will move data between all such pairs of cells. For example, a distance-2 routing is two horizontal steps in the row-major indexing scheme and one vertical step in the shuffled row-major indexing scheme. A distance-8 routing is two vertical steps in either scheme. (It should be obvious that any indexing scheme obtained by permuting the bits of the row-major cell indices must preserve this property. However, it is difficult to verify the property by direct examination of the linear form of the shuffled row-major indexing scheme in Figure 4-21.)

A second property of the shuffled row-major indexing scheme distinguishes it
from the row-major indexing scheme, a property that leads to its improved time performance on the bitonic sort The number of routing steps required to do a distance-23 routing in the shuffled row-major indexing scheme is never more than
PAGE 114
A COMPLEXITY THEORY FOR VLSI
the number of steps required for a distance~2i+~ routing. (Compare this with the row-major indexing scheme, in which a distance-N h/’2/2 routing is N 1/2/2 horizontal steps but a distance-N1”2 routing is only one vertical step.) Since there are many more short routings than long routings in the bitonic sorting algorithm, this property of monotonicity makes the shuffled row-major indexing scheme preferable to the row-major indexing scheme. (It turns out that the difference between the two schemes is asymptotically significant. The shuffled row-major indexing scheme is a factor of 0(log N) faster than the row-major indexing scheme.)

A recirculating bitonic sorting algorithm is obtained from the N-element bitonic sorting network and the linear form of the shuffled row-major indexing scheme for the N-cell mesh shown in Figure 4-21. Each row of the network is simulated in turn by the N cells. Connections between rows are simulated by data routings among the cells. The following lemma bounds the time performance of this algorithm.
Figure 4-21: The linear form of the 16-cell mesh numbered by the shuffled row-major indexing scheme.

Lemma 20:	An N-element sort can be performed on N cells interconnected with a mesh-based recirculation network in time T = 0(N “2tR + (log 2N)tc), if it takes tR units of time to perform a unit-distance routing step and tC units of time to perform a comparisonexchange operation.

Proof (See [Thompson 77].) The time required to do a distance-2 IC routing on the shuffled row-major indexing scheme for the N-cell mesh is just 2 I1~~’2ltR. This observation may be verified easily for the case N = 16 of the right-hand mesh of
UPPER BOUNDS	PAGE 115

Figure 4-20. In the general case, it follows as a consequence of the way in which horizontal and vertical routings alternate in an ascending sequence or routing distances: distance-20 is one horizontal roure, distance-2 ~‘ is one vertical, route, distance-22 is two horizontal routes, distance-23 is two vertical routes, etc.

The time required for a 2k~elernent merge (see Figure 4-5) is less than 8*2L 1,)/2j tR. This bound is obtained from the fact that a 2 kelement merge requires two distance~2k_t routings, two distance-2~<2 routings, . . . , and two distance-I routings. The first four of these routings take at most 4*2V~(_1~)~’2itR time, and the times required by each of the succeeding groups of four routings form a geometric series with ratio one-half. The entire sum is thus less than twice that of the leading term, or 2*4*2L(~ 1)/2j tR.

The time required for a 2 k.element sort (see Figure 4-6) on the shuffled row-major indexing scheme of the N-cell mesh is less than 32*2 L0~_1~~~’2itR. To verify this, note that a 2 &elenient sort is formed of a 2 k..element merge, preceded by two 2’~~-element merges running in parallel, preceded by four 2~2-element merges,.

preceded by N/4 four-element merges, preceded by N/2 two-element merges (these are the same as the two-element sorts that are actually specified in the construction). The first two of these together take less than 2*8*2[(’k — /)/~j tR, by the bound of the preceding paragraph. Tile time taken by each succeeding pair of merges form a geometric series with ratio one-half. The entire 2 k..element sort thus takes less than 2*2*8*2I.~_1~~2itR. (A more rigorous argument tightens this bound to i4*2IC~/2tR for even values of k [Thompson 77].)

The lemma is now almost proved, since an N-element sort (N = 2~IC) takes routing time 0(2 ‘~“2tR) = 0(N IR). The comparison-exchange steps take time 0(log2Nt~), for there are 0(log2N) rows in the complete N-element bitonic sorting
network. 0	-

The performance of an N-element mesh-based sorting circuit can now be described.
PAGE 116	A COMPLEXITY THEORY FOR VLSI

Theorem 21: An N-element sort can be performed in 0(N log2N) area and 0(N1”2loglog N) time on N comparison-exchange cells arranged in a square mesh.

Proof The comparison-exchange cell of Lemma 16 and Figure 4-19 has a comparison-exchange time t~ of 0(log N) and an area of 0(log 2iv,). If N of these are arranged in a mesh, they will occupy a total of A 0(N log 2N) area. Attaching horizontal and vertical transceivers to each cell, as in Figure 4-11, will not affect the asymptotic area requirements, but will result in a data routing time tR of 0(loglog N). (As indicated in the discussion on page 92, tR could be reduced to

0(1) by suitable changes in the upper bound model of computation.) Total time for an N-element sort is thus T = 0(N 1”2loglog N), by Lemma 20. 0

Note that this sorting circuit takes up as much area and is just as fast as the mesh-based FF1 circuit of Subsection 4.3.2. As indicated by the following corollaries, it is very nearly optimal under the AT2 metric of Chapter 3, for it is at most O(log/og2lV) from the optimal AT2 = Q(N2log2N~ It is also nearly optimal under the AT2X metric, since it is at most 0(loglog2xN) from, the optimal value of AT2X ~(N1~ xlog2xN).
Corollary 22: AT2 = 0(N2log2N loglog2N) for the N-element mesh-based sorting circuit.
Corollary 23: AT2X = o(/N1+xzog2Nloglog2XNI~ for the N-element mesh-based sorting circuit.

4.5	Constant factors in the VLSI implementations

This thesis has demonstrated the existence of area-time tradeoffs in VLsI design, at least for chips that solve asymptotically large problems. It is now time to find out whether such tradeoffs will be available to designers in the foreseeable future. In other words, is a design with one hundred million transistors large enough for asymptotic analysis? The answer seems to be “almost”: among designs that solve ten thousand element VETs, the asymptotically “fast but large” shuffle-exchangetype chips are indeed faster but also slightly smaller than their “slow but small” mesh-type counterparts.
UPPER BOUNDS	PAGE 117

The arithmetic circuitry will be examined first. The multiply-add cell of Figure 4-13 or 4-17 can be built in about ~ units of atea, if the word length is sixteen bits. This allows ample room ~br two 32-bit carry-save adders, a few hundred gates of control logic, and a few hundred bits of storage for constants. Accordingly, up to ten multiply-add cells would lit on a present-day chip with 10~ units of area. By the year 1990, something like ~ cells could be formed on the 108 units of area available on a single silicon wafer. Such a circuit would perform a ten thousand element FF1.

The interconnections between the cells have yet to be considered. The mesh-type pattern poses no difficulties. Each of the multiply-add cells will be separated from its neighbor by a sixteen-wire bus (see Figure 4-11). Assuming that the 10 4-area cells are 102 units on a side, the width of the bus is almost negligible.

A ten thousand element FF1’ will also be feasible on a shuffle-exchange-type design. Here five thousand multiply-add cells should be laid out as tall, thin rectangles in a few rows at the bottom of a wafer (see Figure 4-17). The exchange connections are to nearest neighbors, and thus take up little area. The shuffle connections can be routed upwards to some unused horizontal “channel,” across in this channel, then down to the appropriate cell. Since there are i04 horizontal channels on a wafer of 108 units of area, all shuffle connections can be made in this way.

The asymptotic size advantage of the mesh-based design is not apparent in chips of this size. In fact, the shuffle-exchange-type chip would actually be a little smaller, because it uses only half as many cells to perform a ten thousand element FF1’. Furthermore, the routing control logic is much simpler for the shuffle-exchange circuit than for the mesh circuit, since the shuffle-exchange circuit uses the same recirculation pattern after each multiply-add step.

Mesh-type designs might become attractive from the standpoiiit of size if millioncell chips are ever feasible. One million multiply-add cells could be arranged in a
PAGE 118	A COMPLEXITY THEORY FOR VLSI

mesh-type pattern in 1010 units of area. However, shuffle connections among five hundred thousand cells would occupy 1011 square units of wiring in the best embedding known to the author.

As mentioned above, the shuffle-exchange design is a little faster than the mesh design for ten thousand element FFTs. In either case, there are log N 13 stages of computation in the FF1 algorithm. Each multiply-add step takes about 102 clock periods, due primarily to the two 16-bit by 32-bit multiplications. Total multiply-add time for either design is thus ~ clock periods or a few microseconds, if a 5 nS clock is used ~Mead 80].

The total routing time on a mesh-type design also turns out to be a few microseconds. By Equation (4.4), there are 4(102_i) unit distance routing steps in a ten thousand element FFT. Allowing two or three clock pulses per unit route ‘for synchronization and buffering, routing takes /0~ clock pulses or a few microseconds.

Routing on the shuffle-exchange design is somewhat faster than on the mesh-type design. In a ten thousand element FF1’, there are 13 routing steps. Each step is a bit-serial transfer of 16 bits. Total routing time is thus several hundred clock periods or about one microsecond.

The speed advantage of the shuffle-exchange design will increase with the size of the FF1’, as predicted by the asymptotic analysis. If a million-element FF1’ ever became feasible, the mesh-type design would perform 4(/03 — 1) routing steps, while the shuffle-exchange design would do only several hundred steps. (The comparison is between 4N1”2 and log2N.)

Therefore, ten thousand element FFT designs are just large enough for the asymptotic time analysis of this thesis, but not quite large enough for the area
analysis.	-
CONCLUSION	PAGE 119

Chapter 5
Conclusion

The main contributions of this thesis fall into four areas.

1.	A new model of computation is developed, suited to the study of the area and time performance of VLSI chips.

2.	A lower bound is obtained on the area A occupied by a graph when embedded in the plane, in terms of its minimum bisection width w. For a k-level planar embedding, A >

3.	The informational complexity of a function is defined, determining the difficulty of computing that function on a VLsI chip.

4.	Nearly tight upper and lower bounds are derived on achievable area-time performance for sorting and Fourier transformation, as summarized in the list and table below.

• An N-element sorting or Fourier transformation problem can be
solved on a chip of area A = 0(Nlog2N) and time
T = 0(N “2loglog N), using a mesh-based interconnection
scheme. This performance is nearly optimal for any AT2X metric,
0< x< 1.

•	An N-element Fourier transformation problem can be solved on a chip of area A = 0(N 2/log 1~”2N,) and time T = 0(iog2N,), using an interconnection scheme based on the shuffle-exchange graph. This performance is optimal under the AT2 metric.

•	An N-element sorting problem can be solved on a chip of area A = 0(N 2/log 1”2N) and time T = 0(log 3N), using an interconnection scheme based on the shuffle-exchange graph. This performance is nearly optimal under the AT2 metric.
PAGE 120		A COMPLEXITY THEORY FOR VLSI
	AT2	       AT2X

Upper bounds:
Mesh-based FF1,	0(N 2log 2N loglog 2N~	0(N’ + xlog 2N loglog 2xN~
Mesh-based sort	0(N 2log 2N loglog 2N)	0(N1 + xlog 2N loglog 2xN)
Shuffle-exchange FF1	0(N2log 7/2~y)	0(N21og4X_ ~“2N)
Shuffle-exchange sort	0(N 2log h1~’2J~~)	0(N 2log 6x —
Lower bounds:
(For any design)	 c2(’N 2log 2N)	~2(N’ + xlog 2xN)

Table 5-1: Area-time complexity of sorting and Fourier transformation. Several avenues of research have opened up as a result of this thesis.

The model of computation could be expanded to cover other possible VLSI technologies, such as Josephson junctions and magnetic bubble devices. This would permit formal development of upper and lower bound results for these technologies. Other modifications to the model would handle pipelined designs (page 84) and take full advantage of scaling (page 92).

Other problems should be studied besides sorting and Fourier transformation. It should be possible to derive fairly tight upper and lower bounds for matrix multiplication, integer multiplication, Gaussian elimination, and transitive closure. ~ The embedding of the shuffle-exchange graph described in Subsection 4.2.2

5Lower bounds were obtained for several of these problems as this thesis was being written. Savage [Savage 79bJ proved lower bounds on boolcan matrix multiplication and Gaussian elimination, using the VLSI model of computation. Brent and Kung [Brent 79] and Abelson [Abelson 80hJ derived lower bounds for integer multiplication. Brent and Kung obtained a slightly more powerifil result, for they were able to relax assumptions L6 and L7 of Chapter 2. In their model, inputs and outputs did not have to be contained on the chip; however, each input is available at its input port only once. They were able to prove that nearly all of the input bits had to be on the chip at the same time. The rest of their proof technique is similar to that used in this thesis.
CONCLUSION	PAGE 121

deserves careful study. An improved result could tighten the gap between upper and lower bounds for designs using that interconnection pattern. (Dan Hoey and Charles Leiserson have obtained an O(N2/logN) area embedding for the shuffle-exchange graph for the case that N = 22’~ {Hoey 80]. However, there is still an O(iog N) gap between the upper and lower bound results.)

The definition of informational complexity could be improved. As it stands, it is demonstrably weak on such functions as “equality” and “comparison” (see page 66), despite its apparent strength on sorting and Fourier transformation. The problem seems to lie in its assumption of optimal coding (page 62).

Finally, the model of computation might be enhanced. It currently treats information as an imperishable item: in the view of the model, information cannot be destroyed, it merely flows from one side of the chip to another. This view is adequate to model the (nearly) one-to-one mappings of sorting and the DEl. However, it is sure to fail on exponentially hard functions. Somehow, the computation of a hard function must involve more than sending the inputs from one side of the chip to the other, yet this is enough to compute any function according to the present model.

Acknowledgements

To H. T. Kung, my thesis advisor, for his generous help and gentle guidance:

To Jon Bentley, for his patience in teaching a (sometimes ungracious) student to improve his technical writing, and for his suggestions on Theorems 3-1 and 3-2:

To Carver Mead, for his infectious vision of VLSI design:

To Michael Shamos, for his constructive feedback on the first versions of the VLSI model of computation:

To Bob Sproull, for trying to keep inc honest in my descriptions of VLsI circuitry:
PAGE 122	A COMPLEXITY THEORY FOR VLSI

To all of the above, for serving on my thesis committee:

To Leo Guibas and the staff of Xerox PARC, for their support and advice during the earliest phases of this research:

To James B. Saxe and H. Wozniakowski, for their help with the original proofs of Lemmas 8 and 9:

--And last, but certainly not least-To Charles Leiserson, for his ideas on VLsI modeling and his help on Theorem 2:

Thank you.
CONTROL PROGRAM FOR CELL 0 OF A MESH-BASED FFT CIRCUIT	PAGE 123

Appendix A
Control program for cefl 0 of a mesh-based FFT Circuit
	Timer	Control	(‘omment
			V registers contain initial data
logN	--	_ V	Load X0 register from V
			(This step omitted for cell i, i <IV/2
			i.e., omitted if = 1)
				Begin stage 1
(N 1~’2/2) loglog N	--	UP		Get data from cell N/2
				(Cell i, i _ N/2 will receive “garbage”
				during this routing, hence will compute
				garbage during this step)
log N	--	  —	V	Load register X1
—log2N		M-A		Multiply-add: Y0 ~- X0 + a O~
				         Yl ~X0—a0X1.
				(Other cells use different a~ values)
logiV	--	V.—	Y1	Send Y1 down to cell N/2
(‘V ‘~2/V loglog N	--	DOWN
logN	--	  —	V	LoadX0
				End stage 1
PAGE 124	A COMPLEXITY ThEORY FOR VLSI
			Begin stage 2
logN	--	V~-Y0
(N 1/2/4) loglog N	--	UP	Receive data from cell N/4
logN	--	X1 ~ V	LoadX1
			(Cell i, N/4 < I <N/2 and 3N/4 <I <N
			will compute “garbage” during this stage)
—log2N	a°	M-A
log N	--	V ~- Y1	Send Y1 down to cell N/4
(N ~“~/4) loglog N	--	DOWN
log N	--	  ~- V	End stage 2
			Begin stage 3
logN	--
(N 1/2/3) loglog N	--	UP	Receive data from cell N/S
logN	--
‘—log2N	a°	M-A
logN	--	V-.- Y1	SendY1 downtocellN/8
(N 1/’2/8) loglog N	--	DOWN
logN	--	 -.- V	End stage 3

(Stages 4 through (log N)/2 —1 not shown)
			Begin stage (log N)/2
logN ‘	--
1	--	UP	Receive data from cell N1”2 loglogN
logN	--	X~-V
~log2N	a°	M-A
log N	--	V.- Y1	Send Y1 down to cell N1”2 loglog N
1	--	DOWN
logN	--	X0— V	End stage (?ogN,)/2
			Begin stage (‘logN)/2 + I
log N	--	H ~— Y0	Note shift to horizontal routing
(N 1/2/2) loglog N	--	LEFT	Receive data from cell (N 1/2/2) loglog N
logN	--
-~log2N	a°	M-A
logN	--	H Y1	Send Y1 over to cell (N1”2/2,) loglogN
(N “'2/V loglog N	--	RIGHT
logN	--	X0-.--H	endstage(logN)/2+/
CONTROL PROGRAM FOR CELL 0 OF A MESH-BASED FFT CIRCUIT	PAGE 125

(Stages (log i~)/2 + 2 through
(log N) — I not shown)
			Begin stage (log N,~)
logN	--	H~Y0
1	--	LEFT	Receive data from cell I
logN		 ~— II
‘-‘-log2N	a°	M-A
log N	--	H Y1	Send Y1 over to cell I
1	--	RIGHT	End stage (log N)
logN	--	[I..- Y0	This step omitted for cell I, iodd
H registers contain transformed data
PAGE 126	A COMPLEXITY THEORY FOR VLSI

References

[Abelson 80a] Abelson, Harold.
Lower bounds on information transfer in distributed
computations.
Journal of the ACM 27(2):384-392, April, 1980.

[Abelson 80b] Abelson, Harold and Andreae, Peter.
Information Transfer and Area-time Tradeoffs for VLSI
Multiplication.
Communications of the A Clvi 23(1), January, 1980.

[Agarwal 75]	Agarwal, Ramesh C. and Burrus, Sidney C. Number theoretic transforms to implement fast digital
convolutions.
Proc. IEEE 63(4):550-560, April, 1975.

[Aho 741	Aho, Alfred V. , Hopcroft, John E. and Ullman, Jeffrey D. The Design and Analysis of Computer Algorithms.
Addison-Wesley, 1974.

[Batcher 68] Batcher, K. E.
Sorting networks and their applications.
In AFIPS Spring Joint Computer Conference, pages 307-314. 1968.

[Bonneau 73] Bonneau, Richard J.
A Class oJFinite Computation Structures Supporting the Fast Fourier Transform.
Technical Report 31, Massachusetts Institute of Technology Project MAC, March, 1973.

[Brent 79] Brent, R. P. and Kung, H. T.
The Area- Time Complexity of Binary Multiplication.
Technical Report CM U-CS-79- 136, Carnegie-Mellon University, Computer Science Department, July, 1979.
(to appear in JAC’M).

[Cochran 67]	Cochran, William T. , Cooley, James W. , et al. What is the fast Fourier transform?.
IEEE Trans. on Audio and Electroacoustics AU-15(2):45-55, June, 1967.

[Cutler 78]	Cutler, M. and Shiloach, Y.
Permutation layout.
PAGE 127

Networks 8:253-278, 1978.

[Don ath 79] Donath, W. E.
Placement and average interconnection lengths of computer logic. IEEE Trans. Circuits and Systems CAS-26(4):272-277, April, 1979.

[Evans 79] Evans, Stephen A.
Scaling I 2L for VLSI.
IEEE Journal of Solid-State Circuits SC- 14(2) :318-326, April, 1979.

[Floyd 72] Floyd, Robert W.
Permuting information in idealized two-level storage.
In Raymond E. Miller and James W. Thatcher (editor),
Complexity of Computer Computations, pages 105-109. Plenum
Press, NY, 1972.

[Garey 74]	Garey, M. R. , Johnson, D. S. and Stockmeyer, L. Some simplified polynomial complete problems.
In Proc. 6th Annual ACM Symposium on Theory of Computing, pages 47-63. Assoc. Comp. Mach. , April, 1974.

[Grigoryev 76] Grigoryev, Y.
An application of separabili~v and independence notions for proving lower bounds on circuit complexity.
Steklov Mathematical Institute, Leningrad Branch, 1976, pages 38-
48.
~translation courtesy of J. E. Savage, Brown University).

[Hoey 80]	Hoey, Dan and Leiserson, Charles E.
A layout for the shuffle-exchange network.
In Proc. 1980 International Conf on Parallel Processing. IEEE Computer Society, August, 1980.

[Johannsen 781 Johannsen, Dave.
Hierarchical Power Routing.
Technical Report 2069, California Institute of Technology, October, 1978.

[Knuth 73]	Knuth, Donald. E.
The Art of Computer Programming: Volume 3.
Addison-Wesley, 1973.

[Leiserson 80]	Leiserson, Charles E.
PAGE 128	A COMPLEXITY THEORY FOR VLSI

Area-efficient graph layouts (for VLSI).
In 21st Annual Symp. on Foundations of Computer Science. IEEE Computer Society, October, 1980.

[Linnik 44] Linnik, U. V.
On the least prime in an arithmetic progression. I. The basic theorem.
Mathemateceskii Sbornik (N. S.) 15(57): 139-178, 1944.

[Lipton 77] Lipton, Richard J. and Tarjan, Robert E.
Applications of a planar separator theorem.
In 181/2 Annual Symp. on Foundations of Computer Science, pages
162-170.	IEEE Computer Society, October, 1977.

EMead 79] Mead, Carver and Rem, Martin.
Cost and performance of VLSI computing structures.
IEEE Journal of Solid-State Circuits SC-14(2):455-462, April, 1979.

[Mead 80]	Mead, Carver A. and Conway, Lynn A. Introduction to VLSI Systems.
Addison-Wesley, 1980.

[Mohsen 791 Mohsen, Amr M. and Mead, Carver A.
Delay-time optimization for driving and sensing of signals on high-capacitance paths of VLSI systems.
IEEE Journal of Solid-State Circuits SC-14(2):462-470, April, 1979.

[Moravec 79]	Moravec~ Hans P.
Fully Interconnecting Multiple Computers with Pipelined Sorting Nets.

IEEE Trans. Comput. C-28(10) :795-798, October, 1979.

[Moshell 761 Moshell, Michael and Rothstein, Jerome.
Parallel recognition of patterns: insights from formal language theory.
In Proc. 1976 International Conf on Parallel Processing, pages
222-229.	IEEE Computer Society, August, 1976.

[Nicholson 71] Nicholson, Peter J.
Algebraic theory of finite Fourier transforms.
Journal of Computer and System Sciences 5:524-547, 1971.
PAGE 129

[Paterson 70] Paterson, M. S. and Hewitt, C. E.
Comparative schematology.
In Project MAC Conf on Concurrent Systems and Parallel Computation, pages 119-127. Massachusetts Institute of
Technology, June, 1970.

[Pease 68] Pease, Marshall C.
An adaptation of the fast fourier transform for parallel processing.
Journal of the ACM 15(2):252-264, April, 1968.

[Preparata 79] Preparata, Franco P. and Vuillemin, Jean.
The Cube-Connected Cycles: A Versatile Network for Parallel Computation.
In 20th Annual Symp. on Foundations of Computer Science, pages
140-147.	IEEE Computer Society, October, 1979.

[Rosenberg 79] Rosenberg, Arnold L.
On Embedding Graphs in Grids.
Technical Report RC 7559 (#2668), IBM T. J. Watson Research Center, February, 1979.

[Savage 77] Savage, John E. and Swami, Sowmitri.
Space-Time Tradeoffs in the FF7’ Algorithm.
Technical Report TRCS-31, Brown University, August, 1977.

[Savage 79a] Savage, John E. and Swamy, Sowmitri.
Space-time tradeoffs for oblivious integer multiplication.
In 6th Colloq. on Automata; Languages and Programming. European Assoc. for Theoretical Computer Science, Springer-Verlag, July, 1979.

[Savage 79b] Savage, John E.
Area- Time Tradeoffs for Matrix Multiplication and Related Problems in VLSI Models.
Technical Report CS-SO, Brown University Department of Computer Science, August, 1979.

[Seitz 79] Seitz, Charles L.
Self-timed VLSI systems.
In Caltech Conference on VLSI, pages 345-354. Caltech Computer Science Department, January, 1979.
[Shannon 49]	Shannon, Claude E. and Weaver, Warren.
	The Mathematical Theory of Communication.
PAGE 130	A COMPLEXITY THEORY FOR VLSI

Univ. of Illinois Press, Urbana, Ill. , 1949.

[Stevens 71] Stevens, J. E.
A Fast Fourier Transform Subroutine for Illiac IV.
Technical Report, Center for Advanced Computation, Illinois,
1971.

[Stone 71] Stone, Harold S.
Parallel processing with the perfect shuffle.
IEEE Trans. Comput. C-20(2):153-161, February, 1971.

[Sutherland 731	Sutherland, Ivan E. and Oestreicher, Donald. How big should a printed circuit board be?.
IEEE Trans. Comput. C-22(5):537-542, May, 1973.

[Thompson 77] Thompson, C. D. and Kung, H. T.
Sorting on a mesh-connected parallel computer.
Communications of the AG7vI 20(4):263-271, April, 1977.

[Tompa 78] Tompa, Martin.
Time-space tradeoffs for computing functions, using connectivity properties of their circuits.
In Proc. /0th Annual ACiVI Symp. on Theory of Computing, pages
196-204.	Assoc. Comp. Mach. , May, 1978.

[Valiant 76] Valiant, Leslie 0.
Graph-theoretic properties in computational complexity.
Journal of Computation and Systems Sciences 13:278-285, 1976.

[von Neumann 66]
von Neumann, J.
The Theory of Self-Reproducing Automata.
Univ. of Illinois Press, Urbana, Ill. , 1966.

[Wagstaff 79] Wagstaff, Samuel S.
Greatest of the least primes in arithmetic progressions having a given modulus.
A’fathematics of Computation 33(147): 1073-1080, July, 1979.

[Winograd 761 Winograd, S.
On Computing the Discrete Fourier Transform.
Technical Report RC 6291 (#27013), IBM T. J. Watson Research Center, November, 1976.
[Yao 79]	Yao, Andrew.
PAGE 131

Some complexity questions related to distributive computing.
In Proc. 11th Annual ACM Symp. on Theory of Computing, pages
209-213.	Assoc. Camp. Mach. , April, 1979.
SECURITY cLASSrC~~3~ OF ~ P A~E ~ r)~,.C F-u.rd)
REPORT DOCU~,E~TATl0N PAGE
2. GOVT ACCESSION P~O. 3. RECIPIENTS CATALOG p,~MaER	
LREPORT NUMbER

CMU-CS-80-140	OF REPORT & PERIOD COVERED	
4.	TITLE (and SubtItle)

A COMPLEXITY THEORY FOR VLSI	Inter
6.	PERFORYING ORG. REPORT NUMBER	
	8.	CONTRACTORGRANTNUM3ER(I)	
7.	AUTHOR(s)

C.D. THOMPSON

NA’.4E AND ADDRESS	N00014-76-C-0370

10.	PROGRAM EL.EI.4ENT. PROJECT. TASK	
9.	PERFORMING ORGANIZATION

C~rnegie-Me1lon University Computer Science Department pittsburgh, PA 15213			AREA&WORK UNIT NUMBERS

12. REPORT DATE	
II.	CONTROLLING OFFICE NAME AND ADDRESS

Office of Naval Research Arlington, VA 22217	AUGUST 1980	
	CLASS. (of this report)	
	~.	MONITORING AGENCY NAME & AQDRESS(I( dill eront from Controil4ng Office)
		                  this Report)	IS. SECURITY
	UNCLASSIFIED	-
IS.. DECLASSIFICATION OWNGRACN~	
	SCHEDULE	
IS. DISTRIBUTION STATEMENT (of

Approved for public release; distribution unlimited

.nt.ted ft~ Block 20. ii different from Report)	
17.	DISTRIBUTION STATEMENT (of the abstract	
18.	SUPPLEMENTARY NOTES

if
end identity by bloca nuo~b.r)	
19.	KEY WORDS (C< ,Cln.s. on ,.v.re. ai~to
	noc.atmtY
	if	end iti.ntitY oy block numb.t)	
20.	ABSTRACT (Continue ~s revere. silo	
I~r~ FORM
1.11) I JAN 73
EDITION OF 1 NOV 65 IS ODSOLETE S/N 0ZO2-O~4.6&0I I
UNCLAS S IFIED
SECURIT’! CL ~IFICAT10N OF THIS PAGE (When Oat. Zni.rod)