\section{Communication Patterns of Fx Programs}
\label{sec:commpat}

The Fx~\cite{TASK-PARALLELISM-HPF-JOURNAL} compiler parallelizes dense
matrix codes based on parallel array assignment statements and targets
distributed memory parallel computers using the Single Program,
Multiple Data (SPMD) model.  This model is the ultimate target of many
parallel and parallelizing compilers.  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.  In general, this pattern can
be {\em many-to-many}, where each processor sends to any arbitrary
group of the remaining processors.  However, certain patterns are much
more common than others, especially in dense matrix computations such
as those typically coded in High Performance Fortran and Fx.  For
example, the {\em neighbor} pattern, where each processor $p_i$ sends
to processors $p_{i-1}$ and $p_{i+1}$ is common.  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=5in}}
\caption{Fx Communication patterns}
\label{fig:commpats}
\end{figure}