\section{Alternative AAPC implementations}
\label{other-sect}

There are many characteristics one can use to categorize AAPC methods.
One division of AAPC algorithms is between algorithms that utilize
wormhole routing and those that only rely on store and forward
routing.  The phased AAPC algorithm requires a wormhole router to
support sending messages directly between processors that are not
physically adjacent.

The algorithm proposed in~\cite{var92} only requires a very simple
network interface that supports communication between physically
adjacent processors. In this algorithm, all processors communicate to
the same set of relative processors in each step. To send to relative
processor (x,y) takes $|x| + |y|$ steps. In the first $|x|$ steps all
processors send and receive data along the X axis, and in the last
$|y|$ steps all processors send and receive along the Y axis. By
communicating to relative destinations simultaneously, this algorithm
will utilize all of the machine's network bandwidth. However, this
requires a machine that has twice the memory bandwidth as network
bandwidth. This is not the case with iWarp and many other distributed
machines are also more balanced with respect to network and memory
bandwidth.  iWarp can only support two simultaneous relative
destinations, so this algorithm will at best reach half of iWarp's
peak aggregate network bandwidth.

Also, AAPC algorithms differ by whether data is sent directly to the
final destination or not. The phased AAPC algorithm sends each message
directly to its final destination. This algorithm requires $N^2$
message start ups and sends messages of size $B$.

In other algorithms, the processor sends several blocks of data
destined for several different processors in one message. Generally,
these blocks of data are destined for the same dimension or area of
the machine. While a block of data may be sent to several intermediate
processors, the size of each message is larger and the actual number
of message start-ups is smaller.

Several of these multistep algorithms for a mesh are described
in~\cite{bokhari92}. Here is one simple two step algorithm for a
torus.  First, perform an AAPC along the rows to arrange all the data
in its target column. Then perform an AAPC along the columns to move
all the data to its target row. This algorithm needs only $2 \sqrt N$
message startups and moves blocks of size $\sqrt N B$. The larger
blocks better amortize the cost of the message start-up, but this
algorithm requires more buffer management and only uses half of the
network bandwidth.

If message start-up is very expensive, the multistep algorithm is a
good approach. However, the trend for newer distributed memory
machines is to lower the message start-up time through specialized
communication hardware and user level access to the network among
other techniques.

Another major division is between {\em informed} and {\em uninformed}
methods.  Informed methods such as the phased AAPC algorithm use
compile time information about the structure of the communication to
aid in developing good routing and scheduling information.

Message passing can be used to implement an uninformed communication
step.
Most distributed memory machines offer message passing communication.
Message passing ensures door-to-door delivery, so messages are
eventually delivered to the destination without further program
action.  Common models of message passing quantitatively characterize
the message passing system by key parameters like message throughput
and processing overhead and suggest that the programmer does not rely
on the particular details of the target
architecture\cite{logp-extended,postal-model}.  Figure~\ref{mp-code}
shows a simple message passing AAPC program.

\begin{figure}[bht]
\begin{center}
\fbox{\begin{minipage}[t]{\caplen}
{\helv\begin{tabbing}
---\=---\=---\=---\=---\=\kill
 1\>{\bh for} i {\bh from} 0 {\bh to} NumberOfProcessors-1 {\bh do}\\
 2\>\>NBSendMessage(Destination(i), Route(i), DataBlock[i])\\
 3\>{\bh for} j {\bh from} 0 {\bh to} NumberOfProcessors-1 {\bh do}\\
 4\>\>NBReceiveMessage(DataBlock[j])
\end{tabbing}}
\end{minipage}}

\begin{minipage}[t]{\caplen}
\caption{Message passing AAPC code. We assume NBSendMessage and
NBReciveMessages are buffered, non-blocking primitives offered by the
message passing library.}
\label{mp-code}
\end{minipage}
\end{center}
\end{figure}


 Uninformed algorithms are for more adaptable and may be the only
alternative if no compile time information is available. However, with
dense communication steps uninformed methods tend to have problems
with hot spots and congestion. In \cite{val82}, Valiant proves that
uninformed or oblivious routing can statistically avoid these hot
spots by first routing to a random location and then routing to the
final destination. On average this will double the message route
length, so this approach will at best get within half of the optimal
network usage for AAPC.

