%\documentstyle{cmu-art} %%%
%\begin{document} %%%
%\newtheorem{lemma}{Lemma} %%%

\subsection{Optimal AAPC message routes and schedules}
\label{patterns-sect}

\newcommand{\novertwo}{(n/2)}
\newcommand{\noverfour}{(n/4)}

In this section, we briefly describe a set of {\em phases} that
achieve optimal AAPC on arrays with unidirectional or bidirectional
links.\footnote {A unidirectional link connecting node {\em a} to node {\em b}
permits communication either from {\em a} to {\em b}, or from {\em b} to {\em a}, but
not in both directions simultaneously.} See~\cite{aapc-tr} for an
expanded description of these phases.  To simplify presentation, we
first describe AAPC patterns on a one-dimensional ring with
unidirectional links.  We then show how to extend these patterns to a
two-dimensional torus.\footnote {For the sake of simplicity, our
discussion is limited to arrays where the number of nodes in each
dimension is the same, and a multiple of four (in the unidirectional
case) or eight (in the bidirectional case).}  Finally we present the
extension from unidirectional to bidirectional links.  Along the way
we introduce a notation that permits the concise description and
manipulation of the patterns.

Throughout this section, we use the following terminology.  A {\em
message} is a communication transmitted from a source to a
destination.  A {\em pattern} is a link-disjoint set of messages.  If a
pattern is a a communications step in an optimal AAPC, we
sometimes refer to it as a {\em phase}.

%% Reword cite if used
%  Our description of the
%phases is similar to that of~\cite{horie92} and~\cite{scott91}.

First we calculate a lower bound on the number of phases needed.
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}
In a bidirectional array there are twice as many links between bisections;
in this case the lower bound is $n^{d+1}/8$.

To achieve this lower bound, we begin with the construction of AAPC
phases on a one-dimensional ring.  Our phases conform to the
following constraints, which are sufficient to guarantee optimality:
\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.
\end{enumerate}

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}{3}
\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.

%{\Large Question for tom,susan: do you think we need to explicitly
%give the order of operation for $+$ vs. $\cdot$?.  That is,
%do we need to put more parentheses in the above?}

% The patterns used in our phased AAPC can be illustrated graphically.

%\end{document} %%%
