Subject: hpff-doc: Changes to spmd-hpf-ext.tex

From: "Scott B. Baden" <[email-masked]>
Date: Thu, 29 Aug 1996 15:31:20 -0700 (PDT)

---------------------------------------------------------------------------
[email-masked] is a mailing list for HPF 2.0 language specification
authors and editors.  Instructions for adding or deleting yourself from this
list appear at the bottom of this message.
---------------------------------------------------------------------------
I've cleaned this up a bit and also brought
it in line with Extrinsic Approved Extension chapter.

Scott
% File: spmd-to-hpf-ext.tex

% Contents:
% Proposed Extension for SPMD interface to HPF  for HPF 2.0 document

% Revision history:
% Aug-8-96	Created by Scott B. Baden, UCSD
% Aug-15-96	Scott B. Baden, UCSD
% Aug-29-96	Scott B. Baden, UCSD

\chapter{Proposed Extension for SPMD calling HPF}
\label{ch-spmd-hpf}

{\em
Comments on this chapter should be directed to 
Scott Baden ({\tt [email-masked]})
and {\tt [email-masked]}.
Please use ``{\tt Comments on SPMD-to-HPF}'' as the {\tt Subject:}
line.
\par
}

\newcommand{\PROCS}  {{\tt PROCESSORS} }
\newcommand{\HPFINIT}  {{\tt HPF\_INIT} }
\newcommand{\HPFLOCAL}  {{\tt EXTRINSIC(HPF\_LOCAL)}}
\newcommand{\MAD}  {{\tt MAD}}
\newcommand{\CPP}  {{\tt C++}}
\newcommand{\MA}  {{\tt MAPPED\_ARRAY}}
\newcommand{\TMA}  {{\tt TO\_MAPPED\_ARRAY}}
\newcommand{\TOLOCAL}  {{\tt TO\_LOCAL}}
\newcommand{\offset}[1]{\begin{center} \tt #1 \end{center}} 

% ******************** Start of Document ********************

\section{SPMD Coordination of HPF}
\label{f90-locals}

The current HPF standard does not address the problem of
coordinating the concurrent execution of multiple HPF
procedure invocations, nor their interaction via
an SPMD harness written in an extrinsic language such as \CPP.
We propose an interface for
coordinating concurrently executing HPF procedures from an extrinsic SPMD layer.
This interface requires neither language extensions nor new language
features, and requires only a handful of library entries
that access the HPF run time system.
The proposed interface is language-independent.  It enables
inter-operability between software components developed in different
languages.

Note: Chuck Koelbel and Joel Saltz assisted in the development of this
proposal.

\section{Programming Model}
Our model comprises multiple HPF invocations that interact
with each other concurrently.
Separate HPF invocations will be orchestrated
via an  SMPD program, and
may or may not involve the identical code.
HPF invocations will import scalars and global arrays allocated from 
the SMPD  program.
The primary concern here in how to
deal with global arrays.

The SPMD code which controls the
interaction of multiple HPF invocations
may be   written in \HPFLOCAL\ or another
extrinsic language, e.g. \CPP.  We will use \HPFLOCAL\ here.
Other possibilities include multiple HPF programs that communicate
by calling an extrinsic SPMD program, which have been
addressed elsewhere in this document.
The discussions in this chapter
augment those outlined in the \HPFLOCAL\ interface with extensions
that may facilitate coordination via extrinsic languages like \CPP.

\section{The Interface}

Our proposed interface
specifies the interaction of an SPMD program, written
in an extrinsic language,  that calls HPF.
The interface supports the allocation of, and access to,
HPF global arrays from the SPMD coordinating code.
SPMD code views
each HPF global array as an entity called
a {\em mapped array} which will refer to as a \MA.

\subsection{Mapped Arrays}
It is assumed that the HPF compiler translates a call to an HPF
entry as follows.  First, an implementation-specific {\em name-mangling}
rule is applied to the entry name to conform with linkage conventions.
Second, each global array argument is converted to a \MA\
argument.  (Scalars are passed unchanged.)
The conversion process in implementation-dependent.
For example, some implementations convert each global array argument
into a pair of arguments: a
{\em mapped array descriptor} or \MAD\, and a pointer to
the start of the local storage for the mapped array.  In this case two
arguments would actually be passed for each mapped array argument,
though the number and representation of these arguments is generally
implementation-dependent.

By an abuse of notation we will refer to a mapped array reference
as if it were a reference to value of a distinguished type \MA.
While no such type may in fact  exist, the notation simplifies the
ensuing discussions.
We will employ the notation \TMA{\tt (A)} to
designate the desired conversion of global array argument {\tt A}
to a reference of (the fictitious) type \MA.
Thus, an argument of the form 
\TMA{\tt (A)}
is understood to represent the \(k>1\) actual parameters, which
might, for example,
contain a corresponding \MAD\ and starting address.
Similarly a declaration of the form
\offset{MAPPED\_ARRAY(A)} is understood to
declare \(k>1\) variables;  in the above example, there would
be one declaration for the \MAD,
another for the starting address to the corresponding local data.

As described below,
the interface includes various
entries for querying and manipulating \MA.
This interface should be packaged as a module
as described at the end of this chapter.
This module must be {\tt USEd} in all program source files
that employ the proposed interface.

\subsection{SPMD Execution}

This proposal defines a  language-independent
interface consisting of a set of
entries that enables SPMD code
written in an extrinsic language to communicate with HPF.
Interfaces for  other extrinsic languages,
e.g. C are out of the scope of this document.

We define SPMD execution as follows.  An SPMD program
executes on a {\em process group}.
We identify
an HPF \PROCS\  arrangement with  a process group, and employ
an opaque object called 
a {\em communicator} (as in MPI) to  specify the  group's membership.
The advantage of this approach is that the values returned by
{\tt NUMBER\_OF\_PROCESSORS} and {\tt PROCESSORS\_SHAPE} are well-defined,
as are collective communication operations.
%Note that it is possible to dynamically change the members of a process
%group or to change the group's topology by modifying
%attributes of the
%communicator.
Each process will be considered a physical processor by the HPF code.  The
called HPF program will have access to members of the process group.
It will not, however, have direct
access to processes outside that group.

All members
of a process group execute the same program in loosely synchronous
fashion, collectively 
making calls to HPF procedures (including those defined by
the proposed interface)
{\em as if\ } at the same time.
(Calls to HPF from SPMD may or may not need to be explicitly synchronized
at a barrier.)
As far as the HPF procedure is concerned, it will
not know
the origin of the argument, which could have in fact originated from
another HPF program.  It follows that
the SPMD program is responsible for passing mapped arrays to an HPF
procedure in conformance  with the procedure's expectations, i.e. the distribution
must match and so on. All invocations of HPF procedures
in the process group must pass the same \MA\ in each corresponding position
of the argument list (remembering that the accompanying local data
will be generally be different for each invocation.)
Scalar arguments must be consistent among
all members of the process group.

\begin{implementors}
Implementation of the ``HPF-from-extrinsic'' interface will be
facilitated with MPI.
However, implementors are free
to  employ their own implementation strategy.
Implementors who do not employ MPI 
need a mechanism for defining groups of processors that
only talk to each other; non-MPI implementations will obviously treat
these
differently from MPI ones.

The use of the proposed interface will be simplified by the provision
of a macro called \TMA, to
translate an HPF
global array reference to a \MA, containing, in our above
example, an appropriately formed
\MAD\ and the start of a local data area.
\end{implementors}

\subsection{HPF Run Time Initialization}

A call to a procedure \HPFINIT\ is required to establish
various state needed by the HPF run time system, that will, for
example, enable,
the processor to determine `who it is.'
\HPFINIT\ must   be passed a communicator corresponding
to the process group used to invoke the HPF program(s).
Successive calls to \HPFINIT\ may be used to set up alternative
\PROCS\ topologies or as required to invoke HPF code
on different processor groups.

\begin{implementors}
\HPFINIT\ should extract the \PROCS\ topology from the communicator
passed into it.

A mechanism is required for managing MPI-style communicators;
either MPI will be available from the SPMD program, or the
implementor must provide equivalent functionality.
\end{implementors}

Two or more HPF invocations may be simultaneously active if they execute on
different communicators with disjoint process groups.
To achieve this, the individual groups each define their own communicator.
The separate communicators are then used by \HPFINIT\
to establish the communication domains.

To handle multiple HPF invocations across different
processing groups, the SPMD coordinating code  may need to
explicitly query each processor  for membership within the desired communicator.
For example, if we are invoking procedures {\tt A1, A2}
on one processor group, and procedure {\tt B} on another, then
we employ the following:
\begin{verbatim}
!     Set up the processor groups
      call HPF_INIT(GroupA, ...)
      call HPF_INIT(GroupB, ...)

!     isMember( ) determines membership within the respective communicators
      if ( isMember(GroupA)) then
          call A1(...)      
          call A2(...)
      else if ( isMember(GroupB)) then
          call B(....)     
      end if
\end{verbatim}

HPF programs associated with overlapping communicators can also be defined,
but require additional system support to execute in parallel.  (In effect,
the underlying system must allow multi-threading to allow the process(es) in
the overlap to participate in both HPF programs at once.)  Such support may
be desirable, but is not mandated by this proposal.
Overlapping communicators could, however, be useful in different phases.
For example, one phase might use 8 processes, followed by another phase
using only 4.  The programmer could accomplish this by creating an
8-process communicator and a 4-processes communicator with a subset of the
processes.  \HPFINIT\ would have to be called to establish
the communicator for each phase to alert
the HPF runtime that a different communicator was in use.

Regardless of how the communicators are set up, an HPF procedure has
access only to the process group associated with the communicator in the
last executed \HPFINIT\ call.
This allows us to define {\tt NUMBER\_OF\_PROCESSORS} to return the number
of processes in that communicator, and similarly make consistent
definitions for the other HPF inquiry procedures.
It follows that
SPMD code must invoke an HPF procedure on {\em exactly}
those processors in the intended processor group---no more an no less.
This will likely be supported by a conditional statement which
will determine membership within the respective communication domains
established by SPMD program.

Note that physical processors in different communicators may
return different values for {\tt NUMBER\_OF\_PROCESSORS}, but they cannot
be executing the same instantiation of an HPF procedure.
This implies that
actual arguments to an HPF procedure must all be allocated
from the same process group,
and that data motion between mapped arrays allocated to different
process groups must be handled at the SPMD level.
(MPI's inter-communicators allow precisely
this sort of communication.)
We restrict global data accessed in the HPF procedure
in the same way.

\subsection{Global Array Allocation From SPMD}

The functionality required to support extrinsic SPMD coordination of HPF
invocations centers on the ability to allocate, from the SPMD level, global
(mapped)
HPF arrays with a specified \PROCS\ arrangement, alignment,
and decomposition.  In the interest of simplicity, allocation
will be restricted as follows.
\begin{enumerate}
\item Only arrays of builtin types are permitted, i.e. arrays
of derived types are excluded.

\item Only {\tt BLOCK, *, CYCLIC, } and {\tt CYCLIC(K)}
decompositions are permitted.

\item Only the  identity alignment is permitted.  Identically
aligned arrays must have the same rank and extents.
\end{enumerate}

A process group dynamically allocates a mapped array using the call

\noindent
\subsubsection*{alloc\_mapped\_arrayTTT(A, NDIM, EXTENTS, DECOMP, [ALIGN])}

\begin{tabular}{ll}
{\bf OUT} A &         a MAPPED\_ARRAY \\
{\bf IN} NDIM & number of dimensions \\
{\bf IN} EXTENTS & extents of the indices of the array  ({\tt 2*NDIM} entries) \\
{\bf IN} DECOMP & decomposition ({\tt NDIM} entries) \\
{\bf IN} ALIGN & a previously allocated \MA\ (optional) \\
\end{tabular}
\vspace{0.1in}

\noindent
{\tt TTT} is one of 5 builtin HPF types:
\offset{REAL, DOUBLE PRECISION, COMPLEX, DOUBLE PRECISION COMPLEX, INTEGER.}

The first
argument actually refers to the global array to be allocated by HPF.
The {\tt NDIM} and {\tt EXTENT} arguments
specify the number  and extent of the array axes, the {\tt DECOMP}
argument their decomposition across processors.  Each element
of {\tt DECOMP}  must be one of the following predefined names:
\offset{SERIAL, BLOCK, CYCLIC, CYCLIC(K)}

\noindent
where {\tt CYCLIC(K)} will be mapped onto distinct values for 
distinct values of {\tt K.}

The final argument is optional; it is specifies an existing array
to which the newly-allocated array will be aligned.
Such allocations are restricted to identity alignments only;
the {\tt NDIM, EXTENTS,} and {\tt DECOMP} specifications must
also be identical as well.

\subsection{Data Access}

The extrinsic SPMD layer may access a global array through a
\MA\ reference.
The interface  does not permit direct access
to the \MA, however,
since manufacturers need flexibility in representing a mapped
array.
Rather, it treats a \MA\ as an opaque object, and provides
primitives to
query the global array---e.g.
determine global shape, local shape, decomposition, and so on---or
to modify it.

The SPMD programmer has two means of accessing a mapped
array. The first way is  via the \HPFLOCAL\ interface, which 
permits access to various descriptive information
and to local data.  The second way is through
a new set of primitives that perform global copying, and may
be used to access non-local data.  

\subsubsection{Local Data Access}

For local data access we use the
\HPFLOCAL\ interface (see \ref{hpf-local}), adapted as follows
for the task at hand.

\begin{enumerate}
\item All mapped HPF arrays accessible from an
SPMD procedure are logically carved
up into blocks; the SPMD process executing on a particular physical
processor sees an array containing just those elements of the global
array that are mapped to that physical processor.

\item The model assumes that array axes are mapped independently to axes of a
rectangular \PROCS\ grid, each array axis to at most one \PROCS\
axis (no ``skew" distributions) and no two array axes to the same
\PROCS\ axis.  This restriction suffices to ensure that each
physical processor contains a subset of array elements that can be
locally arranged in a rectangular configuration (of course to compute
the global indices of an element given its local indices or vice verse,
may be quite a tangled computation-- but it will be possible)

\item
The portion of a mapped array argument
in an {\tt HPF\_LOCAL} subprogram
associated with a global array dummy argument  in an HPF program
may be accessed in a block-by-block
fashion.  Library procedures such as {\tt LOCAL\_BLKCNT},
{\tt
LOCAL\_LINDEX}, and {\tt LOCAL\_UINDEX}, allow easy access to the local
storage of a particular block.
\end{enumerate}

\begin{implementors}
Random access to the elements of a mapped array is likely to be
expensive, and a separate interface described below
should be used to handle block copies.

Implementations that employ ghost cells or shadow regions may need to provide
the capability of accessing such additional data.  This proposal
does not specify how ghost cells are to be accessed or manipulated.
\end{implementors}

\subsubsection{HPF_LOCAL Primitives}
Included are\\

\begin{tabular}{lll}
{\tt GLOBAL\_ALIGNMENT} & {\tt GLOBAL\_DISTRIBUTION} & {\tt GLOBAL\_TEMPLATE } \\
{\tt GLOBAL\_LBOUND  } & {\tt GLOBAL\_UBOUND } & {\tt GLOBAL\_SHAPE  }\\
{\tt GLOBAL\_SIZE } & {\tt ABSTRACT\_TO\_PHYSICAL  } & {\tt PHYSICAL\_TO\_ABSTRACT }\\
{\tt LOCAL\_TO\_GLOBAL  } & {\tt GLOBAL\_TO\_LOCAL } & {\tt LOCAL\_BLKCNT  }\\
{\tt LOCAL\_LINDEX } & {\tt LOCAL\_UINDEX} & {\tt MY\_PROCESSOR }\\
\end{tabular}

\ \\
\noindent

In order to use the \HPFLOCAL\ interface, we need a way of converting
a \MA\ actual parameter into a form expected by
the \HPFLOCAL\ library.
To this end we define the macro \TOLOCAL, which takes
a \MA\ argument and converts it into the appropriate representation
expected by the \HPFLOCAL\ interface.
For example, we consider the
\HPFLOCAL library primitive {\tt GLOBAL\_SHAPE}.

Assuming that global array {\tt A} has been allocated by the call
\offset{alloc\_mapped\_array(TO\_MAPPED\_ARRAY(A),NDIM=2,EXTENTS=/(3,100,1,200/),...)}
then the value returned by
{\tt GLOBAL\_SHAPE(TO\_LOCAL(A))} is \VECTOR{98 200}.

\subsubsection{Global Copying }
The Interface also provides primitives for moving data
over global sets of indices.
The first primitive merely copies one array to another.

\subsubsection*{copy\_mapped\_array\_TTT(SRC, DEST)}

\begin{tabular}{r ll}
{\tt IN} & {\tt SRC} &		\MA -- source \\
{\tt OUT} & {\tt DEST} &	\MA -- destination \\
\end{tabular}

\noindent
where {\tt TTT} is one of 5 built in HPF types:
\offset{REAL, DOUBLE PRECISION, COMPLEX, DOUBLE PRECISION COMPLEX, INTEGER.}

\noindent
The source and destination descriptors may or may not  be allocated to the same
processor group.

There is also  a variant of
{\tt copy\_mapped\_arrayTTT} that copies over designated array
sections:

\subsubsection*{copy\_mapped\_array\_secTTT(SRC, DEST, S\_SECT, D\_SECT)}

\begin{tabular}{r ll}
{\tt IN} & {\tt SRC} &		\MA -- source \\
{\tt OUT} & {\tt  DEST} &		\MA -- destination  \\
{\tt IN} & {\tt S\_SECT} &		source array section specifier \\
{\tt IN} & {\tt D\_SECT} &		destination array section specifier \\
\end{tabular}

The array section specifiers are {\tt INTEGER} \(d\)-tuples
(arrays)
where \(d\) is the common rank of the arrays.
The format of these tuples is \((r_0, r_1, ..., r_{d-1}\))
where each \(r_k\) specifies the integer range of indices for axis \(k\),
i.e. the array section {\tt (3:4, 5:6)} is specified as
{\tt /(3,4, 5,6/).}

\begin{implementors}
Though the {\tt copy\_mapped\_array\_secTTT( )}
could be implemented
using the \HPFLOCAL\ interface, doing so may not to
be as efficient as taking advantage of direct access to
layout information provided by the compiler.
\end{implementors}

\subsection{Summary of what is to be provided}
In practice, multi-lingual programming  can be given only minimal
language and compiler support.
Some installation-dependent coding is
required, for example to handle name mangling, argument
passing conventions, and so on.  Such code is generally not portable.

We propose an interface that does not rely on language extensions,
yet which offers reasonable assurances of portability.
To this end,
we strongly recommend that Interfaces for SPMD applications
inter-operating with
HPF provide the following constants and entries and package
them in a 
{\tt MODULE}.  (In the
case of {\tt f77, C,} or \CPP, these would be packaged as part of
a header file, and probably contain a class definition in the case of \CPP.)
In addition, certain macros should be defined as described below to facilitate
manipulation of a \MA.

\subsubsection*{Constants}
\begin{tabular}{llll}
{\tt SERIAL} & {\tt BLOCK} & {\tt CYCLIC} & {\tt CYCLIC(K)}\\
\end{tabular}

Note: {\tt CYCLIC(K)} will probably be supported with a macro.

\subsubsection*{Library Primitives}
\begin{tabular}{ll}
{\tt HPF_INIT} & {\tt alloc\_mapped\_arrayTTT}\\
{\tt copy\_mapped\_array\_TTT} & {\tt copy\_mapped\_array\_secTTT} \\
\end{tabular}

\vspace{0.1in}
\noindent
Note: {\tt TTT} is one of 5 built in HPF types:
\offset{REAL, DOUBLE PRECISION, COMPLEX, DOUBLE PRECISION COMPLEX, INTEGER.}

\subsubsection*{Macros}
It is recommended that the macro
\TMA\ be provided to facilitate the handling of the multiplicity
of  values that comprise a \MA\ argument, and the macro \TOLOCAL\
to assist in using the \HPFLOCAL\ interface.
The macro \MA\  is recommended for declaring a value of 
type \MA, e.g.
\offset{MAPPED\_ARRAY(A)}
declares a set of variables that collectively represent
a \MA.
\section{Programming Example}

The application is to iteratively solve Poisson's equation on a
2-dimensional irregularly-shaped domain consisting of two coupled rectangular
blocks of different sizes.  The same solver is applied to each  block.  

Because the blocks have different sizes we will
allocate them to different size \PROCS\ subsets in order to balance
the workloads.  Prior to computing,
each block must furnish boundary conditions that couple
it to the other block.

\CODE
! Example illustrating coordination from an extrinsic layer
! Solve the Laplace Equation on an irregular domain using Red/Black SOR
! The computational domain consists of two squares A&B
! sitting side by side and aligned with the y axis
! Square A is m x m, Square B is n x n

extrinsic(hpf_local) program iter
!   The MAPPED_ARRAY package is part of the interface
!   It includes definitions for constants like BLOCK, SERIAL,
!   the various routines that allocate global arrays, and so on
    use MAPPED_ARRAY
!   This package specifies an HPF binding for MPI
    use MPI

!   MAPPED_ARRAY() is a macro which declares the various pieces of information
!   that make up a MAPPED_ARRAY
    MAPPED_ARRAY(A)
    MAPPED_ARRAY(B)

!   Extents of A and B
    integer, array(4) :: A_EXT = /(0,m+1,0,m+1/), B_EXT = /(0,n+1,0,n+1/)
!   Their decomposition: SERIAL corresponds to  * in HPF
    integer, array(2) :: DECOMP = /(BLOCK,SERIAL/)

    real resid, convergence
    real function smooth
    real, parameter :: EPSILON = 0.001

! Communicators
    Communicator COMM_A, COMM_B
   
!   The size of the blocks are inputs to the program
    read *, m, n

!   Allocate processors 0 to K-1  to block A, the remainder to block B
!   The value of K is determined by the relative sizes of m & n
!   ZERO_TO_KM1 and K_TO_PM1 are integer "color" arrays (i.e.  MPI)
!   specifying the  membership of each processor in the respective groups

!   Set up the process groups and communicators, one for each block
    call MPI_COMM_SPLIT(MPI_COMM_WORLD,ZERO_TO_KM1,DUMMY,COMM_A,IERROR)
    call init_HPF(COMM_A)

    call MPI_COMM_SPLIT(MPI_COMM_WORLD,K_TO_PM1,DUMMY,COMM_B,IERROR)
    call init_HPF(COMM_B)

    if (isMember(COMM_A)
!       TO_MAPPED_ARRAY( ) converts the global array reference to a
!       MAPPED_ARRAY.  k>1 arguments may correspond to TO_MAPPED_ARRAY(A)
        call alloc_mapped_arrayREAL(TO_MAPPED_ARRAY(A), 2, A_EXT, DECOMP)
    if (isMember(COMM_B)
        call alloc_mapped_arrayREAL(TO_MAPPED_ARRAY(B), 2, B_EXT, DECOMP)

    convergence = 10.0 * epsilon

    do while ( convergence < epsilon )
!       Fill in the boundary cells
        mn = min(m,n)
        I0 = /(m+1,m+1,1,mn/)
        I1 = /(m,m,1,mn/)

!       All processors in COMM_A and COMM_B must participate
!       which in this case covers all processors in MPI_COMM_WORLD
!       In a multiblock code with > 2 blocks, appropriate guards would be
!       required to restrict execution of copy_mapped_array_secTTT( ), as
!       2 communicating grids would cover only a subset of MPI_COMM_WORLD

        call copy_mapped_array_secREAL(MAPPED_ARRAY(B),MAPPED_ARRAY(A),I0,I0)
        call copy_mapped_array_secREAL(MAPPED_ARRAY(B),MAPPED_ARRAY(A),I1,I1)

!       Ensures that the global reductions are done correctly.
        residA = 0
        residB = 0

!       These calls to HPF execute in different processor groups; their
!       respective arguments were allocated with different communicators
        if (isMember(COMM_A))
            residA = smooth(A)

        if (isMember(COMM_B))
            residB = smooth(B)

!       global reduction over all processes (MPI functionality)
        call _max_scalar_REAL(residA, MPI_COMM_WORLD)
        call _max_scalar_REAL(residB, MPI_COMM_WORLD)

        convergence = amax(residA, residB)
    enddo
end program

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