%* Last edited: Sep 6 00:43 1996 (misha) % -*- Mode: LaTeX; -*- \chapter{Introduction} %% Vision hard 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 scope of the challenge 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 form should the parallel computer take? Hundreds of parallel system designs have been proposed to attain this level of performance. 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. Currently, 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. 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. Despite this apparently inherent advantage, there are few SIMD systems in existence. The reason for the lack of widespread adoption of SIMD machines becomes obvious when the clock rates of RISC and SIMD systems are compared. \fig{cpucomp} compares the improvement in clock rate within several families of RISC processors to (mostly academic) SIMD designs. \mypsfig{BW/simdgap2.epsi}{cpucomp}{CPU and SIMD System Comparison}{CPU and SIMD System Comparison} %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. \paragraph{Thesis.} The thesis of this dissertation is that \emph{for the problem domain of early vision, parallel computers based on a SIMD %% reconfigurable bit-slice architecture can outperform those based on conventional processors by over an order of magnitude using the same silicon resources}. Hopefully, the thesis will also have several positive cultural effects. It will provide a convincing demonstration of the effectiveness of SIMD processing. The advent of VLSI technology gave SIMD systems a substantial advantage over their discrete-component based uniprocessor competition. With time, this advantage disappeared as SIMD clock rates remained unnecessarily low. This work aims to equalize the clock rates of SIMD and microprocessor systems and therefore regain the performance lead. Experience obtained through the detailed design shows that the clock rate barrier is largely illusory. Important 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 on SIMD machines. 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 research described in this document develops a reconfigurable architecture optimized for high speed VLSI, completes an aggressive implementation of the architecture, and evaluates the performance on standard computer vision algorithms. Parameters from the implementation are then used to investigate an analytical performance model. The existence of a concrete instantiation of the architecture allows empirical evaluation of the costs and benefits of reconfiguration. This thesis demonstrates the performance advantages of a high-speed VLSI reconfigurable bit-parallel (RBP) SIMD architecture on early vision tasks. The overall research approach is to: \begin{enumerate} \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 Complete a system-wide 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 work 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 allows 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. %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 %computers. % This document describes a VLSI-based parallel computer %architecture over ten times more powerful than any previously reported %computer in its class. %{\em Parallel computers based on reconfigurable bit-slice architectures can % be more than 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 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. % 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 encounters system-level consequences of a high speed parallel %computer. %\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. \paragraph{Abacus.} The Abacus architecture can be classified as a reconfigurable bit-parallel (RBP) machine. The key idea of a RBP design is to provide programmable interconnect to link multiple PEs into a single Processing Site (PS) that can operate on several bits of a data word simultaneously. Reconfiguration allows word width 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. 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.\footnote{Carlin says ``Crap''} %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{Organization} Chapter 2 presents an overview of the 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 demonstrating the the SIMD approach is competetive if the clock speed can be raised above previous levels, the discussion turns to issues of high-speed SIMD system designs. The chapter concludes with a review of related architectural performance evaluations. Chapter 3 describes in detail the motivations for an RBP organization, RBP arithmetic algorithms, and specifics of the Abacus design. Chapter 4 describes the implementation of the Abacus-1 chip at a fairly detailed level, as well as chip test results. Chapter 5 describes the system-level design of the Abacus machine, including the approach to issues of high-speed SIMD operation. Chapter 6 is the performance evaluation. It introduces the benchmark algorithms used to evaluate the architectural tradeoffs and 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. Chapter 7 describes the lessons learned from the design of the Abacus-1 architecture, and the set of changes required to produce a smaller yet more powerful design. Looking farther ahead, it introduces modifications that allow a redesigned Abacus element to function in multiple-SIMD mode, as a systolic processor, or to emulate random logic circuits effectively. Chapter 8 concludes with the implications of what has been learned from the design and suggests avenues for future research. % Local Variables: % mode: LaTeX % TeX-master: "main" % End: