\message{ !name(main.tex)}% -*- Mode: LaTeX;  -*-
% File: main.tex|thesis/
% Author: Mike Bolotski (misha@ai.mit.edu)
% Copyright (C) Artificial Intelligence Laboratory, 1996
%*-------------------------------------------------------------------------
%
%* PURPOSE: Top file of thesis
%*
%* HISTORY:
%* Last edited: Sep  6 00:13 1996 (misha)
%*  May 29 13:44 1996 (misha): Gratefull copied from Maja's all.tex
%* Created: Wed May 29 13:43:10 1996 (misha)
%*-------------------------------------------------------------------------

% \documentstyle[11pt,config,equationarray,mapleenv]{mitthesis}
\documentstyle[11pt,thesisconfig,equationarray,mapleenv,singlespace,twoside]{mitthesis}

\pagestyle{headings}

\def\mypsdirectory{/fs/abacus/misha/thesis/PS/}

\def\mapleplot#1{
%\vskip\AboveMaplePlot
\centerline{\vbox{\psfig{figure=\mypsdirectory#1,%
height=80mm,%
width=120mm,%
%%height=\MaplePlotHeight,%
%%width=\MaplePlotWidth,%
angle=\MaplePlotAngle}}}
\vskip -2ex
}




%\def\mapleplot#1{
%\vskip\AboveMaplePlot
%\centerline{\vbox{\psfig{figure=\mypsdirectory#1,%
%height=\MaplePlotHeight,%
%width=\MaplePlotWidth,%
%angle=\MaplePlotAngle}}}
%\vskip\BelowMaplePlot
%}


%%% Draft-oriented stuff
%% \pagestyle{myheadings}
%% \markright{DRAFT VERSION OF \today}

%% \includeonly{rough}

\begin{document}

\message{ !name(analytical.tex) !offset(-54) }
%* Last edited: Sep  6 00:13 1996 (misha)

\chapter{Analytical Modeling \chaplabel{analytical}}


\section{Optimal Bit Width Analysis}

Selection of the bit slice width in a SIMD computer is not 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.
The initial ideal model estimates the area, delay, and
cycles-per-instruction (CPI) of a given bit width and simply
multiplies to obtain a figure of merit. This metric, called
\emph{quality\/} in this work, is normally expressed in bit
operations per nanosecond per unit area, but for better intuition has
been scaled to billions of 16-bit operations per second per standard
chip.

The first refinement uses Amdahl's law to account for operations
which are not sped up by a wider datapath.  The next refinement
recognizes that off-chip memory latency is a critical bottleneck, and
determines the effect of cache misses.  Finally, the model
incorporates the effect of the background loading mechanism on I/O
performance.

\begin{Table}{modelparams}{Analytical Model Parameters}{Analytical
    Model Parameters from the Abacus-1 Implementation.}
\begin{tabular}{|l|l|l|}
\hline
Parameter & Value & Description \\
\hline
$A_{alu}$ & 8 & ALU area, in units of SRAM cells \\ \hline
$A_{ovr}$ & 10 & Overhead area, in units of SRAM cells \\ \hline
$f_A$     & 0.9 & Fraction of operations affected by wider datapath \\
\hline
$T_{mem}$   & 3 ns & Register file access time \\ \hline
$T_{alu}$   & 0.7 ns & ALU datapath bit delay \\ \hline
$T_{ovr}$   & 1.0 ns & Timing overhead \\ \hline
\end{tabular}
\end{Table}


\subsection{Ideal Model}

\paragraph{PE Area.}
A processing element's area is modeled 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}(k) = N_{mem} + kA_{alu} + A_{ovr}
\end{equation}

where $N_{mem}$ is the number of memory bits and $k$ is the width of
the datapath.  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 may provide a more efficient
alternative.

\paragraph{Cycle Time.}
The model assumes an unpipelined design, in which the cycle time
consists of four parts: register file read, ALU ripple-style execute,
register file write, and miscellaneous time margin.  Register file
access times are assumed identical for read and write, and include
precharge and equilibrate time.

\begin{equation}
T_{pe}(k) = 2 T_{mem} + kT_{alu} + T_{ovr}
\end{equation}

