%* Last edited: May 29 17:23 1996 (misha)



\MaplePlotWidth=\textwidth
\MaplePlotHeight=60ex


\section{Optimal Bit Width Analysis}

Selection of the bit slice width in a SIMD computer is yet a solved
problem. Early PEs were bit-serial due to VLSI area constraints. Some
designs have upgraded to a conventional 32-bit datapath, while others moved
to only 8 bits, even in a contemporary technology.  This section develops a
simple model that examines various slice widths in terms of silicon area
efficiency.

Development proceeds in four steps. First, we estimate the area, delay, and
cycles-per-instruction (CPI) of a given bit width and simply multiply to
obtain the figure of merit. This metric, called \emph{quality} in this
work, is normally expressed in bit operations per nanosecond per unit area,
but for easier intuition has been scaled to billions of 16-bit operations
per second per standard chip.

Second, we use Amdahl's law to account for operations which are not sped up
by a wider datapath.  Third, recognizing that off-chip memory latency is a
critical bottleneck, we determine the effect of cache misses.  Finally, we
evaluate the performance gain of the background loading mechanism on the
Abacus architecture.  We begin by describing the assumptions and
limitations of the model.

\begin{Table}{modelparams}{Analytical Model Parameters}{Analytical Model Parameters}
\begin{tabular}{|l|l|l}
\hline
Parameter & Value & Description \\
\hline
$A_{ALU}$ & 8 & ALU area, in units of SRAM cells \\ \hline
$f_A$     & 0.9 & Fraction of operations affected by wider datapath \\ \hline
\end{tabular}
\end{Table}


\subsection{Model Assumptions and Limitations}


\subsubsection{PE Area}

A processing element's area is modelled as consisting of three parts: the
memory cells, the ALU, and the other overhead circuitry, including the
network and the data plane registers.  The basic unit of area is the SRAM
cell. 
\begin{equation}
A_{PE} = m + kA_{ALU} + A_{ovr}
\end{equation}

where $k$ is the width of the datapath and $m$ is the number of memory
bits.  Thus, area growth is linear in the datapath. There will be slight
area growth in overhead components, such as in the size of the buffers
controlling the datapath, but that can be folded into the ALU area.  An
important immediate assumption is that $AT^2$ circuits such as multipliers
and barrel shifters are not present.  These elements have important
applications and should be analyzed in later work, but their inclusion in a
massively parallel system must be evaluated carefully, since their area
grows quadratically with decreased cycle time, and parallelism provides a
more efficient alternative.

\subsubsection{Cycle Time}

\subsubsection{Off-Chip Memory Accesses}

The analysis of the effect of off-chip bandwidth implicitly assumes that
commercially available memory technology will be at least one technology
jump from that available to a university or even a low-volume commercial
design.  If this situation changes, this model will have to be reevaluated.


\paragraph{Pin Bandwidth}

\paragraph{Number of Pins}

\paragraph{Power Issues}

