Subject: hpff-doc: Edited overview.tex

From: P Sadayappan <[email-masked]> (by way of Chuck Koelbel)
Date: Fri, 18 Oct 1996 12:46:47 -0500

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

I have edited the overview chapter to incorporate the suggestions and
corrections sent by Carol and Piyush. I am able to run it through latex
in "includeonly" mode, but I am unable to latex it with the entire document
that Mary had sent via uuencoded e-mail, since latex gets stuck at various
points in library.tex.

One thing that needs to be fixed is the BNF generating macro: e.g. for H106
and H107, overprinting is occuring due to insufficient space.

-- Saday

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++

% File: overview.tex

% Contents:
% Overview for HPF 2.0 document, including
%       Document/language structure
%       Brief descriptions of new features & extensions
%       Fortran language base
%       Notation and Syntax

% Revision history:
% May-10-96     Created by Charles Koelbel, Rice University
%               (copied from HPF 1.1 document)
% June 26-96
% August 20-96  Edited by P. Sadayappan, Ohio State University
% September 8-96  Edited by P. Sadayappan, Ohio State University
% October 3-96  Edited by P. Sadayappan, Ohio State University,
% incorporating text and revision suggestions from Robbie Babb,
% Ken Kennedy, J. Ramanujam, Piyush Mehrotra, Carol Munroe
% Henry Zongaro Mary Zosel.
% Oct 10-11-96  Piyush Mehrotra - Syntax and Reference fixes.
% Oct 11 - 96   Mary Zosel - minor edits
% Oct 15-96     P. Sadayappan - suggestions/corrections from
%               Piyush Mehrotra, Carol Munroe

\chapter{Overview}
\label{ch-overview}

%Please be sure to add this material to some file that glombnf
%will read--- overview.tex  would be fine:
%Check these rule numbers versus the Fortran 95 specification!!!

\Fortranrule{R710}{add-op}
\Fortranrule{R706}{add-operand}
\Fortranrule{R625}{allocate-object}
\Fortranrule{R622}{allocate-stmt}
\Fortranrule{R431}{array-constructor}
\Fortranrule{R512}{array-spec}
\Fortranrule{R735}{assignment-stmt}
\Fortranrule{R838}{assign-stmt}
\Fortranrule{R1210}{call-stmt}
\Fortranrule{R529}{data-stmt}
\Fortranrule{R631}{deallocate-stmt}
\Fortranrule{R1221}{dummy-arg}
\Fortranrule{R1218}{end-function-stmt}
\Fortranrule{R1222}{end-subroutine-stmt}
\Fortranrule{R504}{entity-decl}
\Fortranrule{R215}{executable-construct}
\Fortranrule{R208}{execution-part}
\Fortranrule{R513}{explicit-shape-spec}
\Fortranrule{R723}{expr}
\Fortranrule{R1209}{function-reference}
\Fortranrule{R1215}{function-subprogram}
\Fortranrule{R914}{input-item}
\Fortranrule{R728}{int-expr}
\Fortranrule{R607}{int-variable}
\Fortranrule{R1204}{interface-body}
\Fortranrule{R210}{internal-subprogram-part}
\Fortranrule{R707}{level-2-expr}
\Fortranrule{R741}{mask-expr}
\Fortranrule{R705}{mult-operand}
\Fortranrule{R737}{namelist-group-object}
\Fortranrule{R543}{namelist-stmt}
\Fortranrule{R629}{nullify-stmt}
\Fortranrule{R915}{output-item}
\Fortranrule{R844}{pause-stmt}
\Fortranrule{R736}{pointer-assignment-stmt}
\Fortranrule{R630}{pointer-object}
\Fortranrule{R737}{read-stmt}
\Fortranrule{R734}{specification-expr}
\Fortranrule{R204}{specification-part}
\Fortranrule{R618}{section-subscript}
\Fortranrule{R623}{stat-variable}
\Fortranrule{R842}{stop-stmt}
\Fortranrule{R620}{stride}
\Fortranrule{R617}{subscript}
\Fortranrule{R619}{subscript-triplet}
\Fortranrule{R737}{target}
\Fortranrule{R501}{type-declaration-stmt}
\Fortranrule{R502}{type-spec}
\Fortranrule{R601}{variable}
\Fortranrule{R739}{where-construct}
\Fortranrule{R738}{where-stmt}
\Fortranrule{R737}{write-stmt}

This document specifies the form and establishes the interpretation of
programs expressed in the High Performance Fortran (HPF) language.  It
is designed as a set of extensions and modifications to the established
International Standard for Fortran. At the time of publication of this
document,
the version of the standard used as a base is informally referred to as
``Fortran~95'' (ISO/IEC 1539:1997).
In this overview
chapter of the document, we outline the goals and scope of the language,
introduce the HPF language model, highlight the main features of the language,
describe the changes between HPF~1.1 and HPF~2.0,
and provide a guide to the rest of this document.

