Subject: hpff-doc: latest parallel-ext.tex

From: Chuck Koelbel <[email-masked]>
Date: Sat, 19 Oct 1996 17:15:41 -0500

---------------------------------------------------------------------------
[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.
---------------------------------------------------------------------------

Here it is.  Apologies for yet another case of "Why doesn't my Mac upload
files correctly?"  No apologies for lateness of response, I've been on the
road.

Look for the public comment draft tomorrow sometime.  Not late, since I'm
getting on a plane about 6:00...

						Chuck

% File: parallel-ext.tex

% Contents:
% Approved Extensions for data-parallel computation for HPF 2.0
% document, including
%       ON
%       TASK
%       RESIDENT

% Revision history:
% May-10-96     Created by Charles Koelbel, Rice University
%               (from HPF 2.0 proposals)
% Aug-27-96     Expanded section on task parallelism added
%               Jaspal Subhlok

\chapter{Approved Extensions for Data and Task Parallelism}
\label{ch-parallel-ext}

Modern parallel machines achieve their best performance if
operations are performed by many processors with
each processor accessing its local data.
As such, the highest-performing programs will be those for which the
computation partitioning and data mapping work in synergy.
Three Approved Extensions provide the means to exploit this symmetry:
\begin{enumerate}
\item The {\tt ON} directive partitions computations among the
processors of a parallel machine (much as the {\tt DISTRIBUTE}
directive partitions the data among the processors).
\item The {\tt RESIDENT} directive
asserts that certain data
accesses do not require interprocessor data movement for their
implementation.
\item The {\tt TASK_REGION} construct provides the means to create
independent coarse-grain task graphs, each of which can itself
execute a data-parallel (or nested task-parallel) computation.
\end{enumerate}
All three constructs are related to the concept of \emph{active
processors}, introduced in Section~\ref{sec-active} below.
By assigning computations to processors, the \texttt{ON} directive
(Section~\ref{sec-on}) defines the active processor.
The \texttt{RESIDENT} directive (Section~\ref{sec-resident})
uses this set and the information
given by mapping directives in its assertions of locality.
Finally, the \texttt{TASK_REGION} construct (Section~\ref{sec-tasking})
builds its tasks from active processor sets.

\section{Active Processor Sets}
\label{sec-active}

\emph{Active processors} are an extension of the idea of processors and
processor
arrangements used in HPF 2.0.
There, the language assumed that a (static) set of processors
existed, and that the program used these processors to store data
(e.g.\ through the \texttt{DISTRIBUTE} directive) and perform computations
(e.g.\ by execution of \texttt{FORALL} statements).  Finer divisions
of the processors set were seldom mentioned, although they did have
their uses (e.g. mapping onto processor subsets as in
Section~\ref{mapping-proc-subset}, or in explaining the performance of
computations on subarrays).
Features such as task parallelism, however, require considering a
more dynamic set of processors.
In particular, answering the question ``What processor(s) is (are) currently
executing?'' is important to define these features.

Simply put, an active processor is one that executes an HPF
statement (or group of statements).
Active processors  perform all
operations required to execute the statement(s) {\em except\/} (perhaps)
for the
initial access of data and writing of results.
Some operations require certain processors to be active, as described
below, but for the most part any processor can be active in the
execution of any statement.
An HPF program begins execution with all processors active.
As described in Section~\ref{sec-on}, the \texttt{ON} directive
restricts the active processors set for the duration of its scope.
Consider this simple example (which has a reasonably intuitive meaning):
\CODE
        !HPF$ ON HOME( Z(2) )
        X(1) = X(1) + Y(2) * Z(3)
\EDOC
Let {\tt X}, {\tt Y}, and {\tt Z} have the same distribution.
Following the {\tt ON} directive, the statement would be executed as
follows:
\begin{enumerate}
\item   The processor processor owning {\tt Z(2)} is identified as
        the active processor.  This step will probably be done at
        compile time; the others will have to wait until execution time.
\item   The values of {\tt X(1)}, {\tt Y(2)}, and {\tt Z(3)} are made
        available to the active processor.
        Because of the identical distributions, \texttt{Y(2)} is
        already stored there.
        Depending on the data distribution and the hardware running the
program,
        retrieving the others might correspond to the active
        processor loading registers from
        memory, or
        it might mean two other processors sending messages to the active
        processor.
\item   The active processor performs an addition and a
        multiplication, using the values sent in the last step.
        The previous data movement allows these operations
        to be performed locally.
\item   The result is stored to {\tt X(1)}, which may be on another
        processor.
        Again, this may require synchronization or other
        cross-processor operations.
\end{enumerate}
There are considerable subtleties of this scheme when one of the
statements involved is a function or subroutine call.
Section~\ref{sub-on-subr} deals with these cases.

The active processor set is dynamic, and if a statement is executed
repeatedly the active processor set may be different each time.
In general, an HPF construct (including an extension) can only
restrict the active set, not enlarge it.  However, if the original
active set is partitioned into several independent sets, all partitions
may execute simultaneously.
This is exactly how the \texttt{TASK_REGION}
construct (described in Section~\ref{sec-tasking}) works.

A few additional terms are useful in conjunction with the concept of
active processors.
A processor that is not in the active set is called \emph{passive}.
(Note that a  processor may be passive with respect to one statement,
but active with respect to another.  This is common in
\texttt{TASK_REGION} constructs.)
A set of processors, including both active and passive, is called a
\emph{universal} processors set.
Finally, it is sometimes necessary to query properties of the active
processors set; this is accomplished by the Approved Extension
intrinsics \texttt{ACTIVE_NUM_PROCS} and \texttt{ACTIVE_PROCS_SHAPE}
described in Section~\ref{sec:ext-intrinsic-specs}.

\begin{users}
Section~\ref{sec-tasking} raises the possibility of passive processors that
are
used by the system to perform other computations.
These might be called \emph{passive-aggressive} processors.
\end{users}

\begin{rationale}
It may seem odd at first to concentrate on shrinking the
active processor set.
However, HPF's design assumes that all processors are available at
the beginning of execution.
For example, implementing \texttt{DISTRIBUTE} requires information
about the number of processors (in order to determine block sizes,
for example) and their identity (in order to allocate the memory and
perform data motion).
Therefore, the execution model uses a static set of processors which
can be subdivided dynamically.
\end{rationale}

\subsection{How Active Processors Interact with Data Mapping}

This subsection explains the interaction of active
(and passive) processor sets with explicitly mapped data.  The rule of
thumb is that allocating memory must be done
locally; that is, if a processor stores part of an array, then that
processor must be active when the array is created.
Implications of this rule include:
\begin{itemize}
	\item  Local variables must be stored on the active processor set,
	either when their subprogram is invoked (for explicit shape
	variables) or when they are allocated (for \texttt{ALLOCATABLE}
	variables).

	\item  Dummy arguments are always mapped to the active processors
	set.  Section~\ref{sub-on-subr} explains the mechanism that ensures
this.

	\item  Global variables (i.e.\ variables in \texttt{COMMON} or
	\texttt{MODULE}s) may be declared distributed on passive processors.
	However, those processors must have been active when the
	globals were allocated, either at program initialization (when all
	processors were active) or at an \texttt{ALLOCATE} statement.
\end{itemize}

It should be clear from the treatments of local and global variables
that declarations may need to refer to two types of processor
arrangements.

One type, used mainly for the declaration of global
data, is universal processor arrangements.  These arrangements
represent (part of) the set of all available processors, both active
and passive.  Since they always represent the same processors, these
serve as a fixed point of reference, allowing consistent declarations.
A \textit{processors-directive} (Rule~\ref{processors-directive-rule})
defines a universal processors
arrangement by default.  To accomodate active processors, two slight
changes to the rules in Section~\ref{PROCESSORS-SECTION} need to be
made:
\begin{itemize}
	\item  An HPF compiler is required to accept any \emph{universal}
	processors arrangement with total size
	(i.e.\ product of the arrangement's dimensions) equal to the number of
    processors that would be returned by the call {\tt NUMBER_OF_PROCESSORS()}.

	\item  If two \emph{universal} processor arrangements have the same
shape,
	then corresponding elements of the two arrangements are understood
to refer
	to the same abstract processor.
\end{itemize}
In both cases, the only change is the addition of the word ``universal.''
This is needed to avoid misleading
correspondences between universal processor arrangements and active processor
arrangements, defined next.

Active processor arrangements represent only processors that, at the
time the arrangement is declared, are active.  They are used for
mapping local variables.  To declare a processors arrangement to be
active, one can use the \texttt{ACTIVE} option of the extended
\textit{combined-directive}:
\BNF
combined-attribute-extended  \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
                           \OR  ACTIVE
\FNB
\begin{constraints}
\item The \texttt{ACTIVE} attribute may only be applied to a
processors arrangement.
\end{constraints}
One can also use the statement form of the \texttt{ACTIVE} attribute:
\BNF
active-directive \IS ACTIVE processors-name
\FNB
Examples of the two forms are
\CODE
!HPF$ PROCESSORS, ACTIVE :: P(NP/4,4)
!HPF$ PROCESSORS Q(NP)
!HPF$ ACTIVE Q
\EDOC
As for universal arrangements, there are some modified
rules for the use of active processor arrangements:
\begin{itemize}
	\item  An HPF compiler is required to accept any \emph{active}
	processors arrangement with total size
	(i.e.\ product of the arrangement's dimensions) equal to the number of
    processors that would be returned by the call {\tt ACTIVE_NUM_PROCS()}.

	\item  If two \emph{active} processor arrangements are declared
with the
	same shape and the active processor set has not changed between their
	declarations,
	then corresponding elements of the two arrangements are understood
to refer
	to the same abstract processor.
\end{itemize}
Note that active processor arrangements may have
fewer than \texttt{NUMBER_OF_PROCESSORS()} elements; this reflects
the way that the active processors set can be restricted.
Also note that there is an added condition before two active
processor arrangements are considered identical; this reflects the
dynamic nature of the active processors set.

For explicitly mapped local variables without the \texttt{SAVE}
attribute, the declarations must map all
elements of the variable onto active processors.
This statement gives rise to several cases:
\begin{itemize}
	\item  If the local variable is mapped via a \texttt{DISTRIBUTE}
	directive, then it must be distributed onto a set of active
	processors:
	\begin{itemize}
		\item  If there is an explicit \texttt{ONTO} clause, then
either
		the \textit{dist-target} must be declared with the
\texttt{ACTIVE}
		attribute, or the \textit{dist-target} must be a section of a
		universal processor arrangement in which all the processors
are
		active.

		\item  If there is no \texttt{ONTO} clause, then the
implementation
		must choose a set of active processors to distribute onto.
	\end{itemize}

	\item  If the local variable is mapped by an \texttt{ALIGN}
	directive, then the corresponding elements of the ultimate align
	target must be distributed onto active processors.  This may be
	achieved by:
	\begin{itemize}
		\item  Distributing the ultimate align target onto an
\texttt{ACTIVE}
	processor arrangement, or

		\item  Distributing the ultimate align target
	onto an appropriate section of a universal processor
	arrangement, or

		\item  Aligning the local variable to an appropriate
section of a
		target distributed to all processors.
	\end{itemize}
\end{itemize}
In either case, the active processor set is determined at the time
that the \texttt{DISTRIBUTE} or \texttt{ALIGN} becomes instantiated.
That is, the mapping directives for \texttt{ALLOCATABLE} variables are
instantiated when the variable is allocated; other variables have
their mapping instantiated when they are declared.  Also note that it
is behavior that determines whether a processor is active.  In
particular, if a program contains no \texttt{ON} directives which modify a
program's active processor set, then all processors are always active
and all \texttt{DISTRIBUTE} directives can use the default universal
arrangements.

Explicitly mapped global variables must have consistent mappings wherever they
appear.  Therefore, it is required that global variables be mapped
onto universal processor arrangements. There are several cases to
consider:
\begin{itemize}
	\item  If the global variable is mapped via a \texttt{DISTRIBUTE}
	directive, then it must be distributed onto a universal processors
	arrangement.
	\begin{itemize}
		\item  If there is an explicit \texttt{ONTO} clause, then
		the \textit{dist-target} must \emph{not} be declared with the
		\texttt{ACTIVE} attribute.

		\item  If there is no \texttt{ONTO} clause, then the
implementation
		must choose a set of processors.  This set may contain
processors
		that are currently passive.  However, the set of processors
for any
		particular variable must be chosen consistently for all
declarations
		of that variable.
	\end{itemize}

	\item  If the global variable is mapped by an \texttt{ALIGN}
	directive, then the corresponding elements of the ultimate align
	target must be distributed onto a universal processors arrangement.
	This may be achieved by either of the cases above.
\end{itemize}
Notice that the interpretation of an implicit (i.e.\ missing)
\texttt{ONTO} clause differs for local and global variables; globals
may use any processors as their default set, while locals must use
only active processors.
The universal processors set is determined at the time
that the \texttt{DISTRIBUTE} or \texttt{ALIGN} becomes instantiated,
but this is not critical since HPF does not support dynamic
processor creation and deletion.
Also note that, since universal processors arrangements are the
default for the \texttt{PROCESSORS} directive, no modification to the
mapping of global variables is needed when active processors are
introduced.

Dummy arguments must be declared as local variables using the rules
above.  As Section~\ref{sub-on-subr} explains, the effect of this is
that dummy arguments are always stored on the active processor set.
Other variables, particularly variables local to the subprogram, can
therefore be \texttt{ALIGN}ed to the dummy variables and allocated on
the active processor set.

Variables with the \texttt{SAVE} attribute must be mapped
consistently whenever they come into scope.  Therefore, they act more
like global variables and follow the rules for global variables.

\subsection{Other Restrictions on Active Processors}

In addition to declarations, several other constructs are restricted
when the active processor set does not match the universal processor
set.
In general, the intent of these restrictions is to ensure that all
processors that needed for an operation are
active when it is performed.
In particular, allocating or freeing memory mapped to a processor
requires the cooperation of that processor.
With that in mind, we present constraints on activities performed on
a smaller (non-universal) active processor set.

For a {\tt REDISTRIBUTE} directive,
the set of  active processors must include:
\begin{itemize}
\item All processors that stored any element of the {\it
distributee\/} before the {\tt REDISTRIBUTE} was encountered, and
\item The processors which will store any element of the
\textit{distributee} after the \texttt{REDISTRIBUTE} is performed.
\end{itemize}
Effectively, this means that all data movement for the
\texttt{REDISTRIBUTE} will be among active processors; in addition,
the processors that owned the \textit{distributee} (or anything
aligned to it) beforehand can free the memory, and processors that
now own the \textit{distributee} can allocate memory for it.

Similarly, for a {\tt REALIGN} directive,
the set of active processors must include all processors that stored
elements of the \textit{alignee} before the \texttt{REALIGN} and all
processors that will store \textit{alignee} elements after the
\texttt{REALIGN}.

For an {\tt ALLOCATE} statement
which creates an explicitly mapped variable, the set of active
processors
must include the processors used by the mapping directive for the
allocated variable.
The allocated variable's ultimate align target may fall into one of
three classes:
\begin{itemize}
	\item  Distributed with no explicit \texttt{ONTO} clause.  (This
	case includes ultimate align targets with no \texttt{DISTRIBUTE}
	directive at all.)  In this case, the compiler must choose a set of
	active processors which the variable will be stored on.  Note that
	this may map even a global variable onto a subset of the universal
	processor set.

	\item  Distributed \texttt{ONTO} a section of a universal
	processors arrangement.  In this case, the section must be the set
of active
	processors or a subset of it.  An important special case of this is
	when the \texttt{DISTRIBUTE} directive names an entire universal
	processors arrangement; then the \textit{distributee} can only be
	allocated when all processors are active.

	\item  Distributed \texttt{ONTO} a section of an active processors
	arrangement.  In this case, the allocation is always valid if the
	active processors set has not been restricted since the
	\texttt{PROCESSORS} declaration (i.e.\ if the \texttt{ALLOCATE} is
	not nested in an \texttt{ON} block).  It is also valid if the onto
	section is a subset of the active processors set.
\end{itemize}

For a {\tt DEALLOCATE} statement that destroys an explicitly mapped
variable, the active processor set must include all processors that
owned any element of that variable.
Again, there are three cases for the deallocated variable's ultimate
align target:
\begin{itemize}
	\item  Distributed with no explicit \texttt{ONTO} clause.  (This
	case includes ultimate align targets with no \texttt{DISTRIBUTE}
	directive at all.)  In this case, the active processor set must
	include all the processors that were active when the variable was
	\texttt{ALLOCATE}d.  This can be ensured, for example, if the
	deallocation is performed in the same \texttt{ON} block or in an
	enclosing block.

	\item  Distributed \texttt{ONTO} a section of a universal
	processors arrangement.  In this case, the section must be the set
of active
	processors or a subset of it.

	\item  Distributed \texttt{ONTO} a section of an active processors
	arrangement.  This case is identical to the previous one.
\end{itemize}

\begin{rationale}
Operations which allocate memory require the cooperation of all processors
that will own that memory.
Therefore, they must be active when  variables mapped to them are declared
or allocated.
The most
common cases where these apply are in subroutines called from {\tt ON} clauses.

An alternate description of these constraints is:
\begin{itemize}
\item Local variables that are not {\tt SAVE}d can only be mapped to
  the set of active processors.  This ensures that
  all references to local variables will be {\tt RESIDENT} as defined
  in Section~\ref{sec-resident}.
\item Dummy arguments and result variables can only be mapped to the
  active processors.  Like local variables, this ensures that all
  references to dummies and result variables are to local memory.  Note
  that, although the dummy arguments must be {\tt RESIDENT}, the
  actual argument may not be (due to remapping).
\item Global variables may be explicitly mapped onto any set of processors,
  whether or not the processors are active.  This is required so
  that the mappings of the globals can be consistent in different scopes.
  Memory for the global variables will be allocated either at load time,
  when all processors are active, or in explicit {\tt ALLOCATE}
  statements; when the owners are active.
\item Local variables with the {\tt SAVE} attribute can be mapped onto
  any set of
  processors.  In this sense, they are much like global variables.  Like
  global variables, the restrictions ensure that an appropriate set of
  processors is active when memory is allocated for them.
\end{itemize}
\end{rationale}

\begin{implementors}
These restrictions ensure that HPF data distribution directives inside
an {\tt ON} block can be
implemented without relying on one-way communication outside of the
``current'' processing group.
They guarantee that the processors that need to allocate the memory
are active when the variable comes into existence.
\end{implementors}

\section{The ON Directive}
\label{sec-on}

The purpose of the {\tt ON} directive is to allow the programmer to
control the
distribution of computations among the processors of a parallel machine.
In a sense, this is the computational analog
of the {\tt DISTRIBUTE} and {\tt ALIGN} directives for  data.
The \texttt{ON} directive does this by specifying the active
processor set for a statement or set of statements.
This temporarily shrinks the active processor set and gives the
programmer more control.
If the computations in two \texttt{ON} blocks are not related (for
example, if the \texttt{ON} blocks are two iterations of an
\texttt{INDEPENDENT} loop), then they give the compiler clear
instructions for exploiting parallelism.

\subsection{Syntax of the ON Directive}

There are two flavors of the {\tt ON} directive: a single-statement form
and a multi-statement form.
The BNF for these directives is

\BNF
simple-on-directive \IS ON  home-expr [ , resident-clause ] [, new-clause ]

block-on-directive \IS simple-on-directive BEGIN

on-block \IS
        block-on-directive
        block
        end-directive

end-on-directive \IS END [ ON ]

home-expr \IS HOME( variable )
        \OR HOME( template-elmt )
        \OR ( processors-elmt )

template-elmt \IS template-name [ ( section-subscript-list ) ]

processors-elmt \IS processors-name [ ( section-subscript-list ) ]
\FNB

{\it resident-clause\/} will be defined in Section~\ref{sec-resident}.
For the present, it suffices to say that this is a form of the {\tt RESIDENT}
directive mentioned in the introduction.

{\it home-expr}, {\it template-elmt}, and {\it processors-elmt\/}
are  auxiliary syntax categories.
The \textit{home-expr} is often called the \texttt{HOME} clause, even
in cases when the keyword \texttt{HOME} is not used.
Note that {\it variable\/} is a Fortran syntax term that means
(roughly) ``a reference, including an array element, array section, or
derived type field''; {\it variable\/} does not include template or processor
elements since those are not first-class language constructs.
Note also that {\it block\/} is a Fortran syntax term for
``a series of statements treated as
a group'' --- for example, the body of a {\tt DO} construct.

{\it simple-on-directive\/} is an option under {\it
executable-directive\/} (see rule~\ref{executable-directive-rule}).
This means that
{\it simple-on-directive\/} can appear where an executable statement can.

{\it on-block\/} is a Fortran {\it executable-stmt}.
This syntax implies that the blocks can be nested, and if so they will
be properly nested.

\begin{rationale}
Note the use of parentheses in the last option of the home-expr rule
(involving processors-elmt).
This prevents the following ambiguity:
\CODE
      INTEGER X(4)          ! X(I) will be on processor I
!HPF$ PROCESSORS HOME(4)
!HPF$ DISTRIBUTE X(BLOCK)
      X = (/ 4,3,2,1 /)
!HPF$ ON HOME(X(2))
      X(2) = X(1)
\EDOC
If the parentheses were not required, where should the computation be
done?
\begin{enumerate}
\item Processor HOME(2) (i.e. the owner of X(2))?
\item Processor HOME(3) (i.e. use the value of X(2), before the assignment)?
\item Processor HOME(4) (i.e. use the value of X(2), after the
assignment)?
\end{enumerate}
The definition of {\tt ON} clearly indicates interpretation 1 is correct.  One
can get the effect of interpretation 2 by the directive
\CODE
!HPF$ ON(HOME(X(2)))
\EDOC
There is no way to get the effect of interpretation 3, short of building a
clairvoyant computer.
Introducing reserved keywords into Fortran was
suggested as a better solution to this problem, but was seen as too large a
change to the underlying language.
\end{rationale}

\subsection{Semantics of the ON Directive}

The {\tt ON} directive restricts the active processor set for
a computation to those named in its \textit{home-expr}.
That is, it advises the compiler to use the named processor(s) to
perform the computation.
Like the mapping directives {\tt ALIGN} and {\tt DISTRIBUTE}, this is
advice rather  than an absolute commandment;
the compiler may override an {\tt ON} directive.
Also like {\tt ALIGN} and {\tt DISTRIBUTE}, the {\tt ON} directive may
affect the  efficiency of computation, but not the final results.

\begin{implementors}
If the compiler may override the user's advice in an {\tt ON} directive, then
the compiler should also offer the user an option to force all directives
to be obeyed.
\end{implementors}

The single-statement {\tt ON} directive (i.e. {\it
simple-on-directive}) sets the active processor set for the first
non-comment statement that follows it.  It is said to apply to that
statement.
If the statement is a compound statement (e.g.  a {\tt DO}
loop or an  {\tt IF}-{\tt THEN}-{\tt ELSE} construct), then the {\tt
ON} directive also applies to all nested
statements therein.
Similarly, the block {\tt ON} directive (i.e.  {\it on-block})
applies the initial {\tt ON} clause to---i.e. sets the active processor
set for---all statements up to the matching {\tt END} directive.

The {\tt HOME} clause can name a program variable, a template, or a processors
arrangement.
For each of these possibilities, it can  specify a
single element or multiple elements.
This is translated into the
processor(s) executing the computation as follows:
\begin{itemize}
\item   If the {\tt HOME} clause names a program variable (that is, an
        array element
        or section), then every processor owning any part of that variable
        should execute the computation.  For example, if a is a
        distributed array, then
\CODE
!HPF$ ON HOME ( a(2:4) )
\EDOC
        tells the compiler to perform the statement on the processors owning
        {\tt a(2)}, {\tt a(3)}, and {\tt a(4)}.
        If {\tt a} were distributed {\tt BLOCK}, this might be one
        processor; if it were distributed {\tt CYCLIC}, it would be
        three processors (assuming that many processors were available).
\item   If the {\tt HOME} clause names a template element or section,
        then every processor owning any element of the template should
        execute the computation.
        The example above applies here as well, if {\tt a} is a
        template rather than an  array.
\item   If the {\tt HOME} clause names a processors arrangement, then
        the processor(s)
        referenced there should execute the computation.
        For example, if {\tt p} is a processors arrangement, then
\CODE
!HPF$ ON ( p(2:4) )
\EDOC
        will execute the following statement on the three processors
        {\tt p(2)}, {\tt p(3)}, and {\tt p(4)}.
\end{itemize}
The values of expressions in the {\it home-expr\/}
are determined as if they were evaluated when control flow
reached the {\tt ON} directive.
If evaluation of an expression in a {\tt HOME} clause would
change the value of any variable in the program, then the value of that
variable becomes undefined after the {\tt ON} clause is reached.

In every case, the {\tt ON} directive specifies the processor(s) which should
perform a computation.
More formally, it sets the active processors for the computation, as
described in Section~\ref{sec-active}.
That section also describes how some statements (notably
\texttt{ALLOCATE} and dynamic remapping directives) require that
particular processors be included in the active set.  If one of these
constructs occurs in the \texttt{ON} block and the active processor
set is not sufficient, then the program is not standard-conforming.
Note that this only specifies how computation is partitioned
among processors; it does not indicate processors that may be involved in
data transfer.
Also, the {\tt ON} clause by itself does not guarantee that its
body can be executed in parallel with any other operation.  However,
placing the computation can have a significant effect on data
locality.
As later examples will show, the combination of {\tt ON} and {\tt
INDEPENDENT} can also
provide control over load balancing parallel computations.

\begin{rationale}
This is the heart of the {\tt ON} clause.  It defines where computation is
performed, but not (by itself) what data are accessed.

The ``as if'' wording and making side effects undefined avoids the following
problem:
{\tt ON} is a directive.  Therefore, it cannot have side effects.  But
implementing the {\tt ON} clause may require evaluating some
functions, thereby causing the side effects.
Moreover, different systems may use different implementation
mechanisms.
Such dependencies on the implementation mechanism are outlawed by
making their effect undefined.
\end{rationale}

\begin{implementors}
If the HPF program is compiled into Single-Program-Multiple-Data (SPMD)
code, then the {\tt ON} clause can always be implemented (albeit
inefficiently)
by having all processors compare their processor {\it id} to an {\it id}
(or list of
{\it ids}) generated from the {\tt HOME} clause.
(Similar naive implementations can be constructed in other paradigms
as well.)
If the {\tt ON} clause will be executed
repeatedly, for example in a {\tt DO} loop, it is worthwhile
to invert this process.
That is, instead of all processors executing all the {\tt HOME}
clause tests, the compiler should determine the range of loop iterations
that will test true on the local processor.
(See the ``Advice to implementors'' in Section~\ref{sub-on-examples}
for more details.)
For example, consider the following complex case:
\CODE
DO I = 1, N
    !HPF$ ON HOME( A(MY_FCN(I)) ) BEGIN
        ...
    !HPF$ END ON
END DO
\EDOC
Here, the generated code can perform an ``inspector'' (i.e.  a skeleton loop
that only evaluates the {\tt HOME} clause of each iteration)
to produce a list of
iterations assigned to each processor.
This list can be produced in
parallel, since {\tt MY\_FCN} must be side-effect free (at least, the
programmer cannot rely on any side effects).
However, distributing the {\it home-expr} computation
to all processors may require unstructured communications patterns,
possibly negating the advantage of parallelism.  In general, more advanced
compilers will be able to efficiently invert more complex {\tt HOME}
clauses.
It is recommended that the abilities (and limitations) of a particular
compiler be documented clearly for users.

Note that processors "screened out" by the naive implementation may still
be required to participate in data transfer.
If the underlying architecture
allows one-sided communication (e.g. shared memory or {\tt GET}/{\tt
PUT}), this is not a problem.
On message-passing machines, a request-reply protocol may be used.  This
requires the inactive processors to enter a wait loop until the {\tt ON} block
completes, or requires the runtime system to handle requests
asynchronously.  Again, it is recommended that the documentation tell
programmers which cases are likely to be efficient and which inefficient
on a particular system.
\end{implementors}

\begin{users}
The form of the {\it home-expr\/} in an {\tt ON} directive can be
arbitrarily complex.
This is a two-edged sword;
it can express very complicated computation partitioning,
but the implementation of these partitions may not be efficient.  More
concretely, it may express a perfectly load-balanced computation, but force
the compiler to serialize the computation to implement the {\tt HOME}
clauses.
Although
the amount of overhead for an {\tt ON} clause will vary based on the HPF code,
the compiler, and the hardware, one can expect that compilers will generate
very good code based solely on array mappings or a named processor
arrangement, and progressively worse code as the complexity of the
{\it home-expr\/} increases.
A rough measure of the complexity of an {\tt ON} directive is
the amount of run-time data used to compute it; for example, a constant
offset is fairly simple, while a permutation array is very complex.  See
Section~\ref{sub-on-examples} below for more concrete examples of this
phenomenon.

It is worth noting that the {\tt ON} clause alone does not address
data movement.
(The {\tt RESIDENT} directive defined in Section~\ref{sec-resident}
does this.)
Therefore, on some machines additional
processors will have to enter the {\tt ON} block to take part in communication.

It should also be noted that the {\tt ON} clause does not change the semantics
of a program, in the same sense that {\tt DISTRIBUTE} does not change
semantics.  In particular, an {\tt ON} clause {\em by itself\/} does
not change  sequential code into parallel code,
because the code in the {\tt ON} block can
still interact with code outside the {\tt ON} block.
(To put it another way, {\tt ON} does not spawn processes.)
\end{users}

It is legal to nest {\tt ON} directives, if the set of active processors
named by  the inner {\tt ON} directive is included in the set of
active processors from the outer directive.
The syntax
of {\it on-block\/} automatically ensures that it is properly nested
inside other
compound statements, and that compound statements properly nest inside of
it.
As with other Fortran compound statements, transfer of control to
the interior of an {\it on-block\/} from outside the block is
prohibited, while  transfers within a block may occur.
However, HPF {\em also\/} prohibits transfers
of control from the interior of an {\it on-block\/} to outside the
{\it on-block}.
Note that this is stricter than in ordinary Fortran.
If {\tt ON} clauses are nested, then the
innermost {\it home-expr\/} effectively controls execution of the
statement(s).
A programmer can think of this as successively restricting the set of
processors at each level of {\tt ON} nesting;
clearly, the last restriction must be the strongest.
Alternately, the programmer can think of this as a
fork-join approach to nested parallelism.

\begin{rationale}
The restrictions about control flow into and out of an {\tt ON} block
essentially
make it a single-entry single-exit region, thus simplifying the semantics
considerably.
\end{rationale}

If an {\tt ON} directive includes a {\tt NEW} clause, the meaning is
the same as a {\tt NEW}
clause in an {\tt INDEPENDENT} directive.
The operation of the program would be
identical if the {\tt NEW} variables were allocated anew on every entry to the
{\tt ON} directive's scope, and deallocated on exit from the {\tt ON}
block.
That is, the {\tt NEW} variables are dead on entry (i.e. assigned
before use in the
{\tt ON} block) and dead on exit (i.e. not used after the {\tt ON}
block, unless first  reassigned).
In addition, {\tt NEW} variables cannot be remapped in the {\tt ON}
clause's scope, whether by {\tt REALIGN}, {\tt REDISTRIBUTE}, or by
parameter passing to subroutine calls.
If a variable appears in a \texttt{NEW} clause but does not meet
these conditions, then the program is not HPF-conforming.
{\tt NEW} variables are not considered by any nested {\tt RESIDENT}
directives, as detailed in Section~\ref{sec-resident}.

\begin{rationale}
{\tt NEW} clauses provide a simple way to create temporary variables.  This
ability is particularly important when {\tt RESIDENT} directives come
into play, as  will be clear below.
\end{rationale}

\begin{implementors}
Because they are not used outside of the {\tt ON} blocks, {\tt NEW}
variables need not be kept consistent before and after {\tt ON}
clauses.
Therefore, no communication outside of the active processor set,
determined by the {\tt ON} directive, is
required to implement  them.
Scalar {\tt NEW} variables should be replicated over the active
processor set,
or allocated in memory areas shared by the active processor set.
Note that memory must be dynamically allocated if there is a possibility that
multiple instances of the {\tt ON} block could be active concurrently.
This is similar to the requirements for implementing {\tt NEW}
variables in {\tt INDEPENDENT} loops.
\end{implementors}

\subsection{Examples of ON Directives}
\label{sub-on-examples}

The following are valid examples of {\tt ON} directives.  Most of them are
``reasonable'' in the sense that they illustrate idioms that programmers
might want to use, rather than contrived situations.  For simplicity, the
first several examples assume the following array declarations:
\CODE
        REAL A(N), B(N), C(N), D(N)
        !HPF$ DISTRIBUTE A(BLOCK), B(BLOCK), C(BLOCK), D(BLOCK)
\EDOC
One of the most commonly requested capabilities for HPF as to control how
loop iterations were assigned to processors.
(Historically, the {\tt ON} clause
first appeared to perform exactly this role in the Kali FORALL construct.)
This can be done by the {\tt ON} directive, as shown in the following examples:
\CODE
        !HPF$ INDEPENDENT
        DO I = 2, N-1
          !HPF$ ON HOME(A(I))
          A(I) = (B(I) + B(I-1) + B(I+1))/3
        END DO

        !HPF$ INDEPENDENT
        DO J = 2, N-1
          !HPF$ ON HOME(A(J+1)) BEGIN
            A(J) = B(J+1) + C(J+1) + D(J+1)
          !HPF$ END ON
        END DO
\EDOC
The {\tt ON} directive in the {\tt I} loop
sets the active processor for each iteration of the loop to be the
processor that stores \texttt{A(I)}.
In other words, it advises the compiler to have each processor
run over its local section of the {\tt A} array (and therefore {\tt B}
as well).
The references to {\tt B(I-1)} and {\tt B(I+1)} must be fetched from
off-processor for the
first and last iterations on each processor (except for the boundary
processors); note that those processors are not mentioned in the {\tt HOME}
clause.  The {\tt ON} directive in the {\tt J} loop similarly sets the
active set for each iteration, but advises the compiler to shift
computations. As a result, each processor does a vector sum of its local
sections
of {\tt B}, {\tt C}, and {\tt  D}, stores the first element of the
result on the processor to
its left, and stores the rest of the result (shifted by one) in {\tt A}.
It is worth noting that the directives would still be valid (and minimize
nonlocal data accesses) if the arrays were distributed {\tt CYCLIC},
although the number of nonlocal references would be much higher.

\begin{implementors}
It is highly recommended that compilers concentrate on optimizing
\texttt{DO} loops with a single {\tt ON} clause including the entire
loop body.  Schematically, the code will be:
\ICODE
        DO i = lb, ub, stride
            !HPF$ ON HOME(array(f(i))) BEGIN
            body
            !HPF$ END ON
        END DO
\EDOC
Where array has some data mapping.  Assume the mapping give processor p
the elements my_set(p).  (In a BLOCK distribution, for example, my_set(p)
is a contiguous range of integers.)  Then the generated code on processor
p should be
\begin{tt}
\obeylines\obeyspaces
\ \ \ \ \ \ \ \ DO \(i \in [lb:ub:stride] \cap f^{-1}(myset(p))\)
\ \ \ \ \ \ \ \ \ \ \ \ body
\ \ \ \ \ \ \ \ END DO
\end{tt}
(This schematic does not show where communication or synchronization must
be placed; that must be derived from analysis of the body.) Moreover, \(f\) is
likely to be the identity function or a linear function with integer
coefficients, both of which can be inverted easily.  Given this, techniques
for iterating through the set can be found in several recent conferences.
\end{implementors}

\begin{users}
One can expect the {\tt I} loop above to generate efficient code for the
computation partitioning.  In effect, the compiler will arrange for each
processor to iterate over its own section of array {\tt A}.  The {\tt
J} loop is  slightly more complex, since the compiler must find the
inverse of the {\tt HOME}
clause's subscripting function.  That is, the compiler must solve
{\tt K=J+1} for {\tt J}, where {\tt K} ranges over the local elements
of {\tt A}.
Of course, in this case {\tt J=K-1}; in general, linear functions can
be inverted by the compiler.
(It should be pointed out, however, that complex combinations of {\tt
ALIGN} and  {\tt DISTRIBUTE} may make the description of {\tt K}
unwieldy, and this may add overhead to the inversion process.)
\end{users}

Sometimes it is advantageous to ``split'' an iteration between processors.
The following case shows one example of this:
\CODE
        !HPF$ INDEPENDENT
        DO I = 2, N-1
          !HPF$ ON HOME(A(I))
          A(I) = (B(I) + B(I-1) + B(I+1))/3
          !HPF$ ON HOME C(I+1)
          C(I+1) = A(I) * D(I+1)
        END DO
\EDOC
Here, the active processor sets for the two statements in the loop
body are different.
Due to the first {\tt ON} clause, the reference to {\tt A(I)} is local
in the first statement.
The second {\tt ON} clause makes {\tt A(I)} nonlocal (for some values
of {\tt I})
there.  This maximizes the data locality in both statements, but does
require data movement between the two.

\begin{implementors}
If there are several non-nested {\tt ON} clauses in a loop, then the schematic
above needs to be generalized.  In essence, the iteration range for each
individual {\tt ON} clause must be generated.
A processor will then iterate over the union of these ranges.
Statements guarded by an {\tt ON} directive must now
be guarded by an explicit test.  In summary, the code for
\ICODE
        DO i = lb, ub, stride
            !HPF$ ON HOME(array_1(f_1(i)))
            stmt_1
            !HPF$ ON HOME(array_2(f_2(i)))
            stmt_2
        END DO
\EDOC
on processor \(p\) becomes
\begin{tt}
\obeylines\obeyspaces
\ \ \ \ \ \ \ \ \(set_1 = [lb:ub:stride] \cap f_1^{-1}(myset_1(p))\)
\ \ \ \ \ \ \ \ \(set_2 = [lb:ub:stride] \cap f_2^{-1}(myset_2(p))\)
\ \ \ \ \ \ \ \ DO \(i \in set_1 \cup set_2\)
\ \ \ \ \ \ \ \ \ \ \ \ IF (\(i \in set_1\)) THEN
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ stmt1
\ \ \ \ \ \ \ \ \ \ \ \ END IF
\ \ \ \ \ \ \ \ \ \ \ \ IF (\(i \in set_2\)) THEN
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ stmt2
\ \ \ \ \ \ \ \ \ \ \ \ END IF
\ \ \ \ \ \ \ \ END DO
\end{tt}
where \(myset_1(p)\) is the local set for \(array_1\), and \(myset_2(p)\) is
the local set for \(array_2\).
(Again, synchronization and communication must be handled
by other means.)  Code transformations such as loop distribution and loop
peeling can be used to eliminate the tests in many cases.  They will be
particularly profitable if there are data dependences between the {\tt ON}
blocks.
\end{implementors}

\begin{users}
Splitting an iteration like this is likely to require either additional
tests at runtime or additional analysis by the compiler.  Even if the
compiler can generate low-overhead scheduling for the individual {\tt ON}
clauses, combining them is not necessarily low-overhead.  The locality
benefits must be rather substantial for this to pay off, but there are
cases where multiple {\tt ON} clauses are valuable.  (All these statements are
particularly true if one {\tt ON} block uses data computed in another one.)
\end{users}

Because {\tt ON} clauses nest naturally, they can be useful for expressing
parallelism along different dimensions.  Consider the following examples:
\CODE
        REAL X(M,M)
        !HPF$ DISTRIBUTE X(BLOCK,BLOCK)

        !HPF$ INDEPENDENT, NEW(I)
        DO J = 1, M
          !HPF$ ON HOME(X(:,J)) BEGIN
            DO I = 2, M
              !HPF$ ON HOME(X(I,J))
              X(I,J) = (X(I-1,J) + X(I,J)) / 2
            END DO
          !HPF$ END ON
        END DO
\EDOC
The active processor set for each iteration of the \texttt{J} loop is
a column of the (presumably universal) processors
arrangement.  The {\tt I} loop further subdivides the computation, giving each
processor responsibility for computing the elements it owns.  Many
compilers would have chosen this computation partitioning automatically for
such a simple example.  However, the compiler might have attempted to fully
parallelize the outer loop, executing each inner loop sequentially on one
processor.  (This might be attractive on a machine with very fast
communications.)
By inserting the {\tt ON} clauses, the user has advised against
this strategy, thus trading additional locality for restricted parallelism.
Notice that the {\tt ON} directive neither requires nor implies the
{\tt INDEPENDENT} assertion.
In both nests, each iteration of the {\tt I} loop depends on the
preceding iteration, but the {\tt ON} directive can still partition the
computation among processors.
The {\tt ON} directive does not automatically make a loop parallel.

\begin{implementors}
``Dimension-based'' nesting, as above, will probably be a common case.  The
{\tt HOME} clauses can be inverted at each level, treating indices from outer
loops as run-time invariants.
\end{implementors}

\begin{users}
Nested {\tt ON} directives will tend to have efficient implementations
if their {\tt HOME} clauses refer to different dimensions of the
processors arrangements, as in the above example.
This minimizes the interaction between the levels
of the loops, simplifying the implementation.
\end{users}

Consider the following variation on the above example:
\CODE
        !HPF$ DISTRIBUTE Y(BLOCK,*)

        !HPF$ INDEPENDENT, NEW(I)
        DO J = 1, M
          !HPF$ ON HOME(Y(:,J)) BEGIN
            DO I = 2, M
              !HPF$ ON HOME(Y(I,J))
              Y(I,J) = (Y(I-1,J) + Y(I,J)) / 2
            END DO
          !HPF$ END ON
        END DO
\EDOC
Note that the {\tt ON} clauses have not changed, except for the name of the
array.  The interpretation is similar to the above, except that the outer
{\tt ON} directive assigns each iteration of the {\tt J} loop to all
of the processors.
The inner {\tt ON} directive again implements a simple owner-computes
rule.
The programmer has directed the compiler to distribute a serial computation
across all the processors.  There are a few scenarios where this is more
efficient than parallelizing the outer loop:
\begin{enumerate}
\item Parallelizing the outer loop will generate many non-local references,
   since only a part of each column is on any processor.
   If non-local references
   are very expensive (or if {\tt M} is relatively small), this overhead
   may outweigh any gain from parallel execution.
\item The compiler may take advantage of the {\tt INDEPENDENT}
   directive to avoid inserting any synchronization.
   This allows a natural pipelined execution.
   A processor will execute its part of the {\tt I} loop for one value
   of {\tt J}, then immediately go on to the next {\tt J} iteration.
   Thus, the first processor
   will start on {\tt J=2} while the second receives the data it needs (from
   processor one) for {\tt J=1}.  (A similar pipeline would develop in
   the {\tt X}  example above.)
\end{enumerate}
Clearly, the suitability of these {\tt ON} clauses will depend on the
underlying parallel architecture.

\begin{users}
This example points out how {\tt ON} may improve software engineering.
While the ``value'' of {\tt HOME(X(I))} will change if {\tt X}'s
mapping changes, its intent will usually stay the same - run the loop
``aligned with'' the array {\tt X}.  Moreover,
the form of the clauses is portable, and they simplify experimenting with
alternative computation partitioning.  Both qualities are similar to the
advantages of {\tt DISTRIBUTE} and {\tt ALIGN} over low-level data
layout mechanisms.
\end{users}

{\tt ON} directives are particularly useful when the compiler cannot
accurately estimate data locality, for example when the computation
uses indirection arrays.
Consider three variations of the same loop:
\CODE
        REAL X(N), Y(N)
        INTEGER IX1(M), IX2(M)
        !HPF$ DISTRIBUTE X(BLOCK), Y(BLOCK)
        !HPF$ DISTRIBUTE IX(BLOCK), IY(BLOCK)

        !HPF$ INDEPENDENT
        DO I = 1, N
          !HPF$ ON HOME( X(I) )
          X(I) = Y(IX(I)) - Y(IY(I))
        END DO

        !HPF$ INDEPENDENT
        DO J = 1, N
          !HPF$ ON HOME( IX(J) )
          X(J) = Y(IX(J)) - Y(IY(J))
        END DO

        !HPF$ INDEPENDENT
        DO K = 1, N
          !HPF$ ON HOME( X(IX(K)) )
          X(K) = Y(IX(K)) - Y(IY(K))
        END DO
\EDOC
In the {\tt I} loop, each processor runs over its section of the {\tt
X} array.  (That is, the active processor for iteration \texttt{I} is
the owner of \texttt{X(I)}.)
Only the reference {\tt X(I)} is guaranteed to be local.
(If \(M \neq N\), then {\tt IX} and {\tt IY}
have a different block size than {\tt X}, and thus a different mapping.)
However, if it is {\em usually\/} the case that {\tt X(I)}, {\tt
Y(IX(I))}, and {\tt Y(IY(I))} are
located on the same processor, then this choice of active processors
may be the best
available.  (If {\tt X(I)} and one of the other references are {\em always}
on the
same processor, then the programmer should add the {\tt RESIDENT} clause
as explained in Section~\ref{sec-resident}.)
In the next loop, iteration \texttt{J}'s active processor is the
owner of \texttt{IX(J)}.
Because \texttt{IY} has the same distribution as \texttt{IX},
reference {\tt IY(J)} is always local as well as \texttt{IX(J)}.
This is the most common array reference class in the loop, so it minimizes the
number of nonlocal data references in the absence of any special
properties of {\tt IX} and {\tt IY}.
It may not evenly balance the load among
processors; for example, if {\tt N=M/2} then half the processors will be idle.
As before, if the values in {\tt IX} or {\tt IY} ensure that one of
the {\tt Y} references is always local, a {\tt RESIDENT} assertion
should be added.
In the {\tt K} loop, only reference {\tt Y(IX(K))} is guaranteed to be
local (because {\tt Y} and {\tt X} have the same
distribution).
However, the values stored in {\tt IX} and {\tt IY} may ensure that
{\tt Y(IY(K))} and {\tt X(K)} always local.
Even if the three {\tt REAL} values are not always, but merely
``usually'' on the same processor, this may be a good computation
partitioning for both locality and parallelism.
However, these advantages must be weighed
against the cost of computing this partitioning.
Since the {\tt HOME} clause depends on a (presumably large) array of
runtime values, substantial time
may be required to determine which iterations are assigned to each
processor.  It should be clear from this discussion that there is no magic
solution for handling complex computation partitionings; the best answer
is usually a combination of application knowledge, careful data structure
design (including ordering of the elements), and efficient compilation
methodology and runtime support.

\begin{implementors}
The {\tt K} loop is the situation that the inspector strategy
described above was designed for.
If there is an outer loop around any of these examples, and
that loop does not modify the distribution of {\tt X} or the values of
{\tt IX}, then a record of each processor's iterations can be saved
for reuse.
The cost is at worst linear in the sizes of the arrays.
\end{implementors}

\begin{users}
It is unlikely that any current production compiler will generate
low-overhead code for {\tt K} loop.
The difference from previous examples
is that the {\tt HOME} clause is not a function that can be easily inverted by
the compiler.  Some compilers may choose to execute every iteration on all
processors, testing the {\tt HOME} clause at run-time; others may
pre-compute a
list of iterations for every processor.  Of course, the cost of computing
the list will be substantial.

In practice, one would make all the arrays the same size to avoid some of
the alignment problems above; the example was written this way for
pedagogical reasons, not as an example of good data structure design.
\end{users}

\subsection{ON Directives Applied to Subprogram Invocations}
\label{sub-on-subr}

The key rule about \texttt{ON} directives when applied to subprogram
invocations is that the invocation does not change the active
processor set.
In effect, the callee inherits the caller's active processors.
Thus,
\BNF
!HPF$ PROCESSORS P(10)
!HPF$ DISTRIBUTE X(BLOCK) ONTO P

!HPF$ ON ( P(1:3) )
      CALL PERSON_TO_PERSON()
!HPF$ ON ( P(4:7) )
      CALL COLLECT( X )
\FNB
calls \texttt{PERSON_TO_PERSON} on three processors, while it calls
\texttt{COLLECT} on four.
The actual argument to \texttt{COLLECT} does not reside completely on
the active set of processors.
This is allowed, with appropriate declarations of the corresponding dummy
argument as explained below.

The above rule has interesting implications for data distributions
within the called routine.
In particular, dummy arguments must be declared under the same
restrictions as local variables, thus ensuring that the \texttt{dummy}
is always stored on the active processor set.
This does not imply that the corresponding \texttt{actual} argument is
local, however.
Consider the possibilities for how a dummy can be explicitly mapped:
\begin{itemize}
	\item  \textbf{Prescriptive mapping:} If the actual is not mapped on
	the active processor set, it will be remapped.  This is exactly
	analogous to remapping a \texttt{BLOCK}-distributed array to
	\texttt{CYCLIC} via a prescriptive mapping.

	\item  \textbf{Descriptive mapping:} The user is asserting that the
	actual is already mapped onto the set of active processors.  If the
	assertion is true, then the dummy is already stored locally; if not,
	then the compiler inserts a remapping operation (and reports a
	warning, following the recommendations in Section~\ref{ch-mapping}).

	\item  \textbf{Transcriptive mapping:} In this case, a new
	restriction must be made to allow efficient access to the dummy
	argument.  \emph{If a dummy is transcriptively mapped, then the
	actual argument must be resident on the active processor set at the
	time of the invocation.}  This may be checked at run-time.
\end{itemize}
In summary, a dummy argument is always mapped to the set of active
processors, although the actual argument need not be (except in the case of
transcriptive mappings).

\begin{rationale}
The treatment of dummy arguments as local variables is consistent with
all previous Fortran (and FORTRAN) standards.
Moreover, it has the advantage that it reflects the usual expectations
and wishes of programmers.
Dummy arguments are not expected to create great inefficiencies in
Fortran programs; ensuring that they are always stored locally tends
to reinforce that expectation.
Also, programmers are used to ``pass by reference'' behavior, in which
arguments are not copied; the restrictions on data mapping to active
processor sets allow this implementation when the data is not remapped
on subprogram call.
One case of this deserves special mention---transcriptive mappings.
If the programmer wants to keep the data in place (the usual
expectation of \texttt{INHERIT} and related features)
and control which processors execute the computation (the meaning of
\texttt{ON}), then
the basic principles of active sets (set forth in
Section~\ref{sec-active}) imply that the data must be resident before
the call is made.
When remapping occurs due to explicit directives, then surely the user
expects a communication cost to accompany the remapping.

It should also be noted that these rules do not invalidate any HPF
programs written without using the \texttt{ON} directive.  In those
programs, the active processor set never changes (at least, not from
the view of the language).  Therefore, active and universal processors
arrangements can be used interchangeably, and the restriction on
use of transcriptive mappings is obeyed automatically.
\end{rationale}

\begin{implementors}
These restrictions imply that accesses to dummy arguments never
require one-sided communication if the argument is explicitly mapped
and the \texttt{ON} clause is used.
Of course, accesses to global data may still run into serious
complications.
If the compiler itself partitions the computation, it is not
restricted by the \texttt{ON} directive rules.
\end{implementors}

\begin{users}
The idea to remember in calling subprograms from an \texttt{ON} block
is this: make sure that the actual arguments are stored on the active
set.
If the subroutine interface uses transcriptive (``take anything'')
mappings, then this is a requirement.
If the subroutine uses any other type of mapping, then having local
actual arguments \emph{may} avoid the expense of remapping data.
(Of course, it does not by itself guarentee that remapping doesn't
occur---a prescriptive interface can force a
\texttt{BLOCK}-to-\texttt{CYCLIC} redistribution---but it does ensure
that the remapping is between active processors.  This allows simpler
and more efficient collective communications operations to be
generated in the runtime system.)
\end{users}

Let us return to the previous example:
\BNF
!HPF$ PROCESSORS P(10)
!HPF$ DISTRIBUTE X(BLOCK) ONTO P

!HPF$ ON ( P(4:7) )
      CALL COLLECT( X )
\FNB
If \texttt{COLLECT} were declared as
\BNF
      SUBROUTINE COLLECT( A )
!HPF$ DISTRIBUTE A(CYCLIC)
\FNB
then the call will be executed as follows:
\begin{enumerate}
	\item  \texttt{X} will be remapped from \texttt{BLOCK} on 10
	processors (i.e.\ all of \texttt{P}) to \texttt{CYCLIC} on 4
processors
	(i.e. \texttt{P(4:7)}).  This will be a many-to-many exchange pattern.

	\item  \texttt{COLLECT} will be called on processors \texttt{P(4)},
	\texttt{P(5)}, \texttt{P(6)}, and \texttt{P(7)}.  Accesses to
	\texttt{A} within the subroutine will be satisfied from the
	redistributed array on those processors.

	\item  \texttt{A} will be remapped back to the distribution of
	\texttt{X}.  This is the inverse of step 1.
\end{enumerate}
Note that the distribution of \texttt{A} is onto 4 processors (the
active processor set inside the call), not onto the universal
processor set.
If the interface is
\BNF
      SUBROUTINE COLLECT( A )
!HPF$ DISTRIBUTE A(BLOCK)
\FNB
then the process would be the same, except that there would
be a remapping from \texttt{BLOCK} on 10 processors to
\texttt{BLOCK} on 4 processors.  That is, the block size would
increase by 2.5 times (with related shuffling of data) and then
revert to the original.
Again, it is important to note that the distribution of \texttt{A} is
onto the active processor set rather than onto all of \texttt{P}.

The similar examples
\BNF
      REAL X(100,100), Y(100,100)
!HPF$ PROCESSORS P(4), Q(2,2)
!HPF$ DISTRIBUTE X(BLOCK,*) ONTO P
!HPF$ DISTRIBUTE Y(BLOCK,BLOCK) ONTO Q

      INTERFACE
        SUBROUTINE A_CAB( B )
        REAL B(:)
!HPF$   DISTRIBUTE B *(BLOCK)
      END INTERFACE

!HPF$ ON ( P(4:7) )
      CALL A_CAB( X( 1:100, 1 )
!HPF$ ON HOME( X(1:100,1) )
      CALL A_CAB( X(1:100,100) )
!HPF$ ON HOME( Y(1:100,1) )
      CALL A_CAB( Y(1:100,1) )
!HPF$ ON HOME( Y(99,1:100) )
      CALL A_CAB( Y(99,1:100) )
\FNB
can be explained as follows.
Calling \texttt{A_CAB(1:100,1)} on \texttt{P(4:7)} will produce a
remapping from 10 processors to 4, as in the example above.  (The
compiler would be expected to produce a warning in this case, as
explained in Section~\ref{ch-mapping}.)
Calling \texttt{A_CAB(X(1:100,100))} on \texttt{HOME(X(1:100,1))}
produces no such remapping (or warning), because the active processor
set does not change; therefore, the descriptive mapping correctly
asserts that the data is already on the right processors.
The last two examples, calling \texttt{A_CAB(Y(1:100,1))} and
\texttt{A_CAB( Y(99,1:100) )} on the homes of their arguments, are also
accomplished without remapping.
In both cases, the actual arguments are mapped \texttt{BLOCK}-wise
onto a subset of the processors (a column of \texttt{Q} in the first case,
a row of \texttt{Q} in the second).
Some compilers may not be able to generate code for these more complex
examples, however.

Two examples of transcriptive mapping are also useful:
\BNF
! Assume
! PROCESSORS P(4)
! is declared in a module
      REAL X(100)
!HPF$ DISTRIBUTE X(CYCLIC(5)) ONTO P

      INTERFACE
        SUBROUTINE FOR_HELP( C )
        REAL C(:)
!HPF$   INHERIT C
      END INTERFACE

!HPF$ ON HOME( X(11:20) )
      CALL FOR_HELP( X(11:20) )
!HPF$ ON ( P(1) )
      CALL FOR_HELP( X(51:60) )
\FNB
The first example is valid---the actual argument is (trivially)
distributed on the active processor set.
The second example is invalid---for example, element \texttt{X(51)} is stored
on \texttt{P(3)}, which is not in the active processor set for the call.
The second example would be valid if the \texttt{ON} directive
specified \texttt{P(3:4)} or \texttt{HOME(X(11:20))}, both of which
map to the same processor set.

Calls to \texttt{EXTRINSIC} subprograms also deserve mention.
The ``standard'' HPF 2.0 description of calling an \texttt{EXTRINSIC}
(Section~\ref{ch-extrinsic}) says in part:
\begin{quotation}
A call to an extrinsic procedure must be semantically equivalent to a
call of an ordinary HPF procedure. Thus a call to an extrinsic
procedure must behave {\it as if} the following actions occur\ldots
\begin{enumerate}

\item Exactly the same set of processors are visible to the HPF
environment before and after the subprogram call.

\end{enumerate}
\end{quotation}
This constraint is changed to read
\begin{itemize}
	\item  Exactly the same set of \emph{active} processors are
	available to the HPF environment before and after the subprogram call.

	\item  Exactly the same \emph{universal} processor set is visible
	to the HPF environment before and after the subprogram call.
\end{itemize}
The intent is the same as in the original language design.
Processors where data is stored can neither appear not disappear; nor
may the set of processors executing the program change without notice
to the program.
Similarly, some extrinsic kinds specify ``all processors must be
synchronized'' or ``execution of a local procedure on each
processor''; such language is understood to mean ``all \emph{active}
processors must be synchronized'' or ``execution of a local procedure on each
\emph{active} processor.''

\begin{rationale}
This gives the combination of \texttt{EXTRINSIC} procedures and
\texttt{ON} directives a fork-join model of parallelism, which seems
to be both natural and semantically clean.
\end{rationale}

If a procedure uses alternate return, then the target of the return must
be have the same active processor set as the \texttt{CALL} statement.
In effect, this means that labels
passed as arguments must refer to statements in the same {\tt ON} block as the
{\tt CALL} statement.

\begin{rationale}
This constraint is similar to the prohibition against
jumping out of an {\tt ON} block, and has the same justification.
\end{rationale}

Explicit use of \texttt{CALL}s in {\tt ON} directives is often
associated with task parallelism.  Several examples can be found
in Section~\ref{sec-tasking}.
The following example illustrates how processors can be used
for a one-dimensional domain decomposition algorithm:
\CODE
        !HPF$ PROCESSORS PROCS(NP)
        !HPF$ DISTRIBUTE X(BLOCK) ONTO PROCS

        ! Compute ILO(IP) = lower bound on PROCS(IP)
        ! Compute IHI(IP) = upper bound on PROCS(IP)
        DONE = .FALSE.
        DO WHILE (.NOT. DONE)
          !HPF$ INDEPENDENT
          DO IP = 1, NP
            !HPF$ ON (PROCS(IP))
            CALL SOLVE_SUBDOMAIN( IP, X(ILO(IP):IHI(IP)) )
          END DO
          !HPF$ ON HOME(X) BEGIN
            CALL SOLVE_BOUNDARIES( X, ILO(1:NP), IHI(1:NP) )
            DONE = CONVERGENCE_TEST( X, ILO(1:NP), IHI(1:NP) )
          !HPF$ END ON
        END DO
\EDOC
The algorithm divides the entire computational domain (array {\tt X})
into {\tt NP}
subdomains, one for each processor.  The {\tt INDEPENDENT} {\tt IP}
loop performs a computation on each subdomain's interior.
The {\tt ON} directive tells the compiler which processors to use in
executing these (conceptually) parallel operations. This can increase
data locality substantially, particularly if the compiler could not
otherwise analyze the data access patterns in {\tt SOLVE\_SUBDOMAIN}.
The subroutine {\tt SOLVE\_SUBDOMAIN} can use a transcriptive or descriptive
mapping for its array argument, placing it on a single processor.
In the next phase, the processors collaborate
to update the boundaries of the subdomains and test for convergence.
Subroutines {\tt SOLVE\_BOUNDARIES} and {\tt CONVERGENCE\_TEST} may
well have their own loops similar to the {\tt IP} loop, with
similar {\tt RESIDENT} clauses.
Note that only the lower and upper bounds of each
subdomain is recorded; this allows different processors to process
different-sized subdomains.  However, each subdomain must ``fit'' into one
processor's section of the {\tt X} array.

\begin{implementors}
The {\tt IP} loop above is likely to be a common idiom among programmers doing
block-structured codes.  In general, it can be implemented by inverting the
{\tt HOME} clause as was done above.
In the one-to-one case shown here (probably
very popular with programmers), it can be implemented by assigning the
processor id to the loop index variable and testing the range of the loop
(once).
\end{implementors}

\begin{rationale}
Some compilers will propagate the {\tt ON} information from the caller to the
callee at compile time, and some at run time.
Repeating the {\tt ON} clause in
the caller and callee will tend to give the compiler better information,
resulting in better generated code.
\end{rationale}

\section{The RESIDENT Directive}
\label{sec-resident}

The purpose of the {\tt RESIDENT} clause is to
identify data accessed by
the computation as local to the executing processor.
That is, \texttt{RESIDENT} asserts that certain references (or all
references) in its scope are stored on the active processor set.
The compiler can use
this information to avoid generating communication or to simplify
array address  calculations.
Note that whether a given data element is local depends on
two facts:
\begin{itemize}
\item   Where the data is stored (i.e. {\tt DISTRIBUTE} and {\tt
ALIGN} attributes for the variable)
\item   Where the computation is executed (i.e. its active set, as
specified by an {\tt ON} directive)
\end{itemize}
For these reasons, the {\tt RESIDENT} clause is added to the {\tt ON}
directive, which is usually the earliest point in the program
where the needed facts might  be available.
The {\tt RESIDENT} clause can also appear as a stand-alone directive;
this is useful when the locality information is not true for an entire
{\tt ON} region.
Note that changing the {\tt ON} directive may invalidate some
{\tt RESIDENT} clauses, or may make more {\tt RESIDENT} clauses true.
\BNF
resident-clause \IS     RESIDENT [ ( local-var-list ] ) ]

simple-resident-directive \IS resident-clause

block-resident-directive \IS resident-clause BEGIN

resident-block \IS
                block-resident-directive
                block
                end-resident-directive

end-resident-directive \IS END [ RESIDENT]

local-var \IS variable
\FNB
As for {\it simple-on-directive\/}, {\it simple-resident-directive}
is an option under  {\em executable-directive}
Similarly, {\it resident-block\/} fits as an Fortran {\it executable-stmt}.

Any top-level variables in the {\tt RESIDENT} clause must be explicitly
mapped.  Similarly, the \texttt{RESIDENT} clause must appear at a
point in the program with a declared active processor set (i.e.
inside an \texttt{ON} block).
Otherwise, the assertion (see below) is a statement about how the
compiler works, not about the program.

\begin{implementors}
{\tt RESIDENT} removes need for masked processors to
participate in communication into/out of an \texttt{ON} clause.
\end{implementors}

The {\tt RESIDENT} directive is an assertion to the compiler that
certain array references made within the {\tt ON} are stored in local
memory if the computation is performed by the specified active
processor set.
The scope of the assertion is the next Fortran statement if the
{\it simple-resident-directive\/} form is used and the enclosed {\it
block} of code if the {\it resident-block\/} form is used.
If {\tt  RESIDENT} appears as a clause in an {\tt ON}
directive, then the {\tt ON} and {\tt RESIDENT} apply to the same
statements.

{\tt RESIDENT(}{\it var}{\tt )} means the {\em lexical expression}
{\it var}, when encountered in the
execution of statements in the scope of the {\tt RESIDENT} directive, accesses
only data local to the set of active processors.
(That is, the set of processors named by the innermost available {\tt ON}
directive.)
If {\it var\/} is accessed by the statement (e.g.  it appears on
the right-hand side of an assignment statement, or in the evaluation of a
conditional expression), then at least one copy of the variable and any
subobject of the variable must be mapped to the active processors
set.
If {\it var\/} is assigned to by the statement (e.g.  it appears on
the left hand side of an assignment statement, or in the variable list
of a {\tt READ} statement), then
all copies of the variable and all subobjects of the variable must reside
in the active processors set.
The application of \texttt{RESIDENT} to \texttt{CALL} statements and
function invocations introduces some complexity into this
interpretation; these issues will be dealt with in
Section~\ref{sub-res-subr}.

Note that {\tt RESIDENT} is always an assertion relative to the
surrounding {\tt ON} directive.
Therefore, if the compiler does not implement the {\tt ON} directive
then it must be careful in interpreting {\tt RESIDENT}.
Similarly, if the compiler overrules the programmer-specified {\tt
ALIGN} and {\tt DISTRIBUTE} directives, then it may not rely on the {\tt
RESIDENT} clause in general.

Finally, {\tt NEW} variables are not considered by any nested {\tt RESIDENT}
directives, as detailed below.

\begin{rationale}
The different treatment of variable reads and writes is due to the
implementation requirements. If a variable's value is read (but not
written), then it can be taken from any consistent copy.  Therefore,
{\tt RESIDENT} only asserts that one of those copies is available.
Conversely, all copies of a replicated variable must be consistent, so
{\tt RESIDENT} asserts that all copies are available it it is updated.

The {\tt RESIDENT} assertion is always relative to the declared data
mappings and  {\tt ON} clauses because both pieces of information are
necessary to determine  the locality of data references.
Data mapping determines where the data is
stored, while {\tt ON} clauses determines where they are used; in essence they
determine the endpoints of a data path.
{\tt RESIDENT} itself says that the path
length is very short; obviously, one cannot measure a path without knowing
both endpoints.
\end{rationale}

For example, consider the following:
\CODE
        !HPF$ ON HOME(Z(I)), RESIDENT(X,Y,RECORD(I))
        X(I) = Y(I+1) + RECORD(I)%FIELD1 + RECORD(I+1)%FIELD2
\EDOC
The following facts are asserted by the directive:
\begin{itemize}
\item {\tt Z(I)} would be local if it appeared, due to its use in the
HOME directive.
\item All copies of {\tt X(I)} are stored on the same processor as
{\tt Z(I)}, due to the {\tt RESIDENT} clause.  This may be true
because {\tt X} and {\tt Z} have the same mapping, or because {\tt Z}
is replicated on all processors, or because the single copy of {\tt
X(I)} is the only element of {\tt X} mapped to the same processor as
the single copy of {\tt Z(I)}.  (Other situations are also possible.)
\item At least one copy of {\tt Y(I+1)} is on the same processor as
{\tt Z(I)}, due to the {\tt RESIDENT} clause.  This may be true
because {\tt Y} is replicated on all processors, because {\tt Z(I)}
and {\tt Y(I+1)} are the only elements of their arrays that are mapped
to the same processor, or because the directive
\CODE
        !HPF$ ALIGN Y(J) WITH Z(J-1)
\EDOC
appears elsewhere in the program.  (Other situations also make the
{\tt RESIDENT} assertion true.)
\item At least one copy of all subobjects of {\tt RECORD(I)} is mapped
on the same processor as {\tt Z(I)}.  In particular, the reference
{\tt RECORD(I)\%FIELD1} (i.e. a subobject consisting of one component)
can be accessed locally.   The situations in which this is true are
similar to those for {\tt X(I)}.  No information is available in this
example regarding {\tt RECORD(I+1)\%FIELD2}.
\end{itemize}

If there is no {\it local-var-list}, then {\em all\/} references to
{\em all} variables referenced during execution of the {\tt RESIDENT}
directive's body except those declared {\tt NEW} in a surrounding {\tt
ON} directive are local in the sense described above.
That is, for every usage of any variable's value, at least one copy
of the variable will be mapped to the {\tt ON} processor set.  Likewise, for
every operation that assigns to a variable, all copies of that variable are
mapped to the {\tt ON} processor set.  References and assignments to
{\tt NEW} variables are always considered local.
If there are no function or
subroutine invocations, this is syntactic sugar for listing all variable
references within the directive's scope.
(See Section~\ref{sub-res-subr} for a discussion of {tt RESIDENT}
clauses applied to subprogram calls.)
It might well have been named the
{\tt ALL\_RESIDENT} clause; the present form, however, does not add
yet another keyword to the directive sublanguage.

Note that if the active set includes more than one processor,
then {\tt RESIDENT} only asserts that the variables are stored on one
of the processors.
For example, if a statement is executed on a section of the processors
arrangement, then communication within that section may be needed for some
variables in the {\tt RESIDENT} clause.
Communication with processors outside of
the section will not be needed for those variables, however.

\begin{rationale}
The alternative to this interpretation would be that any variable named in
the {\tt RESIDENT} clause would be local to all processors, i.e. replicated.
While that certainly allows more extensive optimizations, it is a less
common case.  In addition, it does not seem to capture the intent of {\tt ON}
directives applied to {\tt CALL} statements or compound statements.  For
example,
\CODE
        !HPF$ PROCESSORS PROCS(MP,MP)
        !HPF$ DISTRIBUTE X(BLOCK,BLOCK) {\tt ONTO} PROCS
        !HPF$ ON HOME(PROCS(1,1:MP)), RESIDENT( X(K,1:N) )
        CALL FOO( X(K,1:N) )
\EDOC
would presumably call {\tt FOO} on a row of the processors
arrangement, passing elements of {\tt X} in place.
This is what the current definition does; if
{\tt RESIDENT} meant ``resident on every processor'', the call would
force {\tt X} to be replicated.
\end{rationale}

The {\tt RESIDENT} directive is similar to the {\tt INDEPENDENT}
directive, in that if it is correct it does not change the meaning of
the program.
If the {\tt RESIDENT} clause is incorrect, the program is not
standard-conforming (and is thus undefined).
Like the {\tt INDEPENDENT} directive, the compiler may use the
information in the {\tt RESIDENT} clause, or ignore it if it is
insufficient for the compiler's purposes.
If the compiler can detect that the {\tt RESIDENT} clause is
incorrect (i.e.  that a {\tt RESIDENT} variable is definitely nonlocal), it is
justified in producing a warning.  Unlike the {\tt INDEPENDENT} directive,
however, the truth of the {\tt RESIDENT} clause depends on the mapping of
computations (specified with the {\tt ON} clause) and the mapping of data
(specified with {\tt DISTRIBUTE} and {\tt ALIGN} clauses); if the
compiler overrides either of these, then it may not be able to use
information in the {\tt RESIDENT} directive.

\begin{rationale}
Knowing that a reference is local is valuable information for the
optimizer.  It is in keeping with the spirit of HPF to phrase this as an
assertion of fact, which the compiler can use as it pleases.  Expressing
it as advice to the compiler seems to have disadvantages.  Some possible ways
this advice could be phrased, and the counter-arguments, are
\begin{itemize}
\item   ``Don't generate communication for this reference'' has great potential
        for changing the meaning of the program.  Some programmers want this
        capability, but it violates the ``correct directives should
        not change the meaning of a program'' principle of HPF.
        Also, once communication is ``turned off'' for a reference,
        it's not clear how to turn it back on.
\item   ``Generate communication for this reference'' is not a useful
        directive,  since the compiler has to do this anyway.
\item   ``Generate communication for this reference, and place it
        here'' is useful, since it can override the default placement by the
        compiler.
        It still has potential for changing program meaning.
        It also has the potential to create programs as complex as
        message-passing, as programmers try to move communication out of
        loops.
\end{itemize}
\end{rationale}

\subsection{Examples of RESIDENT Directives}
\label{sub-res-exapmles}

As in Section~\ref{sub-on-examples}, our aim here is to suggest idioms
that may be generally useful to programmers.  We begin by expanding on
two earlier examples.

{\tt RESIDENT} is most useful in cases where the compiler cannot
detect access patterns.  Often this arises due to the use of
indirection, as in the following examples:
\CODE
        REAL X(N), Y(N)
        INTEGER IX1(M), IX2(M)
        !HPF$ PROCESSORS P(NP)
        !HPF$ DISTRIBUTE (BLOCK) ONTO P :: X, Y
        !HPF$ DISTRIBUTE (BLOCK) ONTO P :: IX, IY

        !HPF$ INDEPENDENT
        DO I = 1, N
          !HPF$ ON HOME( X(I) ), RESIDENT( Y(IX(I)) )
          X(I) = Y(IX(I)) - Y(IY(I))
        END DO

        !HPF$ INDEPENDENT
        DO J = 1, N
          !HPF$ ON HOME( IX(J) ), RESIDENT( Y )
          X(J) = Y(IX(J)) - Y(IY(J))
        END DO

        !HPF$ INDEPENDENT
        DO K = 1, N
          !HPF$ ON HOME( X(IX(K)) ), RESIDENT( X(K) )
          X(K) = Y(IX(K)) - Y(IY(K))
        END DO
\EDOC

As we saw in Section~\ref{sub-on-examples}, {\tt X(I)} is always local
in the {\tt I} loop and {\tt IX(I)} and {\tt IY(I)} rarely are.
The {\tt RESIDENT} directive above ensures that {\tt Y(IX(I))} is
local as well.  This would most likely be due to some property of the
algorithm that generated {\tt IX} (for example, if {\tt IX(I)=I} for
all {\tt I}).
Note that it is possible for an expression (e.g. {\tt Y(IX(I))}) to be
local even though one of its subexpressions ({\tt IX(I)}) is not.

The directive gives no information about {\tt
Y(IY(I))}; it might have only one nonlocal value, or all its values
might be nonlocal.  (We assume that if there were no nonlocal values,
then the {\tt RESIDENT} clause would include {\tt Y(IY(I))} as well.)
If there are many local elements referenced by this expression, and
they can easily be separated from the local elements, then it may be
worthwhile to restructure the loop to make this clear to the compiler.
For example, suppose that we knew that only the ``first'' and ``last''
{\tt X} elements on each processor were nonlocal.  The loop could then
be split thus:
\CODE
        !HPF$ INDEPENDENT, NEW(LOCALI)
        DO I = 1, N
          !HPF$ ON HOME( X(I) ), RESIDENT( Y(IX(I)), Y(IY(I)) ) BEGIN
            LOCALI = MOD(I,N/NP)
            IF (LOCALI\=1 .AND. LOCALI\=0) THEN
              X(I) = Y(IX(I)) - Y(IY(I))
            END IF
          !HPF$ END ON
        END DO
        !HPF$ INDEPENDENT, NEW(LOCALI)
        DO I = 1, NP
          !HPF$ ON (P(I)), RESIDENT( X(LOCALI), Y(IX(LOCALI)) ) BEGIN
            LOCALI = (I-1)*N/NP
            X(LOCALI) = Y(IX(LOCALI)) - Y(IY(LOCALI))
            LOCALI = I*N/NP
            X(LOCALI) = Y(IX(LOCALI)) - Y(IY(LOCALI))
          !HPF$ END ON
        END DO
\EDOC
The first loop (inefficiently) processes the local elements of {\tt
Y(IY(I))}, while the second (more efficiently) handles the rest.  On
most machines, it would pay to rewrite both loops to avoid the
division operations, for example by creating a logical mask {\em a priori}.

In the {\tt J} loop, the {\tt RESIDENT} clause asserts that all
accessed elements of {\tt Y} are local.  In this case, that is
equivalent to the assertion
\CODE
        !HPF$ RESIDENT( Y(IX(J)), Y(IY(J)) )
\EDOC
Although the original {\tt RESIDENT} clause only referred to the
lexical expression {\tt Y}, the compiler can infer that the
subexpressions are also local.  This is because it is impossible for a
subobject to be on a different processor than the ``parent'' object
is.  This observation can often shorten {\tt RESIDENT} clauses
substantially.

In the {\tt K} loop, the following references are local:
\begin{itemize}
\item {\tt Y(IX(K))}, because {\tt Y} has the same distribution as
        {\tt X} and {\tt X(IX(K))} is local (due to the {\tt ON} clause).
\item {\tt X(K)}, because of the {\tt RESIDENT} clause.
\end{itemize}
Note that a reference may be local even if it does not appear
explicitly in a {\tt RESIDENT} clause.  One mark of a good compiler
will be that it aggressively identifies these elements.

Because it is an assertion of act, the compiler can draw many inferences
from a single {\tt RESIDENT} clause.  For example, consider the following case:
\CODE
        !HPF$ ALIGN Y(I) WITH X(I)
        !HPF$ ALIGN Z(J) WITH X(J+1)

        !HPF$ ON HOME( X(K) ), RESIDENT( X(INDX(K)) )
        X(K) = X(INDX(K)) + Y(INDX(K)) + Z(INDX(K))
\EDOC
The compiler is justified in making the following assumptions in compiling
the assignment statement (assuming it honors both the ALIGN directives and
the {\tt ON} directive):
\begin{itemize}
\item {\tt X(K)} requires no communication (because of the {\tt HOME} clause)
\item {\tt X(INDX(K))} requires no communication (because of the
{\tt RESIDENT} clause)
\item {\tt Y(INDX(K))} requires no communication (because {\tt Y}
has the same mapping as {\tt X}, and {\tt INDX(K)} clearly cannot change
values between its use in the two references {\tt X(INDX(K))} and
{\tt Y(INDX(K)))}
\end{itemize}
The compiler cannot make any assumption about {\tt INDX(K)} or
{\tt Z(INDX(K))} from
the above code.  There is no indication how {\tt INDX} is mapped relative
to {\tt X},
so the {\tt ON} directive gives no guidance.  Note that the fact that an
expression (here, {\tt X(INDX(K))}) is local does not imply that its
subexpressions (here, {\tt INDX(K)}) are also local.
Similarly, {\tt Z}'s mapping does
not determine if {\tt Z(INDX(K))} would be local; it indicates that
{\tt Z(INDX(K)-1)}
is local, but that isn't a great help.  If the compiler has additional
information (for example, {\tt X} is distributed by {\tt BLOCK} and
{\tt INDX(K)} is not near
a block boundary), it might be able to make additional deductions.

\begin{implementors}
One mark of a good compiler will be that it aggressively propagates
{\tt RESIDENT}
assertions.  This is likely to significantly reduce communication costs.
Note the cases under "Advice to users" below.
\end{implementors}

\begin{users}
One can expect compilers to differ in how aggressive they are in drawing
these deductions.  Higher-quality compilers will be able to identify more
references as local, and use this information to eliminate data movement.
All compilers should recognize that if an element of one array is local,
then the same element of any other arrays with the same static mapping
(i.e.  arrays {\tt ALIGN}ed together, or with the same {\tt DISTRIBUTE}
pattern and array size) will also be local.
That is, any compiler should recognize
{\tt Y(INDX(K))} in the above example as local.  Dynamically changing array
mappings (i.e. {\tt REALIGN} and {\tt REDISTRIBUTE}) will tend to limit such
information and information propagation.  Also, assignments that might
change subexpressions (for example, an assignment to {\tt K} or any element of
{\tt INDX} in the above example) will force the compiler to be conservative in
its deductions.
\end{users}

\subsection{RESIDENT Directives Applied to Subprogram Invocations}
\label{sub-res-subr}

If a {\tt RESIDENT} directive applies to a {\tt CALL} statement or
function invocation, then the assertion is more subtle.

\begin{itemize}

\item    If a {\it local-var-list\/} appears in the {\tt RESIDENT}
directive, then no assertion is made about behavior within the called
procedure.
For example, consider the statements:
\CODE
        !HPF$ RESIDENT( A(I), B )
        A(I) = F( A(I), B(LO:HI) )
\EDOC
The directive declares all variable refences in the statement (including
the actual parameters) to be local to the current {\tt ON} processor set.
However, the execution of {\tt F} itself could access elements of arrays named
{\tt A} and {\tt B} stored on arbitrary processors.

\begin{rationale}
Propagating assertions about the behavior of lexical entities is difficult
to define consistently and usefully.  For example, consider the following
function called from the code fragment above:
\CODE
        REAL FUNCTION F( X, Y )
        REAL X, Y(:), B(I)
        !HPF$ ENVIRONMENT :: ON HOME(X)
        !HPF$ INHERIT Y
        !HPF$ ALIGN B(:) WITH Y(:)
        INTEGER I
        USE MODULE_DEFINING_A
        Z = 0.0
        DO I = 1, SIZE(Y)
            Z = Z + A(I)*X + B(I)*Y(I)
        END DO
        F = Z
        END
\EDOC
Assume {\tt A} is defined as a distributed, global array in module
{\tt MODULE\_DEFINING\_A}.
What should the {\tt RESIDENT} clause mean regarding operations in
{\tt F}?
The expression {\tt A(I)} in the {\tt RESIDENT} directive might
reasonably mean references only to the array {\tt A} that is visible in the
caller, or it might mean references to any array named {\tt A}.
Note that the {\tt A} in the caller may be local,
the same global array as the {\tt A} in {\tt F} (if the caller used
{\tt MODULE\_DEFINING\_A}),
or a different global array (if the caller used a different module).
Perhaps a limiting case is array {\tt B}.
The array {\tt B} in function {\tt F} is local, and thus different from the
caller; however, because of the restrictions on {\tt ON} clauses it is certain
that the local {\tt B} will be mapped to the {\tt ON} processors set.
Thus, the {\tt RESIDENT} assertion is trivially true.
To further confuse matters, {\tt RESIDENT} variables might seem to
apply to dummy arguments that become associated with those variables.
Unfortunately, this implies that the lexical expression {\tt B} in the
caller refers to the lexical expression {\tt Y} in {\tt F}, which
stretches the definition of ``lexical'' beyond the breaking point.
For all these reasons, it was decided to limit the meaning of named
variables in {\tt RESIDENT} clauses to the lexical scope of the directive.
\end{rationale}

\item If the {\tt RESIDENT} directive does not contain a {\it
local-var-list}, then the directive asserts that all references in the
caller {\em and the called procedures\/} are local as defined above.
For example, consider the statements:
\CODE
        !HPF$ RESIDENT
        A(I) = F( A(I), B(LO:HI) )
\EDOC
The directive declares all variable refences in the statement
(including the actual parameters) to be local to the current {\tt ON}
processor set, and that {\tt F} itself does not reference or update
any nonlocal variables.

\begin{rationale}
The {\tt RESIDENT} assertion is always true for data local to the called
procedure.  This is true because the called procedure must use a
declarative {\tt ON} clause, which in turn limits the set of
processors that can store any local explicitly mapped variables.
The above definition extends
this assertion to all global explicitly mapped data, producing a very
powerful directive.
This is similar to the meaning of {\tt INDEPENDENT}, in that
it also makes an assertion about variable accesses in any called procedure
in the loop.
An alternative semantics for {\tt RESIDENT} would have been to
avoid propagating the assertion interprocedurally (i.e.  treat both the
variable-list version and the no-list version the same).  However, this
would not provide enough information to optimize code on certain machines.
In particular, it would have made task parallelism quite difficult on
message-passing machines.
\end{rationale}

\end{itemize}

\begin{implementors}
{\tt RESIDENT} without a variable list guarantees that no one-sided
communication outside of the {\tt ON} processor set will be generated by the
callee.  Such a procedure can be called only on the ``active'' processors,
unless the runtime system has additional constraints (for example, if the
runtime system requires all processors to participate in collective
communications).

The other forms of {\tt RESIDENT} provide information that could be propagated
interprocedurally.
For example, if the actual argument to a subprogram is asserted to
be {\tt RESIDENT} and is passed transcriptively, then anything that is
{\tt ALIGN}ed to it in the callee will also be {\tt RESIDENT}.
If the information is not propagated, the only result
will be less optimization.
\end{implementors}

\begin{users}
Although the {\tt RESIDENT} assertion applies interprocedurally, it is by no
means certain that all compilers will make use of this information.  In
particular, separate compilation limits the propagation that can take
place.
It is therefore good practice to include a {\tt RESIDENT} clause
both in the caller's {\tt ON} directive and in the callee.
(This assumes that the assertion is true, of course!)
This ensures that the compiler has the {\tt RESIDENT} information
available when it is compiling both ends of the procedure call.
This is especially useful for {\tt RESIDENT} clauses without a
variable list; knowing that all data accessed is local allows many
optimizations that are not otherwise possible.
\end{users}

Locality information is particularly critical interprocedurally.
Here, the {\tt RESIDENT} directive without a {\it local-var-list\/}
can be used to good advantage.  Consider the following extension of
the block-structured example from Section~\ref{sub-on-subr}:
\CODE
        !HPF$ PROCESSORS PROCS(NP)
        !HPF$ DISTRIBUTE X(BLOCK) ONTO PROCS

        ! Compute ILO(IP) = lower bound on PROCS(IP)
        ! Compute IHI(IP) = upper bound on PROCS(IP)
        DONE = .FALSE.
        DO WHILE (.NOT. DONE)
          !HPF$ INDEPENDENT
          DO IP = 1, NP
            !HPF$ ON (PROCS(IP)), RESIDENT
            CALL SOLVE_SUBDOMAIN( IP, X(ILO(IP):IHI(IP)) )
          END DO
          !HPF$ ON HOME(X) BEGIN
            CALL SOLVE_BOUNDARIES( X, ILO(1:NP), IHI(1:NP) )
            !HPF$ RESIDENT
            DONE = CONVERGENCE_TEST( X, ILO(1:NP), IHI(1:NP) )
          !HPF$ END ON
        END DO
\EDOC
Recall that the {\tt INDEPENDENT} {\tt IP}
loop performs a computation on each subdomain's interior, where a
subdomain is mapped to a particular processor.
The first {\tt RESIDENT} clause additionally informs the compiler that no
subdomain uses data from another processor.
Without this information, the compiler would have to assume a
worst-case scenario in which each subdomain performed its updates
based on non-local read-only data.  Any nonlocal data could not be
written by another processor without violating the {tt INDEPENDENT}
directive; however, if the data were not updated (for example, a large
lookup table) it could be stored remotely.  Particularly on
nonshared-memory machines, access to this remote data would be
difficult.  The {\tt RESIDENT} clause ensures that this possibility
need not be considered.  All data required by {\tt SOLVE\_SUBDOMAIN}
is stored locally.
The second {\tt RESIDENT} clause asserts that all data for {\tt
CONVERGENCE\_TEST} is stored on the same processors that store {\tt
X}.  The same cannot be said for {\tt SOLVE\_BOUNDARIES}, which does
not fall in the scope of the {\tt RESIDENT} directive.
For example, there might be a processors arrangement other than {\tt
PROCS} with necessary data.
Accessing this data might well cause a bottleneck in the computation
as described above.

Again, note the usefulness of {\tt RESIDENT} clauses in giving the compiler
information.  Few compilers would be able to unravel nontrivial assignments
to ILO and IHI, and no current compiler would even attempt to understand
the comments in the above code fragment.
End of advice to programmers.

\section{The TASK\_REGION Directive}
\label{sec-tasking}

Task parallelism is expressed implicitly in HPF by mapping data
objects onto subsets of processors and adding assertions that
allow concurrent execution of different  code blocks on different
processor subsets. A data object is mapped to a processor subset
by distribution onto a
subsection of a processor arrangement.
Execution on a subset of processors is specified by using an
{\tt ON} directive. This section introduces a {\tt TASK\_REGION}
directive that allows the user to implicitly specify that
disjoint processor subsets can execute blocks of code concurrently.

A {\tt TASK\_REGION} directive is used to assert that a block of code
satisfies the following set of constraints.
All lexically outermost {\tt ON} blocks
inside a task region must have a {\tt RESIDENT} attribute
implying that all  data accessed inside them is mapped to the
corresponding active processor subset. Further,
the code inside two such {\tt ON} blocks must not have interfering
I/O. Under these constraints, two such {\tt ON} blocks
 can safely execute concurrently if they execute on disjoint
processor subsets.

\subsection{Syntax of the TASK\_REGION Directive}

A task region is a single entry region delimited by two structured
comments:
\BNF
task-region \IS !HPF$ TASK_REGION
      block
!HPF$ END TASK_REGION
\FNB

There must not be a transfer of control from outside the
{\em task-region} to inside the {\em task-region}.
Transfer of control out of the {\em task-region} is allowed
provided that the transfer does not originate inside an \texttt{ON}
block.
(The reason for this will be apparent later.)

\subsection{Semantics of the TASK\_REGION Directive}

We will refer to a block of code enclosed by a
{\tt TASK\_REGION ... END TASK\_REGION} pair as a {\em task region}.
The {\tt TASK\_REGION} directives are a way for the programmer to assert
that a section of code satisfies a set of conditions. The compiler
is expected to use these assertions to generate task parallel code.

A task region can contain blocks of code that are directed
to execute {\tt ON}
processor subsets.  All other code executes on a subset that
contains all active processors.  Every {\tt ON} block at the outermost
nesting level (i.e.  not inside another {\tt ON} block or another task
region) inside a
task region is defined as a {\em lexical task}.  Every execution instance of
a lexical task is defined as an {\em execution task} and will also be
referred to
as just {\em task} when the distinction is clear from the context.

The following restrictions must hold  inside a task region:
\begin{itemize}
\item Every {\tt ON} block corresponding to a lexical task must
have the {\tt RESIDENT} attribute.
This means that, for  reading a variable inside an execution task,
the executing processor subset for the task
(also referred to as {\em active processors})
must own at least one copy of the variable, and for writing, they must own
all copies of that variable.

\item An I/O operation inside an
execution task may interfere with an I/O operation inside
another execution task if and only if the two tasks execute on
identical subsets of  processors. Note that  two execution tasks
can be  instances of the same or different lexical tasks.
In general, two I/O operations interfere if they access the same
file or unit. The conditions for interference of I/O operations are
detailed in Section~\ref{do-independent} in the context of the
{\tt INDEPENDENT} directive.

\end{itemize}

\subsection{Execution Model and Usage}

A task region does not introduce a fundamentally new execution model.
However, the assertions implicit in a task region imply that only
the specified active processors of an execution task need to
participate in its execution, and that other processors can skip its
execution.  A processor executing a task
region participates in the execution of all tasks
executing on a processor subset that it belongs to and
does not participate in the  execution of tasks executing
on processor subsets that it does not belong to.
Code outside lexical tasks is
executed as normal data parallel code by all active processors.  The access
restrictions for a task region guarantee that the results obtained
by this execution paradigm will be consistent with pure data
parallel execution of a task region.

A task region presents a simple yet powerful model to write integrated
task and data parallel programs. We illustrate three basic computation
structures in which task parallelism can be effectively exploited
with this model.

\begin{enumerate}

\item {\em Parallel sections:}
A task region can be used to divide the available processors into
disjoint sets for performing independent computations, simulating
what is often referred to as {\em parallel sections}. This form of
task parallelism is relatively straightforward and useful in many
application scenarios, an example being multiblock applications.
The task region simply contains
a sequence of {\tt RESIDENT ON} blocks on disjoint processor subsets.
Note that the division of processors among subsets can be dynamic,
that is, it can be in terms of other variables computed during execution.

\item {\em Nested parallelism:}
Task regions can be nested, and in particular, a subroutine call made
from an execution task can further subdivide the executing (or active)
processors using another task region directive. This allows the exploitation
of nested parallelism. An example is the implementation of
dynamic tree structured divide and conquer computations. As a
specific example,
{\em quicksort} can be implemented by  recursively
partitioning the input array of keys
around a pivot and  assigning proportionate number of processors
to the two new arrays obtained as a result of partitioning.

\item {\em  Data parallel pipelines:}
Task regions can be used to implement
pipelined data parallel computations. We will
illustrate this with a 2 dimensional fast Fourier transform (2D FFT)
computation. The first stage of a 2D FFT reads a two dimensional matrix
and performs a 1 dimensional FFT on each row of the matrix. The second
stage performs a 1 dimensional FFT on each column of the matrix and generates
the final output. In a pipelined data parallel implementation of this
form of 2D FFT, the two stages are mapped on to disjoint subsets of processors.
Task and data parallel code for a 2D FFT, along with a brief
description, is included in Section~\ref{sec:2DFFT}.

\end{enumerate}

\subsection{Implementation}
A task region is simply an assertion about a code block and the
exploitation of task parallelism is at least partially dependent
on the compilation scheme. While the specifics of how task parallelism
is exploited will be strongly dependent on the parallel system
architecture, the compiler, and the  underlying communication
model, we will point out some  important considerations and
illustrate task parallel code generation with an example. We primarily
address distributed memory machines using a  message passing
communication and synchronization model, but will point out
some of the important issues relating to shared memory implementations.

\subsubsection{Localized computation and communication}
It is of central importance that computation and communication
inside an executing task should not  involve any processors
other than those directed to execute the task in the
relevant {\tt ON} clause.

On entry to a lexical task, the compiler has to insert checks so
that the processors not in the relevant subset jump to the code
following the task. Since an execution task cannot access data
outside of the active executing processor subset, no communication
needs to be generated between the relevant executing processors
and other processors. In a message passing model, a communication
generation algorithm that only generates necessary messages will
naturally achieve the desired results. However, some communication
schemes can involve generation of empty messages between processors
that do not communicate and it is important to ensure that empty
messages are not generated between active processors of an executing
task and other processors.

A communication model that uses barriers for synchronization (in
shared or distributed memory machines) must ensure that all barriers
inside an executing task are subset barriers that only span the
active processors. An implementation may also need to include a
subset barrier on entry to and exit from an executing task for consistency
of data accesses inside and outside an executing task. In general,
the compilation framework has to ensure the consistency of data
accesses inside and and outside an executing task and this can be done
in the context of  virtually any synchronization scheme in a shared
or distributed memory environment.

\subsubsection{Replicated computations}
All computations exclusively involving replicated variables should be
replicated on all executing processors.
A simple alternative is that  one processor performs the
computation and broadcasts the results to all processors. While such
replication
is generally profitable in HPF anyway, it has additional importance
in a task region since the communication generated by a broadcast can
cause additional synchronization that may interfere with
task parallelism.

\subsubsection{Implications for I/O}
In some parallel system implementations, I/O is performed through
a single processor of the system. Task parallelism in the presence of
I/O assumes that all processors can perform I/O independently and this
paradigm has to be supported, although it is not necessary that
each processor be able to physically perform all I/O operations
independently.
One simple solution is to have a single
designated I/O processor that performs
all I/O but is not considered an executing processor and hence does
not have any execution related dependences.

\subsubsection{SPMD or MIMD code generation}
Another issue for the compiler is whether or not the same code image
should execute on all processors. Since different processor groups
may need different variables, a naive SPMD implementation is likely
to be wasteful of memory since it must allocate all variables on
all processors. This can be addressed by dynamic memory allocation,
but at the cost of added complexity. Using different code images for
different processor subsets is another solution that leads to
significant added complexity.

\subsection{Example: 2-D FFT}
\label{sec:2DFFT}

This section shows the use of task parallelism to build
a pipelined data-parallel 2-dimensional FFT and illustrates
the compilation of task parallelism by  showing
SPMD code generated from the HPF program.

The basic  sequential 2DFFT code is as follows:
\CODE
      REAL, DIMENSION(n,n) :: a1, a2

      DO WHILE(.true.)
          READ (unit = 1, end = 100) a1
          CALL rowffts(a1)
          a2 = a1
          CALL colffts(a2)
          WRITE (unit = 2) a2
          CYCLE
100       CONTINUE
          EXIT
      ENDDO
\EDOC

To write a pipelined task and data parallel 2D FFT
in HPF, the code is slightly modified and several HPF
directives are added.
First,  variables {\tt a1} and {\tt a2} are distributed onto disjoint
subsets of processors, and then a task region is used to create two
lexical tasks to do {\tt rowffts}  and {\tt colffts} on different
subsets of processors. The assignment {\tt a2 = a1} in the task region
specifies transfer of data between the tasks. A new variable {\tt done1}
is introduced to store the termination condition.
The modified code is as follows:

\CODE
        REAL DIMENSION(n,n) :: a1,a2
        LOGICAL done1
!HPF$   PROCESSORS procs(8)

!HPF$   DISTRIBUTE a1(block,*) ONTO procs(1:4)
!HPF$   DISTRIBUTE a2(*,block) ONTO procs(5:8)

!HPF$   TEMPLATE, DIMENSION(4), DISTRIBUTE(BLOCK) ONTO procs(1:4) :: td1
!HPF$   ALIGN WITH td1(*) :: done1

!HPF$   TASK_REGION
        done1 = .false.
        DO WHILE (.true.)
!HPF$       ON HOME(procs(1:4)) BEGIN, RESIDENT
              READ (unit = iu,end=100) a1
              CALL rowffts(a1)
              GOTO 101
    100       done1 = .true.
    101       CONTINUE
!HPF$       END ON

            IF (done1) EXIT
            a2 = a1

!HPF$       ON HOME(procs(5:8)) BEGIN, RESIDENT
               CALL colffts(a2)
               WRITE(unit = ou) a2
!HPF$       END ON
        ENDDO
!HPF$   END TASK_REGION
\EDOC

Finally, we show simplified SPMD code generated
for each processor. We assume
a  message passing model where sends are asynchronous and nonblocking
and receives block until the data is available. We use a simple memory
 model where variable declarations are identical across
all processors even though some variables will be referenced only on
subsets of the processors.
A shadow variable {\tt done1\_copy} is created by the compiler to
transfer information from processor subset 1 to processor subset 2
about termination of processing. The code is as follows:

\CODE
        REAL DIMENSION(n/4,n) :: a1
        REAL DIMENSION(n,n/4) :: a2
        LOGICAL done1

C       Following are compiler generated variables
        LOGICAL done1_copy
        LOGICAL inset1, inset2
C
C       Following magic compiler function call is to set the variables
C       inset1 and  inset2 to .true. for subset 1 and subset 2 processors
C       respectively, and .false. otherwise.
C
        CALL initialize_tasksets(inset1,inset2)

C       Code for processor subset 1
        IF (inset1)
           done1 = .false.
           DO WHILE (.true.)

C       Read is left unchanged as the code depends on the I/O model
              READ (unit = 1,end=100) a1

              CALL rowffts(a1)
              GOTO 101
    100       done1 = .true.
    101       CONTINUE
              _send(done1,procs(5:8))
              IF (done1) EXIT
              _send(a1,proces(5:8))
           ENDDO
         ENDIF

C       Code for processor subset 2
        IF (inset2)
           DO WHILE(.true.)
              _receive(done1_copy,procs(1:4))
              IF (local_done1) EXIT
              _receive(a2,procs(1:4))
              CALL colffts(a2)

C       Write is left unchanged as the code depends on the I/O model.
              WRITE (unit = 2) a2
           ENDDO
        ENDIF
\EDOC

{\tt \_send} and {\tt \_receive} are  communication calls to
transfer variables between subsets of processors. Program execution
until the end of input is as follows.
Subset 1 processors repeatedly read input, compute
{\tt rowffts}, and send the computed output as well as {\tt done1} flag,
which normally has the value {\tt .false.},
 to subset 2 processors. The subset 2 processors
receive the flag and the data set, compute
{\tt colffts} and write the results to the output. When the end of input is
reached, subset 1 processors set the value
 flag {\tt done1} to {\tt .true.}, send it and terminate
execution. Subset 2 processors receive the flag, recognize that the end of
input has been reached, and terminate execution.

---------------------------------------------------------------------------
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>
---------------------------------------------------------------------------