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


