Subject: hpff-doc: mapping-base.tex

From: Piyush Mehrotra <[email-masked]>
Date: Thu, 6 Jun 1996 13:38:33 -0500 (CDT)

---------------------------------------------------------------------------
[email-masked] is a mailing list for HPF 2.0 language specification
authors and editors.  Instructions for adding or deleting yourself from this
list appear at the bottom of this message.
---------------------------------------------------------------------------

% File: mapping-ext.tex

% Contents:
% Approved Extensions for data mapping for HPF 2.0 document, including
%        GenBlock
%        indirect
%        range
%        shadow
%        subsets
%        derived types
%        more on pointers.

% Revision history:
% May-10-96        Created by Charles Koelbel, Rice University
%                (From HPF 2.0 proposals)

\chapter{Approved Extensions for Data Mapping}
\label{ch-mapping-ext}

{\em
Comments on this chapter should be directed to 
Piyush Mehrotra ({\tt [email-masked]}),
Carl Offner ({\tt [email-masked]}),
and {\tt [email-masked]}.
Please use ``{\tt Comments on Extended Mapping}'' as the {\tt Subject:}
line.
\par
}

{\em This chapter contains two extended-dist-formats, one for the new 
distribution formats and one for the shadow width declarations. Something
needs to be done. -- PM}

This chapter describes a set of data mapping features which extend
the capabilities provided by the base set as described in 
Chapter~\ref{ch-mapping-base}. These extensions can be
divided into two categories. The first set of extensions
provide the user a greater control over the mapping of the data. 
These include directives for dynamic remapping of data
which allow the user to redistribute and realign at runtime data which
has been declared {\tt DYNAMIC}.
The {\tt ONTO} clause used in the {\tt DISTRIBUTE} directive is extended
to allow direct distribution to subsets of processors.
Explicit mapping of pointers and components of derived
types are also introduced.
Two new distributions are included, the {\tt GEN\_BLOCK} 
distribution which generalizes the block distribution and
the {\tt INDIRECT} which allows the mapping of individual array
elements to be specified through a mapping array.

The programmer can use the second set of extensions to provide the
compiler with information useful for generating efficient
code. This category includes the range directives which
allows the user to specify the range of distribution that
a dynamically distributed array, a pointer or a formal
argument may have. The shadow directive allows the user
to specify the amount of additional space required on a
processor to accommodate non-local elements in a
nearest-neighbor computation.

Since this chapter deals with extensions, we repeat some of
the sections of Chapter~\ref{ch-mapping-base} and~\ref{ch-mapping-subr} 
providing new rules and extending old
ones where necessary. 
%When extending a rule we use {\tt extended-xx} 
%as the new rule name with the understanding
%that it will replace the old rule name, {\tt xx}, everywhere.

\section{Extended Model}

The fundamental model for allocation of data to abstract
processors still remains a two-level mapping as described in
Chapter~\ref{ch-mapping-base}. However, it is extended to
allow the dynamic remapping of the data objects as
illustrated by the following diagram:

\begin{center}

\setlength{\unitlength}{0.01in}
\begin{picture}(600,240)(0,30)
\thicklines
\put(100,150){\circle{50}}
\put(242,150){\circle{50}}
\put(383,150){\circle{50}}
\put(525,150){\circle{50}}
\put(125,150){\vector(1,0){92}}
\put(267,150){\vector(1,0){91}}
\put(408,150){\vector(1,0){92}}
\put(56,190){\shortstack{Arrays or\strut\\other
objects\strut}}
\put(192,190){\shortstack{Group of\strut\\aligned
objects\strut}}
\put(328,190){\shortstack{Abstract\strut\\processors as
a\strut
                \\user-declared\strut\\Cartesian
mesh\strut}}
\put(494,190){\shortstack{Physical\strut\\processors\strut}}
\put(135,50){\shortstack{{\tt ALIGN}\strut\\(static) or\strut
                \\{\tt REALIGN}\strut\\(dynamic)\strut}}
\put(265,50){\shortstack{{\tt DISTRIBUTE}\strut\\(static) or\strut
                \\{\tt REDISTRIBUTE}\strut\\(dynamic)\strut}}
\put(400,50){\shortstack{Optional\strut\\implementation-\strut
                \\dependent\strut\\directive\strut}}
\end{picture}

\end{center}

Thus, objects can now be remapped at execution time using
the executable directives {\tt REALIGN} and {\tt REDISTRIBUTE}
Any object that is the root of
an alignment tree, i.e., is not explicitly aligned to
another object, can be explicitly redistributed.
Redistributing such an object causes all objects ultimately
aligned with it to be also redistributed so as to maintain the
alignment relationships.

Any object that is not a root
of an alignment tree can be explicitly realigned but not explicitly
redistributed. Such a realignment does not change the
mapping of any other object.
Note that such remapping of data may require communication
among the processors.

By analogy with the Fortran 90 {\tt ALLOCATABLE} attribute, HPF includes
the attribute {\tt DYNAMIC}.  It is not permitted
to {\tt REALIGN} an array that has not been declared {\tt DYNAMIC}.
Similarly, it is not permitted to {\tt REDISTRIBUTE} an array or template
that has not been declared {\tt DYNAMIC}.

Saved local variables, variables in common, and variables accessed by
use association must not be implicitly remapped - e.g., by having
variable distribution formats or being aligned with entities having
variable distribution formats.  Of these three categories of
variables, only variables accessed by use association may have the
{\tt DYNAMIC} attribute.

\section{Syntax of Data Alignment and Distribution Directives}

As in the case of other mapping directives,
the executable directives {\tt REALIGN} and {\tt REDISTRIBUTE}
also come in two forms (statement form and attribute form) but
may not be combined with other attributes in a single directive.
The {\tt RANGE} attribute may be combined with other attributes
in a single directive.

                                                                        \BNF
extend-combined-attribute  \IS  ALIGN align-attribute-stuff
                           \OR  DISTRIBUTE dist-attribute-stuff
                           \OR  DYNAMIC
                           \OR  INHERIT
                           \OR  TEMPLATE
                           \OR  PROCESSORS
                           \OR  DIMENSION ( explicit-shape-spec-list )
                           \OR  RANGE range-attr-stuff-list
                                                                        \FNB