ALU times are also assumed linear. This holds true for both the
ripple-carry adder and the Manchester-carry adder (although in that
case the fixed part of the cycle will grow due to the PG and Sum
cells, and $T_{alu}$ will decrease). Many more sophisticated adder
structures are possible but they require more area and gain in speed
only for large word sizes.


\paragraph{Performance.}
In the ideal model, the number of cycles required to execute an
instruction decreases linearly with the datapath width. Thus, 
a $k$-bit ALU requires twice as many cycles to perform an operation
as a $2k$-bit ALU. 
\begin{equation}
P_{pe}(k) = k
\end{equation}

\paragraph{Quality Metric.} The effectiveness of a PE is expressed as
the number of operations per unit area per unit time.

\begin{equation}
Q_{ideal}(k) = \frac{k}{A_{pe}T_{pe}} = \frac{k}{(N_{mem} + kA_{alu} +
  A_{ovr})(2 T_{mem} + kT_{alu} + T_{ovr})}
\end{equation}

This function is plotted in \fig{idealq}. Several conclusions can be
reached from this plot. First, smaller memory sizes lead to higher
performance.  This is not surprising, since smaller PEs with
identical computational throughput lead to better quality measures.
Second, as memory increases, the optimal datapath width $k$  also increases.
This occurs because adding a few more datapath bits to a large
PE improves performance without a substantial change in area.  The
final conclusion is that the function has a very flat optimum, so
that it does not cost much to err on the side of larger $k$.



\begin{Figure}{idealq}{Foo}{Ideal Performance (GOPS/chip) as a function of
    datapath width.  The four graphs correspond to memory sizes of 32, 64,
    128, and 256, from top to bottom.}
    \leavevmode  \mapleplot{idealq.eps}
  \end{Figure}

  The next observation comes from normalizing the performance to the
  bit-serial case ($k=1$). \fig{idealqn} shows that wide datapaths
  can be up to 4.5 times more efficient than the bit serial case.
  Unfortunately, the greatest relative advantage occurs at a lower
  absolute performance level.

\begin{Figure}{idealqn}{Foo}{Normalized Ideal Performance. This shows the
    relative advantage of the wide datapath over the bit-serial case.}
    \leavevmode  \mapleplot{idealqn.eps}
  \end{Figure}


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


\subsection{Amdahl's Law}

The next refinement to the model is the application of Amdahl's law, which
essentially states that if parallelization (or any speedup) affects only
 a subset of the total computation, the remaining fraction will greatly
 reduce the effectiveness of the speedup. This is the
basic equation of computer architecture. 
  Mathematically:
\begin{equation}
S_a(k) = \frac{1}{\frac{f_A}{S} + (1-f_A)}
\end{equation}
where $f_A$ is the fraction of the computation affected by the
speedup $S$, and $S_a$ is the actual obtained speedup.  
Thus,

\begin{equation}
Q_a(k) = \frac{S_a}{A_{pe}T_{pe}}
\end{equation}

In the context of the current design, $f_A$ represents the fraction of
arithmetic oriented operations in a program.  Operations
that are not sped up by a wider datapath include network communication and
logical flag-manipulating 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 value of $f_A$ used in the model was chosen to be 0.9. It was
supported by the results of two related research works. Holman
\cite{Holman89} explicitly listed $f_A$ for a variety of algorithms,
as in \tab{holmanfractable}.  The obtained values are slightly higher
than expected for vision algorithms, as most of the listed algorithms
are dominated by floating point manipulations.

\begin{Table}{holmanfractable}{Fraction of Operation Costs Affected by Data Path
    Width}{Fraction of Operation Costs Affected by Data Path Width. From
    \cite{Holman89}}
\begin{tabular}{|l|r|}
\hline
Program & $f_A$ \\
\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 \cite{Herbordt94b} evaluation of parallel architectures
included a set of simulation results relating datapath width to
execution time. The value of $f_A$ was extracted by fitting Amdahl's
function to the published performance curves. The fitted functions
agreed well with the simulation data, although half of the algorithms
had unexpectedly high performance for the case $k=1$.  The 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 intermediate value shown for the
IU Benchmark entry occurs because the benchmark 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_A$ \\
\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}


The same configurations as in the ideal case but with Amdahl's-law
correction are shown in \fig{amdq}.  The greatest difference occurs in the
high-performance low-memory case. Here, the additional dead weight of the
wide datapath is a relatively large penalty compared to the small overall
PE size. The maxima are much sharper than in the ideal case, but level off
quickly as memory size is increased.

\begin{Figure}{amdq}{Amdahl-corrected quality values}{Amdahl-corrected quality values.}
  \leavevmode  \mapleplot{amdq.eps}
\end{Figure}

The normalized equations behave similarly to the ideal case, except
that maxima now become apparent. \fig{amdqn} also shows that the
relative overall advantage of wider paths decreases from a former
peak of 4.5 to 3.

\begin{Figure}{amdqn}{Normalized Amdahl-corrected quality values}{Normalized Amdahl-corrected quality values}
    \leavevmode  \mapleplot{amdqn.eps}
  \end{Figure}

The effect of varying $f_A$ is shown in \fig{amdqn3d}.
The axis is actually labelled with $(1-f_A)$, the fraction not affected by
the speedup.  The expected interaction of the two parameters occurs. The
best $k$ for this configuration appears to be 4-6 bits over a wide range of
$f_A$, 0.8 to 0.98.  Notice that in the low $f_A$ case, the multibit
configurations perform worse than the bit-serial ones.

\begin{Figure}{amdqn3d}{Normalized quality vs $k$ and $f_A$}{Normalized quality vs $k$ and $f_A$}
    \leavevmode  \mapleplot{amdqn3d.eps}
  \end{Figure}

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


\clearpage
\subsection{Off-Chip Data}

The preceding analysis applies to algorithms that execute from the on-chip
registers. As soon as a data item must be brought in from off-chip, a
significant delay occurs. This section analyzes the impact of this delay.

An implicit assumption being made here is that commercially available
memory chips are at least one technology jump from that available to
a university or a low-volume commercial design.  If the SIMD chip was
implemented in a comparably dense technology, other design points
would become feasible, and the model will have to be expanded.  A
recent example of research in this direction is the Execube chip,
which integrates several 32Kx8 DRAM memories with 16-bit PEs.

Once off-chip memories are part of the design, the model must determine two
parameters: the available bandwidth per pin, and the number of pins allowed
on the PE chip.  The former is limited by the capabilities of commercial
memory devices and the latter by packaging constraints. A comparison of
contemporary high-bandwidth memory alternaties are shown in \tab{memories}.

\begin{Table}{memories}{Contemporary Memories}{Contemporary Memories}
\begin{tabular}{|l |  r|    r     | r |r|r|}
\hline
Name      & Width  & Cycle & Initial     & Data Rate  & Address \\
          & (max)   &  Frequency &  Latency          &         &   Line \\
             &    &  (MHz) &  (ns)          & bits/pin/ns & Overhead \\
\hline
%% 0.6 GB/sec -> 0.6 bits/ns
Rambus       & 9      & 600 & 50            &  0.6   & 4 \\
Synchronous SRAM        & 32     & 100 & 5             &  0.1   & 18 \\
Synchronous DRAM        & 32     & 100 & 50            &  0.1   & 22 \\
Extended DRAM        &  8     &  66 & 30            &  0.066 & 22 \\
\hline
\end{tabular}
\end{Table}


The parameter that controls how long PEs must stall waiting for the
data is latency: the time from the data request until the data
arrives.  Different memory organizations have varying latencies, from
the 4~ns of high-speed SRAM \cite{Chappell91} to the 35~ns of a fast
DRAM.  SIMD architectures encounter another cause of latency:
bandwidth limitation.  Since all PEs must wait until data is
received, the latency is increased by this wait period.  Because of
this phenomenon, memory organizations with high latency but with a
high burst bandwidth may well exhibit lower latency, especially since
SIMD-oriented transfers occur in units of hundreds (or thousands) of
bits.  The initial latency is amortized over all elements in the
burst. The Rambus part falls into this category. Unfortunately, even
though products are beginning to incorporate this interface, the
technology is still difficult to use in a design.

