Subject: hpff-doc: extrinsics.tex

From: [email-masked]
Date: Fri, 04 Oct 96 17:19:53 -0400

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

Sorry about the lack of Subject last time.

----------------------------------------------------------------------

% File: extrinsics.tex

% Contents:  Extrinsics chapter for HPF 2.0 document

% Revision history:

% May-10-96     Created by Charles Koelbel, Rice University (from HPF 1.2 
document)

% Aug-15-96     Draft stage new chapter (David Loveman) in interim stage (mez)

% Sep-09-96     Next draft of chapter by David Loveman, Digital.

% Oct-04-96     Revised draft of chapter by David Loveman, Digital.

\chapter{Extrinsic Program Units}

\label{ch-extrinsics}

{\em Comments on this chapter should be directed to David Loveman ({\tt
[email-masked]}) and {\tt [email-masked]}. Please
use ``{\tt Comments on Extrinsics}'' as the {\tt Subject:} line.}

The HPF global model of computation extends (and restricts) Fortran to
provide programmers with the Fortran model of computation implementable
efficiently on a wide class of hardware architectures with, in general,
multiple processors, multiple memories with non-uniform access
characteristics, and multiple interconnections. This model of
computation presents a single logical thread of control, including
Fortran's data parallel features such as array syntax and the forall
statement, and data visibility defined by the scoping rules of Fortran.
In particular, this model does not require the use of low-level
features such as threads libraries and explicit message passing to
exploit such architectures. Programmers expect their HPF compilers to
generate efficient code by using HPF's features to assist in mapping
data and computation to the given hardware architecture.

This chapter defines the {\it extrinsic} mechanism by which HPF program
units may use non-HPF program units that don't use the HPF global
model. It describes how to write an explicit interface for a non-HPF
procedure and defines the caller's assumptions about handling
distributed and replicated data at the interface. This allows the
programmer to use non-HPF language facilities, for example to descend
to a lower level of abstraction to handle problems that are not
efficiently addressed by HPF, to hand-tune critical kernels, or to call
optimized libraries. Such an interface can also be used to interface
HPF to other languages, such as C.

\section{Overview}

An HPF program may need to call a procedure implemented in a different
programming model or in a different programming language. A procedure's
{\it programming model} might provide:

\begin{itemize}

\item a single logical thread-of-control where {\it one} copy of the
procedure is conceptually executing and there is a single locus of
control within the program text; this model is called {\it global} when
the underlying target hardware has (potentially) multiple processors or
memories and is called {\it serial} when the underlying target hardware
is treated as a uniprocessor (or a single node in a multiprocessor),

\item multiple threads-of-control, one per processor, each thread
executing the same procedure; this model is called {\it local} or, more
generally, SPMD (Single Program, Multiple Data), or

\item some other model, not discussed here, such as multiple 
threads-of-control, perhaps with dynamic assignment of
loop iterations to processors or explicit dynamic process forking,
where there is, at least initially upon invocation {\it one} copy of
the procedure that is conceptually executing but which may spawn
multiple loci of control, possibly changing in number over time, within
the program text.

\end{itemize}

A {\it programming language} provides a specific syntax (language
features), semantics (meanings), and pragmatics (purposes). Examples of
programming languages include Fortran (an ANSI and ISO standard, the
most recent revision should be approved in 1996), HPF (a specification
of extensions and restrictions to Fortran), Fortran 77 (a previous ANSI
and ISO standard), C, C++, Java, Visual Basic, and COBOL.

A program unit's language and model, when taken together, constitute
its {\it extrinsic kind}. This {\it extrinsic kind} may be specified
explicitly by an {\it extrinsic-prefix} or implicitly by the selection
of a compiler and its invocation with a particular set of compiler
options. Thus, one might view the compiler as providing a {\it host
scoping unit} as defined by Fortran. For example, a program unit
compiled by an HPF compiler will be of extrinsic kind {\tt HPF}.
Alternatively, its extrinsic kind may be specified explicitly by an
{\it extrinsic-prefix} such as {\tt EXTRINSIC(HPF)} or {\tt
EXTRINSIC(LANGUAGE='HPF', MODEL='GLOBAL')}.

\section{Declaration of Extrinsic Program Units}

\subsection{Function and Subroutine Statements}

An {\it extrinsic-prefix} may appear in a {\it function-stmt} or {\it
subroutine-stmt} (as defined in the Fortran standard) in the same place
that the keywords {\tt RECURSIVE}, {\tt PURE}, and {\tt ELEMENTAL} may
appear. This is specified by an extension of rule R1219 for {\it
prefix-spec} in the May 1995 draft Fortran 95 standard. Rules R1217 for
{\it function-stmt}, R1218 for {\it prefix}, and R1222 for {\it
subroutine-stmt} are not changed, but are rewritten here for
reference.

\BNF
function-stmt           \IS [ prefix ] FUNCTION function-name
                              ( [ dummy-arg-name-list ] )
                              [ RESULT ( result-name ) ]
subroutine-stmt         \IS [ prefix ] SUBROUTINE subroutine-name
                              [ ( [ dummy-arg-list ] ) ]
prefix                  \IS prefix-spec [ prefix-spec ] ...
prefix-spec             \IS type-spec
                        \OR RECURSIVE
                        \OR PURE
                        \OR ELEMENTAL
                        \OR extrinsic-prefix
\FNB

\begin{constraints}

\item The definition of {\em characteristics of a procedure} as given
in Section 12.2 of the May 1995 draft Fortran 95 standard is extended
to include the procedure's extrinsic kind.

\item Within any HPF {\it external-subprogram}, every {\it
internal-subprogram} must be of the same extrinsic kind as its host and
any {\it internal-subprogram} whose extrinsic kind is not given
explicitly is assumed to be of that extrinsic kind.

\end{constraints}

\subsection{Program, Module, and Block Data Statements}

An {\it extrinsic-prefix} may also appear at the beginning of a {\it
program-stmt}, {\it module-stmt}, or {\it block-data-stmt}. The
following syntax definition extends the Fortran 95 syntax rules R1102
for {\it program-stmt}, R1105 for {\it module-stmt}, and R1111 for {\it
block-data-stmt}.

\BNF
program-stmt            \IS [ extrinsic-prefix ] PROGRAM program-name
module-stmt             \IS [ extrinsic-prefix ] MODULE module-name
block-data-stmt         \IS [ extrinsic-prefix ] BLOCK DATA [ block-data-name ]
\FNB

\begin{constraints}

\item Within any HPF {\it module}, every {\it module-subprogram} must
be of the same extrinsic kind as its host, and any {\it
module-subprogram} whose extrinsic kind is not given explicitly is
assumed to be of that extrinsic kind.

\item Within any HPF {\it main-program} or {\it module-subprogram},
every {\it internal-subprogram} must be of the same extrinsic kind as
its host, and any {\it internal-subprogram} whose extrinsic kind is not
given explicitly is assumed to be of that extrinsic kind.

\item In any HPF {\it block-data-stmt}, if an {\it extrinsic-prefix} is
present, a {block-data-name} must also be present.

\end{constraints}

\subsection{The Extrinsic Prefix}

\BNF
extrinsic-prefix        \IS EXTRINSIC ( extrinsic-spec )
extrinsic-spec          \IS extrinsic-spec-arg-list
                        \OR extrinsic-kind-keyword
extrinsic-spec-arg      \IS language
                        \OR model
                        \OR external-name
language                \IS [ LANGUAGE = ] char-initialization-expr
model                   \IS [ MODEL = ] char-initialization-expr
external-name           \IS [ EXTERNAL_NAME = ] char-initialization-expr
\FNB

The following constraints are in addition to those specified in the May
1995 draft Fortran 95 standard.

\begin{constraints}

\item The rules for {\it extrinsic-spec-arg-list} are as if {\tt
EXTRINSIC} were a procedure with an explicit interface with a {\it
dummy-arg-list} of {\tt LANGUAGE, MODEL, EXTERNAL_NAME}, each of which
was {\tt OPTIONAL}. Note that, in an {\it extrinsic-spec-arg-list}, at
least one of {\it language}, {\it model}, or {\it external-name} must
occur.

