%* 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: 




