
\subsubsection{Adding support for phased AAPC to other machines}

Our iWarp prototype implementation of the synchronizing switch is
quite efficient, but this implementation relies on a close interaction
between the communication agent and the computation agent, so it is
not a practical approach for many of today's distributed memory
machines. Specifically, the computation agent explicitly waits for all
of the input queues to be NotInMessage before proceeding to the next
phase and explicitly forwards the input queues for the next phase.  In
several other distributed memory
systems\cite{CM5-NETWORK,PARAGON-XPS,T3D-OVERVIEW,AP1000-NETWORK,IBM-SP1},
the communication and computation agents are not as tightly coupled, so
the computation agent cannot directly observe and control the input
queues.


%Using an existing network with the phased AAPC router architecture
%requires a small change to the switching hardware. As streams get
%switched the message headers update the assignment of input queues to
%the outputs (links) in the data forwarding table (see Figure
%\ref{fig:basic-switch}). A change of an a queue assignment is triggered by
%the beginning or the end of a message (markers or byte counters flag
%end of message) and can only take place if the requested output link
%(or virtual channel) is free. 

Changing a traditional wormhole router as described in
Section~\ref{hw-sect} to support the synchronized switch requires a
small change to the switching hardware.  An additional constraint must
be enforced whenever the assignment of a queue is changed. As an
example, consider extending the basic $6 \times 6$ switching chip used
in the Paragon routing backplane. It supports X+,X-,Y+,Y- links
connected as a mesh and two Z+,Z- paths connected to the network
interface of the local processor.  To support phased AAPC, five input
queues must be configured as AAPC queues. For correct execution of the
synchronizing switch, these AAPC queues can only change their
forwarding assignments whenever all five AAPC queues indicate that
they are done forwarding a message. This constraint requires a sticky
{\em NotInMessage} bit for each queue. A simple AND-gate can check
whether all queues have been passed by a message and enable the
processing of a new message header at this queue. Other distributed
memory systems with that use wormhole routing could be extended
in a similar fashion (e.g. AP-1000, SP-1).

%The routing hardware of the AP-1000 the RTC could also be modified
%easily to accommodate synchronous message switching. This network
%architecture is perfectly equipped for different dedicated routers.
%The structured buffer pool already provides a 17th set of queues for
%broadcast routing. An 18th set of queues for synchronized switching
%would be a natural extension of that concept.

%Similarly the switches of the SP-1 could be equipped with synchronous
%switching support for AAPC. Since the SP-1 uses a multistage network,
%we would use the set of AAPC phases that are optimal for the
%multistage switch\cite{take91}.

Figure~\ref{drag2-code} shows the computation agent pseudo-code for
the phased AAPC with the enhanced routing hardware for synchronized switching.
This code is a subset of the code needed for our prototype shown in
Figure~\ref{drag-code}.  Blocks of data are sent according to the
phased AAPC schedule. Unlike the prototype AAPC code, every node sends
a (possibly empty) message in every phase.  The node must send an
empty message to itself if it is not scheduled to exchange data in a
particular phase.  Otherwise, the synchronizing switch would have to
determine whether the node needs to inject a message in each phase,
which would require a tighter interaction between the communication
and computation agents.  With the addition of empty messages, the
synchronizing switch can simply inject a message in each phase.

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

\hspace*{\fill}\begin{minipage}[t]{\caplen}
\caption{Code for sending AAPC messages over an extended AAPC router.}
\label{drag2-code}
\end{minipage}\hspace*{\fill}
\end{figure}

Many routers use multiple pools of buffered queues to support virtual
channels (e.g. AP-1000, iWarp).  Such routers could adapt one pool of
virtual channels for AAPC with synchronized switching and use the
other pools for message passing and other communication methods.  Once
the switch is enhanced for synchronized switching, phased AAPC can
easily be incorporated into an existing message passing library.