In the sense of raw performance, the design is optimal when the off-chip
memory pathway is constantly busy with a minimal number of PE stalls. At
that design point, the internal PE area has been pared down to provide as
much on-chip processing power as possible.  However, this mode of operation
is probably not optimal under the power consumption metric, since large
off-chip buffers are constantly active.   This multivalued optimization
problem is an interesting avenue of future research.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{Amdahl's Law}

\begin{Table}{holmanfractable}{Fraction of Operation Costs Affected by Data Path
    Width}{Fraction of Operation Costs Affected by Data Path Width. From
    \cite{Holman90}}
\begin{tabular}{|l|r|}
\hline
Program & f \\
\hline
Bitonic Sort & 0.75 \\
Matrix Product & 0.94 \\
LU Decomposition & 0.76 \\
Cholesky Decomposition & 0.25 \\
Jacobi Method & 0.91 \\
SOR Method & 0.91 \\
SIMPLE & 0.71 \\
\hline
\end{tabular}
\end{Table}

Herbordt's evaluation of parallel architectures included a set of
simulation results relating datapath width to execution time. Amdahl's
function was fitted to the data points and generated good agreement with
data (although half of the algorithms had unexpectedly high performance for
the case $k=1$).  The fitted data is tabulated in \tab{herbordtfractable}.
The algorithms clearly fall into two classes: mostly bit oriented, with
only $f_A=0.2$ and mostly word oriented, with $f_A=0.9$. The IU Benchmark
entry is a composite of several algorithms.

\begin{Table}{herbordtfractable}{Fraction of Operation Costs Affected by
    Data Path}{Fraction of Operation Costs Affected by Data Path. From
    \cite{Herbordt94}}
\begin{tabular}{|l|r|}
\hline
Program & f \\
\hline
Region-based Line Finder & 0.15 \\
Curve-Fitting Filter & 0.92 \\
Correspondence Problem & 0.21 \\
Fast Line Finder & 0.07 \\
IU Benchmark & 0.41 \\
Depth From Motion & 0.80 \\
\hline
\end{tabular}
\end{Table}

An important source of non-accelerable operations is network operations. In
a multi-chip system, every communication must cross a chip boundary, and
the number of pins does not grow with data path width.  Simple filter-style
algorithms such as convolutions require one mesh move operation for each
multiply and add. If the multiplication is by a known constant, an average
eight-bit multiplication requires four shifts and five adds. Thus,
approximately 90\% of the operations benefit from a wider datapath.
The remainder of the chapter uses $f_A=0.9$.





\subsection{IO}



\subsection{Background Loading}

\subsection{Background Loading}

A memory access on the Abacus machine has a latency of 40 cycles, but can
be initiated before the data is actually required. Only one outstanding
memory reference can be pending.  We would like to determine the benefit of
this feature compared to the worst-case penalty of 40 cycles.  The key
parameters are the latency of a reference, and a distribution probability
on consecutive non-memory references Our first order model assumes a
uniform probability $p$ of an off-chip memory reference.  Thus, the
probability of a sequence of $k$ on-chip references before an off-chip
reference is:
\begin{equation}
  P(N=k) = (1-p)^{k-1}p
\end{equation}

\begin{figure}[                hbtp]
  \begin{center}
    \leavevmode
    \mapleplot{Pk_vs_k.ps}
  \end{center}
  \caption{Probability of an on-chip hit sequence of length $k$ for
    different values of $p$, the miss probability. Note that for high $p$
    almost all the area under the curve is near small values of $k$, and
    therefore long load times.
    }
  \label{fig:seqprob}
\end{figure}

This distribution is shown in \fig{seqprob}.  Notice that the probability
of long sequences is small if $p$ is high.  Therefore, we expect background
loading to help only in the case of low $p$ or low latency.  Since the
loading time given a string of $k$ available cycles is $L-k$, the expected
loading time is:
\begin{equation}
  E[T]  =  \sum_{k=1}^L{q^{k-1}p(L-k)} = \frac {(\,1 - {p}\,)^{{L}} + {p}\,{L} - 1}{{p}}\\
   \end{equation}



\begin{figure}[                hbtp]
  \begin{center}
    \leavevmode
%%    \mapleplot{Leff_vs_f1.ps}
    \mapleplot{Leff_vs_f2.ps}
  \end{center}
  \caption[Effective latency vs latency due to background loading as a
  function of $L$ and $p$]{Effective latency vs latency due to background
    loading as a function of $L$ and $p$. The advantage of background
    loading occurs in a relatively narrow zone: where the frequency of
    loads is very low to begin with, and where latency is low. For low
    values of $L$, the ratio may not be really important, since it
    approaches internal access time.}
  \label{fig:leff}
\end{figure}

Still, even for relatively large  of $L$ and $p$\footnote{40 and 0.1, respectively}, we can get a 3X speedup.

%\begin{figure}[                hbtp]
%  \begin{center}
%    \leavevmode
%\mapleplot{Leff_vs_m.ps}
%  \end{center}
%  \caption{Effective Latency as a function of $m$. This }
%  \label{fig:leff}
%\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{Figure}{idealq}{Foo}{Long Foo}
    \leavevmode  \mapleplot{idealq.eps}
  \end{Figure}
  
\begin{Figure}{idealqn}{Foo}{Long Foo}
    \leavevmode  \mapleplot{idealqn.eps}
  \end{Figure}

\begin{Figure}{amdqn}{Foo}{Long Foo}
    \leavevmode  \mapleplot{amdqn.eps}
  \end{Figure}

\begin{Figure}{amdqn3d}{Foo}{Long Foo}
    \leavevmode  \mapleplot{amdqn3d.eps}
  \end{Figure}

\begin{Figure}{amdqn3d2}{Foo}{Long Foo}
    \leavevmode  \mapleplot{amdqn3d2.eps}
  \end{Figure}

\begin{Figure}{tltc}{Foo}{Long Foo}
    \leavevmode  \mapleplot{tltc.eps}
  \end{Figure}

\begin{Figure}{dio3d}{Foo}{Long Foo}
    \leavevmode  \mapleplot{dio3d.eps}
  \end{Figure}

\begin{Figure}{tltc3d}{Foo}{Long Foo}
    \leavevmode  \mapleplot{tltc3d.eps}
  \end{Figure}

\begin{Figure}{qio5}{Foo}{Long Foo}
    \leavevmode  \mapleplot{qio5.eps}
  \end{Figure}

\begin{Figure}{tleftc}{Foo}{Long Foo}
    \leavevmode  \mapleplot{tleftc.eps}
  \end{Figure}

\begin{Figure}{didb3dk}{Foo}{Long Foo}
    \leavevmode  \mapleplot{didb3dk.eps}
  \end{Figure}

\begin{Figure}{qback5}{Foo}{Long Foo}
    \leavevmode  \mapleplot{qback5.eps}
  \end{Figure}

\begin{Figure}{qio3d}{Foo}{Long Foo}
    \leavevmode  \mapleplot{qio3d.eps}
  \end{Figure}

\begin{Figure}{qb3d}{Foo}{Long Foo}
    \leavevmode  \mapleplot{qb3d.eps}
  \end{Figure}

\section{Architectural Tradeoffs}

In this section we begin to develop a performance model for the Abacus
computer.

\subsection{Representative Algorithms}

Low level vision applications can be divided into four broad categories
based on the required communication.


\paragraph{Point}.  No communication occurs, as each pixel is updated
based only on its value. Examples of this algorithm class are thresholding,
pixel quantization, and image differencing.

\paragraph{Neighborhood.}  Communication occurs only over a small region
surrounding a pixel, typically a 3 by 3 or a 5 by 5 neighborhood. The basic
instance of this algorithm class is spatial convolution with a mask to
perform linear filtering operations such as low pass filtering. Edge
detection can be performed by thresholding the result of a high-pass filter
operation.  Non-linear operations such as median filtering, anisotropic
diffusion, and morphological operations also fall into this class.

Several non-local algorithms have been converted into a systolic form, and
can therefore be performed with purely local communication. The Hough
transform falls into this class.


\paragraph{Data Reduction.} Communication is global but non-overlapping.
Initially dense image-wide information is condensed to a few numbers.
Responder count is an example of such an operation.

\paragraph{Dense Transform.}  Communication is global and
overlapping. Fast Fourier transforms and sorting operations are an example
of this class.



\subsection{Slice Optimization}

In addition to the usual architectural and algorithmic parameters, the RBP
organization allows a compile-time selection of the concatenation factor
$m$.  This is the number of PEs grouped into a single PS.  We would like to
determine the optimal number of bit-slices operating for a particular
algorithm.  Assume the following constants:

\begin{table}[                hbtp]
  \begin{center}
    \leavevmode
    \begin{tabular}{|c|l|}
      \hline
      Name & Description\\
      \hline
      \multicolumn{2}{|c|}{Architectural} \\
      \hline
      D & Number of registers in slice \\
      k & Slice width\\
      B & Bandwidth into each slice (per bit)\\
      \hline
      \multicolumn{2}{|c|}{Algorithmic}\\
      \hline
      R & Number of variables in algorithm\\
      W & Bits in data word \\
      N & Number of ops in sequence\\
      Z & Number of answers and initial data items\\
      \hline
      \multicolumn{2}{|c|}{Derived}\\
      \hline
      f & Fraction of register misses (function of R,E)\\
      E & Effective registers per pixel\\
      \hline
      \multicolumn{2}{|c|}{Compiler Decision}\\
      \hline
      m & Number of slices / pixel\\
      \hline
    \end{tabular}
  \end{center}
  \caption{Architectural and Algorithmic Parameters}
  \label{tab:param}
\end{table}

Thus, a processing site consists of $m$ slices of $D$ registers each of $k$
bits. There are $W$ bits in each data word.  The number of effective
registers per pixel is the total number of bits in a processing site
divided by the word length:


\begin{equation}
  E = \frac{mkD}{W}
\end{equation}

%We have some constraints.  First, there is at least 1 slice allocated per
%pixel. Second, we have no more than $\frac{W}{k}$ slices per pixel (full
%bit-parallelism): $W/k \geq m \geq 1$.  \footnote{As a (not very useful)
%  consequence, $W/mk > 1$, so that $D \geq E$.}


The time to load a word/operate on a word is equal to the number
of bits to be loaded divided by the cumulative bandwidth/ALU width of the
slices doing the loading:
\begin{equation}
  T_{load}  = \frac{W}{mBk} \ \ , \ \ \   T_{alu} = \frac{W}{mk}\\
\end{equation}


So we model an operation sequence on a single pixel as loading some initial
number $Z_{in}$ of words from off-chip memory, performing $N$ arithmetic
operations, and writing $Z_{out}$ result words out, for a total of $Z$
loads and stores. Equation \ref{eq:proctime} gives the time required for
processing a single pixel, assuming that for every memory fault the
processor has to write the previous value to memory and load the requested
value. This memory fault is going to occur on some fraction $f$ of the
memory accesses.

\begin{equation}
\label{eq:proctime}
  T_{seq} = Z T_{load} + 2Nf(R,E)T_{load}  + NT_{alu}
\end{equation}

Assume that there are $P$ pixels to be processed and $M$ slices to process
them. If $m$ slices are allocated to a pixel, $M/m$ pixels are processed in
a time step of $T_{seq}$, so that $Pm/M$ iterations are required.  It is
convenient to define the quantity $l=Z/N$, the ratio of initialization
operations (forced cache misses) to iterative operations (possible cache
hits).


\begin{eqnarray*}
  T_{tot} & = & \frac{P}{M}m T_{seq}\\
          & = & \frac{P}{M}m \left[ \left( Z+2Nf(R,E) \right) \frac{W}{mBk} + N\frac{W}{mk}  \right] \\
%%          & = & \frac{PW}{Mk}\left[ \frac{Z+2Nf}{B} + N \right] \\
%%        & = & \frac{PWN}{Mk}\left[ \frac{Z/N+2f}{B} + 1 \right] \\
          & = & \frac{PWN}{Mk}\left[ \frac{(l+2f)}{B} + 1 \right] \\
          & \propto & \frac{(l+2f)}{B} + 1 \\
\end{eqnarray*}

%% Of course, if $m>k$ , then $T_{alu}$ saturates at 1.


The simplified model presented in this chapter does not consider the
disadvantages of RBP, such as the overhead of PEs whose ALUs are unused, or
the distribution of conditional information to each PE. Therefore, the
obtain optimal concatenation factor $w$ will always be too high.
Nevertheless, the performance improvement is an upper bound on the
advantage of RBP.  However, the analysis applies only to single-phase
algorithms.  The flexibility advantage has not been incorporated.

So, we would like to choose $m$ to minimize $T_{tot}$, given the algorithmic
constraints of $W$, $N$, $Z$, $f$; the architectural constraints of $B$ and
 $D$.  We could evaluate this exactly, except that we do not know the
behavior of the miss function $f(R,E)$.  So we'll explore some plausible
functions.

\begin{enumerate}
\item {\em Case 1: No Cache Misses}.  If $R < E$, we have enough local
  storage and $f = 0$.  $Q$ then becomes independent of $m$.  This
  indicates a bad initial design point: both in the nibble-serial mode and
  in the nibble-parallel mode, all data fits in memory. Therefore, the
  memory is too big.


\item {\em Case 2: All Cache Misses}.  If the algorithms steps repeatedly
  through all the registers, the miss rate is effectively 100\%. Again, the
  number of nibbles allocated is irrelevant.

\item {\em Case 3: Random Register Usage}.  If the register used during
  each step is selected at random from the logical registers, there is a
  $E/R$ probability that it is already in the cache. $f$ is therefore
\begin{equation}
f(E,R) = 1-\frac{E}{R} = 1 - \frac{mkD}{WR} = \frac{WR - mkD}{WR}
\end{equation}

So, to maximize performance we want to lower $f$ and therefore increase
 $m$.
\end{enumerate}

In conclusion, $m$ should always be maximized.



\subsection{Conclusion}

The following plots are for parameter settings of:
\begin{center}
\small
\begin{tabular}{|c|l|r|}
\hline
\hdr{Variable} & \hdr{Meaning}  & \hdr{Value} \\
\hline
Dr & number of registers in slice & 50 \\
k  & slice width & 1   \\
Bw & bandwidth into each slice (per bit)& 0.05 \\
R   & registers in algorithm & 30  \\
Wb & bits per word & 16   \\
Z  & initial loads/saves & 10   \\
N  & number of operations in a sequence& 30   \\
\hline
\end{tabular}
\end{center}


\begin{figure}[                hbtp]
  \begin{center}
    \leavevmode
   \mapleplot{perf_func_m.ps}
  \end{center}
  \caption{Execution time as function of $m$.  The dip in the middle is the
    effect of background loading.  Without it, the graph would have
    continued in a straight line.  Notice that the dip occurs at a
    non-useful $m$ value, as it is difficult to evenly partition a 16-bit
    value.}
  \label{fig:execfuncm}
\end{figure}

The algorithm requires 480 bits. At 9.6 slices per pixel, there are no
external references and time is constant. Background loading makes a
difference only in a narrow zone.  Until about $m=7.8$, The linear
performance improvement is due to the linearly decreasing hit frequency in
our simplified model.



\begin{figure}[                hbtp]
  \begin{center}
    \leavevmode
   \mapleplot{cycles_vs_m_bw.ps}
  \end{center}
  \caption{Execution time as function of m and bandwidth}
  \label{fig:execfuncm2}
\end{figure}

The main conclusion is that external memory references are catastrophic,
and that the number of bit-slices should be chosen to minimize the number of
external loads.


The model can be made more accurate in a number of ways.
\begin{enumerate}
\item Accounting for the circuit density improvement of higher-width bit
  slices.
\item Speed decreases due to larger ALU widths. Of course, this may not matter
  if the cycle time is dominated by memory access.
\item Slower memory accesses with increasing memory size.
\item Better estimates of cache miss behavior as a function of available
  registers.
\end{enumerate}

As illustrated by the graphs in this section, the last modification is
probably the most significant, since the initial three factors are not
likely to be more than a factor of 2 each, while cache misses can result in
order of magnitude performance changes.



\section{Misc}

There are a number of methods to compare design tradeoffs; holdings some
parameters constant while varying others. For reconfiguration analysis, the
hardware is fixed, and only the number of slices operating on a data word
is varied.

In this design example, we return to a design-time analysis, and compare a
bit-serial system with a bit-parallel one. The BP system may or may not be
reconfigurable.

Consider a PE with 2 cycles/bit bandwidth to external memory.  This is
typical of a chip containing 1000 PEs, operating at Consider an algorithm
that requires 1000 ops, and has 10\% misses.

The bit-serial system needs 16K ALU cycles, and encounters 100 misses.
These misses are spaced 9 ops apart, which is 144 cycles. Assuming a load
and a store, each miss costs 2 x 16 x 2 = 64 cycles.  is plenty of time to
do loads between misses. Total time is 16K.

The bit-parallel system with the same memory contents encounters the same
number of misses. BUT its misses are 36 cycles apart, so each miss now has
to wait for 28 cycles. So the 100 misses cost 2.8K cycles. Now, since
computation took 4K cycles, the total time is 6.8K. The fourfold advantage
has now dropped to 2.5.

The same thing without background loading. The 100 misses cost the same in
both cases, 6.4K cycles. The ratio is now (16+6.4)/(4+6.4) = 2.15.

This is somewhat surprising. The background loading helps the bit-parallel
case more than the bit-serial case. Why? Because the IO time is a larger
share of the total compute time. In the first case, total time time dropped
from 22.4 to 16.4. A factor of 0.73.  In the second case, total time
dropped from 10.4 to 6.8, a factor of 0.65.


\section{Local Memory vs External Bandwidth}

In this section we determine how performance on an algorithm varies as a
function of the size on-chip register file, and the off-chip memory
latency.  The limiting cases are obvious. When the entire computation fits
into the register file, the off-chip latency becomes irrelevant. When
latency is very low, there is no need for a register file at all. If we
plot performance as a function of register file size $s$ and off-chip
memory latency $l$, we get a slope falling off to the northwest, where both
latency is high and on-chip capacity is low.

So, for an given acceptable level of performance, we can travel the curve,
trading off capacity for latency.  To convert this expected graph into a
design optimization tool, we need to assign resource costs and physical
limitations, based on current technology.  This cost assignment is a
challenging task, since it incorporates a good number of technology
assumputions.

\begin{verbatim}
 Latency      | L L L M
  High        | L L M H
              | L M H H
              | M H H H
  Low         | H H H H
              ------------
              Low     High
                RF Size
\end{verbatim}



\subsection{Assumptions}

The approach will be be to list assumptions and upcoming technology trends
that will affect them, as well as the direction of change.

\begin{itemize}

\item Perimeter-based IO structure.  Although area-based interconnect
  technologies are coming, they are not dominant. [references. expand].

\item Double-ring structure.  Bonding to a double-ring structure is not
  difficult.

\item 100 micron pitch pads. Lower pitch will decrease the cost of off-chip
  bandwidth.

\item Low inductance area-based packages. BGAs are coming.

\end{itemize}


There are a number of limitations on off-chip access times, based on both
existing technologies, and other design constraints. For example, assume a
10~ns PE cycle time.  Off-chip memory latency consists of two parts. First,
the basic access time of the memory, which can be negligible for a modern
fast SRAM, or significant for a DRAM-based memory such Rambus. By
negligible, I mean times as low as 4~ns for a fast SRAM [ref Chappel]). By
significant, I mean several cycles.

The second component is the bandwidth-limitation imposed latency of getting
the 1000 bits of data or so onto the PE chip through a relatively narrow
bus.  For example, with a 32-bit bus, a 2:1 external/internal cycle time
(16~ns SRAM cycle time, 8~ns internal), 64 cycles are required to load each
of 1024 PEs with a data bit. This second component dominates the overall
latency for any reasonable technologies.

The following table assumes that one memory access is required for every
arithmetic operation. Therefore, total bandwidth in bits/nanosecond is
the GOPS rating multiplied by 16. This model assumes an accumulation
based operation, in which an internal register is updated by an external
value. If each arithmetic operation used two new operands and wrote one
new result, such as in an elementwise vector multiply, the bandwidth
requirements would go up by a factor of three.


\begin{table}
\begin{center}
\begin{tabular}{|l|r|    r     |r  | r   |  r   | r|r|}
\hline
Name         & PEs  & Width & Clock & Cyc/op & GOPS & Bus  & bit rate \\
             &      &       & (MHz) &        &      &      & bits/pin/ns \\
\hline
Abacus-1, BS   & 1024 & 1     & 125   & 1      & 7.5  &  64  &  1.88 \\
Abacus-1, BP   & 1024 & 1     & 125   & 3      & 2.5  &  64  &  0.63 \\
Abacus-2/4     &  256 & 4     & 100   & 1      & 6.4  &  64  &  1.60  \\
Abacus-2/8LC  &   64 & 8     &  62   & 1      & 2.0  &  8  &  4.00 \\
\hline
\end{tabular}
\end{center}
\end{table}

%%The Abacus-8/LC part is designed to fit into a plastic package with a small
%%number of pins. It therefore sacrifices performance density for substantially
%% lower cost.



\subsection{Cost Analysis}

The cost issue is difficult to establish, because of multiple interacting
factors. For example, a low cost design point uses cheap packages with
relatively high package parasitics. But reducing the supply voltage to deal
with the low thermal tolerance of plastic packages also reduces the peak
current draw, and therefore the ground bounce.

Finally, pricing is a delicate matter of balancing chip carrier cost, PCB
cost, defect probability, ease of assembly, and a host of other factors.  Any
analytical equations are therefore misleading in their apparent exactness. At
best, they will serve as guidelines.

Even if this was possible, it would be difficult to assign a cost to
integration. In the extreme case, the best performance per area would be
obtained by a small number of processors with a large pad ring. External
memory accesses would have very low latency in this configuration, so that
very little silicon area need be devoted to the register file. The apparent
performance per area would increase, but at the cost of integration. This
effect will be ignored (instead of say, weighing the number of chips in a
design as part of the cost), but the number of chips required to process an
image will be noted for qualitative evaluation.

\paragraph{Pads}

The equation for the number of pads consts of three parts:
\begin{enumerate}

\item A fixed component due to the instruction, boundary scan, and IO wires.
  This is estimated at 40 pads for a 40-bit instruction word, assuming
  instructions are sent using both clock edges.

\item A slowly varying component of mesh communication wires. Once a
  particular mesh move latency is accepted (say four cycles for a 16-bit
  number, requiring four bits per edge element per cycle), the pad count
  grows as the square root of the total datapath width. Of course, the
  dimensions of the PE array will most likely be powers of two. For example,
  the 1024-bit Abacus-1 data path organized as 16-bit clusters is effectively
  an 8 x 8 array of 16-bit PUs. To transfer a 16-bit number between chips
  with a latency of four requires 4 bits/cycle/edge PU, or 32
  bits/cycle/edge. Assuming sending on both clock edges, each edge must have
  16 pins. Including three control wires per port, the total pin cost was 76.

  In vertical slice mode, $t_{ALU} = 16$, so it can take up to 64 cycles to
  transfer the 16 bits. This is 0.25 bits/cycle/edge PU, or 8
  bits/cycle/edge. Total pin cost is only 44.

  Consider the 8 x 8 array of 8-bit PUs. Transfer of a 16-bit number with a
  latency of eight cycles (four times $t_{ALU}$) requires 2 bits/cycle/edge
  PU or 16 bits/cycle/edge. Each edge must only have 8 data pins, or 11 pins
  in total.

\begin{displaymath}
  N_{mesh} =  4 \times (\sqrt{\frac{N_{datapath}}{\mbox{PE Width}}} + 3)
\end{displaymath}

\item A quickly varying component of memory subsystem wires.
\end{enumerate}

\begin{table}
\begin{center}
\begin{tabular}{%
|l     |l      |l      |l      |l      |l      |l |}
\hline
Pads&    w1  &    h1  &    W    &   H    &   Area &   Core\\
\hline
208 &    52  &    48  &    8.4  &   7.8  &   65.5 &   56.2\\
208 &    39  &    61  &    6.5  &   9.8  &   62.9 &   53.5\\
208 &    26  &    74  &    4.5  &   11.7 &   52.7 &   43.3\\
\hline
336 &    84  &    80  &    13.2 &   12.6 &   166.3&   151.2\\
336 &    63  &    101 &    10.1 &   15.8 &   158.3&   143.2\\
336 &    48  &    116 &    7.8  &   18.0 &   140.4&   125.3\\
\hline
448 &    112 &    108 &    17.4 &   16.8 &   292.3&   272.2\\
448 &    84  &    136 &    13.2 &   21.0 &   277.2&   257.0\\
448 &    96  &    124 &    15.0 &   19.2 &   288.0&   267.8\\
\hline
\end{tabular}
\end{center}
\end{table}

\begin{table}
\begin{center}
\begin{tabular}{%
|l     |l      |l      |l      |l      |l      |l |}
\hline
Pads&    w2  &    h2  &    W    &   H    &   A2   &   Core\\
\hline
208 &    26  &    24  &    4.5  &   4.2  &   24.5 &   14.0\\
208 &    20  &    31  &    3.5  &   5.2  &   23.8 &   13.4\\
208 &    13  &    37  &    2.5  &   6.2  &   21.3 &   10.8\\
\hline
336 &    42  &    40  &    6.9  &   6.6  &   54.0 &   37.8    \\
336 &    32  &    51  &    5.3  &   8.2  &   52.0 &   35.8    \\
336 &    24  &    58  &    4.2  &   9.3  &   47.5 &   31.3    \\
\hline
448 &    56  &    54  &    9.0  &   8.7  &   89.3 &   68.0    \\
448 &    42  &    68  &    6.9  &   10.8 &   85.5 &   64.3    \\
448 &    48  &    62  &    7.8  &   9.9  &   88.2 &   67.0    \\
\hline
\end{tabular}
\end{center}
\end{table}


\begin{displaymath}
Area_1 = p^2wh + 2lp(h+w) + 4l^2   \\
Area_2 = p^2wh + 4lp(h+w) + 16l^2
\end{displaymath}


\subsection{External Memory Alternatives}

The emergence of multimedia and video-intensive applications, as well as the
ever increasing clock speeds in systems, has outpaced the abilities of
standard random access memory. RAM manufacturers have improved technologies
and developed new architectures in response to this demand for higher memory
speeds. This explosion of new RAM types will require careful analysis of the
operating trade-offs among the various alternatives to make best use of
capabilities of the new generation of memories.

\begin{table}
\begin{center}
\begin{tabular}{|l |  r|    r     | r |r|r|}
\hline
Name         & Width  & Cycle & Initial Latency & Data Rate  & Addr Line \\
             & (max)   &  (MHz) &  (ns)          & bits/pin/ns & Overhead \\
\hline
%% 0.6 GB/sec -> 0.6 bits/ns
Rambus       & 9      & 600 & 50            &  0.6   & 4 \\
SSRAM        & 32     & 100 & 5             &  0.1   & 18 \\
SDRAM        & 32     & 100 & 50            &  0.1   & 22 \\
EDRAM        &  8     &  66 & 30            &  0.066 & 22 \\
\hline
\end{tabular}
\end{center}
\end{table}

