%* Last edited: Sep 5 02:44 1996 (misha) \chapter{Reconfigurable Bit-Parallel Architecture} This section describes the basic idea of RBP, provides an argument of its advantage over a bit-serial organization, describes the Abacus PE architecture, and some RBP arithmetic implementations. \section{The Basic Idea of RBP} The basic idea of RBP is the concatenation of several processing elements into a processing site. The advantages of the technique can be viewed from several angles. First, if an algorithm requires many data bits per pixel, then the silicon area of the ALU is small compared with total data area, and therefore adding a few more ALUs will improve performance linearly, with a tiny increase in total area. This interpretation assumes that all data is kept on chip and physically near the ALU. \mypsfigx{4in}{rbp-organization.ps}{RBP Organization}{rbporg}{A bit-serial organization compared to a reconfigurable bit-parallel one. Each of the RBP processors is also capable of acting as a bit-serial unit, if appropriate. } Alternately, RBP may be viewed as a method of adding the appropriate number of registers to a processing site to minimize the frequency of expensive off-chip accesses. The improvement in performance is due mostly to decreased stall time rather than additional ALU bits. \footnote{What really counts is that it's a variable-capacity register file --Carlin} \section{RBP Performance Model} This section quantifies the regime in which the RBP organization is superior to a bit-serial one. We assume that a processing site, be it a bit-serial PE or a group of RBP PEs, requires a certain amount of on-chip storage to operate without frequent off-chip memory accesses. If this requirement is not met, performance will degrade catastrophically due to the limited off-chip bandwidth. In the following discussion, let B be the number of bits in a data word; W, the number of words in the register file; V, the area of the non-memory overhead (ALU and network) component of the PE; and S, the number of cycles required by the bit parallel operation. Area measurements are normalized to the size of one memory bit. A bit-serial organization requires $B$ cycles to step through each bit of a data word and occupies $V+BW$ area. An RBP PS requires $S$ cycles and occupies $B(V+W)$ area. The silicon efficiency can be expressed as performance per unit area, or simply as $1/AT$. The ratio of efficiency, bit-parallel to bit-serial, is: \begin{displaymath} R = \frac{V+BW}{S(V+W)} \end{displaymath} For the vision algorithms we are interested in, computations on 8-bit pixels are done with 16~bits to preserve fractions, and as many as 64 words are frequently accessed. In our implementation of the PE, $V$ was approximately 50. Our algorithms have $S$ ranging from 3 to 6, averaging around 4. A graph of $R$ versus $W$, for relevant values of $B$, $S$ and $V$ is shown in \fig{effgraph}. The important conclusion is that not only does the RBP approach result in faster (lower-latency) computation, but that it is also more efficient in terms of computational power per silicon area. Of course, this can be seen as arguing for hardware bit-parallel. \mypsfig{Rgraph.ps}{Silicon Efficiency Ratios}{effgraph}{Efficiency ratio $R$ vs register file size $W$, for various values of non-memory overhead $V$ and algorithmic inefficiency $S$. The 'X' indicates the design point of our implementation.} \section{Abacus PE Architecture} The Abacus processing element (PE) consists of 64 1-bit registers organized into two banks. There are two 3-input ALUs, each of which takes two inputs from its memory bank and one input from the other bank. The four available data bits allow complex boolean functions, and two result bits can be written in each cycle, one bit to each bank. \mypsfigy{2in}{peblock.eps}{Processing Element Block Diagram}{block}{Processing Element Block Diagram.} A PE also has a 1-bit network interface and background I/O interface. Seven of the registers are used for control, leaving 57 general-purpose registers. \mypsfigy{2in}{netbw.ps}{Network cell}{network}{Network} \paragraph{Activity Register} Conditional execution of an {\tt if (cond) then ... else ...} sequence on SIMD arrays operates by disabling those PEs for which {\tt cond} is true, executing the true branch, disabling the other set of PEs, and executing the false branch. One of the Abacus PE registers serves as the {\tt activity} bit which, when cleared, disables computation by inhibiting the write of the result to the destination register. The ability of the ALU to serve as a multiplexer greatly reduces the use of the activity register. For example, the sequence {\tt if $A$ then $B \Leftarrow C$} incurs two cycles of overhead if implemented with the activity register. Alternately, the operation can be expressed as {\tt $B \Leftarrow$ mux($A$,$C|B$)}, eliminating all overhead. \paragraph{Network} The reconfiguration network serves for both bit-slice interconnection and inter-word communication. The network is a wired-OR reconfigurable \mesh. As in a conventional \mesh\ topology, each PE listens to the output node of one its four \mesh\ neighbors. Each PE is provided with a configuration register that specifies which neighbor to listen to. Unlike a \mesh, each PE can connect its output node to the selected neighbor's output node. Shorted nodes behave as a wired-OR bus: if any PEs in a connected chain send a 1, all PEs listening to the chain receive a 1. \paragraph{Background I/O} Each PE contains a data plane (DP) register, used for background off-chip data transfers. The DP registers of PEs in a column of the array form a 32-bit shift register. At the edge of the PE array, the 32 shift registers are connected to an off-chip memory port. These registers can be shifted without interfering with PE computation. Although the DP register is not used in arithmetic operations it is essential in hiding the latency of external memory accesses. \section{RBP Algorithms} RBP arithmetic algorithms resemble circuits more than bit-serial programs, since they are unrolled in both space and time. During each time step, each PE emulates part of the logic comprising an arithmetic circuit, reconfiguring connections if necessary. In the examples of this section, PSs are shown organized as a line in order to resemble a circuit. In reality, clusters are often arranged as squares or rectangles (a square organization minimizes the average inter-cluster communication distance), and topologically form a ring. In arithmetic circuits, boundary logic cells such as the LSB and MSB are configured differently from the middle cells. Similarly, PEs corresponding to cluster edges are marked as MSB or LSB. In addition, each PE is labeled with its bit position within the cluster. The LSB/MSB bit can be computed from this position, as can network configuration bits. \paragraph{Data Representation} RBP architectures can use a wide variety of number representations. The usual representation is the conventional binary one. In the case of the accumulate operation, the redundant carry-save representation is preferred, as carry computation can be postponed until a non-redundant operation is required. The MGAP designers are proponents of the redundant radix-4 representation where each processor stores a digit in the range of ${-3..3}$ \cite{Irwin91}. This is not a very memory-efficient representation, as it requires five bits to store a two bit number. \paragraph{Logical Shift.} The simplest RBP arithmetic operation is the shift. As shown in \fig{shift}, each PE simply replaces its bit with its neighbor's. For logical shifts, the MSB or LSB is cleared; for arithmetic shifts the MSB is retained. \mypsfigy{1.4in}{LSR.eps}{Shift}{shift}{Logical shift right. The number 6 is shifted down to become 3.} \paragraph{Sum Accumulation.} Accumulating a sum is a very common operation. The sum of a sequence of $n$ numbers can be evaluated in $\Theta(n)$ cycles with a carry-save (CS) algorithm. The CS adder computes the sum and carry bits separately for each addition. The computation is purely local, and the delay of each CS stage is independent of word size. At the end of a summing sequence the carry and sum values must be summed with a full carry-propagation adder, but this delay is amortized over many summations. Many computations usually expressed as additions can be reformulated as accumulations, improving the performance of algorithms such as region summing. It is interesting to note that accumulation is an inherently simpler and faster operation than addition, and yet conventional processors do not make the distinction. \mypsfigy{1.8in}{CSA.eps}{Accumulate}{accum}{Accumulate. The addition of the number 3 to a sum of 11 represented as 2+9. After the operation, the sum is 14, represented as 6+8. All operations are purely local or nearest neighbor. Steps 1 and 2 can happen during the same cycle if a copy of t is present in both memory banks.} \paragraph{Addition.} Fast addition relies on quick computation of the carry bit. A RBP algorithm based on the the well-known logarithmic-time technique was described in \cite{Bolotski93}. The algorithm ``looks-ahead'' at the carry by computing the eventual carry into each one-bit adder. It can be shown that the carry $c_k$ into bit $k$ can be expressed as % $c_{k+1} = g_k + p_kc_k$, where $g_k$ is the {\em generate} bit and $p_k$ is the {\em propagate} bit. Since the computation of successive $p$ and $g$ values can be expressed in terms of a binary associative operator, it can be performed in time logarithmic with the number of bits. This technique forms the basis of many hardware implementation of adder circuits. The Abacus architecture uses a different approach, one based on the hardware implementation of Manchester carry computation. In this technique, the carry bit propagates electrically down the line of bits unless prevented by a switch controlled by the $p$ signal. Although computation time is linear with the number of bits, the constant factors result in faster operation than software emulation of the logarithmic-time circuit. \mypsfigy{1.8in}{ADD.eps}{Addition}{addition}{Manchester-carry addition. A NOP cycle occurs after step 2 to allow the carry bit to propagate. Steps 1 and 2 are actually merged into one cycle, and the {\tt S} bit can be computed during the NOP cycle. } \paragraph{Match.} The match operation compares two bit patterns for equality. First, all PEs form a wired-OR bus. Then, all PEs write {\tt a != b} to the bus. If any bits differ, the bus becomes a 1; if all bits are identical, the bus remains at 0. \paragraph{Comparison.} \mypsfigy{1.8in}{CMP.eps}{Compare}{compare}{The {\tt compare} operation. After the broadcast, the MSB PE receives A>B for the rest of the word. It then merges the result with the MSB bit result.} The comparison algorithm is based on the observation that the most significant differing bit (MSDB) between two words determines which word is greater. Thus if the MSDB occurs in position $i$, $A > B$ when $A_i > B_i$, or equivalently $A_i = 1$ and $B_i = 0$. In the first step of the algorithm, all PEs with identical bits bypass themselves and do not participate in the rest of the computation. Then, all PEs send $A \cdot \overline{B}$ towards the MSB PE. Now, the MSB PE knows the value of $A>B$ for the rest of the word, and merges the result with its own data bits to produce the final answer. This entire process is equivalent to performing a Manchester-carry subtraction and testing for the borrow bit at the MSB. \paragraph{Multiplication.} RBP integer multiplication is composed of iterating through a sequence of shifts, broadcasts and carry-save adds. These operations can be partially overlapped so that an iteration requires 7 cycles. Thus, a 16 by 16 multiply requires 112 cycles, plus about 10 cycles of overhead. These numbers are for unsigned multiplication with a double-length result. If only the low word of the result is required, an iteration requires only 6 cycles. Two's complement multiplication is implemented with a software version of the Baugh-Wooley multiplier, and requires one additional iteration. While hardware multipliers frequently use the modified Booth algorithm to halve the number of iterations, this algorithm is not very efficient on the Abacus architecture since it requires the broadcast of three bits. \paragraph{Mesh Move.} In a \mesh\ move each cluster rearranges itself into several shift registers in the direction of movement. The move operation is relatively expensive, as $k$ bits must be transferred through a $\sqrt{k}$-wide bus, requiring $\sqrt{k}$ time steps. Further, unlike arithmetic operations, \mesh\ moves cross chip boundaries and therefore suffer an additional 1-cycle latency cost. \paragraph{Scan Operations.} A set of computational primitives known as {\em parallel prefix} or {\em scan} operations have been found to be useful programming constructs across a variety of machine architectures. These operations take a binary associative operator $\oplus$, and an ordered set $[a_0, a_1,\ldots, a_{n-1}]$ and return the ordered set $[a_0, (a_0 \oplus a_1), \ldots, (a_0 \oplus a_1 \oplus \ldots a_{n-1})]$. Common scan operations include {\em or-}, {\em and-}, {\em max-}, {\em min-}, and {\em +-scan}. There are also corresponding {\em reduce} primitives that reduce the values in a vector to a single value. For example, {\em +-reduce} calculates the sum of a vector, as shown in \fig{tree-reduce}. \mypsfigx{4in}{tree-reduce.ps}{A +-reduce operation.}{tree-reduce}{A +-reduce operation.} The bypass capability of the Abacus network can be used to implement fast scan operations. %\footnote{expand. describe fast bypass support} A message can propagate across a chip in two cycles. Crossing a chip boundary requires an additional cycle of latency. The prototype is a 16 by 16 chip array, so that 48 cycles are required for a bit to cross the array. Assuming a 4 by 4 bit PS organization, propagation of a 16-bit cluster requires 200 cycles. Since each stage of a logarithmic scan doubles propagation time, an entire scan operation requires approximately 500 cycles, or 4 microseconds. This can be optimized further by pipelining bit transmission. \section{Performance Summary.} The performance of a single Abacus chip on the operations described in this section is given is in Table 1. The left half of the table gives cycle counts, while the right gives the MOPS rating assuming 1024 PEs per chip and a 125~MHz clock rate. \begin{Table}{perf}{Single Chip Arithmetic Performance} \small \begin{tabular}{|l|rrr||rrr|} %\hline \cline{2-7} \mcol{1}{c}{} & \mcol{3}{|c||}{Cycle Count} & \mcol{3}{|c|}{MOPS} \\ \hline \hdr{Operation} & \mcol{1}{|c|}{8-bit} & \mcol{1}{|c|}{16-bit} &\mcol{1}{|c||}{32-bit} & \mcol{1}{|c|}{8-bit} & \mcol{1}{|c|}{16-bit} &\mcol{1}{|c|}{32-bit} \\ \hline Add, Compare & 4 & 4 & 5 & 4000 & 2000 & 700 \\ Shift & 3 & 3 & 3 & 5300 & 2700 & 1300 \\ Accumulate & 4 & 4 & 4 & 4000 & 2000 & 1000 \\ Mesh Move & 5 & 6 & 8 & 3200 & 1300 & 500 \\ Multiply & 66 & 126 & 235 & 242 & 63 & 17 \\ \hline \end{tabular} \end{Table} These ratings are somewhat pessimistic for two reasons. First, they include an additional one-cycle penalty for reconfiguration. For example, if a right shift instruction is followed by an add instruction, PEs must be reconfigured from reading from the MSB direction to reading from the LSB direction. This penalty does not occur during every instruction, and a clever compiler can group instructions with identical configurations to reduce reconfiguration costs. Second, as discussed earlier, microcode for several arithmetic operations can be overlapped. By the table entries above, the sequence $a = b + 2d + 2c$ performed on 16-bit values appears to require 14 cycles (two shifts, an accumulate, and an add). Yet a handcoded program performs the same operations in only 9 cycles by eliminating three reconfiguration steps, overlapping two broadcasts, and duplicating a data bit in both memory banks. A high fraction of peak performance has been observed on simulations of vision algorithms. % Local Variables: % mode: latex % TeX-master: "main" % End: