
\section{Data mapping directives}

\subsection{HPF directives}

     For the purposes of this document, HPF directives will be
written {\em as if} they were part of the Fortran language.
Please note well that in fact the standard defines these directives
to be ``structured comments''.  All the new ``statements''
introduced in the remainder of this document would have
to be preceded with the text ``\verb|!HPF$|'' in real programs.
So, looking ahead to the next section, when we write
\begin{verbatim}
  PROCESSORS P (10)
\end{verbatim}
the actual program text must be
\begin{verbatim}
  !HPF$ PROCESSORS P (10)
\end{verbatim}

     There are two main arguments for making HPF directives into Fortran
comments.  Firstly, used correctly, they do not change the
actual results of a program.  They only effect its {\em performance} on
a parallel machine.  In so far as they have no effect on results, they
have the same status as comments.  Secondly, more pragmatically, an HPF
program can be compiled by an ordinary Fortran 90 compiler, which will
just ignore the HPF comments.  Hence an HPF program can be tested and
debugged on any sequential computer for which Fortran 90 is available.
This is a credible argument, undermined slightly by the
fact that the HPF extensions described in part I (\verb$FORALL$ and
\verb$PURE$) do {\em not} have the status of comments, and would not be
accepted by an ordinary Fortran compiler.

     In any case the justification for not writing HPF directives as
comments in this document is aesthetic---the proliferation of
``\verb|!HPF$|'' strings would clutter the examples.

\subsection{The processor arrangement}

     The programmer is expected to specify how program variables
are distributed between the memory areas associated with a set of
processors.  A necessary (or at least, desirable) prerequisite is for a
program to be able define some representation of the set of processors it
uses.  This can be done through the \verb$PROCESSORS$ directive.

     Before introducing the directive, we should say something about
the relationship between physical and abstract processors.  The
parallel computer on which a program is run will consist of some fixed
set of physical processors.  By and large, when we talk of
``processors'' below we won't be referring to these processors, but to
a set of logical or {\em abstract} processors, which may be larger or
smaller in number than the set of processors in the machine.  If there
are fewer abstract processors than physical processors, probably some
of the physical processors will be idle, or occupied with other
programs.  If there are more abstract processors than physical
processors, the system will somehow simulate the number of processors
specified.  In any case, the programmer has the option of not worrying
about the size of the target machine\footnote{Strictly speaking, an HPF
implementation isn't {\em required} to support sets of abstract
processors whose number differs from the set of physical processors,
but the better systems presumably will.  There may be performance
advantages in making the abstract processor set conform with the
physical processor set}.  An abstract processor has an associated local
memory area, just like a real processor.

     The syntax of a \verb$PROCESSORS$ definition is similar
to the syntax of an array definition in Fortran
\begin{verbatim}
  PROCESSORS P (10)
\end{verbatim}
introduces a set of 10 abstract processors, assigning them the
collective name \verb$P$.

     Like ordinary arrays, abstract processor sets, or {\em processor
arrangements}, can be multi-dimensional.  For example
\begin{verbatim}
  PROCESSORS Q (4, 4)
\end{verbatim}
introduces 16 abstract processors in a 4 by 4 array.
There are a couple of reasons why one might want to declare a processor
arrangement to be multi-dimensional.  Most importantly, the major
data-structures in a program may be multi-dimensional arrays, and it
may be that the best way to divide up this data over processors is by
sub-dividing it into blocks of the same dimension as the whole arrays.
In this situation it certainly simplifies matters if we can view the
processor arrangement itself as an array of the relevant dimension.  As
a secondary consideration, some parallel computers are physically
arranged as multi-dimensional grids, in such a way that
nearest-neighbour communications are cheaper than more remote
communications.  By exploiting such knowledge, and mimicking the
physical grid arrangement in the \verb$PROCESSORS$ declaration, a
sufficiently determined programmer may be able to tweak
performance\footnote{Such machine-specific optimisations are slightly
at odds with the philosophy of portable parallel programming.  Also it
seems likely that the physical processor arrangement will have less
influence on communication speeds in forthcoming parallel machines.}.

     An important point to appreciate is that a single program may