\section{Goals and Scope of High Performance Fortran}
\label{overview-goals}

The primary goals behind the development of the HPF language include:
\begin{itemize}

\item Support for data parallel programming (single threaded, global name
space, and loosely synchronous parallel computation);

\item Portability across different architectures;

\item High performance on parallel computers with non-uniform memory
access costs (while not impeding performance on other machines);

\item Use of Standard Fortran (currently Fortran 95) as a base;

\item Open interfaces and interoperability with other languages (e.g., C)
and other programming paradigms (e.g., message passing using MPI).
\end{itemize}

Secondary goals include:
\begin{itemize}

\item Implementation feasibility within a limited
time span;

\item Provision of input to future standards activities for Fortran and C;

\item Provision of an evolutionary path for adding advanced features to
the language in a consistent manner.
\end{itemize}

The first version of the language definition, HPF~1.0 was released in
May 1993. A number of language features that were defined in HPF~1.0
have now been absorbed into the Fortran 95 language standard
(e.g., the {\tt FORALL} statement and construct, and {\tt PURE} and {\tt
ELEMENTAL} procedures).
These features
are therefore no longer detailed in the definition of HPF~2.0.
Information about the evolution of the HPF language (through versions 1.0,
1.1, and 2.0) and an enumeration of the differences between HPF~2.0 from
HPF~1.1 may be found in
subsection~\ref{hpf-change}.

\section{HPF Language Model}

An important goal of HPF is to achieve code portability across a
variety of parallel machines.  This requires not only that HPF programs
compile on all target machines, but also that a highly-efficient HPF
program on one parallel machine be able to achieve reasonably high
efficiency on another parallel machine with a comparable number of
processors.  Otherwise, the effort spent by a programmer to achieve
high performance on one machine would be wasted when the HPF code is
ported to another machine.  Although
shared-memory machines and distributed-memory machines may use
different low-level primitives, there is broad
similarity with respect to the fundamental factors that affect the
performance of parallel programs on these machines. Thus, achieving high
efficiency across different parallel machines with the same high level
HPF program is a feasible goal. Some of the fundamental factors affecting
the performance of a parallel program are the degree of available parallelism,
exploitation of data locality, and choice of appropriate task granularity.
HPF provides mechanisms for the programmer to guide the compiler with respect
to these factors.

The first versions of HPF were defined to extend Fortran~90.
HPF~2.0 is defined as an extension to the current Fortran Standard
(Fortran~95).
Future revisions of HPF will include and be consistent with advances
in the Fortran standards, as they are approved by ISO.

Building on Fortran, HPF language features fall into four categories:

\begin{itemize}

\item HPF directives;

\item New language syntax;

\item New library routines; and

\item Language changes and restrictions.

\end{itemize}

HPF directives appear as structured comments that suggest implementation
strategies or assert facts about a program to the compiler.  When properly
used, they affect only the efficiency of the computation performed, but
do not change
the value computed by the program.  The form of the HPF directives has
been chosen so that a future Fortran standard may choose to include
these features as full statements in the language by deleting the
initial comment header.

A few new language features have been defined as direct extensions to
Fortran syntax and interpretation.
The new HPF language features differ from HPF directives in that they
are first-class
language constructs and can directly affect the
result computed by a program.

The HPF library of computational functions defines a standard interface
to routines that have proven valuable for high performance computing.
These additional functions include those for mapping inquiry,
bit manipulation, array reduction, array combining scatter, prefix and
suffix, and sorting.

A small number of changes and restrictions to Fortran 95 have also
been defined. The most significant restrictions are those imposed on the
use of
sequence and storage association, since they are not compatible with the
data distribution features of HPF. It is however possible to retain sequence
and storage association semantics in a program by use of certain explicit
HPF directives.

\subsection{Data Mapping Directives}

The fundamental model of parallelism in HPF is that of single-threaded
data-parallel execution with a globally shared address space. Fortran
array statements and the {\tt FORALL} statement are natural ways of
specifying data parallel computation. In addition, HPF provides the
{\tt INDEPENDENT} directive. It can be used to assert that certain loops
do not carry any dependences and therefore may be executed in parallel.

Exploitation of data locality is critical to achieving good performance on
a high-performance computer, whether a uniprocessor workstation,
a network of workstations, or a
parallel computer. On a Non-Uniform-Memory-Access (NUMA) parallel computer,
the effective distribution of data among processor memories is very important
in reducing data movement overheads. One of the key features of HPF is the
facility for user specification of data mapping. HPF provides a
logical view of the parallel machine as a rectilinear arrangement of abstract
processors in one or more dimensions. The programmer can specify the relative
alignment of elements of different program arrays, and the distribution of
arrays over the logical processor grid. Data mapping is specified using HPF
directives that can aid the compiler in optimizing parallel performance,
but have no effect on the semantics of the program. This is illustrated
by the following simple example.

