\section{Measurements and performance evaluation}
\label{measure-sect}

We experimented with several variations of AAPC on an $8 \times 8$
iWarp system. Each node of this system runs at 20 MHz (S) and the
physical transfer time between two nodes is 2 cycles ($T_t$).  With
these parameters, Equation~\ref{system-eqn} predicts that the peak
aggregate bandwidth on this system is 2.56 GB/s.

\subsection{Comparison of methods}

During our study, we implemented versions of several AAPC
algorithms. Figure~\ref{aapc-fig} shows the aggregate bandwidth
performance of these algorithms. These measurements were made for AAPC
where all messages are the same size.

\begin{figure}[htb]
\epsfxsize=3.3in
\centerline{
\epsfbox{\figpath comp2.eps}
}
\caption{Performance of a variety of AAPC implementations.}
\label{aapc-fig}
\end{figure}

We measured the message passing implementation described in
Section~\ref{msgpass-sect}. This implementation operates at 500 MB/s,
about 20\% of optimal.

The performance of the store and forward algorithm described in~\cite{var92}
is constrained by the node's memory bandwidth limitations to half of of 
the optimal aggregate bandwidth. In fact, our implementation approaches 
800 MB/s, about 30\% of optimal.

The two stage algorithm is similar in spirit to the hybrid algorithms
proposed by Bokhari and Berryman\cite{bokhari92}, but it is simpler.
This algorithm first performs an AAPC over the rows and then an AAPC
over the columns. For a $n \times n$ system, the messages will be $n$
times larger, so the startup times are better amortized. However, by
only using the rows or the columns simultaneously at most half of the
network bandwidth can be utilized. Our measurements show that the two
phase algorithm can outperform other methods on small messages but
approaches the same performance limit as the single phase store and
forward algorithm.

Given our prototype implementations on iWarp, the phased algorithm with
the synchronizing switch outperforms other methods for messages
greater than 1500 bytes. We expect that adding direct hardware
support, as proposed in Section \ref{hw-sect}, or even improved
machine specific coding can reduce the phased algorithm's overhead
significantly and make the phased AAPC more competitive for smaller message
sizes. 

Figure~\ref{direct-fig} compares the effect of global and local
synchronization on phased AAPC performance for a larger range of
message sizes. Due to the lower cost of the synchronized switch, the
locally synchronized implementation is more effective over
smaller message sizes. As the message size increases, the globally
synchronized implementation approaches the same performance.

\begin{figure}[htb]
\epsfxsize=3.3in
\centerline{
\epsfbox{\figpath aapc.eps}
}
\hspace*{\fill}\begin{minipage}[t]{\caplen}
\caption{Performance of the phased AAPC algorithm with global synchronization
versus local synchronization.}
\label{direct-fig}
\end{minipage}\hspace*{\fill}
\end{figure}

\subsection{Message size variation}
\label{vary-sect}

We also measured the effects of varying message sizes on AAPC
performance in two experiments. We compare the performance of the
phased AAPC algorithm with the performance of the uninformed message
passing. Since the message passing library delays decisions to run
time, it should be more adaptable to message size variations.

Figures~\ref{vary-fig}(a) and~\ref{vary-fig}(b) show the results of two
probabilistic experiments. In the first experiment, we varied the
message size over a range. Given a base message size of $B$ and a
variance of $V$, we chose a new message size for each step and each
node over the range of $B-V B$ to $B+V B$ with uniform probability.
%The expected value of the message size is still $B$, but the duration
%of each phase of the AAPC will be constrained by the longest message
%transferred (of size $B+cVB$). 

% Putting these values into
%Equation~\ref{dir-eqn}, the expected aggregate bandwidth is
%$\frac{32  \sqrt N S B}{T_t B (1 + cV)} = \frac{32 \sqrt N S}{T_t (1 + cV)}$.
%Therefore, performance should decrease linearly as the message
%variance increases.

Figure~\ref{vary-fig}(a) shows that the phased algorithm performance
decreases as the variance increases.  The message passing versions are
unaffected by the message variation, but for the corresponding block
size, the phased algorithm outperforms the message passing algorithm.
Even though the message sizes vary, the likelihood of zero length
messages is very low.

\begin{figure}[htb]
\epsfxsize=3.3in
\centerline{
\epsfbox{\figpath vary1.eps}
}
\centerline{(a)}

\centerline{
\epsfbox{\figpath vary2.eps}
}
\centerline{(b)}

\hspace*{\fill}\begin{minipage}[t]{\caplen}
\caption{Performance of phased AAPC algorithm over varying message sizes.
In part (a) message sizes vary probabilistically over a range.  In
part (b) message sizes probabilistically vary between 0 and B.  Graphs
show the average over 16 different sets of message sizes.  The lines are
labeled by the base block size sent in bytes.}
\label{vary-fig}
\end{minipage}\hspace*{\fill}
\end{figure}

