\section{Introduction}

This document is intended to serve as a tutorial on the construction of
optimal patterns for use in All-To-All Personal Communication.  The
tutorial is divided into sections, beginning with the simplest case.
Each subsequent section will provide a generalization of the results of
the previous section.  Upon reaching the end of this document, the
reader should be able to construct AAPC patterns for tori of any
dimension, with any number of processors per dimension.

Throughout this tutorial, 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}.

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
simultanteously.

For ease of presentation, we initially 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).  Subsequent sections will eliminate these restrictions.