%While HPF's single-threaded data-parallel model with a global name space
%is very convenient in many application contexts, other programming
%languages (e.g., C) and other parallel programming paradigms (e.g., explicit
%message-passing using MPI) may be more appropriate in certain contexts. In
%recognition of this need, HPF formally defines the {\tt EXTRINSIC} mechanism
%to facilitate interoperability with other programming languages
%and/or paradigms.

                                                                \CODE
      REAL A(1000,1000)
!HPF$ PROCESSORS procs(4,4)
!HPF$ DISTRIBUTE (BLOCK,BLOCK) ONTO procs :: A
      DO k = 1, num_iter
         FORALL (i=2:999, j=2:999)
           A(i,j) = (A(i,j-1)+A(i-1,j)+A(i,j+1)+A(i+1,j))/4
         END FORALL
      END DO
                                                                \EDOC

The code fragment describes a simple Jacobi relaxation computation using
a two-dimensional floating-point array {\tt A}. The HPF directives
appear as structured comments. The {\tt PROCESSORS} directive specifies a
logical \( 4 \times 4 \) grid of processors {\tt proc}. The {\tt DISTRIBUTE}
directive recommends that the compiler partition the array {\tt A} into
equal-sized blocks along each of its dimensions. This will result in a
\( 4 \times 4 \)
configuration of blocks each containing \( 250 \times 250 \) elements,
one block per processor.
The {\tt PROCESSORS} and {\tt DISTRIBUTE} directive are described in detail
later in  Section~\ref{ch-mapping-base}.

The outer {\tt DO k} loop iterates over {\tt num\_iter}
Jacobi relaxation steps. The inner loop uses the Fortran~95 {\tt FORALL}
construct. It specifies the execution of the loop body for all values of
{\tt i} and {\tt j} in the range 2 through 999. The semantics of the {\tt
FORALL}
require that the right-hand-side expressions for all iterations
(i.e. for all values of {\tt i} and {\tt j} between 2
and 999) be evaluated before any of the assignments to the
left-hand-side variables are performed.

When targeted for execution on a distributed-memory machine with 16
processors, the HPF compiler generates SPMD code, with each processor
locally containing a part of the global array {\tt A}. The outer {\tt k} loop
is executed sequentially while the inner {\tt FORALL} loop
is executed in parallel. Each processor will require some ``boundary'' elements
of {\tt A} that reside in partitions mapped to the local memories of other
processors. Primitives to achieve the necessary inter-processor
communication are inserted by the HPF compiler into the generated SPMD code.
The single-threaded data-parallel model with a global name-space makes it
convenient for the programmer to specify the strategy for parallelization
and data partitioning at a higher level of abstraction. The tedious low-level
details of translating from an abstract global name space to the local
memories of individual processors and the management of explicit
inter-processor communication are left to the compiler.

The following example illustrates some of the communication implications of
scalar assignment statements.  The purpose is to illustrate the
implications of data distribution specifications on communication
requirements for parallel execution.  The explanations given do not
necessarily reflect the actual compilation process.

Consider the following code fragment:
                                                                \CODE
      REAL a(1000), b(1000), c(1000), x(500), y(0:501)
      INTEGER inx(1000)
!HPF$ PROCESSORS procs(10)
!HPF$ DISTRIBUTE (BLOCK) ONTO procs :: a, b, inx
!HPF$ DISTRIBUTE (CYCLIC) ONTO procs :: c
!HPF$ ALIGN x(i) WITH y(i+1)
      ...
      a(i) = b(i)                    ! Assignment 1
      x(i) = y(i+1)                  ! Assignment 2
      a(i) = c(i)                    ! Assignment 3
      a(i) = a(i-1) + a(i) + a(i+1)  ! Assignment 4
      c(i) = c(i-1) + c(i) + c(i+1)  ! Assignment 5
      x(i) = y(i)                    ! Assignment 6
      a(i) = a(inx(i)) + b(inx(i))   ! Assignment 7
                                                                \EDOC

In this example, the {\tt PROCESSORS} directive specifies a linear
arrangement of 10 processors.  The {\tt DISTRIBUTE} directives
recommend to the compiler that the arrays {\tt a}, {\tt b}, and {\tt
inx} should be distributed among the 10 processors with blocks of 100
contiguous elements per processor. The array {\tt c} is to be
cyclically distributed among the processors with {\tt c(1)}, {\tt
c(11)}, \ldots , {\tt c(991)} mapped onto processor {\tt procs(1)};
{\tt c(2)}, {\tt c(12)}, \ldots , {\tt c(992)} mapped onto processor
{\tt procs(2)}; and so on.  The complete mapping of arrays {\tt x} and
{\tt y} onto the processors is not specified, but their relative
alignment is indicated by the {\tt ALIGN} directive.  The {\tt ALIGN}
statement recommends that {\tt x(i)} and {\tt y(i+1)} be stored on the same
processor for all values of {\tt i}, regardless of the actual
distribution chosen by the compiler for {\tt y} ({\tt y(0)}
and {\tt y(1)} are not aligned with any element of {\tt x}).  The {\tt
PROCESSORS}, {\tt DISTRIBUTE}, and {\tt ALIGN} directives are discussed
in detail in Section~\ref{ch-mapping-base}.

In Assignment 1 ({\tt a(i) = b(i)}), the identical distribution of {\tt
a} and {\tt b} specifies that for all {\tt i}, corresponding elements of
{\tt a(i)} and {\tt b(i)}
should be mapped to the same processor.  Therefore, execution of
this statement requires no communication of data values between
processors.

In Assignment 2 ({\tt x(i) = y(i+1)}), there is no inherent
communication.  In this case, the relative alignment of the two arrays
matches the assignment statement for any actual distribution of the
arrays.

Although Assignment 3 ({\tt a(i) = c(i)}) looks very similar to the
first assignment, the communication requirements are very different due
to the different distributions of {\tt a} and {\tt c}.  Array elements
{\tt a(i)} and {\tt c(i)} are mapped to the same processor for only
10\% of the possible values of {\tt i}.  (This can be seen from
the definitions of {\tt BLOCK} and {\tt CYCLIC} in
Section~\ref{ch-mapping-base}.) The elements are located on the same
processor if and only if \( \lfloor ({\tt i}-1) / 100 \rfloor = ({\tt i}-1)
\bmod
10 \).  For example, the assignment involves no inherent communication
(i.e.,\ both {\tt a(i)} and {\tt c(i)} are on the same processor) if \(
{\tt i} = 1 \) or \( {\tt i} = 102 \), but does require communication
if \( {\tt i} = 2 \).

In Assignment 4 ({\tt a(i) = a(i-1) + a(i) + a(i+1)}), the references
to array {\tt a} are all on the same processor for about 98\% of the
possible values of {\tt i}.  The exceptions to this are \( {\tt i} =
100*{\tt k} \)
for any \( k = 1, 2, \ldots, 9 \), (when {\tt a(i)} and {\tt a(i-1)}
are on {\tt procs(k)} and {\tt a(i+1)} is on {\tt procs(k+1)}) and  \(
{\tt i} = 100*{\tt k} + 1 \) for any \( k = 1, 2, \ldots, 9 \) (when {\tt
a(i)} and
{\tt a(i+1)} are on {\tt procs(k+1)} and {\tt a(i-1)} is on {\tt
procs(k)}).
This statement requires communication.
only for ``boundary" elements on each processor,

Assignment~5, {\tt c(i) = c(i-1) + c(i) + c(i+1)}, while superficially
similar to Assignment 4, has very different communication behavior.
Because the distribution of {\tt c} is {\tt CYCLIC} rather than {\tt
BLOCK}, the three references {\tt c(i)}, {\tt c(i-1)}, and {\tt c(i+1)}
are mapped to three distinct processors for any value of {\tt i}.
Therefore, this statement requires communication for at least two of
the right-hand side references, regardless of the implementation
strategy.

The final two assignments have very limited information regarding the
communication requirements.  In Assignment~6 ({\tt x(i) = y(i)}) the
only information available is that {\tt x(i)} and {\tt y(i+1)} are on
the same processor; this has no logical consequences for the
relationship between {\tt x(i)} and {\tt y(i)}.  Thus, nothing can be
said regarding communication required at runtime for
the statement without further
information.  In Assignment 7 ({\tt a(i) = a(inx(i)) + b(inx(i))}), it
can be proved that {\tt a(inx(i))} and {\tt b(inx(i))} are always
mapped to the same processor.  Similarly, it is easy to deduce that
{\tt a(i)} and {\tt inx(i)} are mapped together.  Without knowledge of
the values stored in {\tt inx}, however, the relation between {\tt
a(i)} and {\tt a(inx(i))} is unknown, as is the relationship between
{\tt a(i)} and {\tt b(inx(i))}.

\section{Overview of HPF~2.0 Language Features}
\label{overview-hpf2}

The language defined in this document consists of two main parts:
\begin{itemize}
\item The HPF~2.0 Language  (Part~\ref{part-hpf2})
\item HPF~2.0 Approved Extensions (Part~\ref{part-extend})
\end{itemize}
The HPF~2.0 language includes features that are expected
of every HPF implementation
within a year of release of the
language specification. These include basic data distribution features,
data parallel features, intrinsic and library routines, and
the extrinsic mechanism. The Approved Extensions include advanced
features that meet specific needs, but are not likely to be supported
in initial compiler implementations.

\subsection{HPF~2.0 Language Features}

\subsubsection*{Data Distribution Features
(Sections~\ref{ch-mapping-base} and~\ref{ch-mapping-subr})}

