
\section{\label{translation}Translation of ``Mapped'' HPF to Adhoc}

     This document is too short to spell out a detailed translation
scheme from HPF-like languages to Adhoc.  Instead, we attempt to
justify the claim that Adhoc is a viable target for HPF translation by
taking a series of fragments of HPF code and giving equivalent Adhoc
programs.

\subsection{Anatomy of a translator}

     First, a rough sketch of how a real translator might be
arranged.  Figure \ref{translator} illustrates a possible
organisation.
\begin{figure}[hbtp]
\centerline{\psfig{figure=translator.eps,height=0.6in}}
\caption{\label{translator}Schematic of an HPF to Adhoc translator}
\end{figure}
AST stands for Abstract Syntax Tree.  The figure looks like a textbook
model of a simple compiler, except for the insertion of the {\em
mapper} phase.

     The {\em front end} is responsible for syntactic and static
semantic analysis of the input HPF.  It typically outputs symbol table
information, containing descriptor records for the entities in the
source program.  This table is integrated with some abstract syntax
tree---a suitably reorganised parse tree, probably decorated with extra
information, such as the type of expression nodes.

     In our model this analysis is followed by ``expression mapping''.
The {\em mapper} takes the analysed program and decides how all
expression (and subexpression) nodes are to be mapped to the parallel
computer\footnote{We use the term ``expression'' more broadly than in
the Fortran definition---closer to the C idea of an expression.  It
includes procedure calls, assignments, forall constructs, read and
write statements, and so on.  ``Expression mapping'' covers all these
cases.}.  The programmer typically attributes the named variables in an
HPF program with some mapping.  But a compiler also has to generate
many expression temporaries.  The problem of where to store these
temporaries now arises---ie how they are mapped to the computer.  This
is directly related to the question of where individual computations
are performed.

     Mapping of expression temporaries is one of the most problematic
aspects of HPF translation.  In a real translator the the mapper would
decorate each expression node of the abstract syntax tree AST with a
mapping descriptor (in general two mapping descriptors---defining the
point where the expression is calculated, and the point where its value
is to be ``consumed'').  The updated program representation is labelled
AST$'$ in figure \ref{translator}.

     For the examples in this section we assume that a mapping has
already been chosen.  This mapping will typically be indicated roughly in
words.  The subsequent translation to Adhoc should make clear {\em
exactly} what mapping was intended.

     In a real translator, the logical equivalent of this
transliteration from mapped HPF to Adhoc is performed by the {\em code
generator} phase.

     A warning: many of the examples were deliberately contrived so
that they are difficult to translate.  For this reason the Adhoc
programs will often be quite long, and look terribly inefficient.  {\em
Simple} HPF programs generally translate to simple Adhoc, but we have
to live with the awkward fact that HPF can rather easily express many
operations which are extremely difficult to translate efficiently.


\subsection{Mapping of program variables}

\subsubsection*{Example 1}

\begin{verbatim}
       PROCESSORS P (4, 4)

       INTEGER a (16, 16)
  !HPF DISTRIBUTE a (BLOCK, BLOCK) ONTO p

       INTEGER b (8, 4)
  !HPF ALIGN b (i, j) WITH a (5 + j, 1 + 3 * i)

       INTEGER c
  !HPF ALIGN c WITH b (2, *)