\item In {\it language}, values of {\it char-initialization-expr} may
be:

\begin{itemize}

\item {\tt 'HPF'}, referring to the HPF language; if a {\it model} is
not explicitly specified, the {\it model} is implied to be {\tt 'GLOBAL'};

\item {\tt 'FORTRAN'}, referring to the ANSI/ISO standard Fortran
language; if a {\it model} is not explicitly specified, the 
{\it model} is implied to be {\tt 'SERIAL'};

\item {\tt 'C'}, referring to the ANSI standard C programming language;
if a {\it model} is not explicitly specified, the {\it model}
is implied to be {\tt 'SERIAL'}; or

\item an implementation-dependent value with an
implementation-dependent implied {\it model}.

\end{itemize}

If {\it language} is not specified or , it is the same as that of the host
scoping unit in which the {\it extrinsic-prefix} occurs.

\item In {\it model}, values of {\it char-initialization-expr} may be:

\begin{itemize}

\item {\tt 'GLOBAL'}, referring to the global model,

\item {\tt 'LOCAL'}, referring to the local model,

\item {\tt 'SERIAL'}, referring to the serial model, or

\item an implementation-dependent value.

\end{itemize}

If {\it model} is not specified or implied by the specification of a
{\it language}, it is the same as that of the host
scoping unit in which the {\it extrinsic-prefix} occurs.

\item All {\it language}s and {\it model}s whose names begin with the
three letters ``{\tt HPF}'' are reserved for present or future
definition by this specification and its successors.

\item In {\it external-name}, the value of {\it
char-initialization-expr} is the name by which the program unit is
known outside of the program, for example in the external file system
or program library. If {\it external-name} is not specified, its value
is implementation-dependent.

\end{constraints}

HPF defines three {\it extrinsic-kind-keyword}s: {\tt HPF}, {\tt
HPF_LOCAL}, and {\tt HPF_SERIAL}.

\BNF
extrinsic-kind-keyword  \IS HPF
                        \OR HPF_LOCAL
                        \OR HPF_SERIAL
\FNB

\begin{constraints}

\item {\tt extrinsic(HPF)} is equivalent to {\tt extrinsic('HPF',
'GLOBAL')}. In the absence of an {\it extrinsic-prefix} an HPF compiler
interprets a compilation unit as if it were of extrinsic kind {\tt
HPF}. Thus, for an HPF compiler, specifying {\tt EXTRINSIC(HPF)} or
{\tt extrinsic('HPF', 'GLOBAL')} is redundant. Such explicit
specification may, however, be required for use with a compiler that
supports multiple extrinsic kinds.

\item {\tt extrinsic(HPF_LOCAL)} is equivalent to {\tt extrinsic('HPF',
'LOCAL')}. A {\it main-program} whose extrinsic kind is {\tt HPF_LOCAL}
behaves as if it were a subroutine of extrinsic kind {\tt HPF_LOCAL}
that is called with no arguments from a main program of extrinsic kind
{\tt HPF} whose executable part consists solely of that call.

\item {\tt extrinsic(HPF_SERIAL)} is equivalent to {\tt
extrinsic('HPF', 'SERIAL')}. A {\it main-program} whose extrinsic kind
is {\tt HPF_SERIAL} behaves as if it were a subroutine of extrinsic
kind {\tt HPF_SERIAL} that is called with no arguments from a main
program of extrinsic kind {\tt HPF} whose executable part consists
solely of that call.

\item All {\it extrinsic-kind-keyword}s whose names begin with the
three letters ``{\tt HPF}'' are reserved for present or future
definition by this specification and its successors.

\end{constraints}

\begin{implementors}

Other {\it language}s or {\it model}s
may be defined and provided by compiler vendors. Although not part of
this HPF specification, they are expected to conform to the rules and
spirit of HPF extrinsic kinds.

An implementation may place certain restrictions on the programmer;
moreover, each extrinsic kind may call for a different set of
restrictions.