Most parallel and sequential architectures attain their highest speed
when the data accessed exhibits locality of reference. The sequential
storage order implied by Fortran standards often conflicts with
the locality demanded by the architecture. To avoid this, HPF includes
features that describe the co-location of data ({\tt ALIGN}) and the
partitioning of data among memory regions or abstract processors ({\tt
DISTRIBUTE}). Compilers may interpret these annotations to improve
storage allocation for data, subject to the constraint that
semantically every data object has a single value at any point in
the program.
%In all cases, users should expect the compiler to arrange
%the computation to minimize communication while retaining parallelism.
Section~\ref{ch-mapping-subr} defines how the mapping features
interact across subprogram boundaries.

While a goal of HPF is to maintain compatibility with Fortran, full
support of Fortran sequence and storage association, however, is not
compatible with the goal of high performance through distribution of
data in HPF.
Restrictions and directives
related to storage and sequence association are described in
Sections~\ref{ch-mapping-base} and~\ref{ch-mapping-subr}.

\subsubsection*{Data Parallel Execution Features (Section~\ref{ch-parallel})}

To express parallel computation explicitly, HPF
defines the {\tt INDEPENDENT} directive.
It asserts that the statements in a
particular section of code do not exhibit any sequentializing
dependences; when properly used, it does not change the semantics of the
construct, but may provide more information to the language processor
to allow optimizations.
A {\tt REDUCTION} clause can be used with the {\tt INDEPENDENT} directive
to identify variables that are updated by commutative and
associative operations. This facilitates the utilization of parallelism
with reduction operations, in the context of loops where the order of
accumulation of updates to a variable is insignificant.

\subsubsection*{Extrinsic Program Units (Section~\ref{ch-extrinsics})}

Because HPF is designed as a high-level machine-independent language,
there are certain operations that are difficult or impossible to
express directly.  For example, an application may benefit from
finely-tuned systolic communications on certain machines; HPF's global
address space does not express this well.
HPF defines the
Extrinsic mechanism to facilitate interfacing with
procedures written in other paradigms, such as
explicit message-passing subroutine libraries or in other languages, such as
C.

\subsubsection*{Intrinsic Functions and Standard Library
(Section~\ref{ch-library})}

Experience with massively parallel machines has identified many
basic operations that are useful in parallel algorithm design.
The Fortran array intrinsics address some of these.
HPF adds several classes of parallel
operations to the language definition as intrinsic functions and as standard
library functions.  In addition, several system inquiry functions
useful for controlling parallel execution are provided in HPF.

%\subsubsection*{Sequence and Storage Association}
%
%A goal of HPF is to maintain compatibility with Fortran.  Full
%support of Fortran sequence and storage association, however, is not
%compatible with the goal of high performance through distribution of
%data in HPF.  Some forms of associating subprogram dummy arguments
%with  actual values make assumptions about the sequence of values in
%physical memory which may be incompatible with data distribution.
%{\tt COMMON} and {\tt EQUIVALENCE} statements are recognized as
%requiring a modified storage association paradigm. HPF
%provides a directive to assert that full sequence and storage
%association for designated variables must be maintained.  In the absence
%of such explicit directives, reliance on the properties of association
%is not allowed.  An optimizing compiler may then choose to distribute
%any variables across processor memories in order to improve
%performance.  To protect program correctness, a given implementation
%should provide a mechanism to ensure that all such default optimization
%decisions are consistent across an entire program.
%Section~\ref{ch-mapping-subr} describes the restrictions and directives
%related to storage and sequence association.

\subsection{HPF~2.0 Approved Extensions}

\subsubsection*{Extensions for Data Mapping (Section~\ref{ch-mapping-ext})}

The extended mapping features permit greater control over the mapping
of data, including facilities for dynamic realignment and redistribution
of arrays at run-time ({\tt REALIGN, REDISTRIBUTE, DYNAMIC} directives),
mapping of data among subsets of processors, and
support for irregular distribution of data ({\tt GEN\_BLOCK} and
{\tt INDIRECT} distributions). In addition, mechanisms are
defined that permit the programmer to provide information to the compiler
about the range of possible distributions an array might take ({\tt RANGE}
directive) and the amount of buffering to be used with arrays involved
in stencil-based nearest-neighbor computations ({\tt SHADOW}).

\subsubsection*{Extensions for Data and Task Parallelism
(Section~\ref{ch-parallel-ext})}

The {\tt ON} directive facilitates explicit computation partitioning.
The site of recommended execution
of a computation can be specified either as an explicitly identified
subset of a processor arrangement, or indirectly as the set of processors
onto which an array (section) or template is mapped.

In order to assist the compiler in
generating efficient code, the {\tt RESIDENT} directive is defined, to be
used in conjunction with an {\tt ON} directive by the programmer. It can
be used to assert that all accesses to the specified variable
within the scope of the {\tt ON} directive are to be found locally
on the executing processor.
The {\tt TASK\_REGION}
directive allows the user to specify the concurrent execution of
different blocks of code on disjoint processor subsets.

\subsubsection*{Extensions for Asynchronous I/O (Section~\ref{ch-io-ext})}

