%* Last edited: Mar 22 15:58 1996 (misha) \documentstyle[11pt,config,equationarray,mapleenv]{article} \def\sidebar#1{\marginpar{\tiny #1}} \def\emph#1{{\em #1}} \def\mypsdirectory{/homes/misha/abacus/Papers/ChapelHill/PS/} %%\newenvironment{singlespace}{}{} %%\def\mysection#1{\paragraph{#1.}} \hyphenation{wide-spread} \textheight 8.5in \textwidth 6.5in \oddsidemargin 0in \evensidemargin \evensidemargin \topmargin -0.5in \itemsep -0.5ex \pagestyle{myheadings} \markright{DRAFT VERSION OF \today} %%%%%%%%%% \def\mypsdirectory{/homes/misha/abacus/PS/} %% override mapleplot to add mypsdirectory \def\mapleplot#1{ \vskip\AboveMaplePlot \centerline{\vbox{\psfig{figure=\mypsdirectory#1,% height=\MaplePlotHeight,% width=\MaplePlotWidth,% angle=\MaplePlotAngle}}} \vskip\BelowMaplePlot } \def\maskpic#1#2#3#4#5#6#7#8#9{ \begin{picture}(40,30) \put(10,0){\framebox(30,30){\ }} \put(20,0){\line(0,1){30}} \put(30,0){\line(0,1){30}} \put(10,10){\line(1,0){30}} \put(10,20){\line(1,0){30}} \put(15,5){\makebox(0,0){#1}}\put(25,5){\makebox(0,0){#2}}\put(35,5){\makebox(0,0){#3}} \put(15,15){\makebox(0,0){#4}}\put(25,15){\makebox(0,0){#5}}\put(35,15){\makebox(0,0){#6}} \put(15,25){\makebox(0,0){#7}}\put(25,25){\makebox(0,0){#8}}\put(35,25){\makebox(0,0){#9}} \end{picture} } \begin{document} %%\tableofcontents %%\newpage \input{summary} \clearpage \section{Introduction and Motivation} Computer vision, the understanding of images by a computer, is both an exciting component of artificial intelligence and a daunting computational task considered as one of the Grand Challenge problems of parallel processing. The design of a parallel computer for vision is an attractive problem for a computer architect, as the problem domain lends itself to optimizations that promise orders of magnitude performance over general-purpose parallel computer. This thesis proposes to design, implement, and analyze a VLSI-based architecture tailored to the computing demands of early vision. Although the field has received a great deal of academic attention, this work targets a considerably higher speed design than previous efforts, and as a result encounter system-level consequences of a high speed parallel computer. In the body of this section we will the describe the problem domain and the detailed thesis approach. \paragraph{Computing Requirements of Vision.} Computer vision deals with the understanding of imagery by a computer, in contrast to image processing, which generally enhances images for human inspection. The field can be broadly categorized into three levels: low (or early) vision, which extracts physical properties of viewed surfaces, such as distance, orientation, and velocity; middle vision, which manipulates geometric quantities and performs simple recognition; and high level vision, which uses symbolic reasoning to disambiguate objects. Boundaries between each of these levels are rather blurred, especially as recent object recognition research has started to operate at the image level. Of the three, early vision processing is the best understood and therefore the best candidate for acceleration with a specialized architecture. The others are still highly experimental and require flexible general-purpose architectures. The need for a specialized computer becomes apparent when the computational requirements of early vision are considered. A moderately sized image contains approximately 65,000 pixels, each of which may be used a hundred times in a computation. A single vision algorithm may require ten iterations per image, and as many as fifty algorithms may be required to extract essential information such as depth, motion, shapes, and shadows. All of this processing must be repeated thirty times per second to sustain real time response. The aggregate sustained computing power is therefore on the order of 100 billion operations per second (GOPS). It is clear that parallel processing is required to deliver this level of performance. The question now becomes: what should the parallel system look like? There have been hundreds of proposed parallel system designs. These systems can be broadly categorized as Single-Instruction Multiple Data (SIMD) machines that consist of identical processing elements (PEs) executing the same instructions in lockstep, and Multiple-Instruction Multiple-Data (MIMD) machines, whose PEs execute independent programs and use explicit communication to synchronize operations. Historically, SIMD machines have been built with large numbers of simple PEs, while MIMD machines relied on a small number of complex PEs. At the time of writing, the most prevalent parallel architectures are MIMD machines consisting of collections of workstation-class RISC processors. Indeed, only one major SIMD vendor, MasPar, still exists, while there are many MIMD vendors, including Cray, Convex, IBM, and Intel. This overwhelming commercial success is due to the constant improvement in microprocessor performance, driven by marketplace pressure and fueled by enormous investment. Parallel MIMD machines are excellent general--purpose computing and development platforms, since they come equipped with the software inherited from their workstation heritage. As with the uniprocessors on which they are based, these machines excel at computations with irregular and unpredictable instruction streams. Unfortunately, the price of this flexibility is reduced performance. On problems with a data--parallel, highly regular structure, such as image processing, these processors continue to be unnecessarily flexible at every instruction step. When additional domain constraints such as low-precision arithmetic and 2-dimensional mesh communication are considered, a specialized architecture promises order-of-magnitude improvements over general purpose systems. The proposed thesis develops a design for Abacus, a SIMD machine specialized for variable-precision integer operations on a dense 2-dimensional mesh, and targeted for a high-speed VLSI implementation. Predicted performance of Abacus parts is indeed approximately 50 times higher than that of uniprocessors with comparable silicon resources. \paragraph{Reconfigurable Bit-Parallel Processing.} The Abacus architecture can be classified as a reconfigurable bit-parallel (RBP) machine. Reconfigurable processors provide a smooth transition between the two extremes of a slow, small bit-serial PE and a complex, fast bit-parallel PE. The tradeoff between the two is that simple one-bit PEs are capable of arbitrary precision and can run at a high clock speed, but require many cycles per operation. Hardware bit-parallel PEs require few cycles, but run slower and waste valuable silicon when computing with data narrower than their ALU width. RBP designs retain bit-serial flexibility and bit-parallel performance. The key idea of a RBP design is to provide programmable interconnected to link multiple PEs into a single Processing Site (PS) that can operate on several bits of a data word simultaneously. Reconfiguration allows precision to be matched to the need of each algorithm. Even more significantly, on-chip memory capacity at each processing site can also be adjusted by changing the number of PEs in a PS. Since off-chip memory references can be a factor of 20 slower than on-chip accesses, decreasing the miss rate at the cost of ALU capacity may lead to substantial performance increases for many algorithms. There is some overhead associated with RBP, such as the time to combine or distribute information from the entire word, as in conditional operations. As with hardware bit-parallel ALUs, operations on data narrower than the PS size (such as boolean flags) are inefficient. \paragraph{Thesis Approach.} This thesis proposes to analyze, quantify, and demonstrate the performance advantages of a high-speed VLSI RBP SIMD architecture on early vision tasks. The overall research approach will be to: \begin{enumerate} \item Develop an analytical performance model accounting for both architectural and algorithmic effects. \item Design, implement, and test a VLSI chip containing Abacus processing elements. A working chip will both provide architectural parameters for an analytical model and unearth any inaccurate assumptions about high speed SIMD operations. \item Implement a simulator and code a number of vision algorithms including a standard image understanding benchmark suite to determine algorithmic parameters. \item Complete a system-wide (paper) design to ensure that there are no unexpected system-level bottlenecks. \item Use the IC implementation experience and the analytical model to suggest a design for a second generation architecture. \end{enumerate} The expected contributions of this thesis can be grouped under three categories: implementational, analytical, and cultural. A successful implementation will demonstrate a SIMD chip with the highest clock rate to date. It will force the development of system interfaces generally ignored in the academic field. This development is absolutely essential as input/output interfaces may prove to be the bottleneck in high speed designs. The analytical model will allow the selection of an optimal point in implementation space as technology parameters vary. For example, novel high-bandwidth devices such as Rambus memory components may allow reduction in the amount of on-chip memory. The model will allow quantification of these tradeoffs. Also, in the course of obtaining algorithmic parameters, the vision algorithms will be systematically characterized, which may lead to improved intuition about optimizing algorithms for RBP architectures. Hopefully, the thesis will also have several positive cultural effects. It will to provide a convincing demonstration of the effectiveness of SIMD processing. We believe important commercial applications of SIMD technology are near but may be hampered by the unconvincing performance and architectural deficiencies of existing SIMD processor arrays. Vision-related tasks, such as MPEG coding, OCR, paper document processing, digital picture manipulation, medical imagery, face recognition, vehicle collision avoidance, and automatic vehicle guidance all provide important practical applications which can be solved using SIMD techniques. An existing system design will allow the construction of a cheap tera-op level supercomputer for vision research. Such a platform will allow important image, signal, and text processing applications to be prototyped. A successful design will encourage research on specialized architectures, which has been decreasing recently due to the success of RISC-based MIMD machines. Finally, the project will demonstrate that high performance design can be done in a university environment. %The basic technical approach is physical construction where necessary, %analytical models where possible, and detailed simulations to fill in the %gaps. Purely theoretical work makes too many simplifying assumptions to be %trusted outside those areas where the basic implementation technology is %already well understood. %%The key idea of the architecture is to provide a mechanism that allows a %%group of PEs to operate efficiently on a single word of data. Allocating a %%PE for every bit of a data word results in a potential performance %%improvement equal to the word size (compared to bit-serial). %%The observation driving the architecture is that a certain amount of data %%must be located near (ie, on-chip) the PEs \footnote{This assumes that %% external memory is very very slow, which becomes more and more true as %% on-chip speeds increase}. For reasonable data sizes, the silicon area %%occupied by the data is much larger than the ALU of a bit-serial PE. A %%relatively small amount of this area may be converted to ALUs for a %%substantial improvement in performance. %As a result of the lessons learned while developing the first Abacus %architecture, we believe that the second generation, Abacus-2, can be %constructed to provide approximately three times the performance in the %same silicon area. Alternatively, the performance could be kept constant %while substantially reducing the packaging cost and power dissipation. %While the first Abacus machine was designed to be used as a large-scale %parallel computer, the preliminary designs for Abacus-2 allow a %small number of chips to be used as a SIMD accelerator for a conventional %processor or for a node of a MIMD machine. A single circuit board housing %16 Abacus-2 ICs can reach 32 GOPS on low-precision arithmetic operations. \section{Previous and Related Work} \subsection{Architectural Design} There has been a considerable amount of research on architectures for image processing and image understanding. A variety of processor designs and interconnection networks have been proposed (and far fewer have been implemented). This review concentrates on SIMD designs and on alternate approaches with comparable performance. Early examples of machines designed for image processing include Goodyear's MPP\cite{Potter85}, NCR's GAPP \cite{Cloud88}, and ICL's DAP. The most widely produced SIMD machine was Thinking Machines' CM-2. A contemporary commercial product was produced by MasPar \cite{Blank90}, and recently upgraded to the MP-2 \cite{Kim93}. There are also several research designs which have not been put into commercial production. These designs explored different aspects of SIMD architectures. For example, IBM's polymorphic torus \cite{Li89} concentrated on adding connection autonomy by the addition of locally reconfigurable network switches. The MCNC Blitzen project \cite{Blevins88} updated the original MPP design for VLSI technology by adding on-chip RAM, local modification of addresses, and an X-grid 8-neighbor interconnect. A unique Some/None network intended for associative processing was stressed in the CAAAP architecture \cite{Shu89} developed at the University of Massachusetts at Amherst. As in the polymorphic torus, network switches were locally controlled, but groups of processors could be electrically connected. This feature allowed efficient connected components and global statistics algorithms. The idea of an RBP architecture is not completely new. Even the first massively parallel machine, the DAP, allowed columns of PEs to be configured into a ripple-carry chain. This capability was not central to the architecture and operated slower than bit-serial operations. The reconfigurable processor array (RPA) \cite{Rushton89} uses a mixed approach to RBP. Although each PE processes two bits at a time, and a data word is shared among a PS, considerable hardware resources are devoted to supporting bit-slice operations. As a result, each PE is quite complex for a fine-grained machine. A number of recent research efforts promise to achieve substantially higher performance than these early designs. A 256-element SIMD array driven by an on-chip RISC-like processor has been designed at the University of Sheffield \cite{Thacker94}. The performance is reasonable, given the number of processors, but is limited by the instruction issue rate of the RISC controller, the low I/O bandwidth, and the lack of off-chip memory support. A major US semiconductor manufacturer\footnote{Psst: Motorola} is readying an as yet unannounced SIMD processor design with 50 MHz clock rates and sixty-four 8-bit processors for use in embedded multimedia applications. The Supercomputer Research Center has developed a processor-in-memory chip which augments a 128 Kbit SRAM array with bit-serial processors at each row \cite{terasys}. The performance of this design is rather low due to the small number of PEs and modest clock rate. An alternate processor-in-memory MIMD/SIMD architecture has been developed by IBM \cite{execube}. The Execube chip incorporates 8 16-bit PEs, each with 64 KB of DRAM memory, and can be operated in SIMD mode from a global instruction bus. The performance is again rather low due to the long cycle time of DRAM and because instructions are stored in the same memory as data. An integrated micro-MIMD chip, integrating 48 16-bit processors and an interconnection network on each chip has been designed at UC Berkeley \cite{berkeley-dsp}. The IC delivers an impressive 2.4 GOPS on a variety of DSP algorithms and is designed to communicate efficiently with other chips. However, since each PE's instruction memory is only 8 words deep, with no provision for expansion, the architecture is not suitable for more complex algorithms. A class of DSP chips, most notably the Texas Instruments C40 and the Analog Devices SHARC processors, have been designed to support efficient execution over data arrays and inter-processor communication. These appear more promising than the RISC based systems, but still lack performance and waste power. Another technology that delivers comparable performance to Abacus and PADDI is the use of reconfigurable logic as exemplified by Field Programmable Gate Arrays. An array of programmable logic can be used to configure applications specific hardware and thereby obtain excellent performance. For example, research at DEC Paris have implemented algorithms ranging from Laplace filters to binary convolutions \cite{pam_performance_assessment}. If the per-chip performance is computed as aggregate performance divided by the number of FPGA chips in the system, each Xilinx chip delivers approximately 500 million 16-bit operations per second. \begin{table}[htbp] \small \begin{center} \begin{tabular}{|l|r|r|r|r|r|r|r|} \hline Machine & Performance & Clock & I/O BW & \multicolumn{2}{|c|}{Mem BW} & Tech \\ & 16-bit MOPS & MHz & MB/sec & Internal & External & $\mu$ \\ \hline TMC CM-2 & 8 & 8 & 8 & 32 & 16 & 1.5 \\ SRC TeraSys & 20 & 10 & 5 & 80 & 5 & 1 \\ IBM EXECUBE & 50 & 25 & 300 & 400 & 0 & .8 \\ TI C40 & 50 & 50 & 200 & 0 & 200 & .8 \\ MasPar MP-2 & 133 & 12.5 & 45 & 1600 & 45 & 1 \\ HP8000 & 200 & 200 & 800 & 0 & 960 & .5 \\ Sheffield DIP & 320 & 40 & 160 & 2560 & 0 & 1 \\ Xilinx XC3090 & 500 & 20 & NA & NA & NA & 1 \\ Berkeley PADDI-2 & 2400 & 50 & 800 & 14400 & 0 & 1 \\ %%MIT Matrix & ? & ? & ? & ? & ? & ? \\ {\bf MIT Abacus-1} & {\bf 2000} & 125 & 1000 & 32000 & 512 & 1 \\ \hline \end{tabular} \end{center} \caption{Architectural performance comparison} \label{tab:perfcomp} \end{table} %Table~\ref{tab:perfcomp} clearly shows that no other design has the %combination of flexibility, raw performance, communication bandwidth, and %I/O bandwidth required for an effective parallel system. %We have described a number of other approaches to obtaining high %performance in the Summary section. Since an overwhelming amount of %research is already being done commercially on improving the performance of %RISC processors and DSP chips, we will focus on less mainstream research. It is unfair to directly compare the 16-bit performance of Abacus compared to the wider-width Execube and MasPar PEs, as they incorporate floating-point support. However, even granting a factor of five in area, their performance is still lagging. Both of these designs make the classic mistake of single-porting their register files. The implication of requiring three cycles to perform a single instruction is that three times the area could have been allocated to triple-porting the memory. And the area in this case refers to the \emph{entire} silicon area, including communication pads and support circuitry. The only architecture comparable in performance is the Berkeley PADDI-2 chip, and it is not suitable as a general computing element as it can only store eight instructions per PE. Of course, when the computation task can be expressed as piping data through a systolic array, the IC is an ideal high-performance, low chip-count solution. We are not aware of any other research SIMD machine that even approaches the Abacus design in terms of performance per silicon area on low-precision integer operations. Our advantage occurs for a variety of reasons, including an aggressive clock rate of 125 MHz, made possible by careful custom design, high density manual circuit layout, and the inherent advantage of RBP operations. \subsection{Architectural Analysis} Two recent research efforts are most relevant to the proposed work. The performance advantages of RBP architectures due to memory limitations were first evaluated by Audet et al \cite{Audet92}, who referred to RBP as the Dynamic Concatenation Approach. The goal of the research was to determine the optimal number of PEs to be grouped into a PS, given particular hardware and algorithmic parameters. This number is called the concatenation factor, $w$. Although the critical issue of off-chip memory traffic minimization was addressed, the published work contained some shortcomings. Some of the flaws were: \begin{itemize} \item Ignored communication time growth with $w$. For example, on a mesh with square processing sites, time grows as $\sqrt{w}$. \item Scaled execution times by factors based on pipelining effects. The method of deriving these parameters is based on arbitrary assumptions about compilers and hardware implementation. Quantifying pipelining effects applies more to a VLIW-style system where multiple functional units can be triggered by a single instruction. The model appears to apply to multi-cycle, relatively complex functional units, which are not usually present in simple, small SIMD PEs. \item The model assumes a static type of register assignment: the most frequently used variables are placed into registers, and the rest into memory locations. Modern compilers perform dynamic assignments, spilling registers into memory locations when necessary. As the methodology used UNIX-based C profiling tools to determine the often referenced variables, it is not clear whether the need for temporary registers was considered, or whether loop unrolling optimizations were made. \item Virtualization requirements were not considered and program segments appear trivially short. Further, the only program example shown in detail is of a systolic type. Short computation chains between virtual PE synchronizations could lead to a large number of register save and restore operations. \end{itemize} %Define processing time of a PE as total number of ops of each type times %time required for each op (obviously). The types of operations were: %internal register access, external memory access, arithmetic operation, %logic operation, and communication operation. Of all types, only %arithmetic ops change time requirments with word size. %All realistic models need to address: %\begin{itemize} %\item Layout improvement when specialized hardware is used, both area and % speed, %\item{} Slowdown of larger RFs, %\item{} Quantization effects for equal division of words into slices. %\end{itemize} %Quantitative graphs used unreasonable constants such as 1-register PEs %(hopefully a multi-bit register). Concatenation hardware costs used %transistor estimates for chaining costs, ignoring cost of configuration %bits and reconfiguration times. %The cost of broadcasting bits such as ``disable'' to an entire PU doubles %the cost of conditional test operations. %% \paragraph{Herbordt} A simulation approach to SIMD performance evaluation was taken by Herbordt \cite{Herbordt94b}. Traces are generated on an abstract virtual machine and then \emph{trace compiled} for a specific target architecture. The technique can be two orders of magnitude faster than a detailed simulation. This flexibility allows quick evaluations of different architectural parameters, such as register file size or communication latency. Although the centerpiece of the thesis is the trace compilation methodology, a number of architectural studies were run, and some interesting conclusions resulted. For example, some studies showed that increasing ALU width substantially improved performance only up to a width of 8 bits. After that, performance improved only slightly. The key differences between the proposed work and Herbordt's approach are: \begin{itemize} \item Effect of trace compiler quality eliminated through hand-compilation. Since vision algorithms tend to be oblivious, with little data-dependent branching, they can be characterized more exactly than through simulation. \item Algorithms designed with Abacus architectural features in mind. For example, if multiplies are expensive, the implementation may avoid them, or at least specify required precision. Otherwise, unnecessary computations can affect benchmark conclusions. \item Intent is to derive parameters for an analytical model. Possibility of better insight into algorithm structure. \item Use of explicitly allocated off-chip memory rather than cache. This could be approximated by ENPASSANT with a fully associative cache and a LRU replacement policy. \end{itemize} An overall problem is that the simulator simulated algorithms designed for a uniform memory access machine, which is no longer appropriate for today's high-speed designs. %\subsection{MIMD Flexibility Hurts Performance} %The MIMD model incurs enormous overhead for every functional unit that %actually manipulates data. This overhead consists of silicon area required %to store the program (a 10K word program of 32 bits each corresponds to 1.8 %million transistors!), instruction decoding, addressing, and control %circuitry. The overhead can easily be a factor of ten larger than %the functional unit actually processing the data. %A more subtle disadvantage is the loss of integration due to pin %limitations. Today's chip carriers can support very few 32-bit wide %instruction ports. Reduced integration leads to pressure on improving the %performance on a single chip. Regardless of diminishing returns, valuable %silicon resources are allocated to squeezing the last available performance %from a single instruction stream. Thus, only a small fraction of the %circuitry on a chip is devoted to actually manipulating the data. The rest %is allocated to branch prediction, instruction caching, instruction %scheduling and reordering, etc. Other baggage inherited from the %workstation background of RISC chips is support for operating systems, such %as interrupts and fast context switches. %Many important applications are characterized by irregular data and %instruction flow, complex interactions between data sets, and highly %conditional execution. For this wide variety of important computing tasks, %high performance uniprocessors and MIMD parallel machines have emerged as %the best architectural choices. % A general purpose MIMD machine capable of performing the %required massive data manipulations would be prohibitively costly. %Especially in constrained environments where power and size requirements %dictate efficient solutions, the uniprocessor/MIMD approaches are a poor %application of resources. %% ---- Add in only if you make a connection ------- %On a philosophical note, the microprocessor approach locks architecture and %programmers into a rigid way of thinking, as the cycle count does not %reflect the true silicon cost of operations. When logical shift and %multiplication take nearly the same amount of time, programmers (and %compilers) start to use multiplication more. Algorithms get slanted towards %using multiplications, and what's worse, profiling programs for instruction %frequency shows that multiplications are used frequently and should be %accelerated by allocating more area. \section{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. \subsection{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 amount 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. \subsection{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 Figure~\ref{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.} \subsection{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. \subsection{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{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. \subsection{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} \begin{center} \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{center} \caption{Single-chip arithmetic performance} \label{tab:perf} \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. \section{The Abacus-1 Chip Implementation} \subsection{PE Core} \paragraph{Processing Element} Almost half of the PE's area is consumed by registers, which are implemented as standard 6T SRAM cells and arranged into two banks of eight rows and four columns. The {\tt bit} and {\tt /bit} lines are used single-ended to provide two read ports, allowing four bits to be read and two written in each cycle. Bitline precharging to $V_{dd}-V_t$ is done through the column selects, precharging only bitlines that will be read. Each ALU is implemented as a precharged 8-to-1 multiplexer that uses three data bits to select one of eight instruction bits. During each 8~ns cycle, a PE performs a bitline precharge, SRAM read, ALU evaluate, and SRAM write. The background DP register can be shifted simultaneously without interfering with the ALU. % The simplicity of each PE resulted in a compact, $83 \mu$ by $452 \mu$ implementation in a 2.6$\mu$ minimum metal pitch technology. \paragraph{Network} The on-chip interprocessor communications network consists of a precharged output node and four isolating switches. The node is a simple precharged inverter whose input is driven by the {\tt NetOut} register. The four switches are NMOS gates driven by a 2-4 precharged decoder. The precharge pulse is controlled by software to allow multi-cycle propagation times. Propagation delay across a series of pass transistors is usually quadratic in the number of devices. Our implementation greatly reduces this delay by a local accelerator circuit at each node which regeneratively pulls a node to ground as soon as the node voltage drops by a transistor threshold. The circuit is a dynamic NORA style circuit and is well suited to the precharged operation of the network. We found it to be several times faster than an implementation based on a complementary inverter. At the nominal process corner, simulations show that a bit propagates through 18 PEs in one 8~ns cycle. \mypsfigy{2in}{net-accel.ps}{Network Accelerator}{netaccel}{Network accelerator in the NORA circuit style.} This circuit has a noise margin of $V_T$, so careful layout was done to reduce coupling capacitance to the pre-discharged node. Further, the chip is provided with on-chip bypassing and over 200 power and ground pins to reduce dI/dt noise. \mypsfig{chip_photo_bw.ps}{Chip Photograph}{chip}{Chip photograph.} \paragraph{Chip Organization.} The chip is organized into three major parts: the PE array, split into two halves; the control signal drivers in the middle; and control logic at the left. The control logic includes address decoders, instruction decode, external memory control, and a scan path controller. The PE core is organized as 16 strips of 64 PEs each. Each strip also contains two sets of 76 buffers that drive control signals outward from the center. Skew is reduced by distributing signals vertically in a lightly-loaded metal-3 bus, buffering horizontally with identical drivers, and equalizing the load on each horizontal control wire. \paragraph{Input/Output Interface} The Abacus PE chip has a one-bit single-ended ECL input and a one-bit differential ECL output for external data I/O. The aggregate bandwidth of a 256-bit, 125~MHz bus formed by the 256 PE chips is 4 GB/sec, which is almost three orders of magnitude than the 7.7 MB/sec required by 512 by 512 images at 30 Hz. This very high I/O bandwidth makes the architecture well-suited to applications requiring real-time processing of large amounts of data such as video and synthetic aperture radar. The I/O bandwidth can be scaled down to reduce the interface logic and wiring cost. For example, if only the 16 chips comprising the top row of the 256-chip array are connected, the 4 GB/sec bandwidth would be reduced to 250 MB/sec, which is more than an order of magnitude higher than frame rate. The Abacus PE chip contains several mechanisms required for high-speed system-level operation: skew-tolerant instruction distribution pads, high-bandwidth local DRAM interface, low voltage swing impedance-matched mesh pads, and low pin-count I/O interface. \subsection{Off-Chip Interfaces} \emph{All Abacus off-chip interface circuits were designed by Tom Simon. Their implementation does not constitute part of the thesis.} \subsubsection{System Synchronization} Careful synchronization is essential to a high-speed SIMD architecture. On the Abacus PE board the system clock is distributed in differential ECL to each PE chip. Propagation delays are matched by snaking traces so that trace lengths are equalized. To compensate for skew introduced by process variations in the on-chip clock distribution, each chip phase locks its internal clock to the received clock. Phase locking is performed by a delay locked loop (DLL) based on an all-digital delay line. The DLL uses the simple and accurate arbiter circuit shown in Figure~\ref{fig:arbit}. The arbiter has a perfectly symmetric 30~ps uncertainty window at nominal process. \mypsfigy{2in}{arbit.ps}{DLL Arbiter}{arbit}{Arbiter used in the delay-locked loop} The remaining question is: which of the internal clock phases should be locked to the system clock? There are several internal clocks: instruction register, PE register read, network precharge, etc. We choose to synchronize to the clock that drives the mesh output pads. As a result, off-chip communication is synchronized system-wide. \subsubsection{Instruction Distribution} A spatially distributed SIMD system must ensure not only that all clocks are synchronized, but also that all chips are executing the same instruction at the same time. Clock distribution can be controlled by snaking traces to equalize propagation delay, or by using specialized clock distribution parts with programmable delays. Neither technique is feasible for the 30-bit instruction bus running at 250~MHz. Since each PE board is approximately 60~cm on a side, even with signals driven from the center of each board, distribution skew can be as large as 2~ns. Another source of instruction skew is the variability of discrete parts in the distribution path. For example, the clock to output delay on a high-performance ECL shift register has an uncertainty of 0.4~ns. A signal traversing two parts can be skewed by a much as 0.8~ns. The combined effect of these skews is that some chips receive an instruction a cycle later than others, even though all chips are supposed to be executing the same instruction at once. Worse yet, bits of an instruction can be mixed with bits of the next instruction due to parts variability. This skew problem is solved by retiming logic in the instruction pads that synchronizes instruction delivery across all chips. Retiming occurs as part of the system startup process and proceeds in three stages. The first finely adjusts the delay of each bit until the sampling clock occurs in the middle of the data valid period. The second stage lines up all bits within a chip to the same pipeline stage. Finally, pipeline delays are equalized across the system by software. The various stages of the initialization process are controlled through a scan path by the array controller. \subsubsection{Inter-Chip Mesh Communication} The next system level challenge is to provide synchronous high-bandwidth, low-latency mesh communication between PE chips. Due to pin limitations, the edges of the 32 by 32 PE mesh on each chip are time multiplexed onto 16-bit ports. The required clock rate is therefore 250~MHz. %Some of the problems associated with synchronous signalling at %this rate are: clock skew between receiver and transmitter, transmission %line mismatches, a short sampling window, wire length variability, and %process variations. Each of the four mesh ports sends out an escort clock along with the data. Since the off-chip drivers and propagation time are identical for data and clock, the receiving chip can safely use the escort clock (delayed by the setup time of the receiving registers) to sample the data. Metastability problems do not arise as we ensure that data is sampled well before the receiving data needs to use it. The communication pads are driven with custom 1V, on-chip series terminated drivers and matching receivers in order to minimize power dissipation and transmission line reflections \cite{automatic-impedance-control}. Impedance calibration for the series termination is performed at system initialization. Each of the four ports on a chip is calibrated independently, since on-board and board-to-board impedances may differ. In addition to the pipelined, high bandwidth mode of operation, the mesh pads can operate in a flow-through mode that bypasses the on-chip pulldown network with a single wire, allowing fast multi-chip broadcast algorithms. Propagation through a chip is reduced from three clock cycles to half a cycle. However, the time multiplexing is disabled, reducing the effective bandwidth. \subsubsection{Image I/O} While early SIMD designs were concerned with limited image I/O bandwidth, it is not an issue today's high-speed designs. Since I/O is distributed among 256 chips, a single pin on each component results in a very wide bus. The Abacus PE chip has a one-bit single-ended ECL input and a one-bit differential ECL output for external data I/O. The aggregate bandwidth of a 32-byte, 125 MHz bus is 4 GB/sec, which is almost three orders of magnitude than the 7.7 MB/sec required by 512 by 512 images at 30 Hz. The I/O bottleneck is clearly going to occur upstream of the PE array. The I/O bandwidth can be scaled down to reduce the interface logic and wiring cost. For example, if only the 16 chips comprising the top row of the 256-chip array were connected, the 4 GB/sec bandwidth would be reduced to 250 MB/sec, which is more than an order of magnitude higher than frame rate. A single PE instruction initiates a burst transfer of 32 bits from the edge of the PE mesh to the output pin (or vice versa). This background transfer frees the array to perform computation, or in the case of the lower cost interface, to use the mesh connections to shift data towards the connected chips. \subsubsection{External Memory Interface} Since many algorithms will exhaust the 64~Kbit on-chip memory, each PE chip is backed by two 1M x 32 specialized DRAM modules. The data interface is 64~bits wide and operates at 16~ns, which matches the 32-bit, 8~ns PE mesh. The 16~ns cycle time is made possible by the Ramtron extended DRAM part, which contains an SRAM cache integrated in the DRAM. Control signals for the memory chips are synchronized to the PE chips by sending them as part of the instruction stream. Fine control over DRAM timing is made possible by the small instruction cycle time, which is comparable to that of dedicated DRAM controller. A useful side-effect of this approach is the elimination of memory glue logic. A counter in each PE chip generates the external memory addresses. This counter can be loaded from the top row of the PE array, allowing indirect addressing. \section{System-Level Design} This section is empty for now. It will contain relatively detailed design of the entire system, including sequencer, I/O interfaces, and host workstation interfaces. The topics of this section have largely been ignored by academic researchers, with most of the attention going to processing element and interconnection design. However, system interfaces are precisely those elements most likely to cause bottlenecks. %% \subsection{PE Board Design} \section{Parallel Algorithm Implementation and Performance} This section describes the implementation of several vision and communication algorithms on the Abacus architecture. It will eventually contain images processed by the high-level Abacus simulator, as well as characterizations of the inner loops. \subsection{Basic Vision Algorithms} %We described a number of vision algorithms on the Silt architecture in %\cite{Bolotski93}. The Abacus machine alters implementation %details of only the arithmetic operations; the vision algorithms %remained unchanged. \paragraph{Edge Detection} The widely used Marr-Hildreth edge detection algorithm consists of filtering the image with a Gaussian filter, computing the Laplacian of the filtered image, and locating the zero crossings of the result \cite{Horn86}. Convolution with a Gaussian can be approximated by repeated convolution with a triangular filter, with weights $\frac{1}{4}$, $\frac{1}{2}$, and $\frac{1}{4}$, requiring only arithmetic shifts and accumulates. Since the Gaussian filter is separable, it can be implemented by two one-dimensional convolutions. Further, since zero crossings are independent of absolute magnitude, the expensive scaling operation of the Laplacian kernel is not required. \begin{figure}[htbp] \setlength{\unitlength}{1mm} \begin{picture}(150,90) % \put(50,10){\epsffile{\mypsdirectory zerox1.ps}} \put(65,5){(d)} % \put(100,10){\epsfffile{\mypsdirectory zerox2.ps}} \put(115,5){(e)} % \put(50,50){\epsffile{\mypsdirectory gauss1.ps}} \put(65,45){(b)} % \put(100,50){\epsffile{\mypsdirectory gauss2.ps}} \put(115,45){(c)} % \put(0,10){\epsffile{\mypsdirectory bob.ps}} \put(15,5){(a)} \end{picture} \caption[Edge Detection Example]{% Edge detection with the $\nabla^2G$ filter. (a) original image; (b) smoothed with a Gaussian, 2 iterations; (c) smoothed with a Gaussian, 4 iterations; (d) and (e) zero crossings of $\nabla^2G$.} \end{figure} %% \mypsfig{chip_photo_bw.ps}{Chip Photograph}{chip}{Chip photograph.} %The algorithm was implemented with 16-bit clusters to maintain precision %when adding and dividing 8-bit intensity values. One iteration requires 103 %cycles. The calculation of the zero crossings of convolution with a %discrete $3 \times 3$ Laplacian kernel required approximately 1200 cycles. %Total edge detection time for a Gaussian with a $\sigma$ of 2.0, requiring %four iterations of the triangle filter, is approximately 1800 cycles. The %performance metric is for a 128 by 128 array processing 256 by 256 pixel %images. \paragraph{Surface Reconstruction} Surface reconstruction consists of determining the surface shape (height and slope) from a set of potentially sparse and noisy measurements. Harris \cite{Harris86} introduced the coupled depth/slope model for surface reconstruction and developed an iterative solution technique suitable for a mesh-based massively parallel computer. The update equations in each iteration are simple and local and consist of five or six additions and subtractions, followed by a division. The summation of multiple values at a pixel is computed efficiently by the multi-operand addition algorithm. Division is expensive on a DBP architecture, as it is on a word-parallel bit-serial machine. This algorithm only requires division by a constant, which can be implemented by a special purpose sequence of shifts and adds. \paragraph{Optical Flow} In correlation-based optical flow \cite{Little88} the original image is displaced in a variety of directions, and at each displacement the difference between the two images is computed, and summed over a window. If the images are processed to produce binary image features, the difference is the exclusive or of the image pixels in the 11 by 11 neighborhood. Finally, each pixel chooses the layer with the smallest difference value in a winner take all step. Images manipulated by the algorithm may consist either of simple brightness values or of more complex features such as edges. This algorithm has been implemented on the simulator for the binary feature case. The edge detection algorithm discussed earlier could be used to obtain the features (in this case edges) from a raw intensity image. \begin{figure}[htbp] \setlength{\unitlength}{1mm} \begin{picture}(150,70) \put(20,10){\fbox{\epsffile{\mypsdirectory flow1.ps}}} \put(100,10){\fbox{\epsffile{\mypsdirectory flow2.ps}}} \put(35,0){(a)} \put(105,0){(b)} \end{picture} \caption[Optical Flow Example]{Optical flow calculation with maximum displacement of 2 pixels and a 5 \by 5 summation region. (a) original image. (b) displaced image. The top shape moved up by one pixel and partially off the image; the right shape moved down by one pixel and the lower shape moved three units down and one to the left. } \label{fig:optflow} \end{figure} \mypsfig{optvec.ps}{Optical Flow Field}{optvec}{% Optical flow field resulting from the raw data in \fig{optflow}. Some confusion is caused by the movement of the top shape off the image, and by the movement of the lower shape by a distance exceeding the maximum displacement layer.} \paragraph{Performance Summary} In the vision algorithms table, computation times are shown for a 128 by 128 array processing 256 by 256 pixel images (a virtualization factor of four). %images. %\begin{center} %\small %\begin{tabular}{|l|rr|rr|rr|} %\hline %\hdr{Operation} & \mcol{2}{|c|}{8-bit} & \mcol{2}{|c|}{16-bit} & %\mcol{2}{|c|}{32-bit} \\ %%\cline{2-7} & \hdr{Cycles} & \hdr{GOPS} & \hdr{Cycles} & \hdr{GOPS} & %%n\hdr{Cycles} & \hdr{GOPS} \\ %\hline %Add & 4 & 4.0 & 4 & 2.0 & 5 & 0.7 \\ %Shift & 2 & 8.0 & 2 & 4.0 & 2 & 2.0 \\ %Accumulate & 3 & 5.2 & 3 & 2.6 & 3 & 1.3 \\ %Move & 3 & 5.2 & 4 & 2.0 & 6 & 0.6 \\ %Compare & 6 & 2.6 & 11 & 0.6 & 12 & 0.2\\ %%Multiply (16 $\times$ 16) & & & && 180 & 0.03\\ %\hline %\end{tabular} %\end{center} \begin{center} \small \begin{tabular}{|l|r|r|} \hline \hdr{Algorithm} & \hdr{Cycles} & \hdr{Time} \\ & \hdr{1000s} & \hdr{($\mu$sec)} \\ \hline Edge Detection $\sigma=2.0$ & 1.8 & 14.4 \\ % \hline Optical Flow, $\Delta=5$, 5 \by 5 region& 40& 320 \\ % \hline Surface Reconstruction (1 iter) & 1.5 & 12 \\ \hline \end{tabular} \end{center} \subsection{Early vision subset of the DARPA IU Benchmark} This section describes the subset of the DARPA Image Understanding Benchmark that falls in the domain of early vision. \paragraph{Connected Component Labelling: Broadcast} A common problem in image analysis involves labeling the connected regions of constant pixel intensity, where unique regions are constituted from a definition of either 4-connectedness (horizontally or vertically adjacent), or 8-connectedness (horizontally, vertically, or diagonally adjacent). This operation is discussed for binary images in the literature (\cite{Levialdi72}, \cite{Leighton92}, \cite{Ziavras93}, \cite{Choudhary90}, \cite{Cypher90}) but has been extended for grayscale values in the following three algorithms. The first approach described here is the most straightforward but requires the most time, the second alternative is faster but requires considerable amounts of memory, and the third is a modification of the second that compresses memory requirements drastically, at the cost of increased computation. In this algorithm, each pixel of the intensity image is labeled uniquely from its PE row and column. This intensity and its corresponding label (of $O(\log N)$ bits) are broadcast to each of its 8-connected neighbors. At each PE, the neighbors of matching intensity are determined, and the minimum of the their corresponding labels and the current label becomes the new label. This process continues until no more labels in the mesh are updated (checked by a global compare). The number of broadcasting operations required is proportional to the largest ``intrinsic diameter'' of all connected components in the image, defined as the maximal shortest connected path between any two pixels in the region \cite{Leighton92}. For spirals and other high-curvature images, this intrinsic diameter can be as high as $O(N^{2})$ in the worst case, resulting in $O(N^{2}\log N)$ bit operations. \paragraph{Connected Component Labelling: Shrinking} Levialdi's region shrinking operation \cite{Levialdi72} provides a iterative method to directionally compress each region down to a single pixel and then remove it entirely without fragmenting or fusing separate regions. If the results of each operation are saved away, the operation can be reversed to generate a unique label when a region consists of only one pixel, and that label can be transmitted to all possible neighbors in the direction of expansion so that they can make a decision should they become connected in the next stage. The third algorithm modifies the basic one by storing only a subset of the shrunk images and reconstructing on the fly by repeating the shrinking operation. %%See \fig{reg-shrink-alg}. \paragraph{K-curvature Tracking and Corner Detection} The connected components map is processed to produce $K$-curvature values for those pixels on the component borders, which are then smoothed with a Gaussian filter to eliminate multiple peaks near corners. Pixels with smoothed curvature values exceeding a threshold value (peaks) are intersected with the zero-crossings of the first derivative of smoothed curvature to extract candidate corners in the image. Border pixels are defined to be any pixel adjacent (N,E,W,S) to a pixel belonging to another component. $K$-curvature is defined at each border pixel as the interior angle between the two lines passing through the current pixel and those $K$ border pixels away in either direction along the region's border. See \fig{k-curv-def}. \mypsfig{K-curv.ps}{K-curvature definition}{k-curv-def}{K-curvature definition. In this figure, $\theta$ is the K-curvature for $K$=3. Note that all pixels shown are edge pixels.} \paragraph{Median Filter} The median filter is a common image processing operation. Unlike linear filters, each pixel replaced not by a linear combination of its neighbors but rather by the median value. The operation is effective for removing high frequency ``speckle'' noise without degrading the rest of the image. \paragraph{Gradient Magnitude} By computing the magnitude of a discrete intensity gradient in the image and thresholding the result, strong direction-independent edges in the map can be located. Every pixel intensity in a 3x3 neighborhood about the current PE is multiplied by a weight according to the Sobel X and Y masks and summed to form the Sobel X and Y magnitudes. Since the weights are either 0, 1, or 2, the multiplications are converted to shifts. The gradient magnitude is the square root of the sum of the squares of the X and Y magnitudes. Results greater than a threshold value are flagged to create a boolean edges map. The operation is constant in space and time with respect to $N$. \paragraph{Hough Transform} The Hough transform partitions a binary image into discrete bands one pixel thick and oriented at a certain angle, and sums the values within the band to yield a set of projections that can be scanned to locate strong edges in the original image at that angle \cite{Cypher89}. Usually transforms are computed for many angles, so that the aggregate data can provide insights into the image properties. The implemented algorithm partitions the image into bands of constant line offset $\rho$ for a given angle $\theta$ according to the equation: $\{(x,y): x \cos \theta + y \sin \theta = \rho\}$ where $(x,y)$ are PE coordinates and $\theta$ is assumed to be in the range $\pi/2 \leq \theta < 3\pi/4$ (the other angles can be accommodated by pre-rotation of the image). A ``band total'' variable visits all PEs in its assigned band by shifting east, and north if necessary (a result of the angle range is that at most two pixels in the same column belong to the same band). The PEs in the first column are visited first, and then the variable travels eastward across the columns. Since there are many angles to be projected, they are pipelined one column at a time, yielding $P$ projections on an $N$x$N$ image in $O(N+P)$ time. %%\input{hough_fig} \subsection{Sorting and Routing Algorithms} Sorting algorithms can be converted into routing algorithms by associating data with the sort key and ensuring that the combined packet is moved together. This allows packets to be routed to a destination. Two types of sorting algorithms were examined: those with a fixed execution time, and those with a data-dependent execution time. \paragraph{ShearSort and RevSort} %RevSort, like most of the oblivious mesh sorting algorithms depends on the %compare-exchange primitive, which performs a two-element sort. Keys are %compared, and the packet corresponding to the larger key is placed in the %first data location, while the other packet is placed in the second %location. ShearSort is a $\sqrt{N}(\log{N} + 1)$ step sorting algorithm \cite{Leighton92}. It consists of sorting rows in alternating opposite directions starting at the left edge of the array, then sorting the columns from top to bottom. ShearSort relies on the TranspositionSort \cite{Quinn87} procedure to get things sorted. TranspositionSort is the basic linear array sort. It works similar to the uniprocessor BubbleSort: comparing then exchanging (where necessary) alternating pairs of items. An improvement of ShearSort is called RevSort \cite{Schnorr86}. It is identical to ShearSort, except CyclicSort is used to sort rows instead of Transposition Sorts. This algorithm finishes in $\sqrt{N}(\log{\log{N}} + 3)$ steps and the complexity of the each step is equivalent to each step of ShearSort. CyclicSort is a descendant of the TranspositionSort, and performs as fast as its ancestor. The smallest item is sorted to a chosen processor instead of the leftmost processor. %%\paragraph{KielSort} \paragraph{Mesh Greedy Routing Algorithm} A very different packet-based routing algorithm was developed by Herbordt \cite{Herbordt94}. Each PE emulates two communication channels, one vertical and one horizontal. Packets are moved one step through the X channel until the correct X coordinate for the packet is reached. At that point the packet is moved to the Y channel and proceeds vertically. The X and Y routing steps are interleaved, so that one of each occurs during each iteration. Notice that packets can be blocked from switching to the Y channel if that section of the channel is full. When this occurs, packets behind the blocked PE in the X direction are also blocked. The blocking information propagates backward along the X channel one step at a time. Since each PE contains space for two packets, collisions will not overwrite data, and the blocking information can afford to propagate only one step per cycle. The key difference from the user's point of view is that this algorithm is not guaranteed to finish in $O(\sqrt{N})$ iterations. In fact, the worst case performance is $O(N)$, where $N$ is the number of PEs. According to Herbordt, the worst case is very unlikely to arise in either a completely random, or typical routing conditions. In fact, the algorithm generally does not need to be iterated more than 2.5 times the optimal case of $2\sqrt{N} - 2$. The paper demonstrates that this property holds for a number of common permutations, such as transpose, bit shuffle, and rotations. \MaplePlotWidth=\textwidth \MaplePlotHeight=60ex \section{Architectural Tradeoffs} In this section we begin to develop a performance model for the Abacus computer. \subsection{Slice Optimization} In addition to the usual architectural and algorithmic parameters, the RBP organization allows a compile-time selection of the concatenation factor $m$. This is the number of PEs grouped into a single PS. We would like to determine the optimal number of bit-slices operating for a particular algorithm. Assume the following constants: \begin{table}[ hbtp] \begin{center} \leavevmode \begin{tabular}{|c|l|} \hline Name & Description\\ \hline \multicolumn{2}{|c|}{Architectural} \\ \hline D & Number of registers in slice \\ k & Slice width\\ B & Bandwidth into each slice (per bit)\\ \hline \multicolumn{2}{|c|}{Algorithmic}\\ \hline R & Number of variables in algorithm\\ W & Bits in data word \\ N & Number of ops in sequence\\ Z & Number of answers and initial data items\\ \hline \multicolumn{2}{|c|}{Derived}\\ \hline f & Fraction of register misses (function of R,E)\\ E & Effective registers per pixel\\ \hline \multicolumn{2}{|c|}{Compiler Decision}\\ \hline m & Number of slices / pixel\\ \hline \end{tabular} \end{center} \caption{Architectural and Algorithmic Parameters} \label{tab:param} \end{table} Thus, a processing site consists of $m$ slices of $D$ registers each of $k$ bits. There are $W$ bits in each data word. The number of effective registers per pixel is the total number of bits in a processing site divided by the word length: \begin{equation} E = \frac{mkD}{W} \end{equation} %We have some constraints. First, there is at least 1 slice allocated per %pixel. Second, we have no more than $\frac{W}{k}$ slices per pixel (full %bit-parallelism): $W/k \geq m \geq 1$. \footnote{As a (not very useful) % consequence, $W/mk > 1$, so that $D \geq E$.} The time to load a word/operate on a word is equal to the number of bits to be loaded divided by the cumulative bandwidth/ALU width of the slices doing the loading: \begin{equation} T_{load} = \frac{W}{mBk} \ \ , \ \ \ T_{alu} = \frac{W}{mk}\\ \end{equation} So we model an operation sequence on a single pixel as loading some initial number $Z_{in}$ of words from off-chip memory, performing $N$ arithmetic operations, and writing $Z_{out}$ result words out, for a total of $Z$ loads and stores. Equation \ref{eq:proctime} gives the time required for processing a single pixel, assuming that for every memory fault the processor has to write the previous value to memory and load the requested value. This memory fault is going to occur on some fraction $f$ of the memory accesses. \begin{equation} \label{eq:proctime} T_{seq} = Z T_{load} + 2Nf(R,E)T_{load} + NT_{alu} \end{equation} Assume that there are $P$ pixels to be processed and $M$ slices to process them. If $m$ slices are allocated to a pixel, $M/m$ pixels are processed in a time step of $T_{seq}$, so that $Pm/M$ iterations are required. It is convenient to define the quantity $l=Z/N$, the ratio of initialization operations (forced cache misses) to iterative operations (possible cache hits). \begin{eqnarray*} T_{tot} & = & \frac{P}{M}m T_{seq}\\ & = & \frac{P}{M}m \left[ \left( Z+2Nf(R,E) \right) \frac{W}{mBk} + N\frac{W}{mk} \right] \\ %% & = & \frac{PW}{Mk}\left[ \frac{Z+2Nf}{B} + N \right] \\ %% & = & \frac{PWN}{Mk}\left[ \frac{Z/N+2f}{B} + 1 \right] \\ & = & \frac{PWN}{Mk}\left[ \frac{(l+2f)}{B} + 1 \right] \\ & \propto & \frac{(l+2f)}{B} + 1 \\ \end{eqnarray*} %% Of course, if $m>k$ , then $T_{alu}$ saturates at 1. The simplified model presented in this chapter does not consider the disadvantages of RBP, such as the overhead of PEs whose ALUs are unused, or the distribution of conditional information to each PE. Therefore, the obtain optimal concatenation factor $w$ will always be too high. Nevertheless, the performance improvement is an upper bound on the advantage of RBP. However, the analysis applies only to single-phase algorithms. The flexibility advantage has not been incorporated. So, we would like to choose $m$ to minimize $T_{tot}$, given the algorithmic constraints of $W$, $N$, $Z$, $f$; the architectural constraints of $B$ and $D$. We could evaluate this exactly, except that we do not know the behavior of the miss function $f(R,E)$. So we'll explore some plausible functions. \begin{enumerate} \item {\em Case 1: No Cache Misses}. If $R < E$, we have enough local storage and $f = 0$. $Q$ then becomes independent of $m$. This indicates a bad initial design point: both in the nibble-serial mode and in the nibble-parallel mode, all data fits in memory. Therefore, the memory is too big. \item {\em Case 2: All Cache Misses}. If the algorithms steps repeatedly through all the registers, the miss rate is effectively 100\%. Again, the number of nibbles allocated is irrelevant. \item {\em Case 3: Random Register Usage}. If the register used during each step is selected at random from the logical registers, there is a $E/R$ probability that it is already in the cache. $f$ is therefore \begin{equation} f(E,R) = 1-\frac{E}{R} = 1 - \frac{mkD}{WR} = \frac{WR - mkD}{WR} \end{equation} So, to maximize performance we want to lower $f$ and therefore increase $m$. \end{enumerate} In conclusion, $m$ should always be maximized. \subsection{Background Loading} A memory access on the Abacus machine has a latency of 40 cycles, but can be initiated before the data is actually required. Only one outstanding memory reference can be pending. We would like to determine the benefit of this feature compared to the worst-case penalty of 40 cycles. The key parameters are the latency of a reference, and a distribution probability on consecutive non-memory references Our first order model assumes a uniform probability $p$ of an off-chip memory reference. Thus, the probability of a sequence of $k$ on-chip references before an off-chip reference is: \begin{equation} P(N=k) = (1-p)^{k-1}p \end{equation} \begin{figure}[ hbtp] \begin{center} \leavevmode \mapleplot{Pk_vs_k.ps} \end{center} \caption{Probability of an on-chip hit sequence of length $k$ for different values of $p$, the miss probability. Note that for high $p$ almost all the area under the curve is near small values of $k$, and therefore long load times. } \label{fig:seqprob} \end{figure} This distribution is shown in \fig{seqprob}. Notice that the probability of long sequences is small if $p$ is high. Therefore, we expect background loading to help only in the case of low $p$ or low latency. Since the loading time given a string of $k$ available cycles is $L-k$, the expected loading time is: \begin{equation} E[T] = \sum_{k=1}^L{q^{k-1}p(L-k)} = \frac {(\,1 - {p}\,)^{{L}} + {p}\,{L} - 1}{{p}}\\ \end{equation} \begin{figure}[ hbtp] \begin{center} \leavevmode %% \mapleplot{Leff_vs_f1.ps} \mapleplot{Leff_vs_f2.ps} \end{center} \caption{Effective latency vs latency due to background loading as a function of $L$ and $p$. The advantage of background loading occurs in a relatively narrow zone: where the frequency of loads is very low to begin with, and where latency is low. For low values of $L$, the ratio may not be really important, since it approaches internal access time.} \label{fig:leff} \end{figure} Still, even for relatively large of $L$ and $p$\footnote{40 and 0.1, respectively}, we can get a 3X speedup. %\begin{figure}[ hbtp] % \begin{center} % \leavevmode %\mapleplot{Leff_vs_m.ps} % \end{center} % \caption{Effective Latency as a function of $m$. This } % \label{fig:leff} %\end{figure} \subsection{Conclusion} The following plots are for parameter settings of: \begin{center} \small \begin{tabular}{|c|l|r|} \hline \hdr{Variable} & \hdr{Meaning} & \hdr{Value} \\ \hline Dr & number of registers in slice & 50 \\ k & slice width & 1 \\ Bw & bandwidth into each slice (per bit)& 0.05 \\ R & registers in algorithm & 30 \\ Wb & bits per word & 16 \\ Z & initial loads/saves & 10 \\ N & number of operations in a sequence& 30 \\ \hline \end{tabular} \end{center} \begin{figure}[ hbtp] \begin{center} \leavevmode \mapleplot{perf_func_m.ps} \end{center} \caption{Execution time as function of $m$. The dip in the middle is the effect of background loading. Without it, the graph would have continued in a straight line. Notice that the dip occurs at a non-useful $m$ value, as it is difficult to evenly partition a 16-bit value.} \label{fig:execfuncm} \end{figure} The algorithm requires 480 bits. At 9.6 slices per pixel, there are no external references and time is constant. Background loading makes a difference only in a narrow zone. Until about $m=7.8$, The linear performance improvement is due to the linearly decreasing hit frequency in our simplified model. \begin{figure}[ hbtp] \begin{center} \leavevmode \mapleplot{cycles_vs_m_bw.ps} \end{center} \caption{Execution time as function of m and bandwidth} \label{fig:execfuncm2} \end{figure} The main conclusion is that external memory references are catastrophic, and that the number of bit-slices should be chosen to minimize the number of external loads. The model can be made more accurate in a number of ways. \begin{enumerate} \item Accounting for the circuit density improvement of higher-width bit slices. \item Speed decreases due to larger ALU widths. Of course, this may not matter if the cycle time is dominated by memory access. \item Slower memory accesses with increasing memory size. \item Better estimates of cache miss behavior as a function of available registers. \end{enumerate} As illustrated by the graphs in this section, the last modification is probably the most significant, since the initial three factors are not likely to be more than a factor of 2 each, while cache misses can result in order of magnitude performance changes. \section{Next Generation: Abacus-2} \subsection{Lessons of Abacus-1} We have learned a number of lessons from the implementation of Abacus-1 that we believe will result in a substantial performance improvement in the Abacus-2 design. \begin{enumerate} %% Architectural \item {\em Reconfiguration overhead is excessive.\/} The design of the on-chip interconnection network requires a reconfiguration cycle if the direction of data flow changes. This occurs when, for example, an arithmetic shift right instruction, in which bits flow from left to right is followed by an add instruction, in which the carry bit flows from right to left. The single-cycle reconfiguration still represents a substantial cost. \item {\em Arbitrary data formats are expensive.\/} The one-bit bit slice elements could be grouped in almost arbitrary configurations, as long as each set of PEs responsible for a data word formed a topological circle. As a result, on-chip data could not be accessed by the sequencer without a complex corner-turning reformatting procedure. %% VLSI \item {\em Rise/fall times are a substantial fraction of cycle time\/}. When rise/fall times approach 400 picoseconds, three or four non-overlapping control signal transitions consume as much as 3~ns. When combined with process variation uncertainties, the actual active time shrinks further. \item {\em Simple ALUs do insufficient work per cycle.\/} The very simple ALU operates in approximately 400 picoseconds, a tiny fraction of the overall cycle time. \item {\em Lack of pipelining is critical.\/} Due to the nature of the network design, forwarding is essentially impossible and pipelining the read, execute, and write phases is precluded. At this point it appears that pipelining is sufficiently important to modify the network organization. A pipelined design would allow more time for various execution phases and therefore reduce the size and power dissipation of control line drivers. \item {\em Address control wires are expensive.\/} Although the double-banked register files and twin ALUs (see Approach section) allow two result bits to be written per cycle, the number of control wires doubles compared to a single bank. This leads to unnecessary layout constraints, high capacitance, and difficulty in pitch-matching signal buffers to the PE height. Further, the required board-level instruction bandwidth increases substantially. %% Board level \item {\em ECL components are terrible for integration.\/} We designed the instruction distribution and I/O paths to use ECL signaling. This was a mistake, since many ECL-based LSI components are required per board, as well as pulldown resistors, bypass capacitors, and a higher number of board layers. The design of a custom multi-function CMOS part would have been preferable. \item {\em Burst I/O is overconstraining\/.} The Abacus chip has two pins for I/O, one for input and one for output. A single I/O instruction initiates a 32-bit burst. This design choice was intended to increase the overlap of computation and I/O, but was a mistake in retrospect. High performance parts are required to handle the 32-bit, 125~MHz bursts, yet they sit idle almost all of the time, as I/O transfers are very rare. \end{enumerate} Our preliminary design for the Abacus-2 part addresses these issues, among others. We expect to almost double arithmetic performance while reducing power dissipation and decreasing the required packaging cost. The Abacus-2 chip will fit 256 4-bit PEs on a single 10x10 mm die, and operate at 66 MHz in a 3.3 V (or lower) environment. A single Abacus-2 chip will deliver 4.2 billion 16-bit additions per second and approximately 500 billion 8-bit multiplies per second, in a non-aggressive 1 micron VLSI technology. Implementation in the sub-micron technology recently available through MOSIS would of course lead to higher performance numbers. The new design is amenable to integration with a simple sequencer and I/O subsystem, allowing scalability in system size, from a 16-chip 64 GigaOps system that can be utilized as a co-processor attached to a conventional RISC-chip based node of a MIMD system, to a standalone 256-chip TeraOp SIMD machine. The Abacus-2 chip will be designed to operate as smart memory, accessible by the controller with low latency. Corner turning will be incorporated on chip. Scalable I/O should allow the sequencer to access any pixel in the system quickly. This could be done by adding a port to the PE chip or by accessing the external memory. For small systems, the port idea works well, since the access port can be placed on a bus and tristated. For larger systems, discrete tristate parts would have to be added to isolate the bus from capacitive loads. Corner turning can be incorporated on chip, unlike Abacus-1, since the data formats have been restricted somewhat. The only complex part would be the addressing, and that could be taken care of by another set of PALs. \section{Beyond SIMD: Abacus-3} We have a number of preliminary ideas that could lead to new possibilities in performance. \paragraph{M-SIMD Operation.} One way of viewing the Abacus-2 chip is as the integration of a large number of traditional discrete bit-slices (such as the AMD2903) and a flexible interconnection network on a single chip. If a functional version of a discrete sequencer was also integrated, the chip could operate as a uni-processor, ignoring the broadcast SIMD instruction and treating the on-chip memory as registers and the off-chip memory as instruction and data store. The collection of Abacus-2 chips could now operate in a mixed MIMD/SIMD mode, as required by the algorithm. This mode would not be as efficient as pure SIMD, as off-chip memory bandwidth would be reduced, but algorithms more suitable to MIMD operation could be implemented efficiently. \paragraph{Systolic Operation.} A small augmentation of the Abacus-2 PE would allow operation in a systolic mode, where each PE could execute a different instruction. If each PE conditionally latched each bit of the control word under local control (say as a function of the processor ID), then every PE could be programmed to perform a different operation. For example, directing some PEs to multiply their network input by an internal constant and place the result on the network output, while others summed their network inputs, results in a pipelined FIR filter. Of course, there are limitations to this mode, but the research direction seems promising. \paragraph{SIMD Element or Programmable Logic?} Another relatively minor modification allows the Abacus-2 chip chip to emulate programmable logic. If each PE was equipped with local address decoding, and operated in the systolic mode, then different PEs could store different truth tables and therefore emulate programmable logic. \paragraph{Universal Computing Element?} The combination of all three features described above leads to an almost universal computing element, able to operate as a SIMD node, as uniprocessor (with a very wide word), as a collection of systolic computing elements, or as programmable logic. Furthermore, different parts of the chip could be operating in different modes. For instance, some PEs could be serving as logic gates configured as specialized find-first-one hardware co-processors for other SIMD-mode elements. \section{Conclusions} The conclusion section, supported by an actual working device and better algorithm trace analysis, will resemble this section. %The DBP architecture has been shown to be amenable to a very high %performance implementation. We have demonstrated that many important %arithmetic and communication operations can be accelerated with DBP %methods. The usefulness of the accumulate primitive suggests that there %may be arithmetic and logical operations which have no counterpart on %traditional architectures. Further, the peephole micro-optimizations can %occur between what are typically considered to be atomic operations. For %example, a broadcast operation can be overlapped with an addition, so %that while bits are propagating, the ALUs can start on the next %operation. Similarly, when one of the two ALUs is idle due to data %dependency in the current operation, the other can start on the following %operation. %From the implementation viewpoint, we hope to demonstrate that the %regular nature and simplicity of the Abacus SIMD array allows high-speed %(125 MHz) system operation. % %Even at these clock rates, the external %memory subsystem has been designed to deliver data with only a latency %penalty. % %We are currently investigating other interesting issues such as multiple %networks to reduce the need for reconfiguration, indirect addressing %during external memory accesses. An exciting development is the %possibility of integrating a high-speed (200+ MHz) multi-stage %interconnection network port into each chip to augment the reconfigurable %mesh with hypercube-like communication. %This paper described the Abacus machine at a number of levels. We %presented the microarchitecture of the PE comprising the reconfigurable %bit-parallel array, a set of arithmetic and communication primitives, %details of the VLSI implementation, and system-level design issues of a %high-speed SIMD array. First, we tested the limits of the premise that simple one-bit PEs allow a faster overall clock rate. Although this is a common argument in research papers, existing MPP SIMD systems use a clock rate substantially slower than that of commercial bit-parallel microprocessors. The 125~MHz clock of the Abacus chip is the highest of any massively parallel SIMD systems that we're aware of. Further increases in clock speed are limited by instruction bandwidth rather than PE complexity, and therefore transfer the difficulty to off-chip interfaces and printed circuit board design. Retaining the clock speed while increasing the work done per cycle holds more promise as the approach for incorporating smaller and faster VLSI technology. Second, we determined how effectively a collection of simple one-bit PEs could emulate bit-parallel hardware. As shown in Section~4, a variety of arithmetic circuits can be emulated at a cost of two to five cycles. However, while reconfiguration reduces the silicon cost, it increases the time requirements in two ways. Bit-level reconfiguration precludes hardware pipelining by introducing dependencies on network switch settings. Conventional techniques for dealing with data dependencies (such as forwarding) cannot be used. Additionally, reconfiguration overhead is a significant fraction of arithmetic operation times. We plan to address these issues in our next multi-bit bit-slice design. Third, we wanted to complete an entire system to see if there are any unexpected bottlenecks and performance hits in high-speed SIMD designs. Consideration of board-level issues led to the development of instruction retiming logic, high-speed mesh signaling, low pin-count data I/O, and software control over DRAM timing. We now have a system framework that allows us to replace details of the PE core and remain plug compatible with the rest of the machine. Since the clock rate is already aggressive, we'll be able to hold it steady for a number of years while researching how to get more work done per cycle. From a theoretical viewpoint, the Abacus implementation provides a set of realistic constants that can be used to evaluate reconfigurable mesh algorithms. The aggressive (in terms of speed and integration) nature of the design explores physical limitations on architecture that will become more significant in the future. For example, it is becoming obvious that chip boundaries cannot be abstracted away in the interests of software regularity. Specialized architectures have fallen out of favor as commercial pressure continually drives up the performance of general purpose microprocessors. The current trend in parallel architecture is to construct parallel systems from slightly modified commodity processors. The Abacus project demonstrates that architectures optimized for specific computations can be an order of magnitude faster than such general purpose systems. \appendix \section{Rough Work} \subsection{Scan and Reduce Primitives} {\em Need intro here about scans}. Scans on a mesh with bypass are logarithmic time under the unit time assumption. In practice, the assumption is false, and the network operates as a sub-linear mesh. Assume a 4 by 4 square organization of PEs. Let's look at a reduction operation, say summing the pixel values. Even though this number can overflow, for now we'll do the arithmetic in 16-bit integers. This reflects the real life case of crossing chip boundaries. \footnote{Describe model: ie, 2 cycles to cross chip plus one for chip boundary}. \footnote{Note about changing orientation}. \subsubsection{Unpipelined loop} An unpipelined loop algorithm is: \begin{verbatim} for i = 0 to L { set_bypass_reg(i) configure_horizontal() net_out := x for j = 1 to n { wait( WaitTime(i)) net_out := net_in // on the 4th iteration, do Y := in } do_arithmetic() } \end{verbatim} On the $i$th cycle, $2^i$ pixels are bypassed (the first iteration, with no bypassing, is not shown). Waiting time as a function of number of PEs, $p$, bypassed is $p/16$ if $p \leq 32$ and $1.5 p/16$ otherwise (chip crossing penalty of 1 cycle). Since $p = 4 \times 2^i = 2^{i+2}$, this can be expressed as $2^{i-2}$ if $i \leq 3$, and $1.5 \times 2^{i-2}$ otherwise. Let $A$ be the time for the arithmetic operation and other overhead. Say we want to send $n$ bits. %Assume 4 cycles for the arithmetic operation, and another 5 for the other %overhead. Then iteration $i$ requires: \begin{equationarray*}{lll} T_i = A + n & (1 + 2^{i-2}) & \mbox{if}\ i \leq 3 \\ & (1 + 1.5 \times 2^{i-2}) & \mbox{otherwise} \\ \end{equationarray*} The total time $T = \sum_{i=0}^L T_i$ is \begin{eqnarray} T & = & L(A+n) + n(1+1+1+2) + 1.5n \sum_{i=3}^L 2^{i-2} \\ & = & L(A+n) + 5n + 1.5n \sum_{j=1}^{L-2} 2^j \\ & = & AL + n(L+3.5) + 1.5n 2^{L-1} \\ \end{eqnarray} For $L=6$, $n=4$, $A=9$, in this case, $T_i = 54 + 38 + 192 = 284$. \subsubsection{Pipelined Loop} As an aside, given an ideal (transmission line) wire and ideal flip flops with no setup or hold times, how many FFs should be used to pipeline the transmission of $n$ bits? The answer is infinity, if clocking rates can be arbitrarily high. This requires more iterations but smaller waiting time between iterations. \begin{verbatim} for i = 0 to 6 { set_bypass_reg(i) configure_horizontal() net_out := x for j = 1 to NumIter(i) { wait(WaitTime(i)) net_out := net_in // on the 4th iteration, do Y := in } do_arithmetic() } \end{verbatim} WaitTime(i) is easy: if messages have to cross chip boundaries, it is $n-1$, otherwise it is $\lceil p/16 \rceil$, which is effectively 1. The tricky part now is determining NumIter($i$). The number of iterations is the number of bits plus the pipeline length minus 1. If we set up each chip as a pipeline stage, {\tt NumIter(i)} is $N_{\mbox{chips}} + 3$. The time equation decomposes nicely into two parts: within chip and intra chip. \begin{equation} T_i = A + \left\{ \begin{array}{llll} n & \times & (1+1) & \mbox{if}\ i < 3 \\ n-1+2^{i-3} & \times & (1+3) & \mbox{otherwise} \\ \end{array} \right. \end{equation} Making the substitutions: \begin{equation} T_i = A + \left\{ \begin{array}{ll} 2n & \mbox{if}\ i < 3 \\ 4n-4+2^{i-1} & \mbox{otherwise} \\ \end{array} \right. \end{equation} \begin{equation} \begin{array}{lllll} T & = & L(A+1) + 6n + (L-2)(4n-4) & + \sum_{i=3}^L 2^{i-1} \\ & & L(A+4n-3) - 2n +8 & + \sum_{i=3}^L 2^{i-1} \\ & & L(A+4n-3) - 2n +8 & + 2^L - 4\\ & & L(A+4n-3) - 2n + 4 & + 2^L\\ \end{array} \end{equation} For $L=6$, $A=9$, $n=4$, $T= 6(22) - 8 + 4 + 64 = 192$. or about 30\% faster. Compare with $T = L(A+n) + 3.5n - 4 + \frac{3n}{4} 2^L$. The difference is $(\frac{3n}{4}-1)2^L + 5.5n - 4 + L(3n-3)$, or $2(64) + 22 - 6(9) - 4 = 92$. \subsubsection{Conclusions} Notice that we get only 30\% gain. Why? We would naively expect a factor of 3. \subsection{Starting Computing During Background Loading} \paragraph{Start Work Early?} A minor modification is to allow computation to start on a nibble as soon as it's read in, and not wait for the entire word. Assuming that it takes longer to load than to compute, the time for a combined load and operate is just the load time plus the time to compute the final slice. As a result, the arithmetic time drops by the number of external loads. If we assume that the time to process a single slice is 1, then: \begin{eqnarray*} T_{tot} & = & Qm \left[ (Z+2Nf) T_{load} + N(1-f)T_{alu} + Nf \right] \\ & = & Qm \left[ \left( Z+2Nf \right) \frac{W}{mB} + N(1-f)\frac{W}{mk} + Nf \right] \\ %% & = & QW\left[ \frac{Z+2Nf}{B} + \frac{N(1-f)}{k} + \frac{Nf}{W} \right] \\ & = & QWN\left[ \frac{l+f}{B} + \frac{1-f}{k} + \frac{f}{W} \right] \\ & = & \frac{QWN}{Bk}\left[ (l+f) + B \left( 1 - f + \frac{fk}{W} \right) \right] \\ \end{eqnarray*} Recall that we defined $l=Z/N$. This is faster than the non-overlapped case, but not by much. If we define $X$ as $(l + 2f)$ and $Y$ as $k/W$ then: \begin{eqnarray*} R & = & \frac{X+B}{X+B(1-f + fY)} \\ & = & 1 + \frac{f(1-Y)}{\frac{X}{B} + (1-f(1-Y))} \\ \end{eqnarray*} The increase is at most 20\%, even for very high values of $f$ and $B$, so we'll ignore this effect. Let's assume $Y$ is 1/16, for 1 bit PEs and 16-bit data. Let's say 20 cycles are required to load the chip, so $V$ is 20. Since $X$ ranges between 0.2 and 1.2, the term $X/B$ dominates the denominator, about 4 at the least. So $R$ is approximately $1 + \frac{fB}{X}$, or 1.1 at most. This is a minor effect, so we'll ignore it. \bibliographystyle{ieeetr} \bibliography{arch,transit,dpga} \end{document}