For example, an implementation on a parallel processor may find it
convenient to replicate scalar arguments so as to provide a copy on
every processor. This is permitted so long as this process is invisible
to the caller. One way to achieve this is to place a restriction on the
programmer: on return from the subprogram, all the copies of this
scalar argument must have the same value. This implies that if the
dummy argument has {\tt INTENT(OUT)}, then all copies must have been
updated consistently by the time of subprogram return.

\end{implementors}

\section{Calling HPF Extrinsic Subprograms}

A call to an extrinsic procedure behaves, as observed by a calling
program coded in HPF, exactly as if the subprogram were coded in HPF.
If a function or subroutine called from a program unit of an HPF
extrinsic kind does not have an explicit interface visible in the
caller, it is assumed to have the same extrinsic kind as the caller.

In order to call a subprogram of an extrinsic kind other than that of
the caller, that subprogram must have an explicit interface visible in
the caller, and the subprogram is expected to behave, as observed by
the caller, roughly as if it had been written as code of the same
extrinsic kind as the caller. Some of the responsibility for meeting
this requirement may rest on the compiler and some on the programmer.
This interface defines the ``HPF view'' of the extrinsic procedure.

A called procedure that is written in a model or language other than
HPF, whether or not it uses the local procedure execution model, should
be declared {\tt EXTRINSIC} within an HPF program that calls it. The
{\tt EXTRINSIC} prefix declares what sort of interface should be used
when calling indicated subprograms. If there is no extrinsic
specification then the users must assume full responsibility for
correctness of the implementation-dependent interface.

A {\it function-stmt} or {\it subroutine-stmt} that appears within an
{\it interface-block} within a program unit of an HPF extrinsic kind
may have an extrinsic prefix mentioning any extrinsic kind supported by
the language implementation. If no {\it extrinsic-prefix} appears in
such a {\it function-stmt} or {\it subroutine-stmt}, then it is assumed
to be of the same HPF extrinsic kind as the program unit in which the
interface block appears.

The procedure characteristics defined by an {\it interface-body} must
be consistent with the procedure's definition.

The definition and rules for a procedure with an extrinsic interface
lies outside the scope of HPF. However, explicit interfaces to such
procedures must conform to HPF. Note that any particular HPF
implementation is free to support any selection of extrinsic kinds, or
none at all except for {\tt HPF} itself which clearly must be supported
by an HPF implementation.

\subsection{Access to Types, Procedures, and Data}

\label{ext-access}

If a module X of one HPF extrinsic kind is used by a program unit Y of
another HPF extrinsic kind, then only names of items in X that Y is
entitled to use or invoke may be imported; that is, either X makes
private all items that Y is not entitled to use, or the {\tt USE}
statement in Y has an {\tt ONLY} options that lists only names of items
it is entitled to use.

Derived type definitions may be thought of as ``extrinsic kind
neutral;'' a program unit of any HPF extrinsic kind may use derived
type definitions from a module of any HPF extrinsic kind.

An HPF global program or procedure may call other HPF procedures that
are global, local, or serial.

An HPF local program or procedure may only call other HPF local
procedures.

An HPF serial program or procedure may only call other HPF serial
procedures.

A named {\tt COMMON} block in any program unit of an HPF kind will be
associated with the {\tt COMMON} block, if any, of that same name in
every other program unit of that same extrinsic kind; similarly for
unnamed {\tt COMMON}. (Such {\tt COMMON} storage behaves as other
declared data objects within program units of that extrinsic kind; in
particular, for {\tt HPF_LOCAL} code there will be one copy of the {\tt
COMMON} block on each processor.)

It is not permitted for any given {\tt COMMON} block name to be used in
program units of different HPF kinds within a single program;
similarly, it is not permitted for unnamed {\tt COMMON} to be used in
program units of different HPF kinds within a single program.

%A particular restriction is placed on HPF local procedures to be called
%from an HPF procedure or global program: array dummy arguments and
%array components of dummy arguments of a derived type must be declared
%as assumed-shape, both in the definition of the subprogram itself and
%in any interface blocks in other program units.

\begin{table}
\def\QQ#1#2#3{\hbox to 5em{{\bf #1}\quad{\bf #2}\quad{\bf #3}\hfill}}
\begin{tabular}{lr|c|c|c}
&&\multicolumn{3}{c}                 {extrinsic kind of the used module} \\
               &                &{\tt HPF}     &{\tt HPF_SERIAL}&{\tt
               HPF_LOCAL} \\ \hline
extrinsic kind &{\tt HPF}       & \QQ{T}{P}{D} & \QQ{T}{P}{ }   &
\QQ{T}{P}{ }   \\ \hline
of the using   &{\tt HPF_SERIAL}& \QQ{T}{ }{ } & \QQ{T}{P}{D}   &
\QQ{T}{ }{ }   \\ \hline
program unit   &{\tt HPF_LOCAL} & \QQ{T}{ }{ } & \QQ{T}{ }{ }   &
\QQ{T}{P}{D}   \\[8pt]
\multicolumn{5}{l}   {{\bf T} = derived type definitions} \\
\multicolumn{5}{l}   {{\bf P} = procedures and procedure interfaces} \\
\multicolumn{5}{l}   {{\bf D} = data objects}
\end{tabular}
\caption{Entities that a using program unit is entitled to access from
a module, according to the HPF extrinsic kind of each}
\end{table}

\subsection{The Effect of a Call}

A call to an extrinsic procedure must be semantically equivalent to a
call of an ordinary HPF procedure. Thus a call to an extrinsic
procedure must behave {\it as if} the following actions occur. The HPF
technical term {\it as if} means that the described actions should
appear to a user as if they occurred, in the order specified; an
implementation may carry out any actions in any order that provide the
correct user-visible effects.

\begin{enumerate}

\item All actions of the caller preceding the subprogram invocation
should be completed before any action of the subprogram is executed;
and all actions of the subprogram should be completed before any action
of the caller following the subprogram invocation is executed.

\item Each actual argument is remapped, if necessary, according to the
directives (explicit or implicit) in the declared interface for the
extrinsic procedure. Thus, HPF mapping directives appearing in the
interface are binding---the compiler must obey these directives in
calling local extrinsic procedures. Actual arguments corresponding to
scalar dummy arguments are replicated (by broadcasting, for example) in
all processors. As in the case of non-extrinsic subprograms, actual
arguments may be mapped in any way; if necessary, they are copied
automatically to correctly mapped temporaries before invocation of and
copied back to the actual arguments
after return from the extrinsic procedure.
Scalar dummy arguments and scalar function results behave as if they are
replicated on each processor. These mappings may,
optionally, be explicit in the interface, but any other explicit
mapping is not HPF conforming.

\item {\tt IN}, {\tt OUT}, and {\tt INOUT} intent restrictions should
be observed.

\item No HPF variable is modified unless it could be modified by an HPF
procedure with the same explicit interface. Note in particular that
even though an {\tt HPF_LOCAL} routine is not permitted to access and
modify HPF global data, other kinds of extrinsic routines may do so to
the extent that an HPF procedure could.

\item When a procedure returns and the caller resumes execution, all
objects accessible to the caller after the call are mapped exactly as
they were before the call. In particular, the original distribution of
arguments is restored, if necessary.

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

\end{enumerate}

\begin{implementors}

\item To ensure that all actions that logically precede the call are
completed, multiple processors may need to be synchronized before the
call is made.

\item If a variable accessible to the called routine has a replicated
representation, then all copies may need to be updated prior to the
call to contain the correct current value according to the sequential
semantics of the source program.

\item Replicated variables, if updated in the procedure, must be
updated consistently. More precisely, if a variable accessible to a
procedure has a replicated representation and is updated by (one or
more copies of) the procedure, then all copies of the replicated
variable must have identical values when the last processor returns
from the local procedure.

An implementation might check, before returning from the local
subprogram, to make sure that replicated variables have been updated
consistently by the subprogram. However, there is certainly no
requirement---perhaps not even any encouragement---to do so. This is
merely a tradeoff between speed and, for instance, debuggability.