In order to permit overlap of I/O with computation, an extension
has been defined for asynchronous {\tt READ/WRITE} of direct, unformatted
data.
This is done through an additional I/O control parameter in the Fortran
{\tt READ/WRITE} statement that specifies non-blocking execution and
a new statement ({\tt WAIT}).

\subsubsection*{Extensions to Intrinsic and Library Procedures
(Section~\ref{ch-library-ext})}

The approved extensions to the HPF intrinsics and library routines
relate mostly to mapping inquiry procedures. Some new inquiry routines
are defined and other routines defined by the HPF~2.0 language are extended to
facilitate inquiry about extended mapping features, such as
mapping to processor subsets, {\tt GEN\_BLOCK}, {\tt INDIRECT} and
{\tt DYNAMIC} distributions. A generalization of the Fortran
{\tt TRANSPOSE} intrinsic is also defined.

\subsubsection*{Approved Extensions for HPF Extrinsics
(Section~\ref{ch-extrinsic-ext})}

A number of specific extrinsic interfaces are defined in
Section~\ref{ch-extrinsic-ext} as approved HPF~2.0 extensions.
These include interfaces to facilitate interoperability with
other languages (e.g., C and FORTRAN 77) as well as interfaces for
different models of parallelism ({\tt LOCAL}
for SPMD parallel, and {\tt SERIAL} for single-process sequential).
Library routines
useful in the extrinsic models are defined in Section~\ref{ext-lib}.
Additional extrinsic interfaces that are formally recognized by
the HPF Forum, but not defined and maintained by the Forum
are included in Annexes~\ref{ch-hpf-craft} and~\ref{ch-f77-local-library-app}.
The policy and mechanism
for formal recognition of such extrinsic interfaces is described in
Annex~\ref{ch-extrinsic-app}.

% Was File: changes-app.tex
% now included as a section in overview.tex

% Contents:
% Changes and Extensions to the HPF Language

% Revision history:
%Sept-19-96	Created by Mary Zosel / Mike Delves

%\chapter{Changes from HPF~1.1}
\section{Changes from HPF~1.1}
\label{hpf-change}

%{\em
%Comments on this chapter should be directed to
%Ken Kennedy ({\tt [email-masked]})
%Mary Zosel ({\tt [email-masked]})
%and {\tt [email-masked]}.
%Please use ``{\tt Comments on HPF Changes}'' as the {\tt Subject:}
%line.
%\par
%}

HPF~2.0 differs from HPF~1.1 in a number of ways:
\begin{description}
\item[Based on Fortran 95:]  Fortran, instead of Fortran~90 is now defined as
the base language for extensions; this implies that HPF includes all features
added to Fortran at the 1995 revision. With this revision, a few HPF~1.1
features are now part of the Fortran  standard, and hence no longer appear  as
HPF  extensions to Fortran.

\item[Features Removed:] Some features of HPF~1.1, that have not  been
implemented to date, have been removed from the language because experience has
shown that the simplicity gained by doing so outweighs the advantage of the
features.

\item[Repartitioning of the Language:] The new document describes two
components: HPF~2.0 (expected to be widely and relatively
rapidly implemented) and Approved Extensions (which are not part of
HPF~2.0 but
may be included in future implementations in response to user demand, as the
compilation technology matures.)

\item[Elimination of the HPF Subset:] The description in HPF~1.1 of Full HPF
and Subset HPF has not been retained, although the original HPF~1.1 Subset
is documented in an annex.

\item[Features Reclassified as Approved Extensions:] A few features have been
moved from HPF~1.1 to the category of Approved Extensions.

\item[New Features:] A few new features have been added to the base language.

\item[New Approved Extensions:] A number of further new features are defined as
approved extensions to the language.

\item[Recognized Externally-Supported Extrinsics:] Finally, the document
acknowledges a new category, HPF-related Extrinsic Interfaces, that are
recognized as
meeting appropriate standards for such interfaces, but are not included as
Approved Extensions. Responsibility for the content of each such interface is
assumed by the organization proposing it rather than by the HPF Forum.
\end{description}

\noindent Each of these categories is summarized in the following
subsections.

\subsection{Features Now in Standard Fortran}

The following features, which formed part of HPF~1.1, have been removed
from the
document because they are now part of ISO Fortran:
\begin{itemize}
\item The {\tt FORALL} statement and construct;
\item The {\tt PURE} attribute for procedures;
\item Extensions to the {\tt MINLOC, MAXLOC} intrinsics to include an  optional
{\tt DIM} argument.
\end{itemize}

\subsection{Features Removed or Restricted in HPF~2.0}

The following features have been removed from the language:
\begin{itemize}
\item Sequential arrays may no longer be explicitly mapped;
\item In any procedure call in which distributed data may require
redistribution, the  procedure must now have an explicit interface;
\item The treatment of the {\tt INHERIT} directive has been simplified in that
it is no longer  possible to specify both {\tt INHERIT} and {\tt DISTRIBUTE}
together.
\end{itemize}

