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