% -*- Mode: LaTeX; -*- % File: summary.tex % Author: Mike Bolotski (misha@ai.mit.edu) % Copyright (C) Artificial Intelligence Laboratory, 1996 %*------------------------------------------------------------------------- %* FUNCTION: %* %* CLASSES: %* %* RELATED PACKAGES: %* %* HISTORY: %* Last edited: May 29 15:53 1996 (misha) %* Created: Mon Mar 18 20:23:21 1996 (misha) %*------------------------------------------------------------------------- \section*{Summary} Reconfiguration is the ability to dynamically configure memory organization, ALU width, or communication network topology to match the needs of the computational problem. {\em Parallel computers based on reconfigurable bit-slice architectures can be an order of magnitude faster on important applications than those based on conventional architectures}. This dissertation will validate the thesis with an implementation-based approach. The proposed research will develop a reconfigurable architecture optimized for high speed VLSI, complete an aggressive implementation of the architecture, and evaluate the performance on a standard computer vision benchmark suite. Parameters from the implementation will be used to investigate an analytical performance model. The existence of a concrete instantiation of the architecture will allow empirical evaluation of the costs and benefits of reconfiguration. %Reconfigurable computing, the ability for ALUs to function at different %word widths, has been around for some time. The advantages of flexibly %varying the word width have been demonstrated by a number of researchers. %However, this research has been inadequate because it hasn't addressed a %number of key issues: the true hardware costs of reconfiguration, the %constraints of high-speed operation, and the performance on real %applications. % This thesis aims to fill in these gaps by developing a %reconfigurable architecture optmized for high speed VLSI, completeing an %aggressive implementation of the architecture, executing a standard %computer vision benchmark suite on a simulator, deriving an analytical %model of the performance, with the parameters obtained from the hardware %and software implementations.\footnote{The main approach is to {\bf % implement}}. %This thesis investigates the design of a high-performance parallel SIMD %system designed for low-precision integer operations. The hypothesis %underlying the research is that a reconfigurable bit-slice approach can be %substantially more efficient than conventional bit-serial organizations and %more flexible than hardware bit-parallel. Preliminary support for this %conclusion has been obtained from a simplified model of hardware %and algorithms. The goal of the remaining work is to confirm the %conclusion by: Much of the research is already complete. A chip incorporating 1024 processors and designed to operate at 125 MHz has been fabricated. The processor array has been tested at up to 80~MHz and is expected to achieve the design target. Vision algorithms from the DARPA Image Understanding benchmark have been coded at a parallel assembler level. A preliminary performance model has been developed. The remaining tasks are: \begin{itemize} \item complete testing of external chip interfaces. \item implement a simulator for the architecture \item use the vision benchmark instruction traces from the simulator to make detailed architectural evaluations \item validate the an analytical performance model \item design a second-generation architecture that builds on the lessons of the initial implementation, with an eye to technology trends. \end{itemize} The organization of the thesis (and of the proposal) essentially follows the outline presented above. \begin{enumerate} \item {\bf Introduction and Motivation.} Describes the computational requirements of early vision and some parallel processing approaches to achieving these requirements. \item {\bf Previous and Related Work.} There is a substantial body of previous work relating to the topics of this thesis, from SIMD machines to modern architectural alternatives: the SRC PIM chip, Berkeley's PADDI-2 DSP, and FPGA based computing platforms. After the architectural discussion, this chapter evaluates related analytical performance models. \item {\bf Reconfigurable Bit-Parallel Architecture.} Describes in detail the motivations for an RBP organization, RBP arithmetic algorithms, and specifics of the Abacus design. \item {\bf The Abacus-1 Chip and System.} Describes the implementation of the Abacus-1 chip at a fairly detailed level, as well as chip test results. Also describes the issues of a high-speed SIMD machine and presents a relatively detailed design of the Abacus computer, including I/O and control issues. \item {\bf Parallel Vision Algorithms.} Describes a set of vision and communication algorithms chosen both for application value and for architectural evaluation. These algorithms include several from the DARPA Image Understanding Benchmark suite. Discusses the performance of Abacus on these algorithms. %\item {\bf Reconfigurable Mesh: Algorithms And Limitations.} %This unrelated chapter describes the algorithmic improvements to mesh %algorithms based on the RMESH machine model. It evaluates the match of real %VLSI technology to the model and practical speedups on Abacus. \item {\bf Architectural Tradeoffs.} Evaluates architectural tradeoffs such as local memory size, ALU width, off-chip memory bandwidth and network bandwidth based on instruction traces from the parallel algorithms. \item {\bf The Next Generation: Abacus-2.} Describes a set of modifications that allow a redesigned Abacus element to function in multiple-SIMD mode, as a systolic processor, or to emulate random logic circuits effectively. \item {\bf Conclusions.} The contents of this chapter will depend (somewhat) on the results of the actual research. \end{enumerate} \subsection*{Schedule} %% %\begin{table} \begin{center} \begin{tabular}{|l|l|l|l|} \hline Task & Time & Start & End \\ \hline Simulator coding & 14 & Mar 30 & Apr 12 \\ \hline Chip testing & 12 & Apr 13 & Apr 27 \\ \hline Architectural analysis & 14 & May 2 & May 16 \\ \hline Text writing & 28 & May 17 & Jun 17 \\ \hline \end{tabular} \end{center} %%%\end{table} %% \subsection*{Notes} %{ %\small %\begin{itemize} %\item Need to provide a hard model. %\item Encounter system level issues. %\item Already discovered that off-chip memory references are the dominant % factor. %\item Empirical evaluation of the costs of flexibility. %\item Concrete instationation of architecture type. %\item Obtain reasonable limits on communication time. %\item Incorporate overhead of reconfiguration time. %\item Benefit is eacy, but cost analysis requires silicon area and % execution time estimates. %\item Research answer question of ``what does flexibility get you and how % much does it cost?''. %\item To fully answer the question, need to push limits of implementation. %\end{itemize} %} \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. % Local Variables: % mode: LaTeX % TeX-master: "main" % End: