% Add to send of patterns section

Since the phased algorithm\footnote{
For the remainder of the paper, we discuss the bidirectional, two-dimensional
phased AAPC.}
 completes the AAPC in $n^3/8$ steps, it
will complete in $(n^3/8)(T_s + T_t B)$ cycles, where $T_s$ is the
communication start up time. Thus, the algorithm will achieve the
following network aggregate bandwidth
\begin{equation}
\label{phase-eqn}
 Agg_{phase} = \frac{S \times {\rm Total\ bytes\ sent}}{\frac{n^3}{8}(T_s + T_t B)} =
\frac{32 n B S}{T_s + T_t B}
\end{equation}
As the start up time becomes small compared to the message transfer
time, this algorithm's performance approaches the machine's peak
network aggregate bandwidth calculated in Equation~\ref{system-eqn}.

\subsection{A synchronizing switch for phased AAPC}
\label{dragon-sect}
%
% Section that describes iWarp implementation of the dragon router local
% switch
%

% Introduce idea
The phased AAPC algorithm described in Section~\ref{patterns-sect} 
achieves optimal aggregate bandwidth only when the different phases are
carefully separated. Messages from different phases may have routes
that require the same network resources, and this network contention
can destroy the optimal use of network bandwidth. Phase separation
can be maintained by globally synchronizing after each phase
is completed. However, this adds the overhead of $n^3/8$ 
synchronizations, and global synchronization requires additional communication
resources and/or dedicated hardware mechanisms.  

With a {\em synchronizing switch}, the machine can use the
structure of the AAPC phases to synchronize between the
phases using only local information. 

The switching elements of many supercomputer networks use a routing
technique called {\em wormhole routing}.  iWarp's communication agent
also uses wormhole routing, and the synchronizing switch relies on the
details of this wormhole routing hardware.  Before describing the
synchronizing switch in detail, we first give an overview of iWarp's
wormhole routing hardware.

\subsubsection{Basic wormhole router}
\label{hw-sect}

The iWarp component consists of a computation agent, a memory agent,
and a communication agent.  The most interesting part of the iWarp
component is the communication agent, which is responsible for
switching data streams between four incoming links, four outgoing
links, from and to the local memory, and even directly into the
arithmetic units of the local computation agent. The switch associates
a small input queue for buffering and flow control logic with every
incoming stream.

The core unit of the communication agent is a high performance
scheduler that continuously forwards data words queued in the input
buffers to either the local computation agent or to the input buffer
of a neighboring node. The scheduler 
operates in parallel on all links forwarding up to 40 MB/s per link or
320 MB/s in total. The parts of the switch relevant to our synchronizing
switch implementation are illustrated in Figure~\ref{fig:basic-switch}.

\begin{figure}[ht]
\epsfxsize=3.3in
\centerline{\epsfbox{\figpath basic-switch.eps}}
\hspace*{\fill}\begin{minipage}[t]{\caplen}
\caption{\label{fig:basic-switch} Basic structure of the communication
agent of the iWarp VLSI component. Special header and trailer words
control the forwarding state of the queues to construct connections
without computation agent intervention.}
\end{minipage}\hspace*{\fill}
\end{figure}

The scheduler works independently of the computation agent and
continues to forward data even when the computation agent is stalled
or halted.  Similarly, the streams from and to local memory can
continue to transfer data without intervention from the computation
agent after the DMA controllers are set up. The forwarding activity at
every node is controlled by state associated with the input queue.
The forwarding state of these queues is updated by the communication
agent based on detecting specially tagged data items in the data
stream.

Special header words are used to establish source defined connections.
Based on these header words, the communication agent binds the input
queue with a queue on a neighboring node, so the input queue forwards
data to the neighboring queue.  By default these connections cut
straight through a node, but the routing words specify where the route
should change direction or where the final connection destination is.
In addition to the routing words, a set of {\em stop conditions} can
disable forwarding of an input stream.  When the specified condition
occurs, the input queue stops forwarding data until the computation
agent intervenes.

\subsubsection{Synchronizing switch implementation}

In the phased AAPC, all physical links leading into a
node are used in each phase of the AAPC, either for messages
destined for that node or for messages passing through to other
nodes. Due to this structure, when
a node recognizes that all messages for the
current phase have passed over its input links (i.e.~the {\em tails}
of all messages have passed), it can safely proceed to the
next phase. This assumption is the basis of the synchronizing switch,
and the correctness of this assumption is proved in 
Section~\ref{correct-sect}.

An outline of the iWarp synchronizing switch is shown in
Figure~\ref{drag-code}.  In statement 1, the queues are set to stop
forwarding data whenever the link is not in a message, so messages
that arrive too early are stalled.  Otherwise, a message from phase
$i+1$ may pass through a node still sending messages for phase $i$,
destroying the phase synchronization.  In statements 4 and 5, the
stopped queues are set to forward data until the next time the queues
are not in a message.  Statements 6 to 13 send and receive data for
the nodes actively transferring data from and to their memories in the
current phase. All nodes wait at statement 14 until the messages for
the current phase have passed through their input queues.

\begin{figure}
\hspace*{\fill}\fbox{\begin{minipage}[t]{\caplen}
{\helv\begin{tabbing}
---\=---\=---\=---\=---\=\kill
 1\>SetStopCondition(NotInMessage, AAPCinputs)\\
 2\>{\bh for} phase {\bh from} 0 {\bh to} num\_phases-1 {\bh do}\\
 3\>\>pattern = ComputePattern(node\_id, phase)\\
 4\>\>{\bh forall} in\_queue {\bh in} Active(pattern) {\bh do}\\
 5\>\>\>Forward(in\_queue)\\
 6\>\>{\bh if} SenderAndReceiver(pattern) {\bh then}\\
 7\>\>\>SendMessageHeader(Destination(pattern), Route(pattern))\\
 8\>\>\>ReceiveMessageHeader()\\
 9\>\>\>StartDMA(DataBlockOut[Destination(pattern)], out\_queue)\\
10\>\>\>StartDMA(DataBlockIn[Source(pattern)], in\_queue)\\
11\>\>\>{\bh wait for} DMAs\_complete()\\
12\>\>\>SendMessageTrailer() \\
13\>\>\>ReceiveMessageTrailer() \\
14\>\>{\bh wait for} QueuesComplete(pattern)
\end{tabbing}}
\end{minipage}}\hspace*{\fill}

\hspace*{\fill}\begin{minipage}[t]{\caplen}
\caption{Pseudo-code that implements the synchronizing switch between AAPC 
phases on iWarp. The assertion
QueuesComplete(pattern) is true whenever all involved queues
have signaled NotInMsg status. }
\label{drag-code}
\end{minipage}\hspace*{\fill}
\end{figure}

The current best global synchronization implementation for a $n \times
n\;$ iWarp operates in $O(n)$ steps.  The synchronizing switch code
executes in constant time, but the synchronizing switch must wait for
the tails of messages to propagate which is also $O(n)$
steps. However, the global synchronization time does not even start
until all the tails of all the messages on the machine have been
received, so the local synchronization case overlaps synchronization
with the time already needed for tail propagation.




