Subject: hpff-doc: Task region changes in parallel-ext.tex

From: [email-masked]
Date: Thu, 29 Aug 1996 15:51:19 -0500 (CDT)

---------------------------------------------------------------------------
[email-masked] is a mailing list for HPF 2.0 language specification
authors and editors.  Instructions for adding or deleting yourself from this
list appear at the bottom of this message.
---------------------------------------------------------------------------
[I just realized that the task region changes have not propagated to the
 current draft. I am resending the corresponding chapter with the changes
 i.e. current text from the ftp site + new TASK_REGION section. We should
 probably place this on the ftp site and then update it with new ON  and
 RESIDENT sections when they are ready. -- jas]

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

{\em
Comments on this chpater should be directed to 
Chuck Koelbel ({\tt [email-masked]}),
Jaspal Subhlok ({\tt [email-masked]}),
and {\tt [email-masked]}.
Please use ``{\tt Comments on Extended Parallelism}'' as the {\tt Subject:}
line.
\par
}

There are three major Approved Extensions related to parallel
execution:
\begin{enumerate}
\item The {\tt ON} directive, which 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, which asserts that certain data
accesses do not require interprocessor data movement for their
implementation.
\item The {\tt TASKING} construct, which provides an abstract form of
task parallelism in HPF.
\end{enumerate}
Although they are separate constructs, these features have a strong
interaction.  {\tt RESIDENT} requires a notion of where an operation
is being performed in order to make its assertion; this information is
typically supplied by an {\tt ON} directive.  Similarly, the {\tt
TASKING} feature uses {\tt ON} blocks to identify the parallel tasks.
We therefore discuss {\tt ON} in the first section below, and take up
{\tt RESIDENT} and {\tt TASKING} in Sections~\ref{sec-resident}
and~\ref{sec-tasking}, respectively.

\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 dual of the {\tt DISTRIBUTE} and {\tt ALIGN}
directives for  data.
Modern parallel machines will achieve their best performance if all 
operations are performed by separate processors (as specified by {\tt
ON}) with  
each processor accessing its local data (as specified by {\tt DISTRIBUTE}).  
As such, the highest-performing programs will be those for which the
computation partitioning and data mapping work in synergy.
The definition of the {\tt ON} directive is designed to promote this
synergy by referring to the locations of data in order to define the
location of computation.

\subsection{Syntax of the ON Directive}

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

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

decl-on-directive \IS ENVIRONMENT :: simple-on-directive

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

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

end-directive \IS END [ BEGIN ]

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

\begin{constraints}
\item Any expressions in the {\it home-expr\/}
of a {\it decl-on-directive\/} must be specification expressions.
(Expressions in a {\it simple-on-directive} that is not part of a {\it
decl-on-directive\/} are not so constrained.)
\end{constraints}

{\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 just auxiliary syntax 
categories.  
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\/} doesn't 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 decl-on-directive\/} is an option under {\it
specification-directive\/} (see rule~\ref{specification-directive-rule}), as 
{\it distribute-directive\/} is now. 
 This means that {\it decl-on-directive\/} can appear 
where a declaration can.  

{\it on-block\/} most naturally fits as a Fortran {\it
executable-stmt}.
This implies that such blocks are 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.

Separate syntax is needed for simple-on-directive and decl-on-directive 
to avoid ambiguity.  If the same directive can be used as both both an 
executable statement and a declaration, its role is unclear if it is the 
last statement in the declarations/first statement in the executable 
section.  This is particularly bad since the "scope" of the directive is 
rather different in the two uses.
\end{rationale}

\subsection{Semantics of the ON Directive}

The {\tt ON} directive advises the compiler to perform a computation using the 
processor(s) named in the {\it home-expr}.  It has three forms:
\begin{itemize}
\item {\it simple-on-directive\/} and {\it on-block}, which apply to
the next executable  statement or a block of executable statements,
respectively. 
\item {\it decl-on-directive}, which is a declaration for an entire scope.
\end{itemize}
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}) precedes the  
statement for which it is advising behavior, and 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 all statements up to the
matching {\tt END} directive.  
The declarative form of the {\tt ON} directive (i.e.  
{\it decl-on-directive}) applies to all statements and declarations in
a scope;
its intended use is for functions and subroutines that may be called on a 
subset of the processors.

The {\tt HOME} clause can name a program variable, a template, or a processors 
arrangement.  
For each of these possibilities, it can further specify a 
single element or multiple elements.  
This is translated into the 
processor 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}
For the executable forms of the directive, the values of expressions
in the {\it home-expr\/}
are determined as if the expression was evaluated when control flow 
reached the {\tt ON} directive.  
For the declarative form, the values are determined on entry to the scope.  
That is, if the value of a variable used 
in the {\tt HOME} clause changes within an {\it on-block}, work is not
migrated to a  new processor.  
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.  This means that these processors should execute all 
operations required to execute the statements {\em except\/} (perhaps) for the 
initial access of data and writing of results.  
For example, consider the directive and statement
\CODE
        !HPF$ ON HOME( Z(2) )
        X(1) = X(1) + Y(2) * Z(3)
\EDOC
Assume that {\tt X}, {\tt Y}, and {\tt Z} are distributed in some way.
Following the {\tt ON} directive, the statement would be executed as
follows:
\begin{enumerate}
\item   The values of {\tt X(1)}, {\tt Y(2)}, and {\tt Z(3)} are made
        available to the processor owning {\tt Z(2)}.  
        Depending on the hardware running the program, 
        this might correspond to one processor loading registers from
        memory, or 
        it might mean three processors sending messages (and one processor 
        receiving them).
\item   Processor {\tt HOME(Z(2))} performs an addition and a
        multiplication, using the values sent in the last step.  
        That previous data movement allows these operations 
        to be performed locally.
\item   The result is stored to {\tt X(1)}, which may be on a
        different processor  than {\tt Z(2)}.  
        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.
Note that the {\tt HOME} clause 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 dependences 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 id to an id (or list of 
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 probably 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 BEGIN
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 processors
named by  the inner {\tt ON} directive is included in the set of
processors named by 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}

Operations controlled by an {\tt ON} clause must obey certain restrictions:
\begin{itemize}

\item If an {\tt ON} directive applies to a {\tt DISTRIBUTE} directive
whose {\it distributee} is a local variable with neither the
{\tt SAVE} nor the {\tt ALLOCATABLE} attribute, 
then the set of processors named in the {\it home-expr\/} must include
\begin{itemize}
\item All processors named in the {\it DISTRIBUTE}'s {\tt ONTO} clause
if one is present
\item All processors in the default processors arrangement otherwise
\end{itemize}

\item If an {\tt ON} directive applies to a {\tt ALIGN} directive
whose {\it alignee\/} is a local variable with neither the {\tt SAVE}
nor {\tt ALLOCATABLE} attribute, then the set of processors named in
the {\it home-expr\/} must include
all processors that store any element of the {\it align-with-clause}.

\item If an {\tt ON} directive applies to a {\tt REDISTRIBUTE} directive,
then the set of  processors named in the {\it home-expr} must include 
\begin{itemize}
\item All processors that stored any element of the {\it
distributee\/} before the {\tt REDISTRIBUTE} was encountered
\item The processors required by an equivalent {\tt DISTRIBUTE}
directive
\end{itemize}

\item If an {\tt ON} directive applies to a {\tt REALIGN} directive,
then the set of processors named in the {\it home-expr\/} must include
\begin{itemize}
\item All processors that stored any element of the {\it alignee} before 
          the {\tt REALIGN} was encountered
\item The processors required by an equivalent {\tt ALIGN} directive
\end{itemize}

\item If an {\tt ON} directive applies to an {\tt ALLOCATE} statement
which creates an explicitly mapped variable, then the set of
processors named in the {\it home-expr\/} 
must include the processors required by the mapping directive for the 
allocated variable.  

\item If the {\tt ON} directive applies to a 
{\tt DEALLOCATE} statement that destroys an explicitly mapped
variable, then the {\it home-expr\/} must include all processors that
owned any element of that variable.
\end{itemize}
If operations within an {\tt ON} block do not follow these
rules, then the  program is not HPF-conforming.

{\bf Note to language designers:}\\
An alternative for the DISTRIBUTE would be that an missing {\tt ON}TO clause 
would mean "distribute on all processors in the nearest enclosing {\tt ON} 
directive" rather than "distribute on all processors".  In some sense, this 
makes the nested fork-joins more modular (declarations inside a forked 
region only need to know about the region they are part of).  It is 
especially appropriate now that we have the declarative {\tt ON} directive.  I 
have not investigated the difficulty of writing things this way, but it 
probably requires fine-tooth combing through the data mapping chapter and 
inquiry intrinsics.\\
{\bf End of note to language designers.}

\begin{rationale}
Operations which allocate memory require the cooperation of all processors 
that will own that memory.  Therefore, {\tt ON} clauses must schedule those 
operations to execute on the cooperating processors.  This leads to 
constraints on the mappings of variables allowed in {\tt ON} clauses.
The most 
common case where these apply is in subroutines called from {\tt ON} clauses; 
such subroutines must have a declarative {\tt ON} clause that applies to all 
{\tt DISTRIBUTE} and {\tt ALIGN} directives for local variables, dummy
arguments, and  global data.

An alternate description of these constraints is:
\begin{itemize}
\item Local variables that are not {\tt SAVE}d can only be mapped to
  the processors 
  executing the surrounding {\tt ON} clause.  This ensures that all local 
  variables are allocated within the {\tt ON} processor set, and that
  all references to local variables will be {\tt RESIDENT} as defined below.
\item Dummy arguments and result variables can only be mapped to the
  processors 
  executing the {\tt ON} clause.  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 all processors
  (or onto any 
  subset of processors that could normally be used).  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, 
  which will be dealt with below.
\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, it is possible to ensure that an appropriate set of 
  processors is active when memory is allocated for them.
\item {\tt ALLOCATABLE} variables have their mapping determined when they are 
  allocated.  Therefore, the restrictions on those mappings are applied to 
  the {\tt ALLOCATE} statement.
\end{itemize}
\end{rationale}

\begin{implementors}
These restrictions ensure that HPF data distribution directives inside 
an {\tt ON} block (either lexically or in a dynamic call chain) can be 
implemented without relying on one-way communication outside of the 
``current'' processing group.
\end{implementors}

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.  
Finally, {\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 {\tt ON} processor set is
required to implement  them.  
Scalar {\tt NEW} variables should be replicated over the {\tt ON}
processor set,  
or allocated to memory areas shared by the {\tt ON} 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{ON Directives Applied to Subprogram Invocations}
\label{sub-on-subr}

It is legal for an {\tt ON} directive to apply to a {\tt CALL}
statement or a statement  containing a function invocation.  
The {\tt ON} directive tells the compiler 
which processors should execute the statements in the procedure body.
Any procedure which is called from a statement controlled by an {\tt
ON} directive must have an explicit interface in the caller.  
Furthermore, the interface must include a valid declarative {\tt ON}
directive which applies to the entire called procedure.  
(I.e.  If an {\tt INTERFACE} block is used, 
then the {\tt INTERFACE} specification must include an
{\tt ENVIRONMENT ::  ON} clause.)  
The treatment of {\tt ON} clauses in the interface is similar to that 
for a compound statement.  Any processor named by an {\tt ON} directive inside 
the subroutine must be included by the {\tt ON} directive in the caller.  In 
particular, the declarative {\tt ON} directive in the interface must name a 
subset of the processors in the caller's {\tt ON} clause, and any {\tt
ON} clauses in  
the subroutine itself can only restrict the declarative {\tt ON} directive's 
processor set further.  If {\tt ON} clauses appear in a subroutine call chain, 
then the deepest {\tt ON} clause (i.e.  the one in the last called
routine that is still active) effectively controls the computation.

Note that {\tt EXTRINSIC} procedures always have an explicit
interface, and thus  will require an {\tt ON} declaration if they are
called from an {\tt ON} block.  
In this case, the effect of the call is still as if the procedure were called 
on all processors.
 
If the procedure uses alternate return, then the target of the return must 
be in the same {\tt ON} block as the CALL statement.  This implies that labels 
passed as arguments must refer to statements in the same {\tt ON} block as the 
{\tt CALL} statement.

\begin{rationale}
It is natural to treat a procedure call within an {\tt ON} clause as
if it were  an in-lined program block.  
This leads to "propagating" the {\tt ON} directive 
into the procedure.  
Making the {\tt ON} directive explicit in the callee allows 
separate compilation (i.e.  the compiler need not perform interprocedural 
analysis in order to select the calling convention).

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

\begin{implementors}
Notice that nested {\tt ON} clauses do not present additional problems for the 
naive implementation.  If a processor failed the outer {\it home-expr}
comparison,  then it would fail any tests inside the {\tt ON} as well.
Thus, it need not even make the tests.

The difficulties of implementing one-way communication on message-passing 
machines remain, however.
\end{implementors}

\begin{users}
A {\tt CALL} statement from within an {\tt ON} block effectively executes the 
subroutine on a subset of processors.  In conjunction with other 
declarations, this allows a fork-join style of parallelism.

Note that the earlier advice regarding data movement still applies.  
Message-passing machines may need to perform the call statement on many 
(even all) processors in order to properly exchange data between 
processors.
\end{users}

Explicit use of processors arrangements in {\tt ON} directives is usually 
associated with task parallelism.  Several examples can be found
there.
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 BEGIN
        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 computiler 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 propogate 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}

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

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 BEGIN
        END DO