A comparison of these latencies is shown in \tab{latencies}.
\begin{Table}{latencies}{Latencies of Memories}{Latencies of Memories}
\begin{tabular}{|l |    r|    r     | r      |  r      |r|r|}
\hline
Configuration   & Pins   & Pins     & BW      & \mcol{3}{|c|}{Latency}\\
                & Total  & Signal   & bits/ns & initial & data & total \\
\hline
Rambus, 1 port  &  13    &  9      &   5.4    & 50 & 190  & 240 \\
Rambus, 2 ports &  26    &  18      & 10.8    & 50 & 95  & 145 \\
SSRAM, 32 bits  &  50    &  32      & 3.2     &  0 & 320 & 320 \\
SSRAM, 64 bits  &  82    &  64      & 6.4     &  0 & 160 & 160 \\
\hline
\end{tabular}
\end{Table}



The more conservative design described here assumes a conventional SRAM
operating at a 16~ns cycle time through a 64-bit port.  The aggregate
bandwidth is therefore 4 bits/ns.  An important realization incorporated in
the model is that for a fixed chip size, bandwidth (and therefore latency,
as discussed earlier), is also fixed, and may therefore be expressed as
bits per nanosecond per unit area. This somewhat odd normalization is
useful because PE area fluctuates as a function of datapath width, and the
available bandwidth changes with it.  Based on the Abacus design, the
total PE
area consisted of approximately 100,000 SRAM cell equivalents.  Thus the
bandwidth per unit area, $B$, is 0.00004.

The time to provide a data word to  all PEs in the array from an off-chip
chip memory is:
\begin{equation}
T_l = \frac{w}{\mbox{PE bandwidth}} = \frac{w}{A_{pe}B}
\end{equation}
where $w$ is the data word width. It will eventually cancel out, so its
exact value is not important.


The next parameter to be determined is $T_s$, the amount of time
that passes between load operations. Given these two quantities, the
performance degradation $D_{io}$ is given by:
\begin{equation}
D_{io} = \frac{T_s}{T_s+ T_l}
\end{equation}


We use a very simple model of load events, namely a fixed frequency.
Conventional caches often use Poisson (or other) distributions but control
flow is much more predictable in SIMD systems, and loops are likely to
access variables in a repetitive stride.  A load event occurs with a period
of $f_{miss}^{-1}$ instructions. Another important realization of the
model is that the duration of a cache hit sequence is a function of the
average instruction duration.  Thus, $T_s$ is the number of
instructions between misses, times the average number of cycles per
instruction, times the length of each cycle.


\begin{equation}
T_s = \left(\frac{1}{f_{miss}}\right) T_{pe} \frac{w}{kS_a}
\end{equation}

\begin{Figure}{tltc}{Load Time Compared to Load Period.}{Load Time Compared to Load Period. The upper
    monotonic curve is $T_l$, while the lower one is $T_s$.  Their
    ratio, scaled up, is also shown} \leavevmode \mapleplot{tltc.eps}
  \end{Figure}

An interesting effect is shown in \fig{tltc}. The ratio of $T_l$ to $T_s$
exhibits a maximum at about $k=6$.  This occurs because $T_s$ decreases
very quickly at first, far faster than $T_l$ drops due to higher bandwidth
per PE. The shape of the ratio curve should appear familiar, as can be seen
from the following derivation.

\begin{eqnarray}
D_{io} & = & \left( 1+\frac{T_l}{T_s} \right)^{-1}\\
       & = & \left( 1+\frac{\frac{w}{A_{pe}B}}{\frac{T_{pe}w}{f_{miss}}kS_a}
                                             \right)^{-1}\\
       & = & \left( 1+\frac{fkS_a}{A_{pe}BT_{pe}} \right)^{-1}\\
       & = & \left( 1+\frac{fQ_a}{B} \right)^{-1}
\end{eqnarray}

The performance degradation due to off-chip accesses therefore has a simple
form: 
\begin{equation}
D_{io}  = \frac{1}{1+\rho Q_a}
\end{equation}