\subsection{Features Moved to Approved Extensions}

The {\tt DYNAMIC} attribute and the {\tt REDISTRIBUTE} and {\tt REALIGN}
statements have been moved to the Approved Extensions.

\subsection{New Features of HPF~2.0}

The following new constructs have been introduced in HPF~2.0:
\begin{itemize}
\item The {\tt REDUCTION} clause for  {\tt INDEPENDENT} loops;
\item The new HPF_LIBRARY procedures {\tt SORT_DOWN, SORT_UP}.
\end{itemize}

\subsection{New Approved Extensions}

The Approved Extensions include the following features not part of HPF~1.1:
\begin{itemize}
\item Objects may now be mapped to {\em processor subsets}. This aids
efficiency
in some  situations, and is required for effective use of the {\tt TASK_REGION}
construct.
\item Objects with the {\tt POINTER} attribute may be explicitly
mapped.
%SHOULD THIS BE IN FEATURES MOVED????
\item Components of derived types may now be distributed.
\item New distributions, {\tt GEN_BLOCK} and {\tt INDIRECT} have been added.
The closer control
over  data distribution provided by {\tt GEN_BLOCK} allows improved load
balancing; the {\tt INDIRECT} distribution allows a more direct treatment of
irregular grids.
\item The {\tt RANGE} directive provides additional information to the
compiler on {\tt DYNAMIC} variables, transcriptive dummy arguments
or pointers, and may allow for improved  efficiency.
\item The {\tt SHADOW} directive provides information on the appropriate
allocation of  overlap regions for mapped distributed objects.
%\item {\tt ACTIVE PROCESSORS}??
\item The {\tt ON} directive  provides advice to the
compiler on where  best to carry out a computation.
This also introduces the concept of {\it active processor sets},
the currently active subset of processors.
\item The {\tt RESIDENT} directive identifies data which are local to the
currently active processors and removes the need for the compiler to generate
tests for communication outside this set.
\item The {\tt TASK_REGION} directive together with distribution onto
processor subarrays  provides a mechanism for describing a number of parallel
paradigms including  {\em parallel sections, nested parallelism}, and {\em data
parallel pipelines}.
\item Additional intrinsic procedures {\tt ACTIVE_NUM_PROCS} and  {\tt
ACTIVE_PROCS_SHAPE}, and a generalized {\tt TRANSPOSE} intrinsic
have been introduced.
\item The {\tt HPF_LIBRARY} procedures {\tt HPF_ALIGNMENT,
HPF_DISTRIBUTION} and {\tt  HPF_TEMPLATE} have been revised
and new procedures {\tt HPF_MAP_ARRAY} and {\tt  HPF_NUMBER_MAPPED}
have been added.
\item An additional I/O control parameter in the Fortran {\tt READ/WRITE}
statement and a new statement, {\tt WAIT}, facilitates
asynchronous input/output.
\item Extensions to the {\tt EXTRINSIC} facilities defined in HPF~2.0 to
provide support for interoperability with C and FORTRAN 77.
\end{itemize}

\subsection{Recognized Externally-Supported HPF Extrinsics}
 The {\tt EXTRINSIC} attribute deliberately encompasses a potentially very
broad
range of  facilities. Only a few possibilities are incorporated in HPF~2.0 or
Approved Extensions. The HPF Forum has therefore included a mechanism by which
further extrinsic facilities may be proposed, and in due  course
standardized if
found useful. The mechanism requires that a proposal have  demonstrated utility
and ongoing support; it may then be submitted for recognition by the HPF Forum.
There are two such interfaces  recognized in this document:
\begin{itemize}
\item HPF_CRAFT:  providing an SPMD paradigm with HPF features.
\item The Fortran 77 Local Library: defining library support for calling
Fortran 77 procedures in local mode.
\end{itemize}

\section{Notation}
\label{overview-notation}

This document uses the same notation as the Fortran 95 standard.  In
particular, the same conventions are used for syntax rules.  BNF
descriptions of language features are given in the style used in the
Fortran standard.  To distinguish HPF syntax rules from Fortran
rules, each HPF rule has an identifying number of the form H\(snn\),
where \(s\) is corresponds to the one-digit section number
and \(nn\) is a
sequence number.  The syntax rules are also collected in
Annex~\ref{ch-bnf-app}.  Nonterminals not defined in this document
are defined in the Fortran standard.  Also note that certain
technical terms such as ``storage unit'' are defined by the Fortran
standard; Annex~\ref{ch-bnf-crossref} identifies the Fortran rules
defining these nonterminals.  References in parentheses in the text
refer to the Fortran 95 standard.

Part~\ref{part-extend} describes the approved extensions. In some cases this
requires extending the syntax rules already introduced in an earlier section.
In particular, the syntax rules here are often supersets of similar
syntax rules in Part~\ref{part-hpf2}; in these cases, the names of the
nonterminals include the suffix {\it -extended}. Thus, when a non-terminal
such as {\it name} is redefined it is referred to as {\it name-extended}
under the proviso that any reference to {\it name} is to be replaced by
{\it name-extended} in the rest of the syntax rules.