\EDOC
The {\tt ON} directive in the {\tt I} loop 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 advises the
compiler to ``shift''  
computations so that 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 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 BEGIN
        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
\ICODE
        DO i in [lb:ub:stride] intersect finverse(my_set(p))
                body
        END DO
\EDOC
(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
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 
\ICODE
        set_1 = [lb:ub:stride] intersect f_1inverse(myset_1(p))
        set_2 = [lb:ub:stride] intersect f_2inverse(myset_2(p))
        DO i in set_1 union set_2
          IF (i in set_1) THEN
            stmt1
          END IF
          IF (i in set_2) THEN
            stmt2
          END IF          
        END DO
\EDOC
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 BEGIN
        END DO
\EDOC
Each iteration of the {\tt J} loop is executed by a column of the 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 
preceeding 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.  
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 mapping may be the best one 
available.  If {\tt X(I)} and {\tt Y(IX(I))} are {\em always} on the
same processor, then the {\tt RESIDENT} clause should be added as
explained in Section~\ref{sec-resident}
\CODE
        !HPF$ ON HOME( X(I) ), RESIDENT( Y(IX(I)) )
\EDOC
This will avoid communication setup overhead on most systems, and there is 
little chance that the compiler would deduce this automatically.  If both 
references to {\tt Y} are {\em always} on the same processor as {\tt
X(I)}, then further improvement is possible and desirable, as
explained in Section~\ref{sec-resident}
In the {\tt J} loop, references {\tt IX(J)} and {\tt IY(J)} are always
local.  
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 is 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}

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

The purpose of the {\tt RESIDENT} clause is to work together with the ON
directive to  identify data accessed by 
the computation as local to the executing processor.  
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 {\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 some new {\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-directive

local-var \IS variable
\FNB
As for {\it simple-on-directive\/}, {\it simple-resident-directive}
will be 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.  Otherwise, the assertion (see below) is a statement about how the 
compiler works, not about the program.

{\it On-block} fits most naturally as a Fortran {\it executable-stmt},
since that makes  constraints about ``properly nesting'' easier to state.  

\begin{implementors}
{\tt RESIDENT} removes need for masked processors to
participate in communication into/out of and 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 processor(s) named in
nearest enclosing {\tt ON} directive. 
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.
In this case, the {\tt RESIDENT} assertion refers to the {\tt ON}
directive in which it  appears.

{\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 executing processors.  
(That is, the set of processors named by the {\tt ON} directive,
henceforth referred to as the {\tt ON} processors set.)  
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 {\tt ON} 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 {\tt ON} processors set.  

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, the {\tt RESIDENT} clause may
give less information. 

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}
caluses 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 {\tt HOME} clause specifies 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 ON}TO 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{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}

\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 BEGIN
        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 BEGIN
        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.

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

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}

\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 objects 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} construct 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 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}

%[CHUCK : Could  you replace this with a BNF - I suspect
% it will take  you 5 mins and will take me much longer]

A task region is a single entry region delimited by:
\CODE
!HPF$ TASK REGION
  ......
!HPF$ END TASK REGION
\EDOC

\subsection{Semantics of the TASK\_REGION Directive}

The task region directive is 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.
We will refer to a block of code enclosed by a 
{\tt TASK\_REGION ... END TASK\_REGION} pair as a ``task region''.

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 executing 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 ``lexical task''.  Every execution instance of 
a lexical task is defined as an ``execution task'' and will also be
referred to
as just ``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{sub-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 asssertions implicit in a task region imply that only
the specified executing 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 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 implementations may also need to include a
subset barrier on entry and exit to 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 tasks 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 node of the system. Task parallelism in the presence of 
I/O assumes that all nodes can perform I/O independently and this
paradigm has to be supported, although it is not necessary that 
each node 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 which leads to
significant added complexity.

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

This sections 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, a2
        BOOLEAN done1

C       Following are compiler generated variables       
        BOOLEAN done1_copy
        BOOLEAN inset1, inset2

C     
C       Following magic compiler function call is to set the variables
C       inset1 and  inset2 to .true. for subset1 and subset 2 processors
C       respectively, and .false. otherwise.
C
        CALL intialize_tasksets(inset1,inset2)

C       Code for processor subset 1
        IF (inset1)
           done1 = .false.
           DO WHILE (.true.)
              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)
              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 is not set) 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 flag {\tt done1} , send it and terminate
execution. Subset 2 processors receive the flag, recognise 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>
---------------------------------------------------------------------------