contain many \verb$PROCESSORS$ declarations.  There is no
defined relation between two processor arrangements of different
shapes\footnote{There is however, an implicit equivalence between
processor arrangements of the {\em same} shape.  See section
\ref{conformance}}.  Typically they will be independently mapped onto
the same set of underlying physical processors.

\subsection{The template abstraction, and distribution}

     Having seen how to define one or more target processor
arrangements, we need to introduce mechanisms for distributing data
arrays over those arrangements.  Although HPF does allow arrays to be
distributed over processors directly (see section \ref{anonymous}) it
is often more satisfactory to go through the intermediary of an
explicit {\em template}.

     We have already introduced the idea of a ``processor grid'' as a
\verb$PROCESSORS$ array, and suggested that the {\em dimension} of that
grid may well reflect the dimension of the principal data arrays in the
program.  Generally, though, it would be inappropriate for the {\em
size} parameters of the abstract processor array to correspond to those
of the data arrays of the algorithm.  Although the set of abstract
processors needn't exactly match the set of physical processors, there
is a tacit assumption that abstract processors will be used at a similar
level of ``granularity'' to physical processors.
It wouldn't normally do to allocate abstract processors at the
level of one processor per element of a program data array.

     Remembering that a large overhead is usually incurred when a
physical or abstract processor accesses data outside its own memory
area, whereas local accesses are inexpensive, the logical r\^{o}les of
the abstract processor arrangement are
\begin{itemize}
\item
to define the level of data localisation---many important algorithms
can exploit efficient local memory access at the abstract processor
level, and
\item
to delimit evenly divided sets of subtasks, which can be executed
in parallel.
\end{itemize}
On the other hand, there is a niche for a finer grain logical grid,
which {\em is} targetted at the ``array element'' (or ``problem grid'')
level.  In HPF this r\^{o}le is assumed by the template.

     For the remainder of this section we rely on the readers
patience, to accept without further justification the utility of the
template as a representation of a ``problem-oriented grid''.  (This
grid might, for example, correspond to some lattice of points over
which a differential equation has been discretised.)  In the next
section we will see how data arrays are aligned to a template.  Until
then, the template will be treated as a sort of abstract array, with no
associated data.  Figure \ref{mapping} represents the HPF data mapping
scheme: the rest of this section is concerned with the bottom half
of the diagram.
\begin{figure}[hbtp]
\centerline{\psfig{figure=mapping.eps,height=2.5in}}
\caption{\label{mapping} The stages of data mapping in HPF.}
\end{figure}

     A template can be declared in much the same way as a processor
arrangement.
\begin{verbatim}
  TEMPLATE T (50, 50, 50)
\end{verbatim}
delares a 50 by 50 by 50 three-dimensional template called \verb$T$.
Having declared it, we usually want to establish a relation between a
template and some processor arrangement.  We want to say in more or
less detail how the elements of the template are distributed amongst
the elements of the processor arrangement.  This is done by giving
\verb$T$ the \verb$DISTRIBUTE$ attribute\footnote{This is Fortran-speak.
In Fortran any variable has a type, which is best defined through an
explicit type declaration.  It may have other ``attributes'', such
as shape.  For historical reasons attributes of a variable can be
defined in separate statements to the type definition---the
shape attribute can be defined in a separate \verb$DIMENSION$
statement.  Fortran 90 adds a new clutch of allowed attributes.
HPF extends the set again.  In particular ``distribution''
is an attribute, in this sense, of a template.}.

     As a first example, suppose we have
\begin{verbatim}
  PROCESSORS P1 (4)
  TEMPLATE T1 (17)