Note: incorporates about 17 ns of  controller pipelining.


\begin{table}
\begin{center}
\begin{tabular}{|l |    r|    r     | r      |  r      |r|r|}
\hline
Configuration   & Pins   & Pins     & BW      & Lat & Lat  & Lat\\
                & Total  & Signal   & bits/ns & init& data & Tot \\
\hline
Rambus, 1 port  &  13    &  9      &   5.4    & 50 & 190  & 240 \\
Rambus, 2 ports &  26    &  18      & 10.8    & 50 & 95  & 145 \\
Rambus, 3 ports &  39    &  27      & 16.2    & 50 & 63  & 113 \\
SSRAM, 32 bits  &  50    &  32      & 3.2     &  0 & 320 & 320 \\
SSRAM, 64 bits  &  82    &  64      & 6.4     &  0 & 160 & 160 \\
\hline
\end{tabular}
\end{center}
\end{table}


\section{Virtualization}

This analysis assumes a neighbor organization, where a rectangle of
adjacent pixels is mapped onto one WU.  If all virtual pixels fit into
memory, only perimeter data moves require actual communication between
chips.  Thus, if each pixel holds a 3 by 3 neighborhood, only 3 grid
operations are required for a move of all 9 pixels. The rest are internal
memory transfers, or even better, just different local references, which
are free.

\begin{figure}
\begin{center}
\sl \Large VP Perimeter picture
\begin{verbatim}
A2 = FromWest(B3);
A0 = FromWest(B1);
A1 = B0;
A3 = B2;
\end{verbatim}
\end{center}
\end{figure}

High VP ratio also reduce the peak memory requirements of
algorithms. Consider a VR of 16, and the following code segment
(implementing a triangle filter).

\begin{figure}
\begin{center}
\sl \Large VP Perimeter picture
\begin{verbatim}
T1 = FromWest(A);
T2 = FromEast(A);
T2 = (T1 + T2)/2 + A;
\end{verbatim}
\end{center}
\end{figure}


A VR1 WU would transfer T1 and T2 to itself, for a WU requirement of 48
bits (assuming each word is 16 bits). Peak memory requirement for 16 of
these units is 768 bits. The VR16 WU need only use one scratch location for
computing T1, reducing memory needs to $2 \times 16 + 1 = 33$ words of 16
words each, or 528 bits.

Actually, the VR1 ALUs can also perform this reduction if they can compute
with each bit as it comes in, and then discard it.
 

For fast update code, where little computations occurs for every grid
  move, high VP ratios are preferred

  As edge-crossing latencies increase, high VRs will be more favorable.

Consider a VP ratio of 16 when implemented with a 16-bit WUs, which would
be 1 with 1-bit WUs.  A single move operation requires 4 grid moves in the
first case, and 16 in the second. But a grid move of a 4x4 cluster requires
4 cycles, while a grid move of a unit cluster requires only one.  In each
case, the move of 16 pixels requiers 16 cycles. Adding a one cycle penalty
on each transfer due to pipelining leads to 4 * 5 = 20 cycles for the
first, and 16 * 2 = 32 cycles for the second. Extra latency on pin
crossings favors high VP ratios, since its cost is amortized on a move of
several bits in the high VP case.

\paragraph{Foo}

It is clear that concatenation implies virtual processors. Obviously, each
word unit now must iterate over $m$ PEs.  The model in Audet's paper
ignores issues such as context swaps at synchronizations. For example, the
associated \emph{active} bit must be restored for each VP.  While it is
true that simple image filtering operations do not use the active bit, many
other algorithms do. Every algorithm that contains a \emph{where} clause
will be more expensive for wide WUs. In the extreme case of a very simple
computation such as logical AND, the highly concated WU will be twice as
slow, as the active restore overhead takes as much time as the computation.

\paragraph{Bar} A large working set size gives the wide WU an
advantage. Consider an algorithm with a working set size of 4 16-bit words,
(such as a temporal filter), 10 iterations per update, and bit slices with
a physical size of 32 bits, a. A VR1 implementation will require 2 loads
per iteration, while a VR16 iteration requires none. Between VPs, the VR16
implementation has to load up the context half of the time, but this is
amortized over all iterations.

\paragraph{Pithy} Issue is primarily how to allocate fast bits to the
pixel.







%%% Local Variables:
%%% TeX-master: "main"
%%% comment-start: "%%% "
%%% End: ***

