
\section{Multi-processing and distributed data}

     The most successful parallel computers presently available are
built from a number of largely autonomous processors, each possessing
its own local memory area (figure \ref{parallel-computer}).  A
processor can access values in its local memory very rapidly.  It can
also access values in another processor's memory, either by special
machine instructions, or through message-passing software.  But with
current technology remote memory accesses are much slower (often by
orders of magnitude) than local ones.  This puts an onus on the
programmer or compiler to minimise the number of accesses any processor
makes to non-local memory.  This is the {\em communication} problem.
\begin{figure}[hbtp]
\centerline{
\begin{picture}(280, 60)(0, 0)
\put(0, 5){Memory areas}
\put(0, 45){Processors}
\multiput(80, 0)(40, 0){5}{\put(10,50){\circle{20}}
\multiput(0, 0)( 0, 20){2}{\line(1, 0){20}}
\multiput(0, 0)(20,  0){2}{\line(0, 1){20}}
\thicklines
\put(10,20){\line(0, 1){20}}
}
\end{picture}
}
\caption{\label{parallel-computer}Idealised picture of a distributed memory parallel computer}
\end{figure}

     A second problem is ensuring that each processor has a fair
share of the total work load.  Obviously, if most work ends up being
done by one processor the benefits of parallelism are lost.  This
is the {\em load-balancing} problem.

     High Performance Fortran allows the programmer to add various {\em
directives} to a program.  These tell the compiler how program data is
to be distributed amongst the memory areas associated with a set of
(real or virtual) processors.  They {\em don't} allow the programmer to
state directly which processor will perform a particular computation.
But it is expected that if the operands of a particular sub-computation
(for example, an assignment) are all found on the same processor, the
compiler will allocate that part of the computation to the processor
holding the operands, whereupon no remote memory accesses will be
involved.

     Hence the main burden on the HPF programmer is to distribute
the program's data across the processors in such a way that
\begin{itemize}
\item
as many sub-calculations as possible involve groups of operands
allocated to the same processor, to minimize remote memory
accesses, while
\item
the set of {\em independent} sub-calculations which can proceed in
parallel at any time should involve data on as many different processors as
possible, to maximise parallelism.
\end{itemize}
These may sound like conflicting goals.  Sometimes they are, and
programs which look highly parallel are nevertheless difficult to
distribute effectively.  Luckily, equally often it is possible to
perform the juggling act successfully.

     To make these points a bit more concrete, imagine an in idealised
situation where the a particular step in a program contains $p$
sub-calculations which can proceed in parallel.  They might be the $p$
elemental assignments making up an array assignment or
\verb$FORALL$ construct.  For the sake of argument, suppose each
expression to be computed involves two operands.  Together with the
variable being assigned, this makes three operands for the whole
sub-calculation.  Also, suppose there are $p$ processors available.
(In general, the numbers of sub-calculations and processors are likely
to be different---this case is just illustrative).

\begin{figure}[hbtp]
\centerline{\psfig{figure=nonlocal.ps,height=3in}}
\caption{\label{non-local}A data distribution leading to
excessive communication}
\end{figure}

     Figure \ref{non-local} illustrates the situation where
all operands of each sub-calculation reside in different
memory areas.  This means that each assignment involves
at least two communications, wherever the calculation is
performed.

\begin{figure}[hbtp]
\centerline{\psfig{figure=unbalanced.ps,height=3in}}
\caption{\label{unbalanced}A data distribution leading to poor load balancing}
\end{figure}

    Figure \ref{unbalanced} illustrates a situation in which
no communication is {\em necessary}, because all operands of
{\em all} the assignments live on the same processor.
But in this case the calculation will generally be performed where
the data is, so no effective parallelism occurs.
(Alternatively, the compiler might decide to share the tasks
out anyway.  But then {\em all} operands of tasks on processors
other than the first would have to be communicated.)

\begin{figure}[hbtp]
\centerline{\psfig{figure=ideal.ps,height=3in}}
\caption{\label{ideal}An ideal data distribution}
\end{figure}

    Figure \ref{ideal} illustrates the ideal situation, where all
operands of an individual assignment occur on the same processor, but
the operand groups of the sub-calculations are uniformly distributed
over processors.  In this case we can rely on the compiler to
allocate each computation to the processor holding the operands,
requiring no communication, but perfect distribution of workload.

     Except in the most trivial programs, it will never be possible to
choose a distribution of program variables over processors so that
{\em all} steps in the calculation look like figure \ref{ideal}.
The art of distributed memory programming is to arrange things so that
the most critical regions of the program look as much like this as
possible.

     There was a certain awkwardness to the descriptions of these three
situations.  In the last case one could generally rely on the compiler
to allocate sub-calculations to processors in the obvious way.  In the
first two cases one has to hedge one's bets, and say that compiler
might allocate computations over processors in various ways, but in any
case the outcome is likely to be unfavourable.  Given that HPF places
an onus on the programmer to think about these kinds of issues, one
might feel it would have been appropriate to allow the programmer
fuller control over where particular sub-computations were performed
(rather than have the programmer second-guess the compiler).  Well,
this argument has some force, but it isn't how HPF has been defined.
As already emphasized, the programmer can define where particular data
items are stored, but not where calculations are performed.

