%\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)}
\newcommand{\nsqoverfour}{(n^2/4)}

First we present a tutorial overview of the construction of
optimal, contention-free phases used in AAPC.  Throughout this
section, we use the following terminology.  A {\em message} is a block
of data transmitted from a source to a destination node.  A {\em
pattern} is a link-disjoint set of messages.  If a pattern is an
optimal communications step in an AAPC, we sometimes refer to it as a
{\em phase}.

We also make the distinction between {\em unidirectional} and {\em
bidirectional} links.  A unidirectional link connecting node {\em a}
to node {\em b} permits communication from {\em a} to {\em b}, or from
{\em b} to {\em a}, but not in both directions simultaneously.  A
bidirectional link permits communication in both directions
simultaneously.  For ease of presentation, we limit the discussion 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).

\subsubsection{AAPC on a ring of unidirectional links}

We begin with a description of the simplest case:  AAPC patterns on a
one-dimensional ring of $n=4i: (i \in {\cal N})$ processors connected by unidirectional
links.

\paragraph{Communication requirements}
\label{sec:comm-req}

It is helpful to consider all the messages that must be exchanged.
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.

\noindent 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 analogous 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.

Every necessary communication (i.e. a ({\em source,destination}) pair)
for the AAPC is represented by some message in the above two sets, and
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.}

The system cannot transmit all of these messages simultaneously, since
many of them share the same communication links.  At the other
extreme, the system could transmit the messages one at a time, but
doing so would leave most links idle, 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 communication {\em
patterns}.  Figure~\ref{sample-patterns} shows one possible division
of AAPC on a ring of four nodes into contention-free 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}.)

\begin{figure}[t]
%\epsfxsize=6.5in
\begin{center}
\parbox{5in}{
\epsfbox{\figpath exphase.eps}}
\begin{minipage}[t]{\caplen}
\caption{\label{sample-patterns} One possible division of the
communication needed for a four node AAPC into contention-free
phases.}
\end{minipage}
\end{center}
\end{figure}

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

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

\paragraph{Lower bound on number of phases}

It is helpful to 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}
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.

\paragraph{Constructing the phases}

Now we present a method for constructing phases that adheres to our
four optimality constraints.  Each phase 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.  Figure~\ref{one-chain-fig}
shows one such phase.

\begin{figure}
\begin{center}
%\epsfxsize=5in
\parbox{5in}{
\epsfbox{\figpath pat-fig1.eps}}

\begin{minipage}[t]{\caplen}
\caption{One circular phase consisting of four messages.}
\label{one-chain-fig}
\end{minipage}
\end{center}
\end{figure}

One interesting property of these 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.  For example, Figure~\ref{one-chain-fig} shows the (0,1)
phase, since the message contained in the first half of the ring is
from node 0 to node 1.  Using this notation, we can concisely describe
the set of all phases for $n=8$ as:
\[
\lbrace (\mbox{\em i,j}) \mid 
i=0 \ldots (\frac{n}{2}-1), j=0 \ldots (\frac{n}{2}-1) \rbrace
\]

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 previous guidelines, 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 
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.)  Figure~\ref{class3-chain-fig}
shows one such phase constructed by this augmented rule.

\begin{figure}[bht]
%\epsfxsize=5in
\begin{center}
\parbox{5in}{
\epsfbox{\figpath pat-fig2.eps}}

\begin{minipage}[t]{\caplen}
\caption{One circular phase combining 0 hop and $n/2$ hop messages.}
\label{class3-chain-fig}
\end{minipage}
\end{center}
\end{figure}

Given the chaining rule, constructing the phases is straightforward.
The greedy algorithm shown in Figure~\ref{greed-code} suffices.
Figure~\ref{all-phase-fig} shows all phases generated by this algorithm for
$n=8$.