\end{verbatim}
A translation where ranges are named\dots
\begin{verbatim}
  procs p(4, 4) ;
  dimension p_1(p.dim(1)) ;
  dimension p_2(p.dim(2)) ;

  range i_a(16 #blk p_1) ;
  range j_a(16 #blk p_2) ;
  array int a [i_a, j_a] ;
  
  range i_b(8 : base 5 : j_a) ;
  range j_b(4 : base 3 step 3 : i_a) ;
  array int b [i_b, j_b] ;

  array int c {2 : i_b} ;
\end{verbatim}
A completely equivalent translation which doesn't explicitly name
ranges\dots
\begin{verbatim}
  procs p(4, 4) ;

  array int a [16 #blk p.dim(1), 16 #blk p.dim(2)] ;
  
  array int b [8 : base 5 : a.rng(2),
               4 : base 3 step 3 : a.rng(1)] ;

  array int c {2 : b.rng(1)} ;
\end{verbatim}
All Adhoc index ranges start at 0, whereas in Fortran the default is
1.  Otherwise the 3 Adhoc arrays are in direct correspondence
with the HPF arrays.


\subsection{\label{dummies}Mapping of dummy arguments}

     The HPF procedure interface is fairly clunky.  There are three
kinds of mapping directives for a dummy argument
\begin{itemize}
\item Prescriptive
\item Descriptive
\item Transcriptive
\end{itemize}

     The exact distinction between the ``prescriptive'' and
``descriptive'' cases is not entirely clear cut.  The rough idea is that
a called procedure should be prepared to remap a prescriptively mapped
dummy argument on entry, to achieve the desired mapping; the actual
argument may have a different mapping.  On the other hand a procedure
is not required to remap a descriptively mapped dummy---either the
programmer or the compiler arranges that the actual arguments have the
stated mapping.

     It is expected, though, that if the interface of the procedure is
explicit in the calling program, the {\em caller} will perform the
remapping of a {\em prescriptively} mapped argument (on the grounds
that it has static information about the original mapping of the actual
argument expression, so can perform the remapping more efficiently).

     It is a {\em requirement} on the compiler that {\em if} the
interface of the procedure is explicit in the calling program, and a
{\em descriptive} directive appears for a dummy, the code generated for
the caller remaps the actual argument before the call, so that the
called procedure functions properly.

     Hence, when the interface is explicit (the normal situation, one
would hope, in a well-written Fortran 90 program) there is no
discernable difference between the effect of prescriptive and
descriptive mappings\footnote{\label{descRemap} In fact, the generated
code for the procedure may reverse the naive expectation.  Most
obviously a prescriptively mapped dummy may not require code to perform
remapping in the translated procedure, because the caller has already
done the remapping.  More subtly a descriptively mapped dummy might
actually need such code.  This could happen if, say, a descriptive
alignment directive was parameterised by a very complex specification
expression.  The compiler may decide that it is too expensive to take
the evaluation of this expression out of its natural context---in the
code for the declaration block of the called procedure---and place it
in the code of the caller (recall that a Fortran specification
expression can depend on attributes of locally declared variables, can
involve complex intrinsics, and so on).  The only way to meet the
requirements of the HPF specification in this case is if the implied
remapping of the actual argument expression is actually done in the
code for the called procedure (because the caller cannot calculate the
target mapping).}.

     Notice, in any case, that the dummy argument remapping behaviour
inside a given HPF procedure generally depends on whether or not the
caller has an explicit interface for the procedure.  To meet the
requirements of the HPF specification efficiently it may be necessary
to generate two different versions of the code for each procedure: one
called when the interface is explicit, and one called when it isn't.
We will work on this assumption below.

     The meaning of {\em transcriptive} directives is relatively
straightforward:  they leave the mapping (or aspects of the mapping)
unspecified in the called procedure.  The procedure must be compiled to
accept data with {\em any} legal HPF mapping, chosen by the calling
program.

     The following examples are taken from chapter 5 of the {\em High
Performance Fortran Handbook}.  We adopt the convention of prepending
and underscore to names of the translated functions versions called
when the interface is {\em not} explicit in the calling program, where
they differ from the version called when the interface is explicit.
Also an underscore is prepended to un-remapped dummy arguments passed
in to the functions.

\subsubsection*{Example 1}

\begin{verbatim}
      SUBROUTINE MINGO (M)
      REAL M (100, 100)
!HPF$ DISTRIBUTE M (BLOCK, BLOCK)
      ...
      END
\end{verbatim}
This is a very simple example of a prescriptive mapping.  First the
Adhoc version called when the interface is explicit in the calling
program:
\begin{verbatim}
  void mingo(array float m [100 #blk def2d_1, 100 #blk def2d_1])
    ...
  }
\end{verbatim}
The caller has already remapped \verb$m$ to the expected mapping, if
necessary\footnote{In reference to the comments in footnote
\ref{descRemap}, we can certainly rely on the caller to do that here,
since the mapping directive is so simple.}.  So no special code is
needed in the body of \verb$mingo$.  If the interface is {\em not}
explicit in the caller we have\footnote{If the Fortran argument had the
\verb$IN$ or \verb$OUT$ attribute one of the two \verb$remap$
operations could be omitted.}
\begin{verbatim}
  void _mingo(array float _m _ [100 :: _, 100 :: _]) {
    array float m [100 # def2d_1, 100 # def2d_2] ;
    remap(m, _m) ;
    ...
    remap(_m, m) ;
  }
\end{verbatim}
In these translations we suppose \verb$def2d$ is a default two
dimensional process array with dimensions \verb$def2d_1$ and
\verb$def2d_2$.  These identifiers are globally declared.

\subsubsection*{Example 2}

\begin{verbatim}
      SUBROUTINE RICKARD (R)
      REAL R (100, 100)
!HPF$ DISTRIBUTE * R (BLOCK, BLOCK)
      ...
      END
\end{verbatim}
The mapping is descriptive.  In this case only one translation is
needed
\begin{verbatim}
  void rickard(array float r [100 #blk def2d_1,
                              100 #blk def2d_2])
    ...
  }
\end{verbatim}
This is called whether or not the interface is explicit.  If it isn't,
and the actual argument doesn't have the expected mapping, the program
will probably fail (it is illegal Adhoc).  That's fine, because the HPF
program was erroneous.


\subsubsection*{Example 3}

\begin{verbatim}
      SUBROUTINE JAFFEE (J)
      REAL J (100, 100)
!HPF$ DISTRIBUTE J * ONTO *
!HPF$ INHERIT J
      ...
      END
\end{verbatim}
This is a transcriptive mapping.  Again, only one translation is
needed
\begin{verbatim}
  void jaffee(array float j _ [100 :: _, 100 :: _]) {
    ...
  }
\end{verbatim}

\subsubsection*{Example 4}

\begin{verbatim}
      SUBROUTINE MELVIN (AXOLOTL, POIUYT)
      REAL AXOLOTL ( : , : ), POIUYT ( : , : )
!HPF$ INHERIT, DISTRIBUTE * (BLOCK, BLOCK) :: AXOLOTL
!HPF$ ALIGN POIUYTT ( : , : ) WITH * AXOLOTL ( : , : )
      ...
      END
\end{verbatim}
The translation is
\begin{verbatim}
  void melvin(
      array float axolotl [_ : _ #blk def2d_1,
                           _ : _ #blk def2d_2],
      array float poiuytt [axolotl.rng(1), axolotl.rng(2)]) {
    ...
  }
\end{verbatim}
The Adhoc makes explicit a (particularly ugly) feature of HPF.  The
\verb$INHERIT$ attribute means that the \verb$DISTRIBUTE$ directive
applies to the {\em template} of \verb$AXOLOTL$, so the ranges
of \verb$axolotl$ are {\em derived} ranges.  If the HPF mapping of
\verb$axolotl$ had been just
\begin{verbatim}
!HPF$ DISTRIBUTE * (BLOCK, BLOCK) :: AXOLOTL
\end{verbatim}
without \verb$INHERIT$, the more restricted (and therefore
more contentful) Adhoc translation 
\begin{verbatim}
  void melvin(array float axolotl [_ #blk def2d_1, _ #blk def2d_2],
              ...) {
    ...
  }
\end{verbatim}
would be valid.  Notice that a descriptive \verb$DISTRIBUTE$
directive can only be used in conjunction with an \verb$INHERIT$
directive {\em if} the dimensions of the argument are in direct one to
one correspondence with the dimensions of its template.  If in fact
\verb$AXOLOTL$ was aligned to one-dimensional template, say, or to a
two-dimensional template with dimensions transposed---both perfectly
acceptable HPF mappings---then HPF provides no means of presenting the
extra distribution information to the compiler.  In contrast Adhoc
would permit something like
\begin{verbatim}
  void melvin(
      array float axolotl [_ : _ #blk def1d_1, _ : _ #* _],
      ...) {
    ...
  }
\end{verbatim}
or
\begin{verbatim}
  void melvin(
      array float axolotl [_ : _ # def2d_2, _ : _ # def2d_1],
      ...) {
    ...
  }
\end{verbatim}
to represent such cases.  In the first case we suppose \verb$def1d$ is
a globally declared default one-dimensional process array, with
distributed dimension \verb$def1d_1$.

    If the alignment of \verb$POIUYTT$ is replaced by
\begin{verbatim}
!HPF$ ALIGN POIUYTT (I, J) WITH * AXOLOTL (I, J)
\end{verbatim}
(in which case \verb$POIUYTT$ may be a different shape to
\verb$AXOLOTL$---aligned to its lower corner) the translation is
changed to
\begin{verbatim}
  void melvin(
      ...
      array float poiuytt [_ :: axolotl.rng(1),
                           _ :: axolotl.rng(2)]) {
    ...
  }
\end{verbatim}


\subsubsection*{Example 5 (p150)}

\begin{verbatim}
      REAL DOUGH (100)
!HPF$ DISTRIBUTE DOUGH (BLOCK (10))
      CALL PROBATE (DOUGH (7 : 23 : 2))
      ...
      SUBROUTINE PROBATE (BREAD)
      REAL BREAD (9)
!HPF$ INHERIT BREAD
\end{verbatim}
Translates to
\begin{verbatim}
  array float dough [100 #blk(10) def1d_1] ;
  probate(dough [9 : base 6 step 2]) ;
  ...
  void probate(array float bread _ [9 :: _]) {
    ...
\end{verbatim}
The fact that Adhoc range indices start at zero, and triplets are
defined by extent rather than upper bound, introduces some differences
from the HPF.


\subsubsection*{Example 6 (p152)}

\begin{verbatim}
      LOGICAL FRUG (128), TWIST (128)
!HPF$ PROCESSORS DANCE_FLOOR (16)
!HPF$ DISTRIBUTE (BLOCK) ONTO DANCE_FLOOR :: FRUG, TWIST
      CALL TERPSICHORE (FRUG (1 : 40 : 3), TWIST (1 : 40 : 3))

      SUBROUTINE TERPSICHORE (FOXTROT, TANGO)
      LOGICAL FOXTROT ( : ), TANGO ( : )
!HPF$ INHERIT TANGO
\end{verbatim}
No mapping directive is given for \verb$FOXTROT$.  We choose to
collapse it\footnote{Not a very intelligent choice one might think,
but one a compiler might make by default.}.
If the interface is not explicit, the translation is
\begin{verbatim}
  procs dance_floor(16) ;
  range i_frug(128 #blk dance_floor.dim(1)) ;
  array int frug [i_frug] ;
  array int twist [i_frug] ;
  _terpsichore(frug [13 : step 3], twist [13 : step 3]) ;

  void _terpsichore(array int _foxtrot _ [_],
                    array int tango _ [_]) {
    dimension def0d_1 of def0d ;
    array int foxtrot [_foxtrot.rng(1).size() #* def0d_1] ;
    remap(foxtrot, _foxtrot) ;
    ...
    remap(_foxtrot, foxtrot) ;
  }
\end{verbatim}
If the interface {\em is} explicit, a likely translation would be
\begin{verbatim}
  procs dance_floor(16) ;
  range i_frug(128 #blk dance_floor.dim(1)) ;
  array int frug [i_frug] ;
  array int twist [i_frug] ;
  {
    dimension def0d_1 of def0d ;
    array int temp1 [13 #* def0d_1] ;
    range i_temp2(13 : step 3 : i_frug) ;
    remap(temp1, frug [i_temp2]) ;
    terpsichore(temp1, twist [i_temp2]) ;
    remap(frug [i_temp2], temp1) ;
  }

  void terpsichore(array int foxtrot [_ #* _],
                   array int tango _ [_]) {
    ...
  }
\end{verbatim}

     An alternative in the present case is to translate \verb$foxtrot$
as a normal C array (a ``simple variable'', so far as Adhoc is
concerned):
\begin{verbatim}
  procs dance_floor(16) ;
  range i_frug(128 # dance_floor.dim(1)) ;
  array int frug [i_frug] ;
  array int twist [i_frug] ;
  {
    int temp1 [13] ;
    range i_temp2(13 : step 3 : i_frug) ;
    broadcast(temp1, frug [i_temp2]) ;
    terpsichore(temp1, twist [i_temp2]) ;
    where(i_temp2)
      frug = temp1 [i_temp2] ;
  }

  void terpsichore(int foxtrot [], array int tango _ [_]) {
    ...
  }
\end{verbatim}

\subsubsection*{Example 6$'$ (p154)}

\begin{verbatim}
      SUBROUTINE TERPSICHORE (FOXTROT, TANGO)
      LOGICAL FOXTROT ( : ), TANGO ( : )
!HPF$ INHERIT TANGO
!HPF$ PROCESSORS DANCE_FLOOR (16)
!HPF$ TEMPLATE, DISTRIBUTE (BLOCK) ONTO DANCE_FLOOR :: GURF (128)
!HPF$ ALIGN FOXTROT (J) WITH * GURF (3 * J + 2)
\end{verbatim}

      Most of the same information concerning the distribution of
\verb$FOXTROT$ can be expressed in Adhoc through
\begin{verbatim}
  void terpsichore(
      array int foxtrot [_ : base 2 step 3 : 128 #blk _],
      array int tango _ [_]) {
    ...
  }
\end{verbatim}
The only static information which the Adhoc translation fails to
capture is the shape, \verb$(16)$, of the processor arrangement (or
process array).

\subsubsection*{Example 7 (p155)}

\begin{verbatim}
      REAL TROGGS (1024, 473)
!HPF$ DISTRIBUTE TROGGS (BLOCK, *)
      DO J = 1, 473
        CALL WILD_THING (TROGGS ( : , J))
      END DO
      ...

      SUBROUTINE WILD_THING (GROOVY)
      REAL GROOVY ( : )
!HPF$ DISTRIBUTE GROOVY * (BLOCK) ONTO *
      ...
\end{verbatim}
The translation is
\begin{verbatim}
  dimension def1d_2 of def1d ;
  array float troggs [1024 #blk def1d_1, 473 #* def1d_2] ;
  for (j = 0; j < 473 ; j++)
    wild_thing(troggs [ : , j]) ;
  ...

  void wild_thing(array float groovy [_ #blk def1d_2])
  ...
\end{verbatim}
This translation relies on the fact that subscripting the second
dimension of \verb$troggs$ yields a null embedding.

\subsubsection*{Example 8 (p156)}

\begin{verbatim}
      SUBROUTINE NICHOLAS (TSAR, CZAR)
      REAL, DIMENSION (1918) :: TSAR, CZAR
!HPF$ INHERIT :: TSAR
!HPF$ ALIGN WITH TSAR :: CZAR
      ...
\end{verbatim}
Translation\dots
\begin{verbatim}
  void nicholas(array float tsar _ [1918 :: _],
                array float czar tsar.emb() [tsar.rng(1)]) {
    ...
\end{verbatim}

\subsubsection*{Example 9 (p156)}

\begin{verbatim}
      SUBROUTINE GRUNGE (PLUNGE, SPONGE)
      REAL, DIMENSION (1000) :: PLUNGE SPONGE
!HPF$ ALIGN PLUNGE WITH * SPONGE
      ...

      REAL FIJI (5000), SQUEEGEE (2000)
!HPF$ ALIGN SQUEEGEE (K) WITH FIJI (2 * K)
      CALL GRUNGE (FIJI (2002 : 4000 : 2), SQUEEGEE (1001 : ))
      ...
\end{verbatim}
To make things half-interesting, assume that \verb$SPONGE$ has the
\verb$INHERIT$ attribute (otherwise a legitimate translation would be
to turn \verb$SPONGE$ into a ``collapsed'' array, say).
\begin{verbatim}
  void grunge(array float plunge _ [1000 :: _],
              array float sponge plunge.emb() [plunge.rng(1)]) {
    ...

  array float 
     squeegee fiji.emb() [2000 : base 1 step 2 : fiji.rng(1)] ;
  grunge(fiji [1000 : base 2001 step 2],
                             squeegee [1000 : base 1000]) ;
  ...
\end{verbatim}


\subsubsection*{\label{embedUnion}Example 10}

(This is the only example in this section not taken from HPFH)
\begin{verbatim}
      SUBROUTINE FOO (A, B)
      REAL A ( : , : )
!HPF$ INHERIT A
      INTEGER B (SIZE (A, 1))
!HPF$ ALIGN B WITH A ( : , 1)
      ...
      END
\end{verbatim}
The interesting feature is embedded alignment to an argument with
inheritted mapping.  The translation is
\begin{verbatim}
  void foo(array float a _ [_, _], 
           array int b (a.emb() \/ (0 : a.rng(2))) [a.rng(1)]) {
    ...
  }
\end{verbatim}


\subsection{Executable Statements}

     Most of the examples so far concentrated on translation of
declarations.  The ``mapping problem'' arose occasionally when the HPF
examples did not specify mappings for particular program variables;
but, regarding that as an oversight on the part of the programmer, we
justifiably took the trivial default, ``collapsed'' mapping for such
arrays.

     Executable statements typically involve compiler-generated
temporaries, for which the programmer {\em cannot} define a mapping.
In this case the compilation system must be responsible for defining
mappings.  As admitted earlier, we will not try to define any
systematic way of choosing temporary mappings in this document.  We
will just make some intuitively sensible choice, and display the Adhoc
code which would result.

\subsubsection*{Example 1}

\begin{verbatim}
      SUBROUTINE COPY (U, V)
      INTEGER U ( : )
!HPF$ INHERIT U
      INTEGER V (SIZE (U))
!HPF$ ALIGN V WITH U
      ...
      END

      FUNCTION FOO (N)
      INTEGER N
      INTEGER FOO (N)
!HPF$ DISTRIBUTE F (CYCLIC)
      ...
      END

      INTEGER A (10)
!HPF$ DISTRIBUTE A (BLOCK)
      ...
      CALL COPY (A, FOO (10))
\end{verbatim}
In this case a single remapping operation is required\dots
\begin{verbatim}
  void copy(array int u _ [_], array int v u.emb() [u.rng(1)]) {
    ...
  }

  void foo(int n, array int foo_res [n #cyc def1d_1]) {
    ...
  }

  array int a [10 #blk def1d_1] ;
  ...
  {
    array int temp1 [10 #cyc def1d_1] ;
    foo(10, temp1) ;
    array int temp2 [10 #blk def1d_1] ;
    remap(temp2, temp1) ;
    copy(a, temp2) ;
  }
\end{verbatim}
The given translation assumes that the interfaces of the procedures was
explicit in the calling program (note that Fortran {\em requires} the
interface of an array-valued function like \verb$foo$ to be explicit).

     Adhoc doesn't have \verb$array$-valued functions, so \verb$foo$ is
rendered as a two-parameter procedure, returning its result in the
second parameter.  The calling program defines a temporary to hold the
result, and a second temporary to hold the remapped value of this
result.  The interface of \verb$foo$ defines the size of the result, so
both temporaries can be automatic arrays.

     In this example the mapping of the temporaries was rather
obvious---essentially uniquely defined by the procedure interfaces.

\subsubsection*{Example 2}

\begin{verbatim}
      INTEGER FUNCTION SUM (U)
      INTEGER U ( : )
!HPF$ INHERIT U
      ...
      END

      INTEGER A (10, 10)
!HPF$ DISTRIBUTE A (BLOCK, BLOCK)
      INTEGER V (5)
!HPF$ DISTRIBUTE V (BLOCK)
      INTEGER X
      ...
      X = SUM (A (3, 2 : F (X) : 2) + V (2 : G (X)))
\end{verbatim}
Here \verb$F$ and \verb$G$ are some user-defined functions (which must
return related values, if the two array sections are to conform).

     In this case there is no obviously preferred mapping for array
temporaries.  We will assume that the argument of \verb$SUM$ is aligned
with the first array section (although alignment with the second array
section might be more intelligent).
\begin{verbatim}
  int sum(array int u _ [_]) {
    ...
  }

  array int a [10 #blk def2d_1, 10 #blk def2d_2] ;
  array int v [5 #blk def1d_1] ;
  int x ;
  ...
  {
    embed e_t1(4 : a.rng(1)) ;
    range i_t1(f(x) - 1 : base 1 step 2 : a.rng(2)) ;
    array int temp1 {e_t1} [i_t1] ;
    remap(temp1, v [g(x) - 1 : base 1]) ;
    at({e_t1})
      where(i_t1)
        temp1 += a ;
    x = sum(temp1) ;
  }
\end{verbatim}
We sensibly recycled \verb$temp1$---it was used both to hold the
remapped data from \verb$v$ and the sums of elements of \verb$a$ and
\verb$b$\footnote{Whether a compiler would be smart enough to do that
is another question.  It might allocate two temporary arrays.}.

\subsubsection*{Example 3}

\begin{verbatim}
      INTEGER A (100, 20)
!HPF$ DISTRIBUTE A (BLOCK, BLOCK) ONTO P
      INTEGER B (10, 10)
!HPF$ DISTRIBUTE B (BLOCK, BLOCK) ONTO Q
      ...
      FORALL (X = 1 : 10, Y = 1 : 10, Z = 1 : 20)
        A (10 * (X - 1) + Y, Z) = B (X, Y) + F (Y, Z)
      END FORALL
\end{verbatim}
Here \verb$F$ is some \verb$PURE$ function.

     First we give a naive translation.  Assume that throughout the
statement the forall index \verb$X$ is aligned with the first range of
\verb$B$, \verb$Y$ is aligned to the second dimension, and \verb$Z$ is
a collapsed range.  A straightforward translation is
\begin{verbatim}
  array int a [100 #blk p_1, 10 #blk p_2] ;
  array int b [10 #blk q_1, 10 #blk q_2] ;
  ...
  {
    range x_t1(b.rng(1)) ;
    range y_t1(b.rng(2)) ;
    dimension q_3 of q ;
    range z_t1 (20 #* q_3) ;
    array int temp1 [x_t1, y_t1, z_t1] ;

    // temp1 [x, y, z] = b [x, y] + f(y + 1, z + 1)
    where(x_t1)
      where(y_t1)
        where(z_t1)
          temp1 = b + f(y_t1 + 1, z_t1 + 1) ;

    array int temp2 [x_t1, y_t1] ;

    // temp2 [x, y] = 10 * x + y
    where(x_t1)
      where(y_t1)
        temp2 = 10 * x_t1 + y_t1

    // a [10 * x + y, z] = temp1 [x, y, z]
    scatter(temp1, a, temp2, z_t1) ;
  }
\end{verbatim}
The translation is divided into calculation of the RHS of the
assignment, storing the result in \verb$temp1$, followed by scattering
the values into the array \verb$a$ on the LHS.

     We will discuss a few optimisations which could be made to the
calculation of \verb$temp1$.  The worst feature of the naive
translation is that it redundantly calculates the expression
\verb$f(y + 1, z + 1)$ for every value of \verb$x$.  That can easily be
cured by rearranging the loops calculating of \verb$temp1$ as follows
\begin{verbatim}
  where(y_t1)
    where(z_t1) {
      int temp2 = f(y_t1 + 1, z_t1 + 1) ;
      where(x_t1)
        temp1 = b + temp2 ;
    }
\end{verbatim}
We should also worry about the sequentialisation implicit in performing
the \verb$f$ calculation over the collapsed range \verb$z_t1$.  There
is a ``spare'' process dimension \verb$q_1$ available\footnote{As the
translation stands, although the function call is no longer calculated
redundantly for {\em every} value of \verb$x$, it is still calculated
redundantly on every process in the associated \verb$q$\_\verb$1$ dimension,
because the expression is implicitly replicated in this dimension.}.
Unless evaluation of \verb$f$ is known to be very cheap, it would
probably be better to distribute its calculation over this dimension,
and remap the results afterwards.  That leads to the more complex code
\begin{verbatim}
  {
    array int temp2 [y_t1, z_t1] ;

    // temp2 [y, z] = f(y + 1, z + 1)
    where(y_t1) {
      range z_t3(20 #blk q_1) ;
      array int temp3 [z_t3] ;

      // temp3 [z] = f (y + 1, z + 1)
      where(z_t3)
        temp3 = f(y_t1 + 1, z_t3 + 1) ;

      remap(temp2, temp3) ;
    }

    // temp1 [x, y, z] = b [x, y] + temp2 [y, z]
    where(y_t1)
      where(z_t1)
        where(x_t1)
          temp1 = b + temp2 ;
  }
\end{verbatim}
It took a certain amount of intelligence to decide that this
transformation would be a good idea.  In our overall scheme of things,
this intelligence is encapsulated in the mapping phase.


\subsubsection*{Example 4}

\begin{verbatim}
      PURE FUNCTION FOO (N)
      INTEGER N
      INTEGER FOO (F (N))
      ...
      END

      INTEGER A (10, 10)
!HPF$ DISTRIBUTE A (BLOCK, BLOCK) ONTO P
      INTEGER B (10)
!HPF$ DISTRIBUTE B (BLOCK) ONTO Q
      ...
      FORALL (X = 1 : 10)
        A (X, 1 : F (X)) = B (FOO (X))
      END
\end{verbatim}
\verb$F$ is supposed to be some complicated function\footnote{The
program isn't strictly legal Fortran 90, because the declaration of
\verb$FOO$ includes a call to a user-defined function.  Other very
complex ``specification expressions'' are allowed, though; to make a
correct program replace the \verb$F$ calls by some such expression.}.
A possible translation is
\begin{verbatim}
  void foo(int n, dimension d, alloc int foo_res [_ #* d]) {
    foo_res <- new array int [f(n) #* d] ;
    ...
  }

  array int a [10 #blk p_1, 10 #blk p_2] ;
  array int b [10 #blk q_1] ;
  ...
  {
    range x_t1(b.rng(1)) ;
    dimension q_2 of q ;
    array int temp1 [x_t1] [_ #* q_2] ;

    // temp1 [x] [i] = b [foo(x) [i]]
    {
      array int temp2 [x_t1] [_ #* q_2] ;

      // temp2 [x] [i] = foo(x) [i]
      where(x_t1)
        foo(x_t1 + 1, q_2, temp2) ;

      // temp1 [x] [i] = b [temp2 [x] [i]]
      gather(temp1, b, temp2) ;

      where(x_t1)
        delete temp2 ;
    }

    array int temp2 [x_t1] [_ #* q_2] ;

    // temp2 [x] [i] = i
    where(x_t1)
      temp2 <- new range(f(x_t1 + 1) #* q_2) ;

    // a [x, temp2 [x] [i]] = temp1 [x] [i]
    scatter(temp1, a, x_t1, temp2) ;

    where(x_t1)
      delete temp2 ;

    where(x_t1)
      delete temp1 ;
  }
\end{verbatim}
The temporaries are all distributed over the process array of \verb$b$
in this translation (but, again, other choices of mapping would be
equally plausible).  Again, the translation falls broadly into the
evaluation of the RHS in \verb$temp1$, followed by scattering of
results.  \verb$temp1$ and \verb$temp2$ ({em both} \verb$temp2$s) are
non-Cartesian arrays.  Notice that it was necessary to explicitly pass
the process dimension \verb$q_2$ into the function \verb$foo$; mapping
inquiry functions can't be applied to unallocated arrays!  The
subscript array \verb$temp2$ are allocated as a range---recall that a
range can be used to stand for an array with values $0,\ldots$, which
is what is needed here.  The elements of \verb$temp1$ and \verb$temp2$
have to be explicitly deallocated using the \verb$delete$ operator.

\subsubsection*{Example 5}

\begin{verbatim}
      INTEGER A (10, 10)
!HPF$ DISTRIBUTE A (BLOCK, BLOCK) ONTO P
      INTEGER B (10, 10)
!HPF$ DISTRIBUTE B (BLOCK, BLOCK) ONTO Q
      ...
      FORALL (X = 1 : 10)
        FORALL (Y = 1 : X)
          A (X, Y) = B (X, Y) + F (X) + G (Y)
        END FORALL
      END FORALL
\end{verbatim}
First a translation which makes use of non-Cartesian arrays.  The
temporaries are mapped to the to process arra of \verb$B$ (namely
\verb$Q$).  The \verb$Y$ range is collapsed, otherwise the temporaries
would not have a legal HPF mapping.
\begin{verbatim}
  array int a [10 #blk p_1, 10 #blk p_2] ;
  array int b [10 #blk q_1, 10 #blk q_2] ;
  ...
  {
    range x_t1(b.rng(1)) ;
    dimension q_3 of q ;
    array int temp1 [x_t1] [_ #* q_3] ;
    array int temp2 [x_t1] [_ #* q_3] ;

    // temp1 [x] [y] = b [x, y] + f(x) + g(y)
    // temp2 [x] [y] = y
    {
      where(x_t1) {
        range y_t1(x_t1 + 1 #* q_3) ;

        temp1 <- new array int [y_t1] ;

        array int temp2 [yt_1] ;

        // temp2 [y] = b [x, y]
        remap(temp2, b [y_t1]) ;

        // temp3 = f(x + 1)
        int temp3 = f(x_t1 + 1) ;

        where(y_t1)
          temp1 = temp2 + temp3 + g(y_t1 + 1) ;

        temp2 <- new range(y_t1) ;
      }
    }

    // a [x] [y] = temp1 [x] [y]
    scatter(temp1, a, x_t1, temp2) ;

    where(x_t1) {
      delete temp2 ;
      delete temp1 ;
    }
  }
\end{verbatim}
Several inefficient aspects of this translation (sequentialisation
implied by collapsing the \verb$y$ range; redundant calls to \verb$g$;
the use of non-Cartesian arrays; the use of the \verb$scatter$
primitive) can be avoided by adopting a ``masked Cartesian'' mapping.
\begin{verbatim}
  array int a [10 #blk p_1, 10 #blk p_2] ;
  array int b [10 #blk q_1, 10 #blk q_2] ;
  ...
  {
    range x_t1(b.rng(1)) ;
    range y_t1(b.rng(2)) ;
    array int temp1 [x_t1, y_t1] ;

    // temp1 [x] [y] = b [x, y] + f(x) + g(y)
    {
      array int temp2 [y_t1] ;

      // temp2 [y] = g(y + 1)
      where(y_t1)
        temp2 = g(y_t1 + 1) ;

      where(x_t1) {

        // temp3 = f(x + 1)
        int temp3 = f(x_t1 + 1) ;

        // temp1 [x, y] = b [x, y] + temp3 + temp2 [y] ;
        where(y_t1)
          if(y_t1 <= x_t1)
            temp1 = b + temp3 + temp2 ;
      }
    }

    range x_t2(a.rng(1)) ;
    range y_t2(a.rng(2)) ;
    array int temp2 [x_t2, y_t2] ;

    // temp2 [x, y] = temp1 [x, y] 
    remap(temp2, temp1) ;

    // a [x, y] = temp2 [x, y]
    where(x_t2)
      where(y_t2)
        if(y_t2 <= x_t2)
          a = temp2 ;
  }
\end{verbatim}
%[may be better to add an optional mask argument to \verb$remap$?]

\subsubsection*{Example 6}

\begin{verbatim}
      SUBROUTINE FOO (A)
      INTEGER A (10, 10)
!HPF$ INHERIT A
      INTEGER B (10)
!HPF$ ALIGN B WITH A ( * , : )
        ...
        FORALL (X = 1 : 10, Y = 1 : 10)
          A (X, Y) = F (X) + B (Y)
        ENDFORALL
      END
\end{verbatim}
This example illustrates the translation of code in a procedure, when
the arguments have inherited mapping.  A translation is
\begin{verbatim}
  void foo (array int a _ [10 :: _, 10 :: _]) {
    array int b a.emb() [a.rng(2)] ;
    ...
    at(a.emb()) {
      range x(a.rng(1)) ;
      where(x) {
        int temp1 = f(x + 1) ;
        where(a.rng(1))
          a = b + temp1 ;
    }
  }
\end{verbatim}
(Incidentally, notice how the \verb$rng(1)$ inquiry function was used
inside the loop, to save introducing a new name, \verb$y$ say, outside
the loop.  It is worth emphasising two peculiarities that arise because
the \verb$x$ range of \verb$a$ has vanished within the outer loop.
First, it would be impossible to avoid naming the outer range, because
we need the index value of \verb$x$ inside the loop---we can't apply
apply an inquiry function to \verb$a$ to get this value because the
range isn't in the array any more!  Second, the \verb$y$ range is the
{\em first}, not the second range of \verb$a$ at this point---hence
\verb$rng(1)$ rather than \verb$rng(2)$.  To avoid likely confusions,
it is probably better practise to explicitly name all affected ranges
before entering any \verb$where$ loops.)

