\newpage
\section*{Appendix}
\appendix


\section{The iWarp message passing system}
\label{msgpass-appendix}
The usage model of a message passing system excludes any involvement
of the computation agent with routing at the intermediate nodes. Once
initialized, the communication agents of an iWarp system form an
independent switching fabric wired as a $n \times n$ torus.

As described in Section~\ref{hw-sect}, all route selection is done by
the sender.  Randomization in the router is limited to random choices
of alternate routes by the sender node.  Multiple lanes configured
across a single physical link enable additional adaptivity.  These
lanes are implemented with the iWarp mechanism for multiplexed virtual
channels.

The basic message passing routers are based on a reverse e-cube
scheme.  All routes start in the X-direction, eventually turn corners,
and continue in Y-direction. The queues can be assigned to multiple
pools and the routers can use date-lines to break circular
dependencies, avoiding routing deadlocks.

Previous work on mesh routers has shown that the non-adaptive
e-cube routers have severe performance limitations. We have observed a
strong imbalance of congestion between the X-links and the Y-links,
since a majority of messages are routed over X-links first before Y-links 
considered.  In wormhole routers, message congestion leads to
messages waiting in the network with their tails blocking some
communication resources.

Several advanced adaptive wormhole routers have been proposed for
machines with virtual channels, but only few of them have been
implemented in hardware \cite{adapt-route}. 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.  Therefore, we use a fully deterministic e-cube router
with torus routing capability for our measurements in Section
\ref{measure-sect}.

%The recently introduced
%Paragon System \cite{PARAGON-XPS} uses its routing backplane with a
%plain surface e-cube router, while the CM5 network uses adaptive and
%randomized route selection on the upwards-paths in its fat tree. 

To compare a specialized AAPC architecture with a general message
passing system, we are most concerned with the issues routing and data
transfer. We did not use a standard message passing interface such as
PVM or MPI because of the software overheads in their implementations
resulting from safety checking in the operating system, buffer
management, and standardized synchronization semantics.  These
overheads would have obscured all interesting architectural insights
into the nature all-to-all communication.

The iWarp message passing system provides a usage model that 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 the time the message spends
in the network.  The deposit model is similar to the {\em sender
buffered} message passing previously introduced in~\cite{connset}.

iWarp message passing can be characterized using the the common
parameters of {\em processing overhead}, {\em network latency} and
message {\em transfer rates}.  The following table captures these
parameter for a $k$ word message on an $N=n \times n$ processor
machine. (The header and the trailer of a message consist of four
additional data words.) All times are specified in clocks at 50 ns.
each.

\begin{table}[htb]
\begin{center}
\begin{tabular}{|l|c|}
\hline
Primitive			&	send/receive ($i \in \{s,r\}$)\\
\hline
\hline
constant message overhead $c_i$ 			& $480$	\\
network latency $c_i$ 			& avg. $4*\sqrt(N)$ \\
network access bandwidth $1/a$ 				& $1/a_i \;(a_i = 2$)\\
\hspace*{1.5cm} (a in clocks/word)			&		\\
\hline
{\em total time} $t_i$ in clocks 			& $2 k + 496$ \\
\hline
\end{tabular}
\end{center}
\end{table}

The per-message receiving overhead is the composite of the latencies
for the event handlers and starting the tight deposit loop. The
receiver overhead is based on queue management, route lookup and starting
the spooling unit (DMA). 

In a two-dimensional torus the network latency $l$ is
$\Theta(\sqrt{N})$.  The latency of each message is bounded from below
by the network access time $a = 2$ clocks and from above by $4
\sqrt{N}$.






\section{Graphical representation of patterns}
\label{pattern-appendix}
The patterns used in our phased AAPC can be illustrated graphically.
The figures relate to Section \ref{patterns-sect} where a textual and
algebraic description is given.

\begin{figure*}[t]
\epsfxsize=6.5in
\centerline{\epsfbox{\figpath basic-pattern.eps}}
\hspace*{\fill}\begin{minipage}[t]{\caplen}
\caption{\label{patterns-all16} Here we show all one-dimensional phases
for $n = 8$. The equations specify the general case. Notice that the
Class three phases are constructed based on a special rule.}
\end{minipage}\hspace*{\fill}
\end{figure*}

\begin{figure*}[t]
\centerline{\epsfbox{\figpath cross-msg.eps}}

\centerline{(a)}

\centerline{\epsfbox{\figpath cross-pattern.eps}}

\centerline{(b)}
\hspace*{\fill}\begin{minipage}[t]{\caplen}
\caption{\label{cross-two-patterns} 
The top figure illustrates how two messages over two rings can be
{\em crossed} to form a message over a two-dimensional torus. The
bottom figure shows how this technique can be generalized to
cross two one-dimensional phases to form a two-dimensional pattern.}
\end{minipage}\hspace*{\fill}
\end{figure*}