Run time adaptive routing methods have been proposed and studied as a
means to avoid hot spots. However, today's generation of distributed
memory machines do not incorporate adaptive routing, so the value of
adaptive routing algorithms can not be evaluated. However, it seems
unlikely that the local view available to an adaptive router is
sufficient to avoid all hot spots that can occur in an AAPC.


Both phased AAPC and message passing AAPC decompose the AAPC pattern
into messages and route them through the network. However, in message
passing AAPC, a node passes a batch of $n$ messages to the network.
The wormhole router then routes these messages to $n$ different
processors.  Since the network is an independent subsystem with no
information about the system-wide communication structure, the router
uses a simple, greedy scheduling strategy.  Whenever a requested
communication link becomes available, a message will proceed.

Routes between nodes in the AAPC phases described in
Section~\ref{patterns-sect} are the same routes generated by the
simple e-cube torus router. By following the communication schedule
for the phased AAPC, a basic message passing library should recreate
the same AAPC phases and achieve similar performance.  However, not
all nodes will finish each phase at the same time even if the messages
are the same size, because not all nodes are scheduled to send
messages in each phase.  On iWarp, the performance of unsynchronized
nodes following the phased AAPC schedule and using the basic message
passing package was about the same as the performance following a
random schedule.  Figure~\ref{scheduled-fig} compares the performance
of AAPC message passing using the phased schedule with and without
synchronization.

\begin{figure}[htb]
\epsfxsize=4in
\centerline{
\epsfbox{\figpath scheduled2.eps}
}
\hspace*{\fill}\begin{minipage}[t]{\caplen}
\caption{Performance of two message passing AAPC programs both following
the phased schedule. One synchronizes between phases, and the other does not.}
\label{scheduled-fig}
\end{minipage}\hspace*{\fill}
\end{figure}

\subsection{The iWarp message passing system}
\label{msgpass-sect}
On iWarp, the basic message passing routers are based on a reverse
e-cube scheme\cite{stricker-routing}.  All routes start in the
X-direction, eventually turn corners, and continue in the
Y-direction. The queues can be assigned to multiple pools and the
routers can use date-lines to break circular dependencies, avoiding
routing deadlocks.  Many other commercial, distributed memory systems
use similar simple e-cube or reverse e-cube routing schemes. While
most routers are fixed in the communication hardware, the iWarp system
enables a variety of virtual channel configurations and permits
different router software to determine the precise route of every
message before it is sent.

Previous work on mesh routers has shown that the non-adaptive e-cube
routers can have severe performance limitations, due to imbalanced
congestion.  Several advanced, adaptive wormhole routers have been
proposed for machines with virtual channels\cite{adapt-route}, but
only few of them have been implemented in hardware. We have tested
some of these advanced routers with our iWarp message passing system.
Unfortunately the advanced methods delivered only up to 30\% of
improvement over the basic e-cube scheme, and with only two resource
pools, these advanced methods could not use the torus routing
capability.  Faced with the limitation of only two pools, we chose the
torus routing over the randomized, more adaptive router, so our
measurements in Section \ref{measure-sect} are based on a
deterministic e-cube router with the torus routing capability.

To compare a specialized AAPC architecture with a general message
passing system, we are most concerned with the issues of routing and data
transfer. For this reason, we did not use a standard message passing
interface such as PVM\cite{pvm} or MPI\cite{MPI-DRAFT}. These standard interfaces have software
overheads resulting from error- and protection-checking in the
operating system, buffer management, and standardized synchronization
semantics, which result in copying data. These aspects of message
passing libraries are an important issue of research, but for this
study they would have obscured the architectural insights into
the nature of an all-to-all communication.  Instead of a standard
library, we use the deposit message passing library written for the Fx
compiler\cite{fx-ppopp}, based on the deposit model\cite{msg-t3d-tr}.  The
deposit library allows direct deposit of incoming data to its final
destination.  At the time it is sent, a message is guaranteed to
encounter a receiver that is ready to extract it from the network
immediately, minimizing buffering overheads and message congestion at
the receiver.
%  The deposit model is similar to the {\em sender
%buffered} message passing introduced in~\cite{connset}.

The measured overhead per transferred message is constant at around
$400$ cycles ($20 \mu s$). The network latency is proportional to the
network diameter $n$ with a cost of 2 to 4 cycles per hop.
Large data blocks are injected as single messages into the network,
and once data is flowing, the transfer rate is limited only by the
link bandwidth of $40$ MBytes/sec.  The same maximal transfer rate
applies to all of our AAPC implementations.















