Subject: hpff-core: HPF_SPMD doc (latex)

From: Andy Meltzer <[email-masked]>
Date: Mon, 29 Jan 1996 10:46:54 -0600 (CST)

---------------------------------------------------------------------------
[email-masked] is a mailing list for announcements related to High
Performance Fortran.  Instructions for adding or deleting yourself
from this list appear at the bottom of this message.
---------------------------------------------------------------------------

Below is an updated copy of the HPF_SPMD document with
changes based on comments made during its first reading.   

The document is in latex.

					Andy Meltzer

					[email-masked]

#####################

\documentstyle[twoside,11pt]{article}
%\input{psfig}
\pagestyle{myheadings}
%set dimensions of columns, gap between columns, and paragraph indent 
\setlength{\textheight}{8.75in}
\setlength{\textwidth}{5.5in}
\setlength{\footheight}{0.0in}
\setlength{\topmargin}{0.0in}
\setlength{\leftmargin}{0.0in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.25in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\parindent}{1pc}
\setlength{\itemsep}{0.0in}
\setlength{\topsep}{0.0in}
\setlength{\parsep}{0.0in}
\setlength{\parskip}{.10in}

\markboth{Cray Research Inc.}{Cray Research Inc.}

% copied stuff out of art10.sty and modified them to conform to IEEE format.
\makeatletter
% as Latex considers descenders in its calculation of interline spacing,
%to get 12 point spacing for normalsize text, must set it to 10 points 
\def\@normalsize{\@setsize\normalsize{11pt}\xpt\@xpt
\abovedisplayskip 11pt plus2pt minus5pt\belowdisplayskip 
\abovedisplayskip \abovedisplayshortskip \z@ 
plus3pt\belowdisplayshortskip 6pt plus3pt 
minus3pt\let\@listi\@listI}

% need an 12 pt font size for subsection and abstract headings 
\def\subsize{\@setsize\subsize{12pt}\xipt\@xipt}

%make section titles bold and 12 point, 2 blank lines before, 1 after 
\def\section{\@startsection {section}{1}{\z@}{1.0ex plus 
1ex minus .2ex}{.2ex plus .2ex}{\large\bf}}

%make subsection titles bold and 11 point, 1 blank line before, 1 after 
\def\subsection{\@startsection {subsection}{2}{\z@}{.2ex 
plus 1ex} {.2ex plus .2ex}{\subsize\bf}}

\makeatother
\begin{document}
% don't want date printed
\date{}
%make title bold and 14 pt font (Latex default is non- bold, 16pt) 

\title{\Large\bf HPF\_SPMD}

\author{
   Andy Meltzer \\
   Cray Research, Inc. \\
   655F Lone Oak Drive \\
   Eagan, MN 55121
}
\maketitle

% I don't know why I have to reset thispagestyle, but 
% otherwise get page numbers 
\thispagestyle{empty}

\subsection*{\centering Abstract}
% IEEE allows italicized abstract
{\em
HPF\_SPMD is a hybrid language, combining an SPMD execution model with 
HPF Kernel features.
The model combines the multi-threaded execution of HPF\_LOCAL and the
HPF Kernel syntax and features.  The goal of HPF\_SPMD is to 
attain the potential performance of an SPMD programming model with 
access to HPF features and a well-defined extrinsic interface to HPF.
}

\section{Introduction\label{sec:intro}}

HPF\_SPMD is a hybrid language, combining an SPMD execution 
model with HPF Kernel features.
The model combines the multi-threaded execution of HPF\_LOCAL and the
HPF Kernel syntax and features.  The goal of HPF\_SPMD is to 
attain the potential performance of an SPMD programming model with 
access to HPF features and a well-defined extrinsic interface to HPF.
It is built on top of the HPF\_LOCAL extrinsic environment.
This language is based off of the current definition of the HPF Kernel and 
should change as the HPF Kernel changes.  

SPMD features and a multi-threaded model allow the user to take
advantage of the performance and opportunity for low level access of 
a more general purpose programming model.  Including the HPF Kernel data
distribution features gives the programmer access to the highest 
performing aspects of both models with the penalty of a somewhat 
more complex model.
HPF\_SPMD is not appropriate for all platforms, but is consistent with HPF
and easily targeted for platforms that have HPF and can support 
SPMD programming styles.

The syntax of HPF\_SPMD is a superset of the syntax of the HPF Kernel and the
extrinsic language's semantics are very similar to those of HPF. There are 
some differences, however. For example,
I/O causes differences; in HPF\_SPMD different
processors are allowed to read from different files at the same time, in HPF
the processors must all read from the same file.   The differences in the
models are principally caused by the multi-threaded execution model and
the introduction of HPF\_LOCAL data rules.

HPF\_SPMD allows for the notion of {\em private data}.  Data defaults
to a mapping in which data items are allocated so that each processor
has a unique copy.
The values of the individual
data items and the flow of control may vary from processor to
processor within HPF\_SPMD. This behavior is consistent with the behavior
of HPF\_LOCAL.  In HPF\_SPMD a processor
may be individually named and code executed based upon which processor
it is executing on.

\section{Execution Model\label{sec:exec-model}}

HPF\_SPMD is built upon the fundamental execution model of HPF\_LOCAL,
augmented with data mapping and work distribution features from the HPF Kernel.
It is also augmented with many explicit low-level control features,
some taken from Cray Research's CRAFT language.

In HPF\_SPMD there is a single task on each processor and 
all tasks begin executing in parallel, with data defaulting
to a private distribution, the same default distribution used in HPF\_LOCAL.
Each processor gets a copy of the data storage unless specified otherwise by 
the user.
Consequently I/O works identically to I/O in HPF\_LOCAL and 
message passing libraries are easily integrated.

In short, the execution model is that of HPF\_LOCAL.

To provide correct behavior when explicitly mapped data is involved, 
this model defines barrier points at which
conceptually all processors must stop and wait for the execution of all
other processors before they continue.  These barriers are an additional
constraint when compared to an HPF\_LOCAL program, but are only a small
subset of the implicit barriers in the comparable HPF 2.0 program.
An implementation may remove 
many of these barriers where they are deemed unnecessary, but EVERY 
processor must participate in the barriers at each one of these points.

In the following situations, the compiler automatically inserts implicit
barriers into a program:

\begin{itemize}
\item       At the end of many independent loops to ensure correctness
            when one processor may get ahead of others.
\item       When mapped stack variables are allocated; this includes
            when a subroutine is called the remaps data.
\item       At a {\tt SERIAL} or {\tt END SERIAL} directive.
\item       When the {\tt SYMMETRIC} directive is used (this directive
            is described in the ``Other Features" section.)
\item	    At some array syntax statements to ensure correctness.
\end{itemize}

{\em Question: Should an HPF\_SPMD subprogram have access to global HPF data?}

\section{Data Mapping Features}

Data mapping feature syntax is identical to that
in the HPF Kernel.  The semantics of the data mapping directives is
also identical.  

The only difference (as mentioned above) is that
the default distribution is private so that values of the 
same data item on different 
processors may vary.  This is consistent with the HPF\_LOCAL 
interpretation of the data declaration.

When data is explicitly mapped, only one copy of the data storage
is created unless the explicit mapping directs otherwise.  The
value of explicitly mapped replicated data items must be consistent
between processors as is the case in the HPF Kernel.  

A new directive is suggested for completeness: {\tt PE\_PRIVATE}, which
specifies that the data should conform to the default behavior.

\section{Subprogram Interfaces}

\subsection{Calling an HPF\_SPMD Subprogram from HPF\_SPMD}

The behavior and requirements of an HPF\_SPMD program at subprogram 
interfaces is identical to that of the HPF Kernel for dummy arguments that
are explicitly mapped.  

All processors must co-operate in a subprogram
invocation that remaps or explicitly maps data.  In other words, if
an explicit interface is required (by the the HPF Kernel rules) or the 
subprogram declares explicitly mapped data, the subprogram must be called on
all processors.  Processors need not co-operate if there are only 
reads to non-local data.  The {\tt INHERIT} attribute can only be
applied to explicitly mapped data.

The behavior of an HPF\_SPMD subprogram at subprogram interfaces
is identical to that of HPF\_LOCAL for data that has the default private
mapping.  Data is passed individually on every processor and the
processors need not interact in any way.   All HPF arrays are logically
carved up into pieces; the HPF\_SPMD procedure executing on a 
particular physical processor sees an array containing just those
elements of the global array that are mapped to that physical 
processor.

When a subroutine is passed actual arguments that are a combination
of both explicitly mapped data and private data, the explicitly mapped
data follows the HPF rules and the private data follows the HPF\_LOCAL
rules.

The user also has the option of passing data with explicitly
mapped actual arguments to dummy arguments that are not explicitly 
mapped.  The mapping rules for this data are identical to the mapping
rules when HPF calls an HPF\_LOCAL routine.  The data remains ``in-place".

Finally, it is undefined for an actual argument to be private and
the dummy argument to be explicitly mapped.   A definition could 
be supplied for this interaction, but it is the same solution that 
one might propose for a calling sequence when HPF\_LOCAL routines call 
HPF routines.  

\subsection{Calling an HPF\_SPMD Subprogram from HPF 2.0}

The calling convention and argument passing rules for HPF\_SPMD are
a hybrid of those for HPF 2.0 calling HPF\_LOCAL and HPF 2.0 calling
HPF 2.0.  Explicit interfaces are required.  Where dummy arguments
are private (default) storage, the HPF calling HPF\_LOCAL 
conventions are used.  Where dummy arguments are explicitly mapped,
the calling convention matches HPF calling HPF.  

There are a number of constraints on the HPF\_SPMD subprograms
that may be called from HPF.  The following is a list of the restrictions
placed HPF\_SPMD subprograms called from HPF:
\begin{itemize}
\item Recursive subprograms cannot be called from HPF.
\item Subprograms containing alternate returns cannot be called from HPF.
\item An HPF\_SPMD routine may not be invoked directly or
      indirectly from within the body of a {\tt FORALL} construct or
      in the body of an {\tt INDEPENDENT DO} loop inside an HPF program.
\item Scalar dummy arguments in a routine called by HPF must be mapped 
      so that each processor has a copy of the argument.
\item The attributes (type, kind, rank, optional, intent) of the dummy
      arguments in a routine called by HPF
      must match the attributes of the corresponding dummy 
      arguments in the explicit interface.  A dummy argument of an HPF\_SPMD
      routine may not be a procedure name.
\item A dummy argument of an HPF\_SPMD routine called by HPF may not be
      a procedure name.
\item A dummy argument of an HPF\_SPMD routine called by HPF may not have
      the {\tt POINTER} attribute.
\item A dummy argument of an HPF\_SPMD routine called by HPF must be
      non-sequential.
\item A dummy argument of an HPF\_SPMD routine called by HPF must have
      assumed shape even when it is explicit shape in the interface.
\item The default mapping of scalar dummy arguments and of scalar function
      results when an HPF program calls an HPF\_SPMD routine is that it
      is replicated on each processor.
\end{itemize}

\subsubsection{Argument Association}

If a dummy argument of an {\tt EXTRINSIC(HPF\_SPMD)} routine is an
array and the dummy argument of the HPF\_SPMD routine has the default 
private mapping, then the corresponding dummy argument in the 
specification of the HPF\_SPMD procedure must be an array of the same 
rank, type, and type parameters.  When the extrinsic procedure is invoked, 
the dummy argument is associated with the local array that consists of the
subgrid of the global array that is stored locally if it has the
private mapping.  

If the dummy argument of the HPF\_SPMD routine
is explicitly mapped, it must have the same mapping as the dummy argument
of the {\tt EXTRINSIC(HPF\_SPMD)} routine.   Note that this restriction
does not require actual and dummy arguments to match and is no more stringent
than saying that mappings of dummy arguments in interface blocks must 
match those in the actual subprogram.

\subsubsection{Calling Sequence}

The actions detailed below must occur prior to the invocation of the 
SPMD\_HPF procedure on each processor.  These actions are the responsibility
of the compiler and happen automatically.

At the call site the following events occur:
\begin{enumerate}
\item The processors are synchronized.
\item Each actual argument is remapped, if necessary, according to the
      directives in the interface block.  Actual arguments corresponding
      to unmapped scalar dummy arguments are replicated.
\end{enumerate}

At the return of the subprogram, the following events occur:
\begin{enumerate}
\item All processors are synchronized.
\item The original distribution of arguments and results is restored if
      necessary.
\end{enumerate}

If the extrinsic procedure is a function, the the HPF\_SPMD procedure is 
also a function.  If the function result is mapped in the caller, the
function result must:
\begin{itemize}
\item also be explicitly mapped with the same mapping in the extrinsic 
      procedure.
\item or return the local part of the extrinsic function return value.
\end{itemize}
If the extrinsic function is scalar-valued then the implicit mapping
of the return value is replicated.  Thus, all HPF\_SPMD functions must
return the same value.

\subsection{Calling an HPF\_SPMD Subprogram from HPF\_LOCAL}

This document does not define the interface for calling HPF\_SPMD
subprograms from HPF\_LOCAL, since the definition hinges on the
way HPF\_LOCAL data is combined to form explicitly mapped distributions.
Once a calling convention is defined for HPF\_LOCAL calling HPF, this
should be obvious.

One can, however, define a calling convention when dummy arguments
are only comprised of private data.  In this case, the private data
is passed as if to another HPF\_LOCAL routine (in other
words, as if private data is passed to private data within HPF\_SPMD) 
and all is well defined.

\subsection{Calling an HPF Subprogram from HPF\_SPMD}

This document does not define this interface.  However, when passing
explicitly mapped data with an explicit interface the rules could be
defined to be as if an HPF\_SPMD program were calling an HPF\_SPMD
subprogram.  Passing private data would either cause undefined behavior
or need further definition.

\section{Executable Statements}
\subsection{The {\tt INDEPENDENT} directive}

The {\tt INDEPENDENT} directive is part of HPF\_SPMD with the same semantics
as in HPF 2.0.  However, within {\tt INDEPENDENT} loops
the values of private data may vary from processor to processor.

{\tt INDEPENDENT} applied to {\tt FORALL} has identical syntax and 
semantics as in HPF.

\subsection{The {\tt NEW} Clause}

An HPF independent loop optionally may have a {\tt NEW} clause. The {\tt NEW}
clause is not required by HPF\_SPMD for default (not explicitly mapped)
data. In HPF\_SPMD data defaults to
private so values may differ from processor to processor.

Private data has slightly different behavior than
data specified in the {\tt NEW} clause.  
The value of a private datum on each processor can be used beyond a single
iteration of the loop. 
Private data may be used to compute local sums, for example.  
The values of data items named in a {\tt NEW} clause
may not be used beyond a single iteration. The {\tt NEW} clause asserts that
the {\tt INDEPENDENT} directive would be valid if new objects were create for
the variables named in the clause for each iteration of the loop.

The semantics of the {\tt NEW} clause are identical in
HPF\_SPMD and HPF 2.0. The variables named in a {\tt NEW} 
clause apply only to the immediately subsequent loop nest.

The meaning of {\tt INDEPENDENT} when applied to loops with private data
changes slightly with respect to the private data.  The change can be
summarized to say that instead of indicating that iterations have no
dependencies upon one-another, with respect to the private data, iterations 
on different processors have no dependencies upon one-another.

\subsection{{\tt REDUCE}}

The {\tt REDUCE} direcitive has the same syntax and semantics as the
HPF Kernel {\tt REDUCE} directive.  Only explicitly mapped data may
be assigned to in a {\tt REDUCE} directive.

\subsection{Array Syntax}

Array syntax is treated identically in HPF\_SPMD as in HPF 2.0 for 
explicitly mapped objects.   
For private objects the behavior is 
identical to that of HPF\_LOCAL.   When private (default) objects and 
explicitly mapped objects are combined the rules are as follows:

Given:
\begin{tabbing}
---------\=---------\=---\=---\=---\=------------\=\kill
\> {\em result} = {\em rhs$_1$} op$_1$ {\em rhs$_2$} op$_2$ ... op$_m$ 
{\em rhs$_n$}\\
\end{tabbing}
\begin{itemize}
\item If {\em result} is explicitly mapped and all {\em rhs} arrays are 
      explicitly mapped, the work is distributed as in HPF.

\item If {\em result} is private and all {\em rhs} arrays are private the
      computation is done on all processors as an HPF\_LOCAL program
      would do it.

\item If {\em result} is private and all {\em rhs} arrays are explicitly 
      mapped, the 
      work is distributed as in HPF and the values of the results are 
      broadcast to the {\em result} on each processor.

\item If {\em result} is explicitly mapped and NOT all {\em rhs} arrays are 
      explicitly mapped, the results of the operation are undefined.
     
\item If {\em result} is private and some, but not all {\em rhs} arrays are 
      explicitly mapped, the value is computed by on each processor
      and saved to the local {\em result}.

\end{itemize}

For consistency, all processors must participate in any array syntax 
statement in which the value of an explicitly mapped array is modified.

\subsection{{\tt FORALL} Statement and Construct}

The {\tt FORALL} statement is treated exactly as in HPF when data is
explicitly mapped.  When data is private, the {\tt FORALL} is executed
separately on each processor.  Finally, when data in a {\tt FORALL} is
mixed, the rules for array syntax apply.   If any explicitly mapped
data item is modified in a {\em forall-stmt} then arrays in the 
{\em forall-header} must be explicitly mapped.  In a {\tt FORALL}
construct, if any explicitly mapped array is modified, all modified
arrays must be explicitly mapped.

\subsection{{\tt WHERE} Statement}

The syntactic rules for the {\tt WHERE} statement are similar to those
for the {\tt WHERE}.  
The {\tt WHERE} statement is treated exactly as in HPF when data is
explicitly mapped.  When data is private, the {\tt WHERE} is executed
separately on each processor.  Finally, when data in a {\tt FORALL} is
mixed, the rules for array syntax apply.   
If any explicitly mapped
data item is modified in a {\em where-stmt}  then arrays in the 
{\em where-header} must be explicitly mapped.  In a {\t WHERE} statement,
if any explicitly mapped array is modified, all modified
arrays must be explicitly mapped.

\section{Sequence and Storage Association}

Storage and sequence association rules are identical to the HPF Kernel for
explicitly mapped data.  Data that is private follows the rules
for ordinary Fortran 90 sequence and storage association.  This is
consistent with HPF\_LOCAL.

\section{Input and Output}

Private I/O in HPF has sequential semantics, private I/O in HPF\_SPMD
has parallel semantics; in other words, a private read in HPF\_SPMD
requires each processor to read each element of data in a given file, while a
private read in HPF requires a single read by one processor and a broadcast of
that value (where necessary) to all other processors. If the same file is
specified, both languages generate the same results (with great I/O
overhead in the HPF\_SPMD case). HPF\_SPMD allows each processor to open and
read from different files, a feature unavailable to HPF. Private writes
cause many more differences between the two languages, however.
The user must ensure that only one processor writes to a file using some sort
of synchronization in HPF\_SPMD.

\section{Serial Regions}

It is often useful to enter
a region where only one task is executing.  This is particularly 
useful for certain types of I/O.   To facilitate this, two directives
are provided:

\begin{tabbing}
---------\=---------\=---\=---\=---\=------------\=\kill
\> {\tt SERIAL }\\
\> {\tt END SERIAL }\\
\end{tabbing}

In addition, one may optionally attach a {\tt COPY} clause to the 
{\tt END SERIAL} directive which specifies the private 
data items whose
values should be broadcast to all processors.  The syntax of this 
directive is:

\begin{tabbing}
---------\=---------\=---\=---\=---\=------------\=\kill
\> {\tt !HPF\$     } \> {\tt SERIAL }\\
\>\>{\em sequential region} \\
\>\> ... \\
\> {\tt !HPF\$     } \> {\tt END SERIAL [, COPY (} {\em var$_1$}{\tt [} {\em, var$_2$, ... , var$_n$} {\tt ])]} \\
\end{tabbing}

where {\em var} is private data to be copied to the same named
private data on other processsors.

Serial regions provide implicit barrier synchronization points
at both the {\tt SERIAL} and {\tt END SERIAL} directives.  

Serial regions can be nested, but inner directives are ignored.  There
must be a matching, properly nested {\tt END SERIAL} directive for each
{\tt SERIAL} directive.

If a subroutine call occurs within a serial region, the subroutine
executes serially; there is no way to get back to parallel execution
within the subroutine.  All explicitly mapped data is accessible from 
within subroutines called in a serial region, but a subroutine called
from within a serial region cannot declare explicitly mapped data
or remap data.

All processors must participate in the invocation of the serial region.
No branches are allowed into or out of a SERIAL region.

\section{{\tt STOP} and {\tt ABORT}}

Because of the SPMD nature of the HPF\_SPMD routines, the behavior
of these statements must be defined within the context of this extrinsic.
The {\tt STOP} statement stops execution of only the task executing the
statement.  The {\tt ABORT} statement stops execution of all tasks.
If the {\tt STOP} statement is called from a serial region, all tasks
are stopped and the execution is complete.  With respect to the all/one
execution, {\tt EXIT} behaves like {\tt STOP}.

\section{Library and Intrinsic Routines}

\subsection{HPF Local Routine Library}

The HPF\_LOCAL extrinsic environment contains a number of libraries
that are useful for local SPMD programming and a number of libraries
that allow the user to determine global (rather than local) state
information.  These library procedures take as input the name of
a dummy argument and return information on the corresponding global
HPF actual argument.  They may only be invoked by an HPF\_SPMD
procedure that was directly invoked by global HPF code.  They may
be called only for private data.   The libraries reside in a module
called HPF\_LOCAL\_LIBRARY; an HPF\_SPMD routine that calls them should
include the statement
\begin{tabbing}
---------\=---------\=---\=---\=---\=------------\=\kill
\> {\tt USE HPF\_LOCAL\_LIBRARY }\\
\end{tabbing}
or some functionally appropriate variant thereof.

\subsection{HPF Library}

The HPF Library is available to HPF\_SPMD when called with data that is
explicitly mapped and all processors are participating in the call.
In addition, as in HPF\_LOCAL, the entire HPF Library is available for
use with private data.  Mixing private and explicitly mapped data in
calls to the HPF library produces undefined behavior.

\subsection{Parallel Inquiry Intrinsics}

These directives are provided as an extension to HPF.  They provide
information potentially useful to the programmer about the state of
execution in a program.

\begin{tabbing}
---------\=---------\=---\=---\=---\=------------\=\kill
\> {\tt IN\_PARALLEL()} \\
\> {\tt IN\_INDEPENDENT()} \\
\end{tabbing}

\section{Task Identity}

{\tt PROCID} from HPF\_LOCAL is provided.  The physical processors are
identified by an integer in the range of 0 to {\em n-1} where {\em n}
is the value returned by the global HPF\_LIBRARY function 
{\tt NUMBER\_OF\_PROCESSORS}.  Processor identifiers are returned
by {\tt ABSTRACT\_TO\_PHYSICAL}, which establishes the one-to-one
correspondence between the abstract processors of an HPF processors
arrangement and the physical processors.  Also, the local library
function {\tt MY\_PROCESSOR} returns the identifier of the calling
processor.

\section{Synchronization Primitives}

It is suggested that a number of synchronization primitives be provided
since this model can be programmed at a much lower level than HPF 2.0.
These primitives include:

\begin{tabbing}
---------\=---------\=---\=---\=---\=------------\=\kill
\> Barriers (test, set, wait)\\
\> Locks (set, wait, clear)\\
\> Critical Sections \\
\> Events (test, set, wait, clear)\\
\end{tabbing}

These primitives provide full SPMD programming model support to the 
HPF\_SPMD extrinsic environment.

\subsection{Barriers}

The following intrinsics are available to create and use a user defined
program barrier:
\begin{itemize}
\item {\tt SET\_BARRIER()}
\item {\tt WAIT\_BARRIER()}
\item {\tt TEST\_BARRIER()}
\end{itemize}

The {\tt SET\_BARRIER()} intrinsic indicates that the calling task has 
arrived at the barrier.  The {\tt WAIT\_BARRIER()} intrinsic suspends 
execution of the calling task until all of the other tasks have arrived 
at the barrier and called {\tt SET\_BARRIER()}.  The {\tt TEST\_BARRIER()}
intrinsic tests the state of the barrier, returning FALSE if the barrier 
is set and TRUE if all of the tasks have arrived.

In the following example, a barrier is used to make sure that {\em block3}
is not entered by any task until all tasks have completed execution of
{\em block1}.

\begin{tabbing}
---------\=---------\=---\=---\=---\=------------\=\kill
\> {\em block1} \\
\> {\tt CALL SET\_BARRIER()} \\
\> {\em block2} \\
\> {\tt CALL WAIT\_BARRIER()} \\
\> {\em block3} \\
\end{tabbing}

\subsection{Locks}

Locks are used to prevent the simultaneous access of data by multiple
tasks.  The following three intrinsics are used:

\begin{itemize}
\item {\tt SET\_LOCK(}{\em lock}{\tt)} 
\item {\tt CLEAR\_LOCK(}{\em lock}{\tt)} 
\item {\tt TEST\_LOCK(}{\em lock}{\tt)}: 
\end{itemize}

The {\tt SET\_LOCK(}{\em lock}{\tt)} intrinsic sets the shared
value {\em lock} atomically.  If the lock is already set, the task 
that called {\tt SET\_LOCK} is suspended until the lock is cleared by 
another task and then sets it.
The {\tt CLEAR\_LOCK(}{\em lock}{\tt)} intrinsic clears {\em lock}.
After the call {\em lock} is cleared regardless of its state before the call.
The {\tt TEST\_LOCK(}{\em lock}{\tt)} intrinsic tests the value of {\em lock},
returning TRUE if the lock is set when {\tt TEST\_LOCK} is called
and FALSE if the lock is not set when called. {\tt TEST\_LOCK}
sets the lock before returning if it was not previously set (and
returns FALSE.)

\subsection{Critical Sections}

A {\em critical section} prohibits access to a section of code rather
than to a data object.  It is almost identical to a lock, but is 
implemented with a directive.

\begin{itemize}
\item {\tt !HPF\$ CRITICAL} 
\item {\tt !HPF\$ END\_CRITICAL}
\end{itemize}

The {\tt CRITICAL} directive marks the beginning of a code region in 
which only one task can enter at a time.  The {\tt END\_CRITICAL} directive 
marks the end of the critical section.

Every {\tt CRITICAL} directive must have a matching {\tt END\_CRITICAL}
directive in the same program unit.  They can be nested as long as there
are the same number of each directive; the inner directives have no 
effect.  Branching into or out of a critical section is not permitted.

The following example shows how a critical section might be used.

\begin{tabbing}
---------\=---------\=---\=---\=---\=------------\=\kill
\> {\tt ! }{\em Compute} {\tt LOCAL\_SUM} {\em on every task.} \\
\> {\tt !HPF\$} \> {\tt CRITICAL} \\
\>\> {\tt GLOBAL\_SUM = GLOBAL\_SUM + LOCAL\_SUM} \\
\> {\tt !HPF\$} \> {\tt END\_CRITICAL} \\
\end{tabbing}

\subsection{Events}

Events are typically used to record the state of a program's execution
and to communicate that state to another task.  Because they do not set
locks, as do the lock routines described earlier, they cannot easily be
used to enforce serial access of data.  They are suited to work such as
signalling other tasks when a certain value has been located in a search
procedure.  There are four routines needed to perform the event functions.

\begin{itemize}
\item {\tt SET\_EVENT([}{\em event}{\tt ])} 
\item {\tt CLEAR\_EVENT([}{\em event}{\tt ])}
\item {\tt WAIT\_EVENT([}{\em event}{\tt ])}
\item {\tt TEST\_EVENT([}{\em event}{\tt ])}
\end{itemize}

{\em Event} is a shared integer variable.  If this argument is
present then the event routines use the named variable.  If it is not
then it defaults to a compiler generated single event.  Event setting
and clearing are NOT atomic operations, so code should be written carefully
with that in mind.

The {\tt SET\_EVENT} routine
sets or {\em posts} an event; it declares that an action has been
accomplished or a certain point in the program has been reached.  A
task can post an event at any time, whether the state of the event 
is cleared or already posted.
The {\tt CLEAR\_EVENT} routine clears and event.  The {\tt WAIT\_EVENT} 
routine suspends task execution until the specified event occurs.
The {\tt TEST\_EVENT} routine returns the state, either set (TRUE) or 
clear (FALSE) of an event.

\section{Other Useful Features}

We have found a number of other directives to be extremely
useful.  While these are not required by the model, we should 
consider them for inclusion.

\subsection{Barrier Removal}

It is occasionally useful for an advanced programmer to indicate 
to the compilation system where barriers may not be needed (even though the 
compiler might think that they are necessary,
based upon incomplete knowledge.)

\begin{tabbing}
---------\=---------\=---\=---\=---\=------------\=\kill
\> {\tt NO BARRIER} \\
\end{tabbing}

\subsection{Parallelism Specification Directives}

These directives allow a user to assert that a routine will only be
called from within a parallel region, a serial region, or from within
both regions.  Without these directives an implementation might be
required to generate two versions of code for each subroutine, depending
upon implementation strategies.  The directives simply make the 
generated code size smaller and remove a test.

\begin{tabbing}
---------\=---------\=---\=---\=---\=------------\=\kill
\> {\tt PARALLEL\_ONLY} \\
\> {\tt SERIAL\_ONLY} \\
\> {\tt PARALLEL\_AND\_SERIAL} \\
\end{tabbing}

\subsection{{\tt SYMMETRIC}}

{\tt SYMMETRIC} data is private data that is guaranteed to be at the
same storage location on every processor.  The feature is obviously
tied to certain implementations, but does make PUT and GET functionality
much easier to deal with.

\subsection{{\tt ON} clause}

In addition to the version of {\tt INDEPENDENT} available from HPF 2.0,
a new version of {\tt INDEPENDENT} is proposed that incorporates
the {\tt ON} clause and has a 
number of differences to more easily facilitate the use of the {\tt ON}
clause.  If a restricted
version of the current {\tt ON} proposal is adopted for the HPF Kernel,
that proposal should be adopted instead of this one.

{\tt INDEPENDENT} without the {\tt ON} clause is identical 
to the current HPF implementation of {\tt INDEPENDENT}.

The new version of the {\tt INDEPENDENT} directive in HPF\_SPMD may be 
applied to the first of a group of tightly nested loops and may apply 
to more than one of them. 
This more easily facilitates the use of the {\tt ON} clause. 
The current {\tt INDEPENDENT} directive applies only to a single loop nest.  

The {\tt INDEPENDENT} directive is extended so that multiple loop nests can
be named.

The general syntax for these independent loops is as follows:
\begin{tabbing}
---------\=---------\=---\=---\=---\=------------\=\kill
\>{\tt !HPF\$} \> {\tt INDEPENDENT} ($I_1,I_2,\ldots,I_n$) {\tt ON} {\em array-name}($h_1(I_1),h_2(I_2),\ldots,h_n(I_n))$ \\
\>       \> {\tt DO} $I_1 = L_1, U_1, S_1$       \\
\>       \>\> {\tt DO} $I_2 = L_2, U_2, S_2$     \\
\>       \>\>\> {\tt DO} $I_n = L_n, U_n, S_n$ \\
\>       \>\>\>\> $\ldots$                              \\
\>       \>\>\> {\tt END DO}                            \\
\>       \>\> {\tt END DO}                              \\
\>       \> {\tt END DO}
\end{tabbing}

The syntax and semantics of {\tt INDEPENDENT} with the {\tt ON} 
clause are different from its syntax and semantics without the {\tt ON} 
clause. With the
{\tt ON} clause the directive states that there are no cross-processor
dependencies, but there may be dependencies between iterations on a
processor. It also indicates which loop iterations it refers to. 

If the {\tt ON} clause is used, {\tt INDEPENDENT} must be used 
in the multi-line form.

The rules for the  array specified by the {\tt ON}
clause are as follows.  
The iteration space of a {\tt INDEPENDENT} nest must be rectangular.  
That is, the lower loop bound, the upper loop bound, and the step 
expression for each loop indicated by the {\tt INDEPENDENT} induction 
list must be invariant with regard to the {\tt INDEPENDENT} nest.  
Triangular and trapezoidal nests, such as the following, are not allowed:

\begin{tabbing}
---------\=---------\=---\=---\=---\=------------\=\kill
\>{\tt !HPF\$}\>{\tt INDEPENDENT (I, J)  ON A(I,J)  ! Erroneous } \\
\>\>      {\tt DO I = 1, N                ! code} \\
\>\>\>      {\tt DO J = 1, I} \\
\>\>\>      {\tt ...} \\
\end{tabbing}

Each index expression of {\em array-name} in the
{\tt ON} clause (the functions {\em h$_i$} above,) 
must be of the form 

\begin{tabbing}
---------\=---------\=---\=---\=---\=------------\=\kill
\>{\bf [ }{\em a }{\tt * }{\tt loop\_control\_variable }{\tt + }{\bf ] }{\em b}.
\end{tabbing}
Where {\em a} and {\em b} must be integer values; they can be 
expressions, constants,
or variables. The value of {\em a} cannot be equal to 0.  The 
values of {\em a} and {\em b} must be
invariant with regard to the {\tt INDEPENDENT} loop nest.  

For example, specifying {\tt A(I,J,K)} is valid.  Specifying {\tt A(3,I+J,K)} 
is not valid.  Specifying {\tt A(I,I,K)} is not valid because I appears twice.

Division is prohibited in any index expression of the {\tt ON} clause.  
For example, specifying {\tt A(I/2,J,K)} is not valid.

\subsection{{\tt RESIDENT}}

The {\tt RESIDENT} directive can be applied to loops and at the
subroutine level.  It is an assertion that the accesses to a particular
variable in the subroutine (or loop) are only accesses to data that is
local to the processor making the assertion.  For example:

\begin{tabbing}
---------\=---------\=---\=---\=---\=------------\=\kill
\> \> {\tt REAL A(100), B(100)} \\
\> {\tt !HPF\$     } \> {\tt DISTRIBUTE A(BLOCK), B(BLOCK) }\\
\> {\tt !HPF\$     } \> {\tt RESIDENT A, B }\\
\end{tabbing}

indicates that only local elements of arrays {\tt A} and {\tt B} will
be accessed within the subroutine.  
Note that this is an assertion about the behavior of a program and
not a directive to make it so.

\subsection{{\tt GEOMETRY}}

The {\tt GEOMETRY} directive is like a mapping typedef, allowing the
user to conveniently change the mappings of many arrays at the same
time.  It is similar in many ways to the {\tt TEMPLATE} directive, but
since it is bound to no particular extent it is easier to apply in a
general way.  Users of CRAFT tend to rely heavily on this feature to quickly
distribute a set of arrays similarly.

The syntax of the {\tt GEOMETRY} directive is:

\begin{tabbing}
---------\=---------\=---\=---\=---\=------------\=\kill
\> {\tt !HPF\$     } \> {\tt GEOMETRY} {\em geom}{\tt(}{\em$\delta_1$} {\tt[}{\em , $\delta_2$, ..., $\delta_n$}{\tt])} \\
\> {\tt !HPF\$     } \> {\tt DISTRIBUTE} {\em geom} [::] {\em var$_1${\tt[}, var$_2$, ... , var$_m$}{\tt]} \\
\end{tabbing}

Where $\delta_i$ indicates one of the allowable distribution formats.

\section{New Features of HPF\_SPMD}

HPF\_SPMD starts with the HPF\_LOCAL extrinsic environment then adds all
of the HPF Kernel.   This section lists the new features of HPF\_SPMD.  

\begin{itemize}
\item Suggested changes to {\tt INDEPENDENT} to better support {\tt ON}.
\item New rules defining the interaction of explicitly mapped and private
      data.
\item Parallel inquiry intrinsics:
  \begin{itemize}
  \item {\tt IN\_PARALLEL()}
  \item {\tt IN\_INDEPENDENT()}
  \end{itemize}
\item Serial regions ({\tt SERIAL / END SERIAL})
\item Explicit synchronization primitives:
  \begin{itemize}
  \item Locks (set, wait, clear)
  \item Critical Sections 
  \item Events (test, set, wait, clear)
  \item Barriers (test, set, wait)
  \end{itemize}
\item {\tt PE\_PRIVATE} directive to specify default data mapping behavior
\item Other suggested features:
  \begin{itemize}
  \item {\tt PARALLEL\_ONLY} 
  \item {\tt SERIAL\_ONLY} 
  \item {\tt PARALLEL\_AND\_SERIAL} 
  \item {\tt RESIDENT} 
  \item {\tt SYMMETRIC} 
  \item {\tt GEOMETRY}
  \end{itemize}
\end{itemize}

\end{document}
---------------------------------------------------------------------------
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>
---------------------------------------------------------------------------