\section{REDISTRIBUTE Directive}
\label{REDISTRIBUTE-SECTION}

The {\tt REDISTRIBUTE} directive is similar to the {\tt DISTRIBUTE}
directive but is considered executable.  An array (or template) may be
redistributed at any time, provided it has been declared {\tt DYNAMIC}
(see Section \ref{DYNAMIC-SECTION}).  Any other arrays currently
ultimately aligned with an array (or template) when it is redistributed
are also remapped to reflect the new distribution, in such a way as to
preserve alignment relationships (see Section \ref{ALIGN-SECTION}).
(This can require a lot of computational and communication effort at
run time; the programmer must take care when using this feature.)

The {\tt DISTRIBUTE} directive may appear only in the {\it specification-part}
of a scoping unit.  The {\tt REDISTRIBUTE} directive may appear
only in the {\it execution-part} of a scoping unit.  The principal
difference between {\tt DISTRIBUTE} and {\tt REDISTRIBUTE} is
that {\tt DISTRIBUTE} must contain only a {\it specification-expr} as the
argument to a 
distribution format, e.g.,
{\tt BLOCK} or {\tt CYCLIC}, whereas in {\tt REDISTRIBUTE}
such an argument may be any integer expression.  Another difference is that
{\tt DISTRIBUTE} is an attribute, and so can be combined with other attributes
as part of a {\it combined-directive}, whereas {\tt REDISTRIBUTE} is not an attribute
(although a {\tt REDISTRIBUTE} statement may be written in the
style of attributed syntax, using ``{\tt ::}'' punctuation).

Formally, the syntax of the {\tt DISTRIBUTE} and
{\tt REDISTRIBUTE} directives is:

                                                                        \BNF
redistribute-directive     \IS  REDISTRIBUTE distributee dist-directive-stuff
                   \OR  REDISTRIBUTE dist-attribute-stuff :: distributee-list
                                                                        \FNB
\begin{constraints}

\item  A {\it distributee} that appears in a {\tt REDISTRIBUTE} directive
must have the {\tt DYNAMIC} attribute (see Section \ref{DYNAMIC-SECTION}).

\item Neither the {\it dist-format-clause} nor the {\it dist-target}
in a {\tt REDISTRIBUTE} may begin with ``{\tt *}''.

\end{constraints}

A {\tt REDISTRIBUTE} directive must not cause any data object
associated with the {\it distributee} via storage association ({\tt
COMMON} or {\tt EQUIVALENCE}) to be mapped such that storage units of
a scalar data object are split across more than one abstract
processor.  See Section \ref{sequence} for further discussion of
storage association.

The statement form of a {\tt REDISTRIBUTE} directive
may be considered an abbreviation for an attributed form that
happens to mention only one {\it distributee}; for example,
                                                                        \CODE
!HPF$ REDISTRIBUTE distributee ( dist-format-list ) ONTO dist-target
                                                                        \EDOC
is equivalent to
                                                                        \CODE
!HPF$ REDISTRIBUTE ( dist-format-list ) ONTO dist-target :: distributee
                                                                        \EDOC

\section{REALIGN Directive}
\label{REALIGN-SECTION}

The {\tt REALIGN} directive is similar to the {\tt ALIGN} directive but
is considered executable.  An array (or template) may be realigned at
any time, provided it has been declared {\tt DYNAMIC} (see Section
\ref{DYNAMIC-SECTION}) Unlike redistribution (see Section
\ref{DISTRIBUTE-SECTION}), realigning a data object does not cause any
other object to be remapped.  (However, realignment of even a single
object, if it is large, could require a lot of computational and
communication effort at run time; the programmer must take care when
using this feature.)

The {\tt ALIGN} directive may appear only in the {\it
specification-part} of a scoping unit.  The {\tt REALIGN} directive is
similar but may appear only in the {\it execution-part} of a scoping
unit.  The principal difference between {\tt ALIGN} and {\tt REALIGN}
is that {\tt ALIGN} must contain only a {\it specification-expr} as a
{\it subscript} or in a {\it subscript-triplet}, whereas in {\tt
REALIGN} such subscripts may be any integer expressions.  Another
difference is that {\tt ALIGN} is an attribute, and so can be combined
with other attributes as part of a {\it combined-directive}, whereas
{\tt REALIGN} is not an attribute (although a {\tt REALIGN} statement
may be written in the style of attributed syntax, using ``{\tt ::}''
punctuation).

Formally, the syntax of {\tt REALIGN} is as follows:

                                                                        \BNF
realign-directive          \IS  REALIGN alignee align-directive-stuff
                           \OR  REALIGN align-attribute-stuff :: alignee-list
                                                                        \FNB
\begin{constraints}

\item  Any {\it alignee} that appears in a {\tt REALIGN} directive
must have the {\tt DYNAMIC} attribute (see Section \ref{DYNAMIC-SECTION}).

\item If the {\tt align-target} specified in the {\tt align-with-clause}
has the {\tt DYNAMIC} attribute, then each {\tt alignee} must also have the
{\tt DYNAMIC} attribute.

\item An object may not have both the {\tt INHERIT} attribute and
the {\tt ALIGN} attribute.  (However, an object with the {\tt INHERIT}
attribute may appear as an {\it alignee} in a {\tt REALIGN} directive,
provided that it does not appear as a {\it distributee} in a {\tt DISTRIBUTE}
or {\tt REDISTRIBUTE} directive.)
\end{constraints}

\section{DYNAMIC Directive}
\label{DYNAMIC-SECTION}

The {\tt DYNAMIC} attribute specifies that an object may be dynamically
realigned or redistributed.
                                                                        \BNF
dynamic-directive      \IS  DYNAMIC  alignee-or-distributee-list

alignee-or-distributee \IS  alignee
                       \OR  distributee
                                                                        \FNB

\begin{constraints}

\item An object in {\tt COMMON} may not be declared {\tt DYNAMIC} and
may not be aligned to an object (or template) that is {\tt DYNAMIC}.
(To get this kind of effect,  Fortran 90 modules must be used instead
of {\tt COMMON} blocks.)

\item An object with the {\tt SAVE} attribute may not be declared {\tt DYNAMIC}
and may not be aligned to an object (or template) that is {\tt DYNAMIC}.

\end{constraints}

A {\tt REALIGN} directive may not be applied to an {\it alignee} that does not
have the {\tt DYNAMIC} attribute.  A {\tt REDISTRIBUTE} directive may not be
applied to a {\it distributee} that does not have the {\tt DYNAMIC} attribute.

A {\tt DYNAMIC} directive may be combined with other directives, with the
attributes stated in any order, consistent with the Fortran
90 attribute syntax.

Examples:
                                                                        \CODE
!HPF$ DYNAMIC A,B,C,D,E
!HPF$ DYNAMIC:: A,B,C,D,E
!HPF$ DYNAMIC, ALIGN WITH SNEEZY:: X,Y,Z
!HPF$ ALIGN WITH SNEEZY, DYNAMIC:: X,Y,Z
!HPF$ DYNAMIC, DISTRIBUTE(BLOCK, BLOCK) :: X,Y
!HPF$ DISTRIBUTE(BLOCK, BLOCK), DYNAMIC :: X,Y
                                                                        \EDOC
The first two examples mean exactly the same thing.
The next two examples mean exactly the same second thing.
The last two examples mean exactly the same third thing.

The three directives
                                                                        \CODE
!HPF$ TEMPLATE A(64,64),B(64,64),C(64,64),D(64,64)
!HPF$ DISTRIBUTE(BLOCK, BLOCK) ONTO P:: A,B,C,D
!HPF$ DYNAMIC A,B,C,D
                                                                        \EDOC
may be combined into a single directive as follows:
                                                                        \CODE
!HPF$ TEMPLATE, DISTRIBUTE(BLOCK, BLOCK) ONTO P,   &
!HPF$   DIMENSION(64,64),DYNAMIC :: A,B,C,D
                                                                        \EDOC

An {\tt ALLOCATABLE} object may also be given the {\tt DYNAMIC} attribute.
If an {\tt ALLOCATE} statement is immediately followed by {\tt REDISTRIBUTE}
and/or {\tt REALIGN} directives,
the meaning in principle is that the array is first created
with the statically declared mapping, if any, then immediately remapped.
In practice there is an obvious optimization: create the array
in the processors to which it is about to be remapped, in a single
step.  HPF implementors are strongly encouraged to implement this
optimization and HPF programmers are encouraged to rely upon it.
Here is an example:
                                                                       \CODE
      REAL,ALLOCATABLE(:,:) :: TINKER, EVERS
!HPF$ DYNAMIC :: TINKER, EVERS
      REAL, ALLOCATABLE :: CHANCE(:)
!HPF$ DISTRIBUTE(BLOCK),DYNAMIC :: CHANCE
      ...
      READ 6,M,N
      ALLOCATE(TINKER(N*M,N*M))
!HPF$ REDISTRIBUTE TINKER(CYCLIC, BLOCK)
      ALLOCATE(EVERS(N,N))
!HPF$ REALIGN EVERS(:,:) WITH TINKER(M::M,1::M)
      ALLOCATE(CHANCE(10000))
!HPF$ REDISTRIBUTE CHANCE(CYCLIC)
                                                                       \EDOC
While {\tt CHANCE} is by default always allocated with a {\tt BLOCK}
distribution, it should be possible for a compiler to notice that it will
immediately be remapped to a {\tt CYCLIC} distribution.  Similar remarks
apply to {\tt TINKER} and {\tt EVERS}.  (Note that {\tt EVERS}
is mapped in a thinly-spread-out manner onto {\tt TINKER};
adjacent elements of {\tt EVERS} are mapped to elements of
{\tt TINKER} separated by a stride {\tt M}.  This thinly-spread-out
mapping is put in the lower left corner of {\tt TINKER},
because {\tt EVERS(1,1)} is mapped to {\tt TINKER(M,1)}.)

\section{Remapping and Subprogram Interfaces}
\label{DYNAMIC-DUMMY-SECTION}

{\em
Part of this section needs to go into the Chapter on Subprogram Interfaces
since it deals with the issues of implicit remapping across 
procedure boundaries.}

The rules on the interaction of the {\tt REALIGN} and {\tt
REDISTRIBUTE} directives with a subprogram argument interface are:
\begin{enumerate}

\item A dummy argument may be declared {\tt DYNAMIC}.  However, it is subject
to the general restrictions concerning the use of the name of an
array to stand for its associated template.

\item If an array or any section thereof is accessible by two or more
paths, it is not HPF-conforming to remap it through any of those paths.  For
example, if an array is passed as an actual argument, it is forbidden
to realign that array, or to redistribute an array or template to which
it was aligned at the time of the call, until the subprogram has
returned from the call.  This prevents nasty aliasing problems.  An
example:

                                                                        \CODE
      MODULE FOO
      REAL A(10,10)
!HPF$ DYNAMIC ::  A
      END

      PROGRAM MAIN
      USE FOO
      CALL SUB(A(1:5,3:9))
      END

      SUBROUTINE SUB(B)
      USE FOO
      REAL B(:,:)
      ...
!HPF$ REDISTRIBUTE A            !Nonconforming
      ...
      END
                                                                        \EDOC
Situations such as this are forbidden, for the same reasons that an assignment
to {\tt A} at the statement marked ``Nonconforming'' would also be forbidden.
In general, in {\it any} situation where assignment to a variable
would be nonconforming by reason of aliasing, remapping of that variable
by an explicit {\tt REALIGN} or {\tt REDISTRIBUTE} directive is also forbidden.

\end{enumerate}

An overriding principle is that any mapping or remapping of arguments
is not visible to the caller.  This is true whether such remapping is
implicit (in order to conform to prescriptive directives, which may
themselves be explicit or implicit) or explicit (specified by {\tt
REALIGN} or {\tt REDISTRIBUTE} directives).  When the subprogram returns
and the caller resumes execution, all objects accessible to the caller
after the call are mapped exactly as they were before the call.  It is
not possible for a subprogram to change the mapping of any object in a
manner visible to its caller, not even by means of {\tt REALIGN} and
{\tt REDISTRIBUTE}.