Note that, as with a global HPF subprogram, actual arguments may be
copied or remapped in any way, so long as the effect is undone on
return from the subprogram.

\item To ensure that all actions of the procedure logically complete
before execution in the caller is resumed, multiple processors may need
to be synchronized after the call.

\end{implementors}

\section{Examples of Extrinsic Procedures}

Consider:

\CODE
PROGRAM DUMPLING
  INTERFACE
    EXTRINSIC('HPF','LOCAL') SUBROUTINE GNOCCHI(P, L, X)
      INTERFACE
        SUBROUTINE P(Q)
          REAL Q
        END SUBROUTINE P
        EXTRINSIC('COBOL','LOCAL') SUBROUTINE L(R)
          REAL R(:,:)
        END SUBROUTINE L
      END INTERFACE
      REAL X(:)
    END SUBROUTINE GNOCCHI
    EXTRINSIC('HPF','LOCAL') SUBROUTINE POTSTICKER(Q)
      REAL Q
    END SUBROUTINE POTSTICKER
    EXTRINSIC('COBOL','LOCAL') SUBROUTINE LEBERKNOEDEL(R)
      REAL R(:,:)
    END SUBROUTINE LEBERKNOEDEL
  END INTERFACE
  ...
  CALL GNOCCHI(POTSTICKER, LEBERKNOEDEL, (/ 1.2, 3.4, 5.6 /) )
  ...
END PROGRAM DUMPLING
\EDOC

The main program, {\tt DUMPLING}, when compiled by an HPF compiler, is
implicitly of extrinsic kind {\tt HPF}. Interfaces are declared to
three external subroutines {\tt GNOCCHI}, {\tt POTSTICKER}, and {\tt
LEBERKNOEDEL}. The first two are of extrinsic kind {\tt HPF_LOCAL} and
the third is of kind {\tt COBOL_LOCAL}. Now {\tt GNOCCHI} accepts two
dummy procedure arguments and so interfaces must be declared for those.
Because no {\it extrinsic-prefix} is given for dummy argument {\tt P},
its extrinsic kind is that of its host scoping unit, the declaration of
subroutine {\tt GNOCCHI}, which has extrinsic kind {\tt HPF_LOCAL}. The
declaration of the corresponding actual argument {\tt POTSTICKER} needs
to have an explicit {\it extrinsic-prefix} because its host scoping
unit is program {\tt DUMPLING}, of extrinsic kind {\tt HPF}.

As a second example, consider:

\CODE
  INTERFACE
    EXTRINSIC('HPF','LOCAL') FUNCTION BAGEL(X)
      REAL X(:)
      REAL BAGEL(100)
        !HPF$ DISTRIBUTE (CYCLIC) :: X, BAGEL
    END FUNCTION
  END INTERFACE

INTERFACE OPERATOR (+)
    EXTRINSIC('C','LOCAL') FUNCTION LATKES(X, Y) RESULT(Z)
      REAL, DIMENSION(:,:), INTENT(IN) :: X
      REAL, DIMENSION(:,:), INTENT(IN) :: Y
      REAL, DIMENSION(SIZE(X,1), SIZE(X,2)) :: Z
        !HPF$ ALIGN WITH X :: Y, Z
        !HPF$ DISTRIBUTE (BLOCK, BLOCK) X
    END FUNCTION
  END INTERFACE

  INTERFACE KNISH
    FUNCTION RKNISH(X)                      !normal HPF interface
      REAL X(:), RKNISH
    END RKNISH
    EXTRINSIC('SISAL') FUNCTION CKNISH(X)     !extrinsic interface
      COMPLEX X(:), CKNISH
    END CKNISH
  END INTERFACE
\EDOC

In the last interface block, two external procedures, one of them
extrinsic and one not, are associated with the same generic procedure
name, which returns a scalar of the same type as its array argument.
Note that the declaration of the explicit size of {\tt BAGEL} as 100 refers
to its {\it global} size and not its local size.
Also note that the {\tt ALIGN} statement asserts that {\tt X}, {\tt Y}, and
{\tt Z} all have the same shape.

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