where $\rho = f/B$. Thus,
\begin{equation}
Q_{io} = Q_{a} D_{io} = \frac{Q_a}{1+\rho Q_a}
\end{equation}

 This equation says that as the quality factor
increases, the impact of off-chip accesses grows.  The method of achieving
high performance is irrelevant. For a fixed algorithm ($f_{miss}$) and a
fixed memory bandwidth ($B$), higher performance will throttle itself back
at the memory level.


%\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}{IO-derated Quality Metrics}{IO-derated Quality Metrics}
    \leavevmode  \mapleplot{qio5.eps}
  \end{Figure}

This effect can be seen in \fig{qio5}. At high $Q_a$ values, $Q_{io}$ begins
to approach $\frac{1}{\rho}$.

\begin{Figure}{qio3d}{IO-derated Quality Metrics (m=64,256))}{IO-derated Quality Metrics (m=64,256))}
    \leavevmode  \mapleplot{qio3d.eps}
  \end{Figure}

\clearpage

\subsection{Background Loading}

Performance of computer systems with predictable memory access
patterns can be improved with the technique of prefetching or
background loading. The Abacus-1 design allows a memory access to be
initiated before the data is actually required, and relies on the
compiler to perform this scheduling rather than analyzing access
patterns at runtime.

The net effect of background loading is to reduce the loading time
penalty. The effective loading time is:
\begin{equation}
T_{\mbox{eff}} = max(0,T_l - T_s)
\end{equation}
and the derating factor becomes
\begin{equation}
D_{back} = \frac{T_s}{T_s + T_{\mbox{eff}}}
\end{equation}



% The ratio maximum again appears at around $k=6$. 

%\begin{Figure}{tleftc}{Foo}{Effective loading time and sequence time}
%    \leavevmode  \mapleplot{tleftc.eps}
%  \end{Figure}

\begin{Figure}{didb3dk}{Performance improvement due to background loading.}{Performance improvement due to background loading.}
    \leavevmode  \mapleplot{didb3dk.eps}
  \end{Figure}

The derating reduction improvement due to prefetching is shown in
\fig{didb3dk}. There are several interesting aspects of this graph.  First,
at high miss rates ($f_m = 0.1$), prefetching only helps by about 10\%.
The improvement is very rapid as hit rates increase, reaching the 50\%
``sweet spot'' at $f_m = 0.02$.  Second, the relative improvement begins to
worsen again at very low miss rates, when prefetching completely eliminates
the load penalty and therefore cannot improve performance further, while
the non-prefetched design is still reaping the benefits of less frequent
accesses.

\begin{Figure}{qback5}{Absolute performance, background loading.}{Absolute performance, background loading.}
    \leavevmode  \mapleplot{qback5.eps}
  \end{Figure}

Interesting effects can also be seen in the absolute performance curves in
\fig{qback5}.  

\begin{Figure}{qb3d}{Prefetching-derated quality metrics}{Prefetching-derated quality metrics}
    \leavevmode  \mapleplot{qb3d.eps}
  \end{Figure}


Prefetching is so effective that performance saturates at
the memory bottleneck. A two-dimensional version of this plot is shown in \fig{qb3d}.

Repeating the mathematical analysis of the previous section leads to very
interesting results. First, we need only look in the case where $T_{eff} >
0$, since otherwise the load penalty is zero, and $D_{back} = 1$.
\begin{equation}
D_{back}  =  \frac{T_s}{T_s+(T_l-T_s)} =  \frac{T_s}{T_l} =  \frac{1}{\rho S_a}\\
\end{equation}

This equation says that prefetching makes performance independent bit-slice
width!  When this computation is made explicit, the intuitive explanation
becomes apparent: a long as a sequence of computations takes less time that
the load delay, there is no benefit to improving the datapath efficiency.
There are several observations:
\begin{itemize}

\item Prefetching makes the IO system behave in two qualitatively different
  modes.  If the load penalty is smaller than the sequence delay, the
  external memory seems to disappear, since the PEs operate as if all data
  was in local registers.  If the load penalty is greater than the
  sequence delay, the external memory becomes the only factor controlling
  performance. 

