\section{Using a standard message passing system for AAPC}
\label{msg-sect}

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]
\hspace*{\fill}\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}}\hspace*{\fill}

\hspace*{\fill}\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}\hspace*{\fill}
\end{figure}

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.

Since message passing libraries do not rely on the communication
structure for scheduling or routing, message passing is more adaptable
in situations where the communication structure is sparse, changing,
or unknown.

%\nocite{MPI-DRAFT}

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








