\section{Communication Patterns}
\label{sec:commpat}

A popular model for programming parallel computers is the Single
Program, Multiple Data (SPMD) model.  In the SPMD model, each
processor executes the same program, which works on processor-local
data.  Frequently, the processors exchange data by message passing,
which also synchronizes the processors.  This message exchange is
referred to as a {\em communication phase}.  The parallel program
executes as interleaved communication and local computation phases. 

A communication phase can be classified according to the pattern of
message exchange among the processors.  For example, a phase may
exhibit a {\em neighbor} pattern, where each processor $p_i$ sends to
processors $p_{i-1}$ and $p_{i+1}$.  Another common pattern is {\em
all-to-all},  where each processor sends to every other processor.  A
third pattern is {\em partition}, where the processors are partitioned
into two or more sets and each member of a set sends to every member
of another set.  Fourth, a single processor may {\em broadcast} a
message to every other processor.  Finally, the pattern can be a {\em
tree}, where every second processor sends to its left neighbor and
then drops out.  This is repeated until one processor remains.
Sometimes this is followed with a ``down-sweep'', reversing the
process.  These communication patterns are summarized in 
Figure~\ref{fig:commpats}.


\begin{figure}
\centerline{\psfig{figure=commpatterns.eps,width=2.5in}}
\caption{SPMD Communication patterns}
\label{fig:commpats}
\end{figure}