\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 0.1 $\mu$seconds ($T_t$),
and data is transferred in flits of 4 bytes ($f$).  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 the AAPC algorithms
described in Section~\ref{other-sect}.  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=4in
\centerline{
\epsfbox{\figpath alg_comp2.eps}
}
\caption{Performance of a variety of AAPC implementations.}
\label{aapc-fig}
\end{figure}

The message passing implementation operates at 500 MB/s, about 20\% of
optimal. In theory, this message passing implementation could
reach the machine's optimal bandwidth, but the uninformed
routing  approach makes network congestion quite likely.

The performance of the store and forward algorithm 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.

Since the two stage algorithm uses at most half of the links
simultaneously, it also constrained to half of the optimal aggregate
bandwidth.  Our measurements show that the two phase algorithm can
out-perform other methods on small messages but approaches the same
performance limit as the single stage store and forward algorithm.

Given our prototype implementation on iWarp, the phased algorithm with
the synchronizing switch outperforms other methods for messages
greater than 512 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. 

\subsection{Synchronization support}

Figure~\ref{direct-fig} compares the effect of global and local
synchronization on phased AAPC performance for a larger range of
message sizes. In addition to the local switch, we measured the performance
of phased AAPC using two versions of a global synchronization. The
hardware-based global synchronization completes in 50 $\mu$ seconds. The
software-based global synchronization completes in 250 $\mu$ seconds.

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

The AAPC program with local synchronization consistently out-performs
the globally synchronized implementations as one would expect from the
lower-overhead local synchronization constraints. However, the
implementation using hardware global synchronization shows quite
similar performance. The implementation that used software-based
global synchronization shows a distinct performance penalty, though
it too approaches the same bandwidth utilization.

Since the hardware global synchronization works so well, it makes
sense to use global synchronization for phase separation if the target
architecture already has a fast, hardware global synchronization
mechanism. However, if the machine must rely on software for
synchronization, it may make sense to consider added support for a
local synchronization as described in Section~\ref{hw-add-sect}. AAPC
phase separation does not require the power of full global
synchronization, and the synchronizing switch should be a simpler and
more scalable design addition.

\subsection{AAPC on other machines}
 
In addition to measuring AAPC performance on iWarp, we compared the
iWarp AAPC performance with all-to-all communication performance on
three other commercial distributed memory systems: the Cray
T3D\cite{T3D-OVERVIEW}, Thinking Machine's CM-5\cite{cm5}, and IBM's
SP1\cite{IBM-SP1}. Figure~\ref{mach-comp-fig} compares the performance
of these systems over a range of message sizes. All systems use 64
nodes. The T3D is a $2 \times 4 \times 8$ 3-dimensional submesh with a
bisection bandwidth of 1.6 GB/s. The CM-5 is a 64 node fat tree with a
bisection bandwidth of 320 MB/s.

\begin{figure}[htb]
\epsfxsize=4in
\centerline{
\epsfbox{\figpath mach_comp2.eps}
}
\hspace*{\fill}\begin{minipage}[t]{\caplen}
\caption{Performance of the phased AAPC algorithm on several machines.}
\label{mach-comp-fig}
\end{minipage}\hspace*{\fill}
\end{figure}

The AAPC algorithm on the CM-5 was optimized for use in the CM-5
scientific library. The algorithm and performance numbers are due to
Unger\cite{aapc-cm5}.

The SP1 AAPC algorithms and measurements are from \cite{IBM-AAPC}.
This algorithm attempts to minimize endpoint processing. Since SP1 is
a switch-connected machine, it does not attempt to optimize network
use.

We made two preliminary measurements on the T3D. In the first naive
implementation (labeled ``unphased''), each node sends messages with
no synchronization. This implementation works well until it reaches an
aggregate bandwidth of 2 GB/s where network congestion appears to be
an issue. The second implementation (labeled ``phased'') divides the
messages into 64 simple phases and synchronizes the nodes between each
phase. With this synchronized implementation, the aggregate bandwidth
continues on beyond 3 GB/s. This comparison shows that even new, high
bandwidth interconnects benefit from careful utilization of network
bandwidth for all-to-all communication.

\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=5in
\centerline{
\epsfbox{\figpath vary1.eps}
}
\centerline{(a)}

\epsfxsize=5in
\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=5in
\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}