The second experiment explores the effect of zero length messages by
probabilistically selecting between a non-zero message length and a
zero message length. Given a base message size $B$ and probability
$P$, the new message length is 0 with probability $P$. Otherwise, it is $B$.
%The new expected message size is $B\times(1-P)$ and the worst case
%message size is $B$.

%  Given equation~\ref{dir-eqn} the new expected
%aggregate bandwidth is
%$\frac{ 32 \sqrt N B (1-P)}{T_t B} = \frac{32 \sqrt N (1-P)}{T_t}$. 
%Again as the probability of the zero length message increases, the
%aggregate network bandwidth performance should decrease linearly.

Figure~\ref{vary-fig}(b) shows that the phased algorithm performance
decreases linearly as the probability of the zero length message
increases. As in the previous experiment the message passing performance
is relatively unaffected by the change in message size. In this case, 
the phased AAPC algorithm is out performed by the message passing algorithm
as $P$ increases. 


\subsection{Common communication steps as AAPC}
\label{subaapc-sect}

All communication steps can be executed as subsets of AAPC by
inserting empty messages between non-communicating nodes. 
We measured several common communication steps
executed
as subsets of AAPC and compared their performance to adaptable
message passing versions to evaluate what these communication patterns
would lose. We looked at a nearest neighbor communication step,
hypercube exchange communication step, and a communication step from a
finite element method application described in~\cite{connset}\footnote{
The performance of the FEM communication step in this paper differs from
the performance in~\cite{connset} because this implementation does not
measure the application buffering costs.}. 
Table~\ref{comm-tab} shows the performance of these communication steps.

\begin{table}[bht]
\begin{center}
\begin{tabular}{ c | c | c | c}
 & AAPC & Message  & Factor  \\
Pattern & (MB/s) &  passing (MB/s) &  difference \\
\hline
Nearest neighbor & 485 & 1425 & 2.9 \\
Hypercube & 511 & 1083 & 2.1\\
FEM & 84 & 195 & 2.3 \\
\end{tabular}
\end{center}
\hspace*{\fill}\begin{minipage}[t]{\caplen}
\caption{Bandwidth of several common communication patterns implemented as
subsets of AAPC and implemented with message passing.}
\label{comm-tab}
\end{minipage}\hspace*{\fill}
\end{table}

These are all relatively sparse communication patterns. Each node
need only communicate with 4 to 15 other nodes. In these
implementations, the subset AAPC versions are a factor of 2 to 3 worse
than the message passing version. This observation agrees with the
second probabilistic experiment.  If only 10\% of the messages are
non-zero, the message passing versions outperformed the AAPC version.

\subsection{AAPC communication in 2D FFT}
\label{2dfft-sect}

Many parallel programs for medical imaging, radar processing and robot
vision rely on two-dimensional fast Fourier transforms (FFTs) for
various filtering steps. These are time-critical applications with
serious computation requirements.  A two-dimensional FFT for a $512
\times 512$ video image at 30 frames per second requires roughly 700
MegaFlop/sec.

Most current High Performance Fortran (HPF) compilers generate message
passing library calls to execute array transposes and other ``dense''
communication steps. An HPF compiler exists for
iWarp\cite{FX-COMMUNICATION}, and the communication segment of a two-dimensional FFT generated by this compiler consists of two AAPC steps
to execute the array transposes. Here we calculate the impact of
improved AAPC performance on this application. The full integration of
our new phased AAPC primitive into this compiler is in progress.

In general, the application time will be reduced by $P(F-1)$ \% where
$P$ is the percentage of the original time spent in communication and
$F$ is the factor change of the new communication time.  For the $512
\times 512$ two-dimensional FFT executed on an $8 \times 8$ iWarp, 52\% of the time
is spent in two AAPC steps that exchange messages of 128 words running
in 801,000 cycles.  The phased AAPC should execute these two steps in
184,400 cycles, which would be a factor reduction of 0.23 over the
original communication time. Thus, the phased AAPC would reduce the
$512 \times 512$ two-dimensional FFT time by 40\%.  The message passing
program could generate 13 frames/sec, while the program using phased
AAPC can generate 21 frames/sec.

Figure~\ref{fft-fig} shows the performance break down of several
two-dimensional FFTs executed on a $8 \times 8$ iWarp. 

\begin{figure}[htb]
\epsfxsize=3.3in
\centerline{
\epsfbox{\figpath twodfft.eps}
}
\hspace*{\fill}\begin{minipage}[t]{\caplen}
\vspace{-18pt}
\caption{Performance improvements of a two-dimensional FFT code using
phased AAPC over a code based on message passing AAPC.}
\label{fft-fig}
\end{minipage}\hspace*{\fill}
\end{figure}







