\section{AAPC on a One-Dimensional Ring with Unidirectional Connections}

We begin with a description of the simplest case:  AAPC patterns on a
one-dimensional ring of $n=4i$ processors connected by unidirectional
links.

\subsection{Communication Requirements}
\label{sec:comm-req}

It is helpful to consider all the communications that must take
place.  First we consider communications in the clockwise direction only.

Each node sends a message to the node that is:
$\left\{\begin{array}{l}
\mbox{0 hops away (send-to-self),}	\\
\vdots					\\
\frac{n}{2} \mbox{ hops away}
\end{array}
\right\}$ clockwise.

A similar set of communications must take place in the counterclockwise
direction as well:

Each node sends a message to the node that is:
$\left\{\begin{array}{l}
\mbox{1 hop away,}			\\
\vdots					\\
(\frac{n}{2}-1) \mbox{ hops away}
\end{array}
\right\}$ counterclockwise.

Note that the counterclockwise communications are analagous to the
clockwise communications, except for the 0 hop and $(n/2)$ hop
messages.  Since these messages reach the same destinations regardless
of the direction of travel, there is no need to include both clockwise
and counterclockwise versions of these messages.

The reader should be convinced that every possible communication
({\em source,destination}) is represented by some message in the above two
sets, and that every message follows a shortest route to its
destination.\footnote{For example, on an 8 node ring, it is possible to reach the
same destination either by moving 5 hops in the clockwise direction
or 3 hops in the counterclockwise direction.  Our messages will
always take the shortest route.}
Figure~\ref{fig:all-64-messages} graphically shows these lists for the
case $n=8$.


Note that we cannot transmit all these messages simultaneously, since
many of them share the same communication links.  In the other extreme,
we could transmit the messages one at a time, but doing so would leave
most links idle and thus is clearly not an optimal AAPC.  However,
since link-disjoint messages can be transmitted simultaneously without
conflict, it is natural to try to combine messages in a logical way to
form communications {\em patterns}.  Figure~\ref{fig:sample-patterns}
shows some possible patterns.  Our goal is to find a set of patterns
that is optimal.  (Using our terminology, we will refer to these
optimal patterns as {\em phases}.)

To guarantee optimality, our phases must conform to the following
three constraints:
\begin{enumerate}
\item Every possible message appears exactly once in the phases.
\item Each of these messages follows a shortest route to its destination.
\item Every link in the array is used exactly once per phase--that is,
there is no contention for links, and no link is ever idle.\footnote
{When the number of processors in a dimension is not
a multiple of 4 (8) for the unidirectional (bidirectional) case, it
becomes necessary to leave some links idle, violating constraint 3.
Later sections will describe how to construct patterns that are optimal
in those cases.}
\end{enumerate}

Because memory bandwidth is usually a bottleneck in typical machines,
our phases also adhere to the following additional constraint:
\begin{enumerate}
\setcounter{enumi}{3}
\item Each node must send and receive at most one message per phase.
\end{enumerate}

\subsection{Lower Bound on Phases Needed}

It is helpful to
calculate a lower bound on the number of phases needed.  Here we present
a general formula that will be useful in later sections as well.
Assume a $d$-dimensional array with $n$ nodes in each dimension.  Since
every node needs to send a message to every node (including itself),
$(n^d)^2$ messages must be sent.  Because there are not
enough links to send all of the messages simultaneously, we partition
the set of messages into phases.
The lower bound on the number
of phases needed follows from the bisectional bandwidth:
\begin{equation}
\label{eq:num-phases-needed}
\frac{\mbox{\em number of messages between bisections}}
	 {\mbox{\em number of links between bisections}} =
\frac{2 \times (n^d/2)^2}{2 \times n^{d-1}} =
\frac{n^{d+1}}{4}
\end{equation}
A bidirectional array has double the communication bandwidth between bisections;
in this case the lower bound is $n^{d+1}/8$.

In the one-dimensional, unidirectional case, $ n^2 $ messages need to
be sent.  Formula~\ref{eq:num-phases-needed} shows that the lower bound
on the number of phases needed is $ \nsqoverfour $.  This implies that
we will need to send on average four messages per phase in order to
meet this lower bound.

\subsection{Constructing the Phases}