\item For a memory-limited design, increases in computational efficiency
  are invisible. Even if a clever data representation halves the computing
  time at no area penalty, the overall performance will be completely
  unaffected.

\end{itemize}

The advantage of reconfigurable systems now becomes clear. Whenever an
algorithm enters a bandwidth-saturated phase, a reconfigurable system can
configure itself as a wider datapath with more local memory to reduce the
miss frequency and therefore improve performance. For purposes of
illustration assume miss frequency is linear in memory size. Using the data
of \fig{qb3d}, a \{k=4,m=64\} system operating at $f_{miss} = 0.04$ can
become \{k=16,m=256\} system at $f_{miss}=0.02$ and gain 30\% improvement.




\subsubsection{Less Predictable Access Patterns}

We would like to determine the benefit of background loading 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 more pessimistic 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 $T$ given a string of $k$ available cycles is $L-k$, the expected
value of $T$ 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}{leff}{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.}
    \leavevmode
%    \mapleplot{Leff_vs_f1.ps}
    \mapleplot{Leff_vs_f2.ps}
  \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}

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



\subsection{Conclusions}


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.


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


\section{What's Missing}


What this section really needs is to 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
assumptions.

%\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}





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

%\section{WARNING: NOT READY: 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{Effect of Virtualization}

%This analysis assumes a neighbor organization, where a rectangle of
%adjacent pixels is mapped onto one PS.  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 PS would transfer T1 and T2 to itself, for a PS requirement of 48
%bits (assuming each word is 16 bits). Peak memory requirement for 16 of
%these units is 768 bits. The VR16 PS 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 PSs, which would
%be 1 with 1-bit PSs.  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.



%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 PSs. In the extreme case of a very simple
%computation such as logical AND, the highly concated PS will be twice as
%slow, as the active restore overhead takes as much time as the computation.

%A large working set size gives the wide PS 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.








%\section{Unfinished}

%\paragraph{Pin Bandwidth} The good news is that the IO rates of memories
%have been rapidly increasing in recent years, driven by wide variety of
%device architectures. This explosion of new RAM types requires careful
%analysis of the operating trade-offs among the various alternatives.


%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.



%\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}


%\paragraph{Number of Pins}


%\begin{Table}{padringcalc}{Pad Ring Organizations}{Pad Ring Organizations}
%\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 &    26  &    74  &    4.5  &   11.7 &   52.7 &   43.3\\
%\hline
%208 &    26  &    24  &    4.5  &   4.2  &   24.5 &   14.0\\
%208 &    13  &    37  &    2.5  &   6.2  &   21.3 &   10.8\\
%\hline
%336 &    84  &    80  &    13.2 &   12.6 &   166.3&   151.2\\
%336 &    48  &    116 &    7.8  &   18.0 &   140.4&   125.3\\
%\hline
%336 &    42  &    40  &    6.9  &   6.6  &   54.0 &   37.8    \\
%336 &    24  &    58  &    4.2  &   9.3  &   47.5 &   31.3    \\
%\hline
%448 &    112 &    108 &    17.4 &   16.8 &   292.3&   272.2\\
%448 &    84  &    136 &    13.2 &   21.0 &   277.2&   257.0\\
%\hline
%448 &    56  &    54  &    9.0  &   8.7  &   89.3 &   68.0    \\
%448 &    42  &    68  &    6.9  &   10.8 &   85.5 &   64.3    \\
%\hline
%\end{tabular}
%\end{Table}

%The pin availability analysis assumes the common perimeter-based IO
%structure (a pad ring). Although area-based interconnect technologies such
%as C4 are available, they are still a premier, higher-cost technology.
%One of the problems with a perimeter-based organization is that it can
%become \emph{pad-limited}, where the rectangle formed by the pads is larger
%than the computing function of the chip.  This problem can be ameliorated
%by the use of double-ring structure, as used in the Abacus-1 chip. Finally,
%the analysis assumes that low-parasitic structures like the ball-grid array
%(or BGA) will become standard.

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

\message{ !name(main.tex) !offset(-989) }
\end{document}