\begin{figure}
\begin{center}
\begin{minipage}{6in}
\begin{tabbing}
tabtab\=tabtab\=tabtab\=tabtab\= \kill
{\em Messages} $\leftarrow$ The set of all messages that must be sent except 0 hop
and $n/2$ hop messages\\
{\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)$  and \\
\>	\>	\>	{\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} ({\em Phase})\\
\\
{\em Messages} $\leftarrow$ The set of all $n/2$ hop messages\\
{\bf while} {\em Messages} $ \not= \emptyset $ \\
\>	{\bf remove} some message {\em m=(source,destination)} from {\em Messages} \\
\>	{\bf remove} some message {\em m$'$=(source$'$,destination$'$)} from {\em Messages}, such that: \\
\>	\>	{\em source}$' = ${\em destination}	\\
\>	{\em Phase} $\leftarrow m \cup m'$\\
\>	$m \leftarrow ({\em source}-1,{\em source}-1)$\\
\>	$m' \leftarrow ({\em source}'-1,{\em source}'-1)$\\
\>	{\em Phase} $\leftarrow {\em Phase} \cup m \cup m'$\\
\>	{\bf output} ({\em Phase})\\
\end{tabbing}
\end{minipage}

\begin{minipage}{\caplen}
\caption{Greedy algorithm for creating optimal one-dimensional phases
from the list of required communications.}
\label{greed-code}
\end{minipage}
\end{center}
\end{figure}

\begin{figure}
\begin{center}
\parbox{6.5in}{
\epsfxsize=6.5in
\epsfbox{\figpath pat-fig3.eps}}

\begin{minipage}[t]{\caplen}
\caption{All phases generated by the greedy algorithm for $n=8$.}
\label{all-phase-fig}
\end{minipage}
\end{center}
\end{figure}

\paragraph{Making the transition to two dimensions}

The two-dimensional phases we describe 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}
\setcounter{enumi}{4}
\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 the greedy algorithm shown in
Figure~\ref{greed-code}, 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 6.  

We enforce constraint 6 to simplify the creation of dense
two-dimensional phases for the 0 hop $(n/2)$ hop messages described in
the next section.  With these additional constraints on the 0 hop
$(n/2)$ hop messages, Figure~\ref{patterns-all16} depicts all the
phases for $n=8$.

\begin{figure}
\begin{center}
\parbox{6.5in}{
\epsfxsize=6.5in
\epsfbox{\figpath pat-fig4.eps}}

\begin{minipage}[t]{\caplen}
\caption{\label{patterns-all16} Here we show all one-dimensional phases
for $n = 8$ following the additional constraints for the 0 hop, $n/2$
hop messages.}
\end{minipage}
\end{center}
\end{figure}

\subsubsection{AAPC with two-dimensional, unidirectional links}
\label{sec:two-d-phases}

We now show how to extend these one-dimensional 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.

\paragraph{Cross products}
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} show the
cross product operation on two messages, and the entire figure shows
the cross product operation on two patterns.

\begin{figure}[htb]
\begin{center}
\parbox{4in}{
\epsfxsize=4in
\epsfbox{\figpath cross-pattern.eps}}

\begin{minipage}[t]{\caplen}
\caption{\label{cross-two-patterns} 
Illustrating the {\em cross product} operation to create a message in
two dimensions based on two one-dimensional messages.}
\end{minipage}
\end{center}
\end{figure}

\paragraph{Creating dense phases}
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$ taking the cross produce of
corresponding patterns $p_i$ and $q_i$ and overlaying the results:
\[ p_0 \times q_0 + \ldots + p_{(n/4)-1} \times q_{(n/4)-1} \]
where $+$ is the pattern overlay operation.
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)$, and ${\bf r}^k(M_a)$ is {\bf r()}
applied to $M_a$ $k$ times.  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:
\begin{equation}
\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\}
\label{2d-phase-eq}
\end{equation}
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}.


\subsubsection{Phases with bidirectional links}

It is straightforward to extend these unidirectional phases to the
cases of rings and tori with bidirectional links. For bidirectional
rings, look at the node disjoint $M$ tuples calculated in the previous
section. Overlay elements of $M_i$ with elements of $\overline{M_i}$ as below:
\[ \forall  p_k \in M_i : p_k + \overline{p_{k+1}} \]
The elements that are overlaid must be node disjoint.  All
unidirectional phases are paired to form the bidirectional phases, so
the number of bidirectional phases is half the number of
unidirectional phases.

For the case of bidirectional tori, we must 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\}
\]
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
as calculated in Equation~\ref{eq:num-phases-needed}.

%\subsubsection{Construction of phases for higher dimensions}

%The cross product and overlay techniques described in the last two
%sections extend naturally to higher dimension topologies. For example,
%by taking the cross product of three one-dimensional phases, one can
%calculate a pattern for a three-dimensional torus. The description of
%the two-dimensional phases in Equation~\ref{2d-phase-eq} can be
%generalized in higher dimensions. For $d$ dimensions, $2^d$
%combinations of $d$ $M$ tuples will be required. There are $n/2$
%choices for each $M_i$ and $n/4$ rotations possible, so the number of
%phases will be:
%\[ 2^d \times n^{d+1} / 2^{d+2} = n^{d+1}/4 \]
%which matches our lower bound of Equation~\ref{eq:num-phases-needed}.