In this section we present a method for constructing phases that
adheres to the constraints stated previously.  Each phase in our set is
a circular {\em chain} of four messages, in which the destination node
of one message serves as the source node of the next, and so on.  In
order to meet the constraints, we pair up short messages with long ones
in the following way: 0 hop messages with $n/2$ hop messages, 1 hop
messages to $(n/2)-1$ hop messages, and so on.  Since the total length
of any such pair is $n/2$, it will reach halfway around the ring.  If
we chain two such pairs we will create a pattern composed of four
messages that spans the ring, using all the links.  See
Figure~\ref{fig:chain-example} for an example phase.

Special care must be taken when constructing the phases that chain
0 hop messages to $n/2$ hop messages.  If we were to chain them according
to the guidelines in the previous paragraph, the result would be
that two processors would send and receive two messages each,
in violation of Constraint 4.  In these cases, we modify the above chaining
rule so that the source node of an 0 hop message is the node
{\em before} the destination node of a $n/2$ hop message.  (Likewise,
the source node for the next $n/2$ hop message is the node {\em after}
the destination node of a 0 hop message.)
See Figure~\ref{fig:0-hop-exception} for an example of this type
of phase.

Constructing the phases is now straightforward.  The following
greedy algorithm suffices:

\begin{tabbing}
tabtab\=tabtab\=tabtab\=tabtab\= \kill
{\em Messages} $\leftarrow$ The set of all messages that must be sent, as described in
Section~\ref{sec:comm-req} \\
{\bf while} {\em Messages} $ \not= \emptyset $ \\
\>	{\bf remove} some message {\em m=(source,destination)} from {\em Messages} \\
\>	{\em Phase} $\leftarrow \lbrace m \rbrace$ \\
\>	{\bf repeat} 3 times \\
\>	\>	{\bf remove} a message {\em m$'$=(source$'$,destination$'$)}
		from {\em Messages}, such that: \\
\>	\>	\>	{\bf direction}$(m') = $ {\bf direction}$(m)$, \\
\>	\>	\>	{\bf length}$(m') = (n/2) - ${\bf length}$(m)$, \\
\>	\>	\>	and {\em source}$' = ${\em destination}	\\
\>	\>	{\em Phase} $\leftarrow$ {\em Phase} $\cup \; \lbrace m' \rbrace$ \\
\>	\>	$m \leftarrow m'$ \\

\>	{\bf output} $(Phase)$
\end{tabbing}

For the sake of simplicity, the algorithm as presented does not
correctly handle chaining 0 and $(n/2)$ hop messages, but can be easily
modified to do so.

\subsection{Making the Transition to Two Dimensions}

The two-dimensional phases we will construct in Section~\ref{sec:two-d-phases}
are easily derived from the one-dimensional phases.  However, they impose two
additional constraints on those phases:
\begin{enumerate}
\item The number of phases in each direction must be equal
\item In a given direction, the phases that pair 0 hop and $(n/2)$ hop messages must be node-disjoint with respect to one other.
\end{enumerate}

The one-dimensional phases described in the previous section do not satisfy these
constraints, but can be easily modified to do so.  From
Section~\ref{sec:comm-req} and Algorithm~{\bf ???} it should be clear that
the number of phases in both directions would be the same, were it not for
the phases that pair 0 hop and $(n/2)$ hop messages.  These phases all communicate
in the clockwise direction.  The solution is straightforward: we reverse the
direction of half of those phases, being careful to satisfy constraint 2, above.

Figure~\ref{patterns-all16} depicts all the phases for $n=8$.

An interesting property of the phases is that given any one of the
messages it contains, it is straightforward to infer the other three.
Furthermore, each phase has exactly one message that both starts and
ends inside the first half of the ring.  We use the notation ({\em
source,destination}) to refer to the phase which contains that
message.  The phases in Figure~\ref{patterns-all16} have been labeled
using this notation.

Using this notation, we can describe the set of all phases for
$n=8$ in the following concise way:
\[
\lbrace (\mbox{\em i,j}) \mid 
i=0 \ldots (\frac{n}{2}-1), j=0 \ldots (\frac{n}{2}-1) \rbrace
\]

{\LARGE Stop reading here}


\section{AAPC on a One-Dimensional Ring with Unidirectional Connections}

We begin with a description of the simplest case:  AAPC patterns on a
one-dimensional ring of $4i$ processors connected by unidirectional
links.  Equation~\ref{eq:num-phases-needed} predicts a lower bound
of $n^2/4$ phases.  The patterns that we present achieve this lower bound.

There is more than one possible set of phases that conforms to these
constraints.  The set of phases that we present conforms to the following
additional constraints:
\begin{enumerate}
\setcounter{enumi}{4}
\item Because there are $n^2/4$ phases, it follows
that we must send {\em on average} four messages per phase.  The phases we
present send {\em exactly} four messages per phase.
\item To limit memory bandwidth requirements, we require that each node
send and receive at most one message per phase.
\end{enumerate}

%\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.  Note that the
%%Class three phases are constructed based on a special rule.}
%\end{minipage}\hspace*{\fill}
%\end{figure*}

Thus each phase in our set is a {\em chain} of four messages, in which
the destination node of one message serves as the source node for
the next, and so on.
  It is helpful to consider all the
communications that must take place; we start by concentrating on the
clockwise direction only.  Each node must send a message to the node
that is: 0 hops away (send-to-self), 1 hop away, \ldots, $n/2$ hops
away.  We chain short messages to long ones in the following way: 0 hop
messages to $n/2$ hop messages, 1 hop messages to $(n/2)-1$ hop
messages, and so on.  Since the total length of any such pair is $n/2$, it
will reach halfway around the ring.  If we chain two such pairs we will
create a pattern composed of four messages that spans the ring, using all
the links.  This is essentially how all of the phases are constructed.
The left side of Figure~\ref{patterns-all16} depicts all the clockwise
phases for $n=8$.

An interesting
property of the phases is that given any one of the messages it
contains, it is straightforward to infer the other three.  Furthermore,
each phase has exactly one message that starts and ends inside the
first half of the ring.  We use the notation ({\em source,destination})
to refer to the phase which contains that message.  The phases in
Figure~\ref{patterns-all16} have been labeled using this notation.

A similar set of messages must travel in the reverse direction.
The counterclockwise phases are obtained by simply reversing the
direction of the messages in the clockwise phases; these are depicted
on the right side of the same figure.\footnote{Special care must be
taken in the construction of the class 3 phases that chain 0 hop to $n/2$ hop
messages:  1.~Since the 0 hop messages traverse no links, chaining them
in the usual way would cause a node to be the source for two different
messages, violating constraint 5.  2.~Since all possible
messages of sizes 0 and $n/2$ are contained in the clockwise phases,
there is no need for the corresponding counterclockwise phases.
However, symmetry suggests that there ought to be an equal number of
phases in each direction, so the direction of half of these
phases is reversed.  3.~All of these phases that communicate in the same direction
must be node-disjoint; this will be useful in the extension to two
dimensions.  The bottom of Figure~\ref{patterns-all16} illustrates
these phases.}
The total number of phases is $n^2/4$, which matches the lower bound
computed in Equation~\ref{eq:num-phases-needed}.  Since these phases
conform to the other constraints as well, they enable an optimal AAPC.

We now show how to extend these phases to achieve optimal AAPC on a
two-dimensional $n \times n$ torus with unidirectional links, achieving the
lower bound of $n^3/4$ phases.

Every message on the torus can be routed as a horizontal motion
followed by a vertical motion.  We define the {\em cross product} of
two one-dimensional messages $u$ and $v$ as a two-dimensional message
that takes its horizontal motion from $u$ and its vertical motion from
$v$, and we write this as $u \times v$.  We define the cross product of
two one-dimensional patterns $p$ and $q$ as a two-dimensional pattern
composed of cross products of all possible pairs of messages from $p$
and $q$.  The bold arrows in Figure~\ref{cross-two-patterns} depict the
cross product operation on two messages, whereas the figure in its
entirety depicts the cross product operation on two patterns.

%\begin{figure}[htb]
%\epsfxsize=3.3in
%\centerline{\epsfbox{\figpath cross-pattern.eps}}
%\hspace*{\fill}\begin{minipage}[t]{\caplen}
%\caption{\label{cross-two-patterns} 
%The graphical representation illustrates the algebraic {\em cross product}
%operation.  The bold arrows depict the cross product of two one-dimensional
%messages.  The figure in its entirety depicts the cross product of two
%one-dimensional patterns.}
%\end{minipage}\hspace*{\fill}
%\end{figure}

As can be seen from Figure~\ref{cross-two-patterns}, forming the cross
product of two one-dimensional phases results in a two-dimensional
pattern that saturates four rows and four columns of the torus.  When
$n>4$, this pattern leaves some links idle and is therefore not an
optimal AAPC phase.  In these cases we must {\em overlay} multiple
two-dimensional patterns which saturate disjoint row and column sets in
order to create a phase that saturates all of the rows and columns.
The number of patterns that must be simultaneously overlaid is
$n/4$.

Here we introduce some notation in order to more conveniently describe
the two-dimensional phases.  An optimal two-dimensional phase is formed
by taking the {\em dot product} of two ordered tuples,
$M_a = (p_0,\ldots,p_{(n/4)-1})$
and
$M_b = (q_0,\ldots,q_{(n/4)-1})$,
where each of the $p_i$ or $q_i$ is a clockwise one-dimensional phase.
We define the dot product $M_a \cdot M_b$ as overlaying 
$p_0 \times q_0$,
\ldots,
$p_{(n/4)-1} \times q_{(n/4)-1}$.
We define $\overline{p_i}$ as the counterclockwise pattern which corresponds
to $p_i$, and $\overline{M_a}$ as
$(\overline{p_0},\ldots,\overline{p_{(n/4)-1}})$.
The $M$ tuples must conform to the following two constraints:
\begin{enumerate}
\item All the one-dimensional phases in a given $M$ must be
node-disjoint.
\item Every clockwise one-dimensional phase must appear
in exactly one $M$.
\end{enumerate}

There is a simple algorithm for creating the $M$ tuples.  If we think
of each node in the upper half of the ring as a player in an
arbitrary two-player game (e.g. chess), then each clockwise
one-dimensional pattern $(a,b)$ (with $a<b$) can be thought of as a
game involving players $a$ and $b$.  If $c$ and $d$ ($c<d$) are
distinct from $a$ and $b$, we can schedule their game (i.e. pattern
$(c,d)$) simultaneously.  Building the $M$ tuples then becomes simply
an instance of the well-known tournament scheduling algorithm.  Here
is one possible tournament schedule for $n=8$:
$M_1=((0,1),(2,3))$,
$M_2=((0,2),(1,3))$,
$M_3=((0,3),(1,2))$.
This schedule contains all the clockwise phases except the $(a,a)$
phases--those involving send-to-self communication.  Since these were
deliberately constructed to be node-disjoint, they can all be
scheduled together.  Thus the schedule must include one more
entry:  $M_0=((0,0),(2,2))$.  In general, the number of $M$ tuples
will be $n/2$.

%With one additional bit of notation, we can
%concisely describe all the two-dimensional phases.  
We define a rotate operator ${\bf r}$ such that if 
$M_a = (p_0,p_1 \ldots p_{(n/4)-1})$, then
${\bf r}(M_a) = (p_1,\ldots,p_{(n/4)-1},p_0)$.  Also,
${\bf r}^2(M_a) = {\bf r}({\bf r}(M_a))$, and so on.
We use this operator to ensure that every one-dimensional phase
is crossed with every other one-dimensional phase in some
two-dimensional phase.

Using this notation, the set of all unidirectional
AAPC phases on a $n \times n$ torus can be described as:
\[
\left\{
\begin{array}{c}
M_i \cdot r^{\,k}(M_j),				\\
M_i \cdot r^{\,k}(\overline{M_j}),		\\
\overline{M_i} \cdot r^{\,k}(M_j),		\\
\overline{M_i} \cdot r^{\,k}(\overline{M_j})	\\
\end{array}
\right\}
\]
for
$i$ in $\{0 \ldots \novertwo  -1\}$,
$j$ in $\{0 \ldots \novertwo  -1\}$, and
$k$ in $\{0 \ldots \noverfour -1\}$.

Thus the total number of phases is
$
4 \times (n/2) \times (n/2) \times (n/4) = n^3/4
$,
which matches the lower bound computed in Equation~\ref{eq:num-phases-needed}.

It is straightforward to extend these phases to the case of a torus
with bidirectional channels.  To accomplish this, all we need to do is
overlay one unidirectional two-dimensional pattern with another
pattern that is node-disjoint, and uses the links in the reverse
direction.  One such set of phases is:
\[
\left\{
\begin{array}{c}
M_i \cdot r^{\,k}(M_j) + \overline{M_i} \cdot r^{\,k+1}(\overline{M_j}),	\\
M_i \cdot r^{\,k}(\overline{M_j}) + \overline{M_i} \cdot r^{\,k+1}(M_j)
\end{array}
\right\}
\]
where the $+$ operator overlays two
phases.  In this case the total number of phases is
$
2 \times (n/2) \times (n/2) \times (n/4) = n^3/8
$
which again matches the lower bound.