\begin{rationale}
Throughout this document, material explaining the rationale for including
features, for choosing particular feature definitions, and for making
other decisions, is
set off in this format.  Readers interested only in the language definition
may wish to skip these sections, while readers interested in
language design may want to read them more carefully.
\end{rationale}

\begin{users}
Throughout this document, material that is primarily of interest to users
(including most examples of syntax and interpretation)
is set off in this format.  Readers interested only in
technical material may wish to skip these sections, while readers
wanting a more tutorial approach may want to read them more carefully.
\end{users}

\begin{implementors}
Throughout this document, material that is primarily of interest to
implementors is set off in this format.  Readers interested only in the
language definition may wish to skip these sections, while readers
interested in compiler implementation may want to read them more carefully.
\end{implementors}

\section{Syntax of Directives}

HPF directives are consistent with Fortran  syntax in the following
sense: if any HPF directive were to be adopted as part of a future
Fortran standard, the only change necessary to convert an HPF program
would be to replace the directive-origin with blanks.

                                                      \BNF
hpf-directive-line     \IS   directive-origin hpf-directive

directive-origin       \IS   !HPF$
                       \OR   CHPF$
                       \OR   *HPF$

hpf-directive          \IS   specification-directive
                       \OR   executable-directive

specification-directive  \IS   processors-directive
                       \OR   align-directive
                       \OR   distribute-directive
                       \OR   inherit-directive
                       \OR   template-directive
                       \OR   combined-directive
                       \OR   sequence-directive

executable-directive   \IS  independent-directive
                                                      \FNB

\begin{constraints}

\item An {\it hpf-directive-line} cannot be commentary
following another statement on the same line.

\item A {\it specification-directive} may appear only
where a {\it declaration-construct} may appear.

\item An {\it executable-directive} may appear only where an {\it
executable-construct} may appear.

\item An {\it hpf-directive-line} follows the rules of either Fortran
 free form (3.3.1.1) or fixed form (3.3.2.1) comment lines, depending
on the source form of the surrounding Fortran  source form in that
program unit. (3.3)

\end{constraints}

An {\it hpf-directive} is case insensitive and
conforms to the rules for blanks in free
source form (3.3.1), even in an HPF program otherwise in fixed source
form.  However an HPF-conforming language processor is not required
to diagnose extra or missing blanks in an HPF directive.
Note that, due to Fortran  rules, the {\it directive-origin}
in free source form must be the characters {\tt !HPF$}.
HPF directives may be continued, in which case
each continued line also begins with a
{\it directive-origin}. No  statements may
be interspersed within a continued HPF-directive.  HPF directive lines
must not appear within a continued statement.
HPF directive lines may include trailing commentary.

In either source form, the blanks in the adjacent keywords
{\tt END FORALL} and {\tt NO SEQUENCE} are optional.

An example of an HPF directive continuation in free source form is:

                                                      \CODE
!HPF$ ALIGN ANTIDISESTABLISHMENTARIANISM(I,J,K) &
!HPF$        WITH ORNITHORHYNCHUS_ANATINUS(J,K,I)
                                                      \EDOC

An example of an HPF directive continuation in fixed source form follows.
Observe that column 6 must be blank, except when signifying continuation.

                                                       \CODE
!HPF$ ALIGN ANTIDISESTABLISHMENTARIANISM(I,J,K)
!HPF$*WITH ORNITHORHYNCHUS_ANATINUS(J,K,I)
                                                       \EDOC

This example shows  an HPF directive continuation which is ``universal'' in
that it can be treated as either fixed source form or free source form.
Note that the ``{\tt \&}'' in the first line is in column 73.

                                                       \CODE
!HPF$ ALIGN ANTIDISESTABLISHMENTARIANISM(I,J,K)                         &
!HPF$&WITH ORNITHORHYNCHUS_ANATINUS(J,K,I)
                                                       \EDOC

Part~\ref{part-extend} introduces new directives,
both specifications and executable ones, for the approved extensions
to HPF~2.0. These are reproduced below:

                                                       \BNF
specification-directive-extended  \IS   processors-directive
                       \OR   align-directive
                       \OR   distribute-directive
                       \OR   inherit-directive
                       \OR   template-directive
                       \OR   combined-directive
                       \OR   sequence-directive
                       \OR   dynamic-directive
                       \OR   range-directive
                       \OR   shadow-directive

executable-directive-extended \IS  realign-directive
                       \OR   redistribute-directive
                       \OR   active-directive
			\OR simple-on-directive
			\OR block-on-directive
			\OR end-on-directive
		       \OR simple-resident-directive
                       \OR block-resident-directive
			\OR end-resident-directive
		       \OR task-region-directive
                       \OR end-task-region-directive
                                                      \FNB

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