\end{verbatim}
There are various ways in which \verb$T1$ may be distributed over
\verb$P1$.  The four basic distribution formats are illustrated in figure
\ref{1d-distribution}.
\begin{figure}[hbtp]
\centerline{\psfig{figure=block.ps,height=1.5in}}
\vspace{0.2in}
\centerline{\psfig{figure=cyclic.ps,height=1.5in}}
\vspace{0.2in}
\centerline{\psfig{figure=block-block.ps,height=1.5in}}
\vspace{0.2in}
\centerline{\psfig{figure=block-cyclic.ps,height=1.5in}}
\caption{\label{1d-distribution}The four basic formats of
template distribution}
\end{figure}
In the figure, each template element inhabits a particular memory
area.  This should be taken to mean that any data element aligned with
a particular template element will be stored in the associated memory
area (the template itself doesn't occupy any memory, of course).

     Simple block distribution is specified by
\begin{verbatim}
  DISTRIBUTE T1(BLOCK) ONTO P1
\end{verbatim}
In this case, each processor gets a contiguous block of template
elements.  All processor get the same sized block, unless the number
of processors doesn't divide the number of template elements, in
which case the template elements are divided as evenly as possible
(with the last processor holding fewer than the others, as illustrated).

     Simple cyclic distribution is specified by
\begin{verbatim}
  DISTRIBUTE T1(CYCLIC) ONTO P1
\end{verbatim}
The first processor gets the first template element, the second
gets the second, and so on.  When the set of processors is
exhausted, go back to the first processor, and continue allocating
the template elements from there.

     In a variant of the block distribution, the number of
template elements allocated to each processor can be explicitly
specified, as in
\begin{verbatim}
  DISTRIBUTE T1 (BLOCK (6)) ONTO P1
\end{verbatim}
If this means that we allocate all template elements before
exhausting processors, some processors are left empty.  It
is {\em illegal} with to choose a block size here which
cause template elements to be left over after all processors
have had their blocks allocated.  But in an analogous variant
of the cyclic distribution (``block-cyclic distribution'')
\begin{verbatim}
  DISTRIBUTE T1 (BLOCK (3)) ONTO P1
\end{verbatim}
the product of the number of processors with the block size can be
smaller than the template size, and allocation wraps round after the
first assignment of blocks to all processors.

     That covers the case where both template and processor are one
dimensional.  When the template both have (the same) higher dimension,
each dimension can be distributed independently, mixing any of the four
distribution formats.  The correspondence between the template and the
processor dimension is the obvious one.  In
\begin{verbatim}
  PROCESSORS P2 (4, 3)
  TEMPLATE T2 (17, 20)
  DISTRIBUTE T2 (CYCLIC, BLOCK) ONTO P2
\end{verbatim}
the first dimension of \verb$T2$ is distributed cyclically over
the first dimension of \verb$P2$; the second dimension is
distributed blockwise over the second dimension of \verb$P2$.

     Finally, some dimensions of a template may have ``collapsed
distributions'', allowing a template to be distributed onto a processor
arrangement with fewer dimensions than the template.  So
\begin{verbatim}
  DISTRIBUTE T2 (BLOCK, *) ONTO P1
\end{verbatim}
means that the first dimension of \verb$T2$ will be distributed over
\verb$P1$ as was \verb$T1$ in the first example above.  But for a fixed
value of the first index of \verb$T2$, all values of the second
subscript are mapped to the same processor.

\subsection{\label{alignment}Data alignment}

     Some apologies are in order, for asking the reader to accept the
idea of template distribution before giving any concrete examples of
template usage.  This we proceed to do.

     Data is aligned to templates through the ALIGN directive.
Before describing this directive, we return to one of the
parallel examples given in section \ref{examples}, for motivation.
The core of the LU decomposition subroutine, around which the
linear solver example was written, looks like this:
\begin{verbatim}
  REAL A (N, N)
  INTEGER N, R, R1
  REAL, DIMENSION (SIZE (A, 1)) :: L_COL, U_ROW

  DO R = 1, N - 1
    R1 = R + 1
    L_COL (R  : ) = A (R : , R)
    A (R , R1 : ) = A (R, R1 : ) / L_COL (R)
    U_ROW (R1 : ) = A (R, R1 : )
    FORALL (I = R1 : N, J = R1 : N)
      A (I, J) = A (I, J) - L_COL (I) * U_ROW (J)
    ENDFORALL
  ENDDO
\end{verbatim}
For simplicity, pivotting has been omitted here (pivotting improves the
numerical stability of the algorithm, but the algorithm remains
logically correct without it).  The assignment to \verb$U_ROW$ has
been rearranged slightly (for reasons which will be explained later).
The final assignment to \verb$A$ has been changed to use a \verb$FORALL$
construct; the more opaque pure Fortran 90 version given
earlier used simple array assignments and the intrinsic function
\verb$SPREAD$.

     A cursory inspection of this algorithm should suggest that
a possible choice of template for the problem is
\begin{verbatim}
  TEMPLATE T (N, N)
\end{verbatim}
This template exactly matches the main data structure of the problem,
namely, the array \verb$A$ which holds the matrix.  To align \verb$A$
to \verb$T$ we can add an \verb$ALIGN$ attribute declaration for
\verb$A$ as follows
\begin{verbatim}
  ALIGN A (I, J) WITH T (I, J)
\end{verbatim}
In this context \verb$I$ and \verb$J$ act as {\em alignment dummies}.
An alignment dummy is a named integer variable appearing as a subscript
of the ``alignee'' (the array which is to be aligned) in an
\verb$ALIGN$ directives.  The idea is that the variable ranges over all
possible index values associated with the array dimension involved.
The ``align target'' (in this case the template \verb$T$) can have
expressions involving the alignment dummies amongst its subscripts.  In this
way, every element of the alignee is mapped to some element of the
template.

     In the example given above the mapping is very straightforward:
it is the ``identity mapping'' between array and template.
Much more general alignment relations are possible.  We will illustrate
a few, before returning to the main example above.

     For one thing, indices can be permuted:
\begin{verbatim}
  DIMENSION B (N, N)
  ALIGN B (I, J) WITH T (J, I)
\end{verbatim}
maps \verb$B$ to \verb$T$, but in a ``transposed'' manner: \verb$B (1, 2)$
is mapped to \verb$T (2, 1)$, etc.  More generally, a subscript of
an {\em align target} (not an alignee) can be a linear expression
in {\em one} of the alignment dummies (with integer expression coefficients).
For example
\begin{verbatim}
  DIMENSION C (N / 2, N / 2)
  ALIGN C (I, J) WITH T (N / 2 + I, 2 * J)
\end{verbatim}
Figure \ref{alignment-example} illustrates how \verb$C$ would be
aligned to \verb$T$.
\begin{figure}[hbtp]
\centerline{\psfig{figure=alignment-example.ps,height=2.5in}}
\caption{\label{alignment-example}Example alignment of the array {\bf C}
to the template {\bf T}}
\end{figure}

     The rank of alignee and align-target do not have to match.  A
dimension of the alignee may be ``collapsed''; or some dimension of the
align-target might be a constant---for example a scalar might be
aligned to the first element of a one-dimensional template; or the
alignee may be ``replicated'' over some dimensions of the template.  As
an example of collapsing:
\begin{verbatim}
  DIMENSION D (N, N, N)
  ALIGN D (I, J, K) WITH T (I, J)
\end{verbatim}
The template element is independent of \verb$K$.  This means that
for fixed \verb$I$, \verb$J$, all elements of \verb$C$ differing only
in their third index mapped to the same template element.
Replication of array elements will be illustrated in the
LU example below.

     Before returning to that example, some general remarks on
alignment.  Firstly, restrictions on alignment: as mentioned, the
expressions used to subscript a template must be linear in the alignment
dummies, with integer coefficients; each subscript can depend on at
most {\em one} of the alignment dummies (local to the \verb$ALIGN$
directive); and each alignment dummy can appear in at most {\em
one} of the subscript expressions for the template.  Secondly, we should
say that there are various shorthand forms of the alignment directive
which were not described here---they don't add any new facilities.

     Returning to the main example, how should the other arrays
in the program, \verb$L_COL$ and \verb$U_ROW$ be mapped?
Most of the work in a single iteration is in the statement
\begin{verbatim}
      A (I, J) = A (I, J) - L_COL (I) * U_ROW (J)
\end{verbatim}
We can minimise (indeed, eliminate) the need for communication
in this assignment if \verb$L_COL (I)$ is stored wherever
\verb$A (I, J)$, for any \verb$J$ is stored, and if
\verb$U_ROW (J)$ is stored wherever \verb$A (I, J)$ for any \verb$J$
is stored.  This can be specified by using a replicated
alignment to the template \verb$T$:
\begin{verbatim}
  ALIGN L_COL (I) WITH T (I, *)
  ALIGN U_ROW (J) WITH T (*, J)
\end{verbatim}
where an asterisk as a template subscript means that data is
replicated in the corresponding processor
dimension\footnote{We specified {\em processor} dimension
here, because it would be pointless to keep many copies of the data on
a {\em single} processor, just because of a replicated alignment to a
template dimension which had several index values mapped to the
processor.}.  Figure \ref{row-col-alignment} is an attempt to
visualise the alignment of the three arrays and the template.
\begin{figure}[hbtp]
\centerline{\psfig{figure=replicated-example.ps,height=2.5in}}
\caption{\label{row-col-alignment}Alignment of the three arrays
in the LU decomposition example}
\end{figure}

    As claimed, the main assignment in the \verb$FORALL$
construct will require no communications, because all operands
of each elemental assignment will be stored on the same processor.
What about the other statements?
\begin{verbatim}
  A (R , R1 : ) = A (R, R1 : ) / L_COL (R)
\end{verbatim}
requires no communication.  It is equivalent to
\begin{verbatim}
  FORALL (J = R1 : N)
    A (R, J) = A (R, J) / L_COL (R)
  ENDFORALL
\end{verbatim}
and we know that \verb$L_COL (R)$ will be stored on any processor
where \verb$A (R, J)$ is stored.

     The other two array assignments {\em do} require communication.
For example, the assignment to \verb$L_COL$ is equivalent to
\begin{verbatim}
  FORALL (I = R : N)
    L_COL (I) = A (I, R)
  ENDFORALL
\end{verbatim}
Because \verb$L_COL (I)$ is replicated in the ``$J$'' direction
(as it has been consistently named above), whereas \verb$A (I, R)$
is held only on the processor holding the $J = R$ template element,
updating the \verb$L_COL$ element involves broadcasting the
\verb$A$ element to all interested parties.  These communications
the compiler will duly insert.  Similarly, the \verb$U_ROW$ assignment
involves broadcasts, this time in the ``$I$'' direction.

    In the original Fortran 90 program the assignments to \verb$U_ROW$
and \verb$A (R, :)$ were done by
\begin{verbatim}
  U_ROW (R1 : ) = A (R, R1 : ) / L_COL (R)
  A (R , R1 : ) = U_ROW (R1 : )
\end{verbatim}
The first assignment is equivalent to
\begin{verbatim}
  FORALL (J = R1 : N)
    U_ROW (J) = A (R, J) / L_COL (R)
  ENDFORALL
\end{verbatim}
The problem here is that there are two strategies available to the
compiler.  It could allocate the computation on the RHS to the processor
holding template element \verb$T (R, J)$ then broadcast the result in
the $I$ direction to assign to \verb$U_ROW (J)$.  This would reproduce
the communication and computation pattern described above.
Unfortunately, the compiler might alternatively broadcast \verb$A (R,
J)$ and \verb$L_COL (R)$ in the $I$ direction, {\em then} repeat the
computation on every processor holding a copy of \verb$U_ROW$.  This is
clearly a bad strategy, because it doubles the amount of communication,
and unnecessarily introduces repeated computation.  On would hope that
a clever compiler wouldn't make this choice.  But compilers aren't
always clever\footnote{The second strategy would be the one adopted by
a system blindly following the celebrated ``owner-computes''
heuristic.}.  In situations like this it is probably wise to arrange
assignments to {\em force} the compiler to do computations in
sensible places, as the HPF version does.

    Finally, we should comment on the distribution of the scalar
``control'' variables \verb$N$, \verb$R$, \verb$R1$.  These really want
to be replicated across all processors.  Because they are typically
assigned in terms of globally replicated values, updating requires no
communication.  This is a case where we {\em can} tolerate replicated
computation, because the assignments only happen occasionally.  (One
can see that it might difficult for a compiler to automatically
recognise this fact, though).  Although the HPF standard doesn't
explicitly make the guarantee, a reasonable expectation is that
(scalar) variables which don't have explicit mapping directives will be
replicated globally.  So we won't give an explicit mapping for these
variables.

     Having chosen a plausible alignment of our arrays to a template,
we have to distribute that template.  \verb$BLOCK$ distribution
isn't particularly attractive for this computation, because successive
iterations work on a shrinking area of the template.  A block
distribution could leave whole processors idle in later iterations.
A \verb$CYCLIC$ distribution will achieve better load balancing (figure
\ref{lu-distribution}).
\begin{figure}[hbtp]
\centerline{\psfig{figure=block-example.ps,height=2.5in}}
\vspace{0.4in}
\centerline{\psfig{figure=cyclic-example.ps,height=2.5in}}
\caption{\label{lu-distribution}{\bf A} elements involved (shaded) in iteration
{\bf R}=4, when {\bf N}=6 and processor arrangement is 3 by 3.
Block and cyclic distributions are illustrated.}
\end{figure}
     Our final HPF program, distributed onto an \verb$M$ by \verb$M$
processor arrangement, is
\begin{verbatim}
  INTEGER M, N, R, R1

  PROCESSORS P (M, M)

  TEMPLATE T (N, N)
  DISTRIBUTE T (CYCLIC, CYCLIC) ONTO P

  REAL A (N, N)
  ALIGN A (I, J) WITH T (I, J)

  REAL, DIMENSION (SIZE (A, 1)) :: L_COL, U_ROW
  ALIGN L_COL (I) WITH T (I, *)
  ALIGN U_ROW (J) WITH T (*, J)

  DO R = 1, N - 1
    R1 = R + 1
    L_COL (R  : ) = A (R : , R)
    A (R , R1 : ) = A (R, R1 : ) / L_COL (R)
    U_ROW (R1 : ) = A (R, R1 : )
    FORALL (I = R1 : N, J = R1 : N)
      A (I, J) = A (I, J) - L_COL (I) * U_ROW (J)
    ENDFORALL
  ENDDO
\end{verbatim}

\subsection{\label{anonymous}Indirect alignments and implicit templates}

     The alignments described so far were all direct alignments
to templates.  It is also allowed to align an array to another
array, using all the normal syntax of the \verb$ALIGN$ directive.
So the alignments of \verb$L_COL$ and \verb$U_ROW$ in the example
of the previous section could be written as
\begin{verbatim}
  ALIGN L_COL (I) WITH A (I, *)
  ALIGN U_ROW (J) WITH A (*, J)
\end{verbatim}
In general, the meaning is that the alignee element is stored
wherever the align-target array element is.  Any such alignment {\em
can} be written as an alignment to a template (provided the template is
in scope).  If there are several levels of indirection (array
aligned to array aligned to array, etc) writing the ``ultimate
alignment'' directly could be relatively complicated.

     Also, templates can be left completely implicit, with
DISTRIBUTE directives can applied directly to arrays.  So, in
the example, the \verb$T$ directives could be omitted, and we could
add the directive
\begin{verbatim}
  DISTRIBUTE A (CYCLIC, CYCLIC) ONTO P
\end{verbatim}
The implicit template has the same shape as the array distributed.
It is {\em not} allowed for any array to be both distributed in this way
{\em and} to appear as an alignee in an \verb$ALIGN$ directive.  So
this idiom can always be regarded as shorthand for introduction of an
explicit template.

     These conventions are particularly useful for procedure dummy
arguments, because templates can't be explicitly passed through the
subprogram interface, as we will see in the next section.