\begin{implementors}
There are several implementation strategies for achieving this behavior.
For example, one may be able to use a copy-in/copy-out strategy for
arguments that require remapping on subprogram entry.  Alternatively,
one may be able to remap the actual argument on entry and remap again
on exit to restore the original mapping.
\end{implementors}

%----------------------------------------------------------------------------
% Mapping to subsets proposal
%--------------------------------------------------------------------------
\section{Mapping to Processor Subsets}
\label{mapping-proc-subset}

This extension allows  objects  to  be  directly  distributed  to  processor
subsets  by allowing a processor subset to be specified
where  a  processor  could  be  named,  e.g.,  in  a   {\tt DISTRIBUTE}
directive.   The  specified subset must be a proper subset of the
named processor arrangement.

Formally the syntax of the extended {\it dist-target} is as
follows:

                                                                        \BNF
extended-dist-target    \IS processor-name [( section-subscript-list )]
                        \OR * processor-name [( section-subscript-list )]
                        \OR *
                                                                        \FNB
\begin{constraints}

\item The {\it section-subscript}s in the
{\it section-subscript-list} may not be 
{\it vector-subscript}s and are restricted to
either {\it subscript}s or {\it subscript-triplet}s.

\item In the {\it section-subscript-list}, 
the number of {\it section-subscript}s
must equal the rank of the {\it processor-name}.

\end{constraints}

                                                                        \CODE
!Example 1
!HPF$ PROCESSORS P(10)
        REAL A(100)
!HPF$ DISTRIBUTE A(BLOCK) ONTO P(2:5)

!Example 2
!HPF$ PROCESSORS Q(10,10)
        REAL A(100,100)
!HPF$ DISTRIBUTE B(BLOCK,BLOCK) ONTO Q(5:10,5:10)
                                                                        \EDOC

In Example 1, the array A is distributed by block across the
processors P(2) to P(5) while in t eh second example, the array B
is distributed across the lower right quadrant of the processor array Q.

\begin{users}
This extension is most useful in conjunction with the
tasking construct, see Section~\ref{tasking}, which allows
multiple independent phases of a computation to execute simultaneously
on different subsets of processors. A similar situation arises when 
the code uses multiple data structures which can be computed in 
parallel where the computation on each individual object also
exhibits parallelism, e.g., the multiple blocks in
a multi-block grid used in some fluid dynamics calculation. Here, the
individual blocks have to be distributed over subsets of processors
to exploit both levels of parallelism.
\end{users}

\section{Pointers}
\label{POINTERS-SECTION}

Under the approved extensions, pointers can be explicitly mapped.
Formally, this implies that the constraints that a {\it distributee}
and an {\it alignee} may not have the {\tt POINTER} attribute
as stated in 
Sections~\ref{DISTRIBUTE-SECTION} and~\ref{ALIGN-SECTION} respectively,
have to be removed.

As is the case of an allocatable object, the mapping specification
for a pointer does not take effect immediately but plays a role when
the pointer becomes pointer associated with a target either through allocation
or through pointer assignment.

When a pointer with an explicit mapping is used in an {\tt ALLOCATE}
statement, the data is allocated with the specified mapping.

For example:
                                                                        \CODE
      REAL, POINTER, DIMENSION(:) :: A, B
!HPF$ ALIGN B WITH A
!HPF$ DISTRIBUTE A(BLOCK) ONTO P
      ...
      ALLOCATE(A(100))
      ALLOCATE(B(50))
      ...
      ALLOCATE(B(200))                  ! Nonconforming
                                                                        \EDOC

Pointer {\it A}  is declared to have a {\tt BLOCK}
distribution while pointer {\tt B} is declared to be identically
aligned with {\it A}. When {\it A} is allocated, it is created
with a block distribution on the processor  arrangement {\it P}.
When {\it B} is allocated, it is aligned with the first 50 elements
of {\it A}. Note, that the allocation statements
may not occur in the opposite
order, since an object may be aligned to another only if
it has already been  created or allocated.
Also, the second allocation for {\it B} is nonconforming,
since a larger object, {\it B} here, cannot be aligned
with a smaller object, {\it A} in this case.

A pointer with an explicit mapping can be pointer
associated with a target through a pointer assignment statement
if and only if the target has an explicit compatible mapping.
Two objects are considered to have a compatible mapping if and only if the
corresponding elements are mapped to the same abstract processor.
Since a pointer does not have an inherent size only a rank, the compatibility
of mappings may only be determinable when the assignment statement
is executed.

For example:
                                                                        \CODE
!HPF$ PROCESSORS P(10)
      REAL, POINTER, DIMENSION(:) :: A
      REAL, TARGET::  B, C
      DIMENSION B(100), C(200)
!HPF$ DISTRIBUTE A(BLOCK(10)) ONTO P
!HPF$ DISTRIBUTE (BLOCK) ONTO P :: B, C
      ...
      A => B                 ! Conforming
      A => C                 ! Nonconforming
      ...
                                                                        \EDOC

Here, {\it A} can be pointer associated with the array {\it B} 
since the latter has a size of 100 and thus when block
distributed on the ten processor arrangement, its mapping
is compatible with a {\tt BLOCK(10)} mapping onto the
same processor arrangement. On the other hand, the size of
{\it C} makes its mapping incompatible with that specified
for {\it A}.

Also, if a pointer has a partially specified (or underspecified)
mapping, it can be
pointer associated with a target as long as inheriting the rest
of the mapping from the target provides a complete specification
which is compatible with the mapping of the target.
For example, the following pointer assignment is valid even though
no processor arrangement is specified for the pointer:
                                                                        \CODE
      REAL, POINTER, DIMENSION(:) :: A
      REAL, TARGET, DIMENSION(100) ::  B
!HPF$ DISTRIBUTE A(BLOCK)
!HPF$ DISTRIBUTE (BLOCK) ONTO P :: B
      ...
      A => B                 ! Conforming
      ...
                                                                        \EDOC

If a dummy argument is a pointer with an explicit mapping, then
the actual argument must be a pointer with an explicit compatible mapping
as described above.

