%%% * Last edited: Sep 5 02:44 1996 (misha) %%% $Log: related.tex,v $ %%% Revision 1.2 1996/08/23 12:43:13 misha %%% Before combining arch/theory. %%% \chapter{Previous and Related Work} %%% Since the scope of the thesis is rather broad, there is considerable amount %%% of related work. First, m Many systems have been developed to perform vision and image processing. The performance of the Abacus-1 design must be considered in the context of other major approaches. When the clock rate is boosted with aggressive design, SIMD machines are more than competetive with other approaches. A survey of previous work on the challenges of high-speed SIMD design indicates that an effective high speed design has not yet been worked out. Once such a design is developed, the processor/memory bottleneck becomes apparent. Dynamic reconfiguration may be used for tuning on-chip memory size to the needs of a particular algorithm at run-time. After analyzing previous reconfigurable machines, it is clear that none of them have been optimized for this sort of reconfiguration. %% Further, even theoretical analysis of the benefits of reconfiguration is %% inadequate. \mypsfig{simdblock.ps}{SIMD System Block Diagram}{simdblock}{SIMD System Block Diagram. The five interfaces shown are: local memory, instruction distribution, global feedback, inter-chip communiction, and data input/output. Although the PEs are shown arranged in an array, most architecture organize them in a 2-dimensional \mesh.} \section{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 (but few 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 \cite{Parkinson90}. 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. 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. 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}. 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} & {\bf 125} & {\bf 1000} & {\bf 32000} & {\bf 512} & {\bf 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 still lags Abacus. Both of these designs make the mistake of using single-ported 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 PADDI is an ideal high-performance, low chip-count solution. No other research SIMD machine in the literature even approaches the Abacus design in terms of performance per silicon area on low-precision integer operations. The 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. \section{High-Speed SIMD Issues} Recently a number of researchers have started to address system-level high-speed SIMD design issues \cite{Rockoff93,Allen95,Weems94}.\footnote{Mention Pixel-Planes 5!} The consensus problems are clock distribution, instruction generation and broadcasting, non-local data access. \paragraph{Clock Distribution} Since the clock skew budget is typically less than 10\% of the clock period, a 200~MHz SIMD array must maintain skew below 500~picoseconds. To overcome this problem, Weems \cite{Weems94} proposes a loosely synchronized SIMD processor. This degree of complexity is somewhat surprising since commercial chip sets with tunable delay times are easily available, and the salphasic \cite{Chi94} clock distribution scheme has been used to provide a 160~MHz clocks to 60 system boards with less than 200~psec of skew across a 10-foot-long system. \paragraph{Instruction Broadcasting} Rockoff \cite{Rockoff93} believes that distribution of finely synchronized instructions to hundreds of PE chips is a fundamental limitation on the clock rate due to transmission skew. His doctoral thesis is based on the idea of using instruction caches internal to each PE chip to allow operation faster than the transmission limit. The approach appears to be a complex solution to a non-problem, since sufficiently frequent registers along the transmission path can resynchronize the instruction stream. The cost of this retiming is increased latency in instruction distribution. Allen analyzes a tree-structured transmission and retiming model to determine an optimal number of stages. The model is mostly theoretical as it uses RC delays and clock rate as limitations instead of the actual transmission-line effects encountered at high speeds. Further, there is no good reason for different stages to have identical fanout factors, since there are differences both between inter-board and on-board wire delays, and between the receiving circuitry. The Abacus system design presents a method for synchronized instruction distribution along widely varying transmission paths that adds programmable delay elements to the instruction pads on each chip and retimes the signals on a pin-by-pin basis. This scheme allows propagation variations on the order of several cycle times with a skew equal to the clock skew. \paragraph{Instruction Generation} Another suggested bottleneck in SIMD performance is instruction generation. The traditional SIMD model is that instructions for operations such as 16-bit addition are sent from the host to the sequencer, where they are converted to a sequence of microinstructions to be executed by the PE array. Weems claims that between 20 and 50 RISC-like instructions are required to transform a single array instruction. The system design chapter presents three instruction generation techniques that in combination reduce the ratio of sequencer/array cycles to 1. In contrast, Weems proposes to solve the problem by substantially increasing the complexity of each PE chip to allow on-chip expansion of broadcast instructions. \paragraph{Data Cache} As in mainstream conventional microprocessors, high-speed implementations widen the gap between processor speed and main memory speed. The common approach is to insert a medium-speed memory between the small fast register file and the large slow main memory. SIMD machines are inherently cache-unfriendly, since \emph{any} cache miss by any PE will cause the entire machine to stall, and with a large enough machine, such a miss is virtually guaranteed. Allen observes that as long as PEs are allowed only direct memory accesses, all PEs will either miss or hit at the same time, and therefore proposes \emph{direct-only-data} caches. This is an interesting approach, but many vision and image processing algorithms are oblivious in the sense that their execution does not change as a function of data, and therefore the memory access patterns are known at compile time. As a result, the compiler can optimally manage the slower memory without using additional hardware at run-time. \paragraph{High Latency Issues} Allen points out that one of the costs of instruction synchronization via pipelined distribution is the increased latency of the array response to a sequencer command. This is an important issue, especially in the Abacus-1 design, which has a 10-stage pipeline. However, since the global OR computation already requires about 5 or 6 cycles, the extra two cycle cost of instruction pipelining is negligible, especially when the controller runs at least two (and possibly four) times slower than the parallel array. For any reasonable implementation, the pipeline cost is either zero or one one extra stall cycle per compare. In the pathological case of a very tight loop, there is a software technique for reducing the effect of a pipeline stall. Most iterative code does not damage the solution if it executes an extra iteration or two. Our proposed solution is to unroll the loop, checking for completion only once every 3 or 4 iterations. Since iterative code usually executes for at least dozens of iterations, the extra two or three iterations at the end are reduced to a 10\% cost. \section{Reconfigurable Architectures} The idea of dynamically changing the data path width to better match the algorithm requirements has been around since the earliest days of SIMD computing. The Illiac-IV, initiated in 1965 and completed in 1975 \cite{Illiac}, had 64 64-bit PEs that could be partitioned as 128 32-bit PEs or as 512 8-bit PEs. Three years before its completion, work started in Britain on the Distributed Array Processor (DAP) \cite{Parkinson90}, a bit-serial machine whose PEs could be configured together with a ripple-carry path to perform 64-bit arithmetic. This capability was not central to the architecture and operated with one eighth the throughput of the bit-serial mode. A prototype was produced in 1976 and a commercial model in 1980. The first VLSI-era member of the class, the reconfigurable processor array (RPA) \cite{Rushton89} was developed between 1985 and 1989 at the University of Southampton. Although a chip was designed and fabricated, a full scale computer was not completed. The RPA uses a mixed approach to reconfigurability. Although each PE processes two bits at a time and a data word is shared among several PEs, considerable hardware resources are devoted to supporting bit-slice operations. As a result, each PE is quite complex for a fine-grained machine. A substantially finer-grain architecture, Silt \cite{Barman90}, was designed at the University of British Columbia between 1988 and 1990. The design took a minimalist path, exploring the approach of minimal area and high clock speed. The Silt chip led to the Abacus design presented in this thesis. Work on Abacus began in 1991, and a full-scale chip was fabricated in 1995. In 1992, a reconfigurable processor, MGAP, was developed at the Pennsylvania State University. Its key distinction was the orientation towards a fully-redundant radix-4 arithmetic system. A second generation design, the MGAP-2, was completed in 1996. Mainstream processors have recently rediscovered and fully embraced reconfigurable processing. Driven by multimedia applications with similar characteristics to image processing, Sun's UltraSparc, Hewlett-Packard's PA-RISC, and Intel's MMX chips all support the partitioning of the 64-bit data path into 8 independent byte-wide processors. \section{Architectural Studies} SIMD machines are an attractive class of architectures to study since the effects of data path enhancement can be easily isolated from issues of control circuitry or cache organization improvements. A number of studies have been done, especially for vision applications. % Holman/Snyder (89): investigated area/performance tradeoffs in parallel % machines. Used metrics from coarse-grained processors. Good conclusions, % but did not consider off-chip memory effects. % Audet 92: \subsection{Normalized Analysis} A methodology for comparing parallel computer performance was described by Holman and Snyder \cite{Holman89,Ho90}. They introduced the distinction between three types of analysis: \begin{enumerate} \item \emph{cost-free} analysis, where absolute performance is the relevant metric, and the amount of consumed resources is not relevant. For example, cache studies are typically cost-free analyses since the comparison metric is absolute performance, neglecting the resource cost of the caches. \item \emph{budget-constrained} analysis, where different systems are compared under the constraint that they use identical amounts of hardware. \item \emph{normalized} analysis, where an improvement in a PE is compared to using the same hardware as the original PE, but using more processors. \end{enumerate} The approach is based on the generally true observation that ``There are two ways to improve any parallel architecture using additional hardware - by speeding up the processor elements or by adding more processor elements.'' There are clearly situations in which neither approach is very effective and indeed can be counterproductive. For example, in memory-bandwidth or communication-limited designs, speeding up the PE is not going to have a substantial effect on performance. Similarly, if the computation is already fully parallellized, with one PE per data item, adding PEs cannot improve the performance. The curious part of the work is that while analyzing optimal data path size, due to a fraction inversion error, the authors drew the exact opposite conclusion from the data. Specifically, analysis assumed that any area applied to making a PE more powerful could instead be applied to create a larger number of simple PEs, and that the resulting speedup is linear. Similarly, the area cost is linear in the size of the register file and ALU, and quadratic in the size of the shifter. The machine composed of many simple elements is termed the XPE machine, and the machine composed of fewer complex elements is the IPE machine. The basic unmodified architecture is the BA (base architecture) machine. They derive the following performance metrics for execution time, assuming $SU$ is the speedup provided by the enhancement, $f$ is the fraction of instructions affected by the enhancement, and $c$ is the chip area of the respective machines.\footnote{This is still kinda crappy --Carlin} \begin{equationarray}{lll} T_{IPE} & = & T_{BA} \left( 1 - f + \frac{f}{SU} \right) \\ T_{XPE} & = & T_{BA} \frac{c_{BA}}{c_{IPE}} \end{equationarray} Combining the two yields \begin{equation} \mbox{effective} su = \frac{T_{XPE}}{T_{IPE}} = \frac{c_{BA}}{c_{IPE}} \left( 1 - f + \frac{f}{SU} \right)^{-1} \\ \end{equation} To choose an example from the paper, consider a 4-bit PE and a 32-bit PE, with area ratio approximately 1:8. The Batcher implementation has $f=0.75$, leading to $su = 0.36$ (the paper computed 0.41). This is as expected, since the area penalty was a factor of 8, while the performance improvement was only a factor of 3. Nevertheless, the authors conclude that ``the best performance is obtained with a 32-bit data path''. We will see later that the determining factor in this design choice turns out to be the amount of silicon area dedicated to the memory, and the memory access patterns of the algorithm. The Holman/Snyder model does not account for the diminished storage capacity of each simplified PE. If the algorithm needs to access 16 32-bit words per pixel for one iteration, and only 2 32-bit words are available, the machine will perform a large number of memory spills. With the growing gap between processor and memory speeds, this effect becomes critical. \subsection{Simulation-Based Performance Evaluation} A simulation approach to SIMD performance evaluation was taken by Herbordt \cite{Herbordt94b}. His \emph{trace compilation technique} compiled traces generated on an abstract virtual machine 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 his dissertation is the trace compilation methodology, the tool was used to perform a number of architectural studies, and resulted in some interesting conclusions. 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 simulator is an excellent tool for evaluating system performance. It allows the architect to experiment with different virtualization ratios, datapath width, register file size, and off-chip memory latency. The potential danger is the unknown effect of the trace compiler quality on performance. The other inherent problem with the methodology is that algorithms were not optimized on a per-case basis: the same address trace was used for a wide variety of system parameters. Algorithms designed for the virtual machine are not necessarily optimal for a large memory or narrow datapath variant. Similarly, the virtual machine compiler generated code for a uniform memory access model, which is almost guaranteed to be suboptimal for a contemporary machine with a high disparity between on-chip and off-chip access times. Nevertheless, many of the results in Herbordt's work can be used directly as a starting point for selecting good concatenation factors for reconfigurable architectures. % The approach in this thesis is to hand-code characteristic inner loops of % key algorithms and optimize on a case-by-case basis. % Intent is to derive parameters for an analytical model. Possibility % of better insight into algorithm structure. \subsection{Dynamic Concatenation: Audet et al.} The performance advantages of reconfigurable architectures due to memory limitations were first evaluated by Audet et al \cite{Audet92}, who referred to reconfiguration as the Dynamic Concatenation Approach. The goal of the research was to determine the optimal number of PEs to be grouped into a PU, 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. For example, a particularly strange pipelining model was chosen, and execution times were scaled 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. The model assumes a static type of register assignment: the most frequently used variables are placed into registers, and the rest into memory locations. Algorithms that use one variable frequently in the first half of operation, and use another during the second half, would be forced to assign different registers even if their use did not overlap in time. As the methodology used UNIX-based C profiling tools to determine the often referenced variables, it is not clear whether the compilation was optimized for the right number of registers, or whether loop unrolling optimizations were made. 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. Virtualization could play a large role due to the time involved in restoring context. %Finally, the cost estimates of reconfiguration circuitry were suspect. %The analysis used transistors as a basis of area, which is often a poor %estimate, as different tr %Also, in Holman's terminology, this comparison is a cost-free %one. Reconfiguration ability is assumed without a notion of the %reconfiguration hardware costs. %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. \subsection{Phase-Specific Reconfiguration} Unlike earlier comparisons that maintained the same concatenation factor throughout an algorithm, this work broke vision algorithms into phases, and evaluated the performance of a particular CF on each phase \cite{Ligon94}. They found that changing CF between phases could improve performance by approximately 25\%.\footnote{Cut or expand --Carlin} %%% Local Variables: %%% comment-start: "%%% " %%% TeX-master: "main" %%% End: ***