In order to allow pointers to point to target with any explicit mappings
we introduce the concept of pointers with transrcipitive mappings.
For example:
                                                                        \CODE
      REAL, POINTER, DIMENSION(:) :: A
!HPF$ DISTRIBUTE * :: A
      REAL, TARGET, DIMENSION(100) ::  B, C
!HPF$ DISTRIBUTE B(BLOCK), C(CYCLIC)
      ...
      A => B                 ! Conforming
      A => C                 ! Conforming
      ...
                                                                        \EDOC

Here, the {\tt *} is used to indicate a transcriptive distribution for the
pointer {\it A} and thus it can be pointer associated with both
targets {\it B} and {\it C} distributed by {\tt BLCOK}
and {\tt CYCLIC} respectively.

To allow pointers to have a transcriptive distribution, we have
to change the constraint for {\it dist-format-clause} as specified
in Section~\ref{DISTRIBUTE-SECTION}, to read as follows:

\begin{constraints}
\item If either the {\it dist-format-clause} or the {\it dist-target}
in a {\tt DISTRIBUTE} directive begins with ``{\tt *}'' 
then every {\it distributee} must be a dummy argument, 
{\em 
except if the {\em distributee}
has the {\tt POINTER} attribute.}
\end{constraints}

Note, that pointers with the transcriptive distribution
can be pointer associated only with targets which
have explicit mappings.
When such pointers are used in an {\tt ALLOCATE} statement,
the compiler may choose any arbitrary mapping for the allocated data.

A range declaration (see Section~\ref{range}) can be used to restrict
the set of target distribution formats.

A pointer with an explicit mapping, as described above, may
also have the {\tt DYNAMIC} attribute. Such pointers can be
pointer associated with targets
if and only if they have the {\tt DYNAMIC} attribute.
Thus, the target associated with the pointer may be remapped
using a {\tt REDISTRIBUTE} or {\tt REALIGN} statement under the
following restrictions.

An pointer may be used in {\tt REALIGN} and {\tt REDISTRIBUTE} as an
{\it alignee}, {\it align-target}, or {\it distributee}
if and only if it is currently
associated with a whole array, not an array section.  One may remap an object
by using a pointer as an {\it alignee} or {\it distributee} only if the
object was created by {\tt ALLOCATE} but is not an {\tt ALLOCATABLE} array.

Any directive that remaps an object constitutes an assertion on the
part of the programmer that the remainder of program execution would
be unaffected if all pointers associated with any portion of the
object were instantly to acquire undefined pointer association
status, except for the one pointer, if any, used to indicate the
object in the remapping directive.

\begin{implementors}
If HPF directives were ever to be absorbed as actual Fortran
statements, the previous paragraph could be written as
``Remapping an object causes all pointers associated with any portion
of the object to have undefined pointer association status, except
for the one pointer, if any, used to indicate the object in the
remapping directive.''  The more complicated wording here is intended
to avoid any implication that the remapping directives, in the form
of structured comment annotations, have any effect on the execution
semantics, as opposed to the execution speed, of the annotated
program.)
\end{implementors}

{\em 
Question: What about the case when both the actual and formal
are pointers and are declared dynamic - is remapping reflected
when the rpocedure returns? An allocation of teh summy would
certainly be carried back to the calling procedure. -- PM}

\section{Mapping of Derived Type Components}
%-----------------------------------------------------------------------------
% Derive type mappings, apparent date Jan 18, 1996
%-----------------------------------------------------------------------------

An {\tt ALIGN}, {\tt DISTRIBUTE}, or {\tt DYNAMIC} directive may appear within a
{\it derived-type-def} wherever a {\it component-def-stmt} may appear.  Every
{\it alignee} or {\it distributee} within such a directive must be the name of
a component defined within that {\it derived-type-def}.
To allow mapping of the structure components, the rules have to be extended 
as follows:

                                                                        \BNF

extended-distributee    \IS  object-name
                        \OR  template-name
                        \OR  structure-component
                                                                        \FNB

A derived type is said to be an {\it explicitly mapped type}
if any of its components is explicitly mapped or if any of its
components is of an explicitly mapped type.

\begin{constraints}
\item A component of a derived type may be explicitly distributed
only if the type of the component is not an explicitly mapped type.

\item A variable or array of a derived type may be explicitly
distributed only if the derived type is not an explicitly mapped type.

\item A {\it distributee} in a {\tt DISTRIBUTE} directive may not be a
{\it structure-component}, only a {\it component-name}.

\item A {\it distributee} that is a {\it structure-component} may occur
only in a {\tt REDISTRIBUTE} directive 
and every {\it part-ref}
except the rightmost must be scalar (rank zero).
The rightmost {\it part-name} 
in the {\it structure-component} must have the {\tt DYNAMIC} attribute.
\end{constraints}

                                                                        \BNF
extended-alignee        \IS  object-name
                        \OR  structure-component
                                                                        \FNB

\begin{constraints}
\item A component of a derived type may be explicitly aligned
only if the type of the component is not an explicitly mapped type.

\item A variable or array of a derived type may be explicitly
aligned only if the derived type is not an explicitly mapped type.

\item An {\it alignee} in an {\tt ALIGN} directive may not be a
{\it structure-component}.

\item An {\it alignee} that is a {\it structure-component} may occur
only in a {\tt REALIGN} directive 
and every {\it part-ref}
except the rightmost must be scalar (rank zero).
The rightmost {\it part-name} in the {\it structure-component} must
have the {\tt DYNAMIC} attribute.

\end{constraints}

The above constraints imply that components of structures can be 
mapped within the derived type definition itself such that
any objects of that type are created with the specified mapping.
Structure components which have been declared {\tt DYNAMIC} may be
remapped using the {\tt REDISTRIBUTE} or {\tt REALIGN} directive.

Example:

                                                                        \CODE
      TYPE SIMPLE
        REAL S(100)
!HPF$   DISTRIBUTE S(BLOCK)
      END TYPE SIMPLE

!HPF$ TEMPLATE, DISTRIBUTE(BLOCK, *) :: HAIRY_TEMPLATE(47,73)

      TYPE COMPLICATED
        INTEGER SIZE
        REAL RV(100,100), KV(100,100), QV(47,73)
! Arrays RV, KV, and QV may be mapped
!HPF$   DISTRIBUTE (BLOCK, BLOCK):: RV, KV
!HPF$   ALIGN WITH HAIRY_TEMPLATE :: QV
        TYPE(SIMPLE) SV(100)
! The following directive is not valid because SIMPLE
!  is an explicitly mapped type.
!HPF$   DISTRIBUTE SV(BLOCK) 
      END TYPE COMPLICATED

      TYPE(COMPLICATED) LOTSOF(20)

! The following directive is not valid because COMPLICATED 
! is an explicitly mapped type.
!HPF$ DISTRIBUTE LOTSOF(BLOCK)
                                                                        \EDOC

Here, a component of the derived type {\tt SIMPLE} has been mapped,
thus objects of this type, e.g., {\tt SV} in type {\tt COMPLICATED},
cannot be distributed. The array {\tt LOTSOF} cannot be distributed for the 
same reason.

Components of structures can be remapped using the {\tt REDISTRIBUTE}
or {\tt REALIGN} directive if they have been declared {\tt DYNAMIC}.
FOr example, the following code fragment can be used to allocate and map 
multiple blocks (called {\tt SUBGRID} here) of a multi-block grid:

                                                                        \CODE
!HPF$ PROCESSORS P( number_of_processors() )

      TYPE SUBGRID
        INTEGER SIZE
        INTEGER LO, HI          ! target subset of processors
        REAL, POINTER BL(:)
!HPF$   DYNAMIC BL
      END TYPE SUBGRID

      TYPE (SUBGRID), ALLOCATABLE :: GRID(:)

      READ (*,*) SUBGRID_COUNT
      ALLOCATE GRID(SUBGRID_COUNT)

      DO I = 1, SUBGRID_COUNT
        READ(*,*) GRID(I)%SIZE
      END DO

! Compute processor subsets for each subgrid, setting the LO and HI values
      CALL FIGURE_THE_PROCS ( GRID, number_of_processors()) 
! Allocate each subgrid and distribute to the computed processors subset 
      DO I = 1, SUBGRID_COUNT
        ALLOCATE( GRID(I)%BL( GRID(I)%SIZE ) )
!HPF$   REDISTRIBUTE GRID(I)%BL(BLOCK) ONTO P( GRID(I)%LO : GRID(I)%HI )
     END DO
                                                                        \EDOC

%-----------------------------------------------------------------------------
% Indirect mapping proposal, apparent date Jan 18, 1996
%----------------------------------------------------------------------------

\section{New Distribution Formats}
\label{dist-formats}

This section describes two new 
distribution formats. Formally, we can extend the syntax as follows:

                                                                \BNF
extended-dist-format    \IS  BLOCK  [ ( int-expr ) ]
                        \OR  CYCLIC [ ( int-expr ) ]
                        \OR GEN\_BLOCK (int-array)
                        \OR INDIRECT (int-array)
                        \OR  *
                                                                \FNB

\begin{constraints}
\item
    An {\it int-array} appearing in a {\it extended-dist-format} of a
    {\tt DISTRIBUTE} or {\tt REDISTRIBUTE} directive must be an 
integer array of rank 1.

\item
    An {\it int-array} appearing in a {\it extended-dist-format} of a
    {\tt DISTRIBUTE} directive must be a {\it restricted-expr}.

\item
    The size of any 
 {\it int-array} appearing with a {\tt GEN\_BLOCK} distribution must be
equal to the extent of the corresponding dimension of the target processor
arrangement.

\item
    The size of any 
 {\it int-array} appearing with an {\tt INDIRECT} distribution must be
equal to the extent of the corresponding dimension of the {\it distributee}
to which the distribution is to be applied.

\end{constraints}

The ``generalized'' block distribution, {\tt GEN\_BLOCK}, allows
contiguous segments of an array, of possibly unequal sizes, to be mapped
onto processors. The sizes of the segments 
are specified by values of a user-defined integer mapping array,
one value per target processor of the mapping.
That is,  the {\it ith} element of the mapping array specifies the
size of the block to be stored on the {\it ith} processor
of the target processor arrangement.
Thus, the values of the mapping arrays are restricted to be 
non-negative numbers and their sum must be greater than or equal to
the extent of the corresponding dimension the array being distributed.

The mapping array has to be a restricted expression when used in  the
{\tt DISTRIBUTE}   directive,  but  can  be  an  array  variable  in  a
{\tt REDISTRIBUTE} directive. In the latter case, changing the value of
the  map  array  after  the  directive has been executed will not
change the mapping of the distributed array.

Let {\it l} and {\it u} be the lower and upper bounds of the dimension
of the {\it distributee}, {\it MAP} be the mapping array
 and let {\it BS(i):BE(i)} be the resultant 
elements mapped to the {\it ith} processor in the corresponding
dimension of the target processor arrangements.
Then,
\begin{eqnarray*}
BS (1) & = & l,\\
BE (i) & = & max( BS(i)+MAP(i)-1, u),\\
BS (i) & = & BE(i-1) + 1.\\
\end{eqnarray*}

Example:
                                                                        \CODE
        PARAMETER (S = /2,25,20,0,8,65/)
!HPF$ PROCESSORS P(6)
        REAL A(100), B(200), new(6)
!HPF$ DISTRIBUTE A( GEN_BLOCK( S) ) ONTO P
!HPF$ DYNAMIC  B
        ...
       new = ...
!HPF$  REDISTRIBUTE ( B( GEN_BLOCK(new) )
                                                                        \EDOC
Given the above specification, array elements A(1:2) are mapped on P(1),
A(3:27) are mapped on P(2), A(28:37) are mapped on P(3),
no elements are mapped on P(4), A(37:45) are mapped on P(5), and
A(46:100) are mapped on P(6).
The array {\it B} is distributed based on the array {\it new} whose 
values are computed at runtime. 

\begin{implementors}
Accessing elements of an array distributed using the generalized 
block distribution may require accessing the values of the mapping
array at runtime. However, since the size of such an array 
is equal to that of the processor arrangement, it can in most
cases be replicated over all processors.

For dynamic arrays, an independent copy of the mapping array
will have to be maintained internally so that a change
in the values of the mapping array does not affect the access 
of the distributed array.
\end{implementors}

There are many scientific applications in which the structure  of
the  underlying domain is such that it does not map directly onto
Fortran data structures. For example, in many CFD applications  a
unstructured mesh (consisting of triangles in 2D or tetrahedra in
3d) is used to represent the underlying domain. The nodes of such
a mesh are generally represented by a one-dimensional array while
another is used to  represent  their  interconnections.   Mapping
such  arrays  using the structured distribution mechanisms, {\tt BLOCK}
and {\tt CYCLIC}, results in mappings in which unrelated  elements  are
mapped  onto  the  same  processor. This in turn leads to massive
amounts of unnecessary communication.   What  is  required  is  a
mechanism  to  map a related set of arbitrary array elements onto
the same processor.  The  {\tt INDIRECT}  distribution  
provides  such  a  mechanism.  

The  {\tt INDIRECT}  distribution  allows  a  many-to-one  mapping   of
elements  of  a  dimension  of a data array to a dimension of the
target processor arrangement. An integer array is used to specify
the  target  processor  of  each  individual element of the array
dimension being distributed.  That is, the {\it ith} element of the mapping
array  provides  the  processor  number  onto which the {\it ith} array
element is to be mapped.  Since the mapping array maps array elements
onto  processor  elements, the extent of the mapping array must match
the extent of the dimension of the array it is distributing. Also,
the  values of the mapping array must lie between the lower and upper
bound of the target dimension of the processor arrangement.

The mapping array has to be a restricted expression when used in  the
{\tt DISTRIBUTE}   directive,  but  can  be  an  array  variable  in  a
{\tt REDISTRIBUTE} directive. In the latter case, changing the value of
the  mapping  array  after  the  directive has been executed will not
change the mapping of the distributed array.

Example:

                                                                        \CODE
!HPF$ PROCESSORS P(4)
        REAL A(100), B(50)
        INTEGER map1(100), map2(50)
        PARAMETER (map1 = /1,3,4,3,3,2,1,4, ..../)
!HPF$ DYNAMIC B
!HPF$ DISTRIBUTE A( INDIRECT(map1) ) ONTO P
!HPF$ DISTRIBUTE map2(BLOCK) ONTO P

        map2 = ...
!HPF$ DISTRIBUTE B( INDIRECT(map2) ) ONTO P
        ....
                                                                        \EDOC

Here, the array {\it A} is distributed statically using the constant
array {\it map1}.  Thus:

\hspace{0.5in}
\parbox{3in}{
A(1) is mapped onto P(1),\\
A(2) is mapped onto P(3),\\
A(3) is mapped onto P(4),\\
A(4) is mapped onto P(3),\\
A(5) is mapped onto P(3),\\
A(6) is mapped onto P(2),\\
A(7) is mapped onto P(1),\\
A(5) is mapped onto P(4), and so on.\\
}

The array {\it B} is declared  dynamic and is redistributed using
the mapping array {\it map2}.

\begin{implementors}
In general, the {\tt INDIRECT} distribution is going to be used in  the
{\tt REDISTRIBUTE}  directive  with an array variable as the map array.
Also, since the size of the mapping array must be  the  same  as  the
array  being  distributed,  it  will  itself  be distributed most
likely using the {\tt BLOCK} distribution.  This raises several issues.
To  correctly  implement  this  distribution,  the runtime system
should maintain a (distributed) copy of the mapping array so that  if
the  program  modifies  the  mapping array, the distribution does not
change.  Using an array variable as a mapping array implies that  the
location  of  each  element  of the array will not be known until
runtime. Thus, a communication maybe required to figure  out  the
location  of  a  specific array element.
\end{implementors}

%-----------------------------------------------------------------------------
% Shadow regions proposal, apparent date Feb 7, 1996
%-----------------------------------------------------------------------------

\section{Range Directive}
\label{range}

The {\tt RANGE} attribute is used to restrict the possible distribution formats for an object or template that has the {\tt DYNAMIC} attricute or 
a transcriptive  distribution format, or an object with the{\tt POINTER}
attribute.

                                                                \BNF
range-directive         \IS RANGE ranger range-attr-stuff-list

ranger                  \IS object-name
                        \OR template-name

range-attr-stuff        \IS ( range-attr-list )

range-attr              \IS range-dist-format
                        \OR ALL

range-dist-format       \IS BLOCK [ ()]
                        \OR  CYCLIC [ () ]
                        \OR GEN\_BLOCK
                        \OR INDIRECT 
                        \OR  *

                                                                \FNB

\begin{constraints}

\item
The {\it ranger} must have the {\tt DYNAMIC} attribute, the {\tt POINTER} 
attribute, the {\tt INHERIT} attribute and no explicit {\tt DISTRIBUTE},
or it must have been specified with a {\it dist-format-clause}
of {\tt *} in a {\tt DISTRIBUTE} or combined directive.

\item
The length of any {\it range-attr-list} must be equal to the rank of
the {\it ranger}.

\item
The {\it ranger} must not appear as an alignee in an {\tt ALIGN}
or {\tt REALIGN} directive.
\end{constraints}

If a {\it ranger} is given the {\tt RANGE} attribute, every {\it range-attr}
in at least one of the {\it range-attr-stuff}s must be compatible
with the distribution format of the corresponding dimension of the:

\begin{enumerate}

\item
template of the {\it ranger}, if the {\it ranger} is transcriptevly
distributed;

\item
target of the {\it ranger}, if the {\it ranger} has the {\tt POINTER} attribute,
and is associated; or

\item the {\it ranger} if the {\it ranger} has the {\tt DYNAMIC} attribute.
\end{enumerate}

This compatibility must be maintained by any {\tt DISTRIBUTE}
or {\tt REDISTRIBUTE} directive in which the {\it ranger} appears as
a distributee, or if the ranger has the {\tt POINTER}
attribute, for any target with which the {\it ranger}
becomes associated.

A distribution format of 

\begin{enumerate}

\item
{\tt BLOCK} is compatible with a {\it range-dist-format} of {\tt BLOCK},
{\tt BLOCK()} or {\tt CYCLIC()};

\item
{\tt BLOCK(n)} is compatible with a {\it range-dist-format} of 
{\tt BLOCK()} or {\tt CYCLIC()};

\item
{\tt CYCLIC} is compatible with a {\it range-dist-format} of {\tt CYCLIC}
or {\tt CYCLIC()};

\item
{\tt CYCLIC(n)} is compatible with a {\it range-dist-format} of {\tt CYCLIC()};

\item
{\tt GEN\_BLOCK} is compatible with a {\it range-dist-format} of 
{\tt GEN\_BLOCK};

\item
{\tt INDIRECT} is compatible with a {\it range-dist-format} of {\tt INDIRECT};

\item
{\tt *} is compatible with a {\it range-dist-format} of {\tt *}.

\end{enumerate}

All distribution formats are compatible with a {\it range-dist-format} of 
{\tt ALL}.

\section{Shadow Width Declarations}

In compiling nearest-neighbor code (as is used, for instance, in
discretizing partial differential equations or implementing
convolutions), a standard technique is to allocate storage on each
processor for the local array section that includes additional space
for the elements that have to be moved in from its neighboring
processors.  This additional storage is referred to as ``shadow
edges.''  There are conceptually two shadow edges for each array
dimension:  one at the low end of the local array section, and the
other at the high end.

In a single routine, the compiler can tell which arrays require shadow
edges, and allocate this additional space accordingly.  However, since
the width of the shadow area is dependent on the size of
the computational stencil being used, an array may require
different shadow widths in different routines. Thus, without
interprocedural analysis, an array argument may need to be 
copied into a space with the appropriate shadow width
on each procedure call. A similar data motion would be
required to copy the data back to its original location
on exit form the subroutine.
This unnecessary data motion can be avoided by allowing
the user to specify the required shadow width when the
array is declared.

Formally, the syntax for declaring shadow widths is as follows:

                                                                \BNF
extended-dist-format    \IS  BLOCK  [ ( int-expr [, shadow-spec-or-int-expr] ) ]
                        \OR  BLOCK  ( shadow-spec )
                        \OR  CYCLIC [ ( int-expr [, shadow-spec-or-int-expr] ) ]
                        \OR  CYCLIC  ( shadow-spec )
                        \OR GEN\_BLOCK (int-array [, shadow-spec-or-int-expr] )
                        \OR INDIRECT (int-array)
                        \OR  *

shadow-spec-or-int-expr \IS shadow-spec
                        \OR int-expr

shadow-spec             \IS SHADOW = int-expr
                        \OR LOW\_SHADOW = int-expr [, HIGH\_SHADOW = int-expr]
                        \OR HIGH\_SHADOW = int-expr [, LOW\_SHADOW = int-expr]
                                                                \FNB
\begin{constraints}
\item Any {\it int-expr} appearing in a {\it shadow-spec} or in a
{\it shadow-spec-or-int-expr} must be a constant {\it specification-expr} with
value greater than equal to {\it 0}.

\item
The absence of a {\it shadow-spec} or a
{\it shadow-spec-or-int-expr} is equivalent
to {\tt SHADOW = 0}.

\item The specification
{\tt SHADOW =  w} (where {\tt w} is an {\it int-expr}) is
equivalent to {\tt LOW\_SHADOW = w,  HIGH\_SHADOW = w}

\item
A {\it shadow-spec-or-int-expr} that is just an
{\it int-expr} (say {\tt w}) is
equivalent to {\tt SHADOW = w}.

\item
Specifying only {\tt LOW\_SHADOW} implies {\tt HIGH\_SHADOW = 0}.

\item
Specifying only {\tt HIGH\_SHADOW} implies {\tt LOW\_SHADOW = 0}.

\end{constraints}

Thus, the directive

                                                                \CODE
!HPF$    DISTRIBUTE(BLOCK(n, w))  ::  A 
                                                                \EDOC

\noindent
specifies that the array {\it A} is distributed by {\tt BLOCK(n)}
and is to have a
shadow width of {\it w} on both sides.
If {\it A} is a dummy argument, this gives the
compiler enough information to inhibit unnecessary data motion at
procedure calls.

The shadow width parameter can also be referenced by using the keyword
{\tt SHADOW}; this is really a preferred usage, and is necessary if the
distribution is {\tt BLOCK}, rather than {\tt BLOCK(n)}.  So for instance, the
following are equivalent:

                                                                \CODE
!HPF$    DISTRIBUTE(BLOCK(n, w))  ::  A 
!HPF$    DISTRIBUTE(BLOCK(n, SHADOW = w))  ::  A 
                                                                \EDOC

A {\tt BLOCK} distributed dimension with a shadow width would be
indicated simply as

                                                                \CODE
!HPF$    DISTRIBUTE(BLOCK(SHADOW = w))  ::  A 
                                                                \EDOC
In a similar fashion,
                                                                \CODE
!HPF$    DISTRIBUTE(CYCLIC(n, w))  ::  A 
!HPF$    DISTRIBUTE(CYCLIC(n, SHADOW = w))  ::  A 
                                                                \EDOC

\noindent
are both equivalent and refer to a {\tt CYCLIC(n)} distribution with a
shadow width of {\it w}.

Using the keywords 
{\tt LOW\_SHADOW} and {\tt HIGH\_SHADOW}, different
shadow widths can be specified for the low end and high end
of a dimension. For example:
                                                                \CODE
         REAL, DIMENSION (1000) :: A
!HPF$    DISTRIBUTE(BLOCK(LOW_SHADOW = 1, HIGH_SHADOW = 2))  ::  A 
        ....
        FORALL (i = 2, 998)
            A(i) = 0.25* (A(i) + A(i-1) + A(i+1) + A(i+2))
                                                                \EDOC
\noindent
specifies that only one non-local element is needed at the lower end
while two are needed at the high end.
---------------------------------------------------------------------------
To (un)subscribe to this list, send mail to [email-masked].
Leave the subject line blank, and in the body put the line
(un)subscribe <email-address>
---------------------------------------------------------------------------