
\documentstyle[psfig]{article}


%\documentstyle[psfig,12 pt]{article}
%
%\textwidth=6.5in
%\textheight=8.5in
%\voffset=-0.5in
%\hoffset=-0.5in

%\documentstyle[psfig]{llncs}

\begin{document}

\pagestyle{empty}

\title{Language Bindings for a Data-Parallel Runtime}

%\author{Guansong Zhang, Bryan Carpenter, Geoffrey Fox \\
%        Xiaoming Li\thanks{Visiting scholar from HIT, China},
%        Xinying Li, Yuhong Wen \vspace{5mm} \\
%        \em NPAC at Syracuse University \\
%        \em Syracuse, NY 13244 \\
%        \em \{zgs,dbc,gcf,lxm,xli,wen\}\@npac.syr.edu}

\author{Bryan Carpenter, Geoffrey Fox \\
        Xinying Li, Yuhong Wen, Guansong Zhang \vspace{5mm} \\
        \em NPAC at Syracuse University \\
        \em Syracuse, NY 13244 \\
        \em \{dbc,gcf,xli,wen,zgs\}\@npac.syr.edu}


\date{October 20, 1997}

\maketitle

\begin{abstract}
The NPAC kernel runtime, developed in the PCRC (Parallel Compiler
Runtime Consortium) project, is a runtime library with special support
for the High Performance Fortran data model.  It provides array
descriptors for a generalized class of HPF-like distributed arrays,
support for parallel access to their elements, and a rich library of
collective communication and arithmetic operations for manipulating these
arrays.  The library has been successfully used as a component in
experimental HPF translation systems.  With prospects for early
appearance of {\em fully-featured, efficient} HPF compilers looking
questionable, we discuss a class of more easily implementable
data-parallel language extensions that preserve many of
the attractive features of HPF, while providing the programmer with
direct access to runtime libraries such as the NPAC PCRC kernel.
\end{abstract}

\section{Introduction}


As part of the PCRC\cite{pcrc:1} project we completed development of a
high-level runtime library for data-parallel languages\cite{NPACker}.
The motivating goal was to simplify translation of HPF by providing a
coherent interface to the distributed array descriptors and collective
operations needed for straightforward, efficient translation of
parallel constructs like FORALL and array assignments.  This goal
was achieved quite successfully, and two experimental subset HPF
translators have used the library to manage their communications
\cite{Zha97,Mer96}.

%In keeping with the multilingual goals of PCRC,
%other language interfaces to the library have been developed, or are
%under development (specifically, C++ and Java).

Unfortunately it is evident that implementing compilers for 
a language as complex as {\em full} HPF is a formidable task.
While the runtimes that have evolved to support HPF
and its kin are powerful and have an underlying elegance, using them
without a compiler---through direct calls from an SPMD program written
in a standard language---is clumsy and error prone.  This is due in part
to the large number of parameters needed to describe distributed
arrays.  We face the unpleasant prospect that---in the near term
future at least---neither HPF or conventional languages will permit
full exploitation of libraries such as the one developed in PCRC.

In this paper we discuss possibilities for enhancing
programming languages like Fortran with relatively
simple extensions to support
declaration and manipulation of HPF-like distributed arrays.  In
contrast to HPF, our extensions assume the programmer specifies in full
logical detail exactly where computations and communications are
performed.  This makes compilers a much more straightforward
proposition.  In spite of this simplification, we argue
that---supplemented by a binding to a suitable collective communication
library such as ours---the resulting hybrid data-parallel/SPMD
programming models can achieve a level of elegance and expressivity
comparable to full HPF.  Moreover, because the underlying programming
model is SPMD, low-level message-passing phases of computation can be
freely interleaved with data-parallel phases, without passing through
an awkward ``extrinsic'' interface.

\section{Background: runtime kernel\label{runtime}}

The kernel of NPAC library is a C++ class library.  It is
most directly descended from the run-time library of an earlier
research implementation of HPF\cite{Mer96} with influences from the
Fortran 90D run-time and the CHAOS/PARTI libraries.  The kernel is
currently implemented on top of MPI.  The library design is solidly
object-oriented, but efficiency is maintained as a primary goal.

\begin{figure}[bt]
\centerline{\psfig{figure=architecture.eps,width=4.8in}}
\caption{NPAC runtime architecture\label{architecture}}
\end{figure}

The overall architecture of the library is illustrated in figure
\ref{architecture}.  At the top level there are several
compiler-specific interfaces to a common run-time kernel.  
The four interfaces shown in the figure are illustrative.
They include two different Fortran interfaces (used by different HPF
compilers), a user-level C++ interface called ad++\footnote{ad++ is
currently implemented as a set of header files defining distributed
arrays as type-secure container class templates, function templates for
collective array operations, and macros for distributed control
constructs.}, and a Java interface under development\footnote{We also intend to
produce a METACHAOS interface.}.  The development of several top-level
interfaces has produced a robust kernel interface, on which we
anticipate other language- and compiler- specific interfaces can be
constructed relatively straightforwardly.

The largest part of the kernel is concerned with global communication
and arithmetic operations on distributed arrays.  These are represented on
the right-hand side of figure \ref{architecture}.  
The communication operations supported include HPF/F90 array intrinsic
operations such as {\tt CSHIFT}, the function {\tt write\_halo}, which
updates ghost areas of a distributed array, the function {\tt remap},
which is equivalent to a Fortran 90 array assignment between
two conforming sections of two arbitrarily distributed HPF arrays,
and various gather- and scatter- type operations allowing irregular patterns
of data access.  Arithmetic operations supported include all F95
array reduction and matrix arithmetic operations, and HPF
combining scatter.  A complete set of HPF standard library functions
is under development.

All the data movement schedules are dependent on the infra-structure on the
left-hand side of the figure \ref{architecture}.  This provides the
distributed array descriptor, and basic support for traversing
distributed data (``distributed control'').  Important substructures
in the array descriptor are the {\em range} object, which describes
the distribution of an array global index over a process
dimension, and the {\em group} object, which describes the embedding
of an array in the active processor set.

At the time of writing the kernel is fully functional and quite mature,
two of the four interfaces illustrated are complete, and others are
in progress.

\section{Outline of an extended Fortran dialect}

It is hoped that eventually the HPF language definition and the associated
compilers will mature to the point where it is the language of choice
for scientific application programmers who need the performance of
parallel machines.
%Some four years after definition of the language,
It is not clear that we are close to seeing this goal achieved.  As
an interim measure, at least, we are
considering other approaches that capture the some of the
most important concepts and technologies associated with HPF without
relying on very advanced compilers, which have been slow to
materialize.

Our suggested language extensions provide a flexible hybrid of the data parallel
and SPMD approaches.  They provides HPF-like distributed arrays as
language primitives, and new {\em distributed control} constructs to
facilitate access to the local elements of these arrays.
In the SPMD mold,
the model allows processors the freedom to independently execute
complex procedures on local elements: it is not
constrained by SIMD-style array syntax.

All access to {\em non-local} array elements must go through
library functions---typically collective communication operations.
This puts an extra onus on the programmer; but making communication
explicit encourages the programmer to write algorithms that exploit
locality, and simplifies the task of the compiler writer.

A distinguishing
property of the proposed system, compared to HPF, is that it includes
ordinary Fortran as a strict subset, {\em and ordinary Fortran
constructs are unchanged by the translator}.
Our system will {\em not} attempt to exploit parallelism even in
``explicitly parallel'' constructs such as the array syntax of Fortran
90 or the FORALL statement of Fortran 95.  This policy drastically
simplifies the translator, and gives the programmer much finer control
over the generated code.

\subsection{Example syntax}

The examples in the following sections use certain syntax extensions.  The
syntax is purely illustrative.  We have yet to define a detailed
detailed concrete syntax for Fortran (more detailed investigations
are in progress in C++ and Java).  Where possible
we copy the syntax of HPF, because that syntax
is widely understood.

%The distributed data {\em model} of HPF will be subsumed
%wholesale.  Although our presentation of distributed arrays
%differs in some obvious ways, we explicitly or implicitly support all the
%distribution and alignment options of HPF.

Processor arrangements will be declared as in HPF.
The explicit {\tt TEMPLATE} concept
of HPF is abandoned in favour a {\em distributed range} concept.
A distributed range
represents a range of subscript values, and incorporates a mapping
of that range into a dimension of a processor arrangement.
The mapping options will be similar to HPF: block, cyclic, block-cyclic, etc.
A distributed array declaration is distinguished from a
sequential array declaration by using a
different kind of brackets:
\small
\begin{verbatim}
  PROCESSORS P(4, 4)

  RANGE X(N), Y(M)
  DISTRIBUTE X ONTO P(BLOCK, *)
  DISTRIBUTE Y ONTO P(*, CYCLIC)

  REAL A [X, Y]
  INTEGER B [Y]
  INTEGER C [X, Y, 10]
  REAL D [X(1 : N / 2), Y(::2)]
\end{verbatim}
\normalsize
Ranges {\tt X} and {\tt Y} are each distributed over a single dimensions
of the processor arrangement.
The array {\tt A} is an {\tt N} by {\tt M} distributed array,
distributed blockwise in its first dimension and cyclically in its
second.  In general the brackets in a distributed
array declaration contain a list of {\em orthogonal} ranges.  {\tt B} is a one
dimensional array distributed cyclically  in the second dimension of
{\tt P} and implicitly replicated over the first.  {\tt C} is a three
dimensional array with two distributed and one {\em collapsed} range.
The declaration of D illustrates how HPF-like non-trivial alignment
relations can be introduced by using subranges in array declarations.
{\tt D} is an {\tt N / 2} by {\tt N / 2} distributed array.

Provision of distributed arrays as language primitives provides a
clean, systematic interface to libraries of collective operations.
%A standard library will parallel Fortran 90
%transformational intrinsics on ordinary sequential arrays.
Examples of standard collective operations are
\small
\begin{verbatim}
  CALL DA_CSHIFT(DST, SRC, DIM, SHIFT)
  RES = DA_SUM(SRC)
  CALL DA_REMAP(DST, SRC)
\end{verbatim}
\normalsize
Here {\tt DST} and {\tt SRC} are distributed arrays.  The
subroutine {\tt DA\_CSHIFT} is closely analogous to the Fortran 90 {\tt
CSHIFT} intrinsic.
%  The arguments should be {\em aligned} arrrays.
The function {\tt DA\_SUM} sums all elements of the argument and broadcasts
the result value.  The subroutine {\tt DA\_REMAP} takes two distributed
arrays of the same shape {\em which may have any, unrelated mapping}
and copies the elements of one to the other.

The syntax for declaration of {\em distributed data} is complemented by
syntax extensions for {\em distributed control}.  The simplest
example is the {\tt AT} construct.
A distributed array is subscripted with a global subscript.
Subscripting expressions are only meaningful on the
processors that hold the elements selected.  To make
sure a statement using a distributed array element is
only executed on a processor
that holds copies of of the element, a stylized form of conditional
called the {\tt AT} construct is provided.
The code fragment below illustrates a pair of nested {\em at} constructs.
\small
\begin{verbatim}
  AT(X(n))
    AT(Y(17))
      A [n, 17] = B [17] + 23 ;
    ENDAT
  ENDAT
\end{verbatim}
\normalsize
This construct is an abstraction of the {\em if}
statement in a low-level SPMD program that tests whether the local
processor contains a desired array element.

A more important and powerful distributed control construct is the
{\tt OVERALL} distributed loop.  This construct
superficially resembles the Fortran 95 {\tt FORALL} construct.
It differs from {\tt FORALL} in several respects
\begin{itemize}
\item
The index ranges are distributed ranges, not triplets.
\item
There are no restriction on what kind of statements can appear in the
body of the construct.  Any executable statements are allowed.
This reflects the explicit SPMD emphasis of the language, in constrast
to the SIMD heritage of HPF.
\item
Each ``iteration'' of the construct is localized to a well-defined processor
(or group of processors)
through the use of distributed ranges for the loop indices.  An iteration
should only access array elements held locally on a processor
executing the iteration.
This restriction sounds inconvenient: in practise it can usually be
accomodated quite painlessly by limiting access
to arrays aligned with the loop ranges.
\end{itemize}
In this simple example of an {\tt OVERALL} construct is used to
initialize the array {\tt A} with some expression involving
the global subscripts
\small
\begin{verbatim}
  OVERALL(I = X, J = Y)
    A [I, J] = I + J
  ENDOVERALL
\end{verbatim}
\normalsize
In a slightly more complex example we add together elements from two
arrays
\small
\begin{verbatim}
  OVERALL(I = X, J = Y)
    A [I, J] = B [J] + C [I, J, 17]
  ENDOVERALL
\end{verbatim}
\normalsize
This operation is legal due to the alignment relation between the
{\tt A}, {\tt B} and {\tt C} arrays.

\subsection{Example 1: Cholesky decomposition}

\begin{figure}[btp]
\footnotesize
\begin{verbatim}
  INTEGER, PARAMETER :: N = 100

  PROCESSORS P(NP)
  RANGE, DISTRIBUTE ONTO P(CYCLIC) :: X(N)

  REAL A [N, X]

  REAL B [N]          ! used as a buffer

  ! initialize the array;

  AT(X (1))
    A [1, 1] = SQRT(A [1, 1])
  ENDAT

  DO K = 1, SIZE - 1
    AT(X (K))
      DO S = K + 1, SIZE
        A [S, K] = A [S, K] / A [K, K]
      ENDDO
    ENDAT

    CALL DA_REMAP(B [K + 1 :], A [K, K + 1 :])

    OVERALL(I = X (K + 1 :))
      DO J = I, SIZE
        A [J, I] = A [J, I] + B [J] * B [I]
      ENDDO
    ENDOVERALL

    AT(X (K + 1))
      A [K + 1, I] = SQRT(A [K + 1, I])
    ENDAT
  ENDDO
\end{verbatim}
\normalsize
\caption{\label{cholesky}Implementation of Cholesky decomposition
in mooted syntax.}
\end{figure}

Figure \ref{cholesky} gives a parallel implementation
of Cholesky decomposition in the extended language.
In the declaration of {\tt A} the first dimension is specified with
an integer range rather than a distributed range.  This means that
this dimension is on-processor---{\em collapsed} in HPF terminology.
In general the collective operation {\tt DA\_REMAP} copies the elements of
one distributed array or section to another of the same shape.  In the
current example it is used to implement a variant of the the operation
called {\tt GATHER-TO-ALL} in MPI.
In spite of the fact that we have demanded that the
programmer explicitly specify which processor performs every operation,
and exactly how communications are to be inserted, we claim that this
implementation is at least as simple as any that could be achieved in
HPF (and clearer than anything that could be written in MPI).

Other features illustrated by this example are construction of
sections of distributed arrays (directly analogous to construction
of sections of Fortran 90 arrays) and use of a {\em subrange} to
parametrize an {\tt OVERALL} loop.

\subsection{Example 2: Red-Black relaxation}

\begin{figure}[btp]
\footnotesize
\begin{verbatim}
  PROCESSORS P(NP, NP)

  RANGE X(N), Y(N)
  DISTRIBUTE X ONTO P(BLOCK, *)
  DISTRIBUTE Y ONTO P(BLOCK, *)
  SHADOW (1) X, Y

  REAL A [X, Y]

  ! initialize the array

  OVERALL(I = X, J = Y)
    A [I, J] = ...
  ENDOVERALL

  DO ITER = 1, NITER
    DO ICOLOUR = 0, 1
      CALL DA_WRITE_HALO(A, (/CYCL, CYCL/), (/1, 1/))

      OVERALL(I = X)
        OVERALL(J = Y(MOD(ICOLOUR + I, 2) : : 2))
          A [I, J] = (A [I, J - 1] + A [I, J + 1] +     &
     &                A [I - 1, J] + A [I + 1, J]) / 4
        ENDOVERALL
      ENDOVERALL
    ENDDO 
  ENDDO
\end{verbatim}
\normalsize
\caption{\label{red_black}Implementation red-black relaxation in
mooted syntax.}
\end{figure}

Figure \ref{red_black} gives a parallel implementation
of red-black relaxation in the new language.  Following the
proposals of HPF 2.0 standard, {\em ghost regions} are allowed
for arrays.  In the example the width of these regions is defined by
specifying the {\tt SHADOW} attribute (in our language this attribute is
specified for ranges rather than arrays).  The ghost regions are
explicitly brought up to date using the subroutine {\tt DA\_WRITE\_HALO}
from the standard library.  The arguments following the array itself
define the mode of updating ghost regions at the extremes of the array (cyclic
wraparound in this case) and the actual width of the halo to be written.
Subsequently the {\tt OVERALL} construct can access elements of
the array displaced by up to one place from the alignment of the
parametric range.

Note the ease with which sites of a particular colour are selected
by using nested {\tt OVERALL} constructs, parametrizing the inner one
with a subrange.  In HPF this could be expressed using array syntax
and a {\tt WHERE} construct, but that would be relatively inefficient.
Alternatively it could be expressed using nested {\tt INDEPENDENT DO} loops or
{\tt FORALL}s, but nesting these constructs makes it difficult for
a compiler to analyse them and emit efficient parallel code.  In our
scheme no special analysis is necessary.  A simple efficient scheme is
applied universally to translate subscripts in {\tt OVERALL}
constructs.



\section{Discussion and related work}

ZPL\cite{zpl}
is a new programming language for scientific computations.
Like Fortran 90, it is an array language.  It has an idea of
performing computations over a {\em region}, or set of indices.
Within a compound statement prefixed by a {\em region specifier}, aligned
elements of arrays distributed over the same region can be accessed.
This idea has certain similarities to our {\tt OVERALL} construct.
In ZPL, parallelism and communication are more implicit than in our
proposed languge.  The connection between ZPL programming and SPMD
programming is not explicit.  While there are certainly attractions
to the more abstract point of view, the language we are proposing
deliberately provides lower-level access to the parallel machine.

%\subsection{F-\,-}

F-\,-\cite{Num97}
is an extended Fortran dialect for SPMD programming.  The
approach is quite different to the one proposed here.  In F-\,-, array
subscripting is local by default, or involves a combination of local
subscripts and explicit process ids.  There is no analogue of global
subscripts, or HPF-like distribution formats.
In F-\,- the logical model of communication
is built into the language---remote memory access with intrinsics for
synchronization.
In our proposal there are no communication primitives in the language
itself.  We follow the MPI philosophy of providing communication
through separate libraries.  
While F-\,- and our approach share an underlying
programming model, we believe that our framework offers greater opportunities
for exploiting established software technologies, such as the PCRC libraries.

The language model described in this paper has already been
explored using of C++ class libraries\cite{AdlibLang}.  In fact, before
attempting implementation of translator for an extended Fortran, we
intend to move similar ideas to Java, as an intermediate
stage.  These are essentially prototype systems, not offering the
immediate expectation of very high performance.  Our hope is that
a Fortran translator for a language such as the one described here
will be an order of magnitude easier to implement than a compiler for full
HPF.  We also suspect it will offer higher performance than extant
HPF systems, relying on the intelligence of reasonably sophisticated
programmers, rather than on very advanced compilers.  Moreover, we
claim that for many purposes the explicitly SPMD language model
espoused here is more flexible and convenient than HPF.


%%\subsection{Global Arrays}
%
%Global Arrays\cite{Nie94} is a successful
%application-oriented library for SPMD programming in Fortran
%(and other languages).  It includes a model of distributed arrays
%similar to HPF (and therefore similar to our proposal).  As in our
%proposal---unlike in HPF---non-local elements of distributed arrays
%must be accessed through library calls.
%Global Arrays differs from our proposal in two important respects.
%Firstly it does not assume language extensions---the distributed arrays
%are represented as integer handles manipulated through library
%functions\footnote{GAs manages without language extensions because it
%emphasizes the task-parallel approach rather than data parallel
%loops.}.  Secondly the model for access to remote data is through
%simulated shared memory operations rather than collective communication
%operations.  However, we see no fundamental incompatibility between
%our model and the GAs model.  The distributed array models have
%much in common and it seems feasible that we could eventually
%import GAs-like communication and synchronization into our
%library, or simply provide a more elegant language-binding to the
%standard GAs library.  Similar comments apply to other runtime
%libraries, such as CHAOS/PARTI.

%\subsection{CHAOS/PARTI}

%CHAOS\cite{Das94}
%is a run-time library of collective
%communications to support (especially) applications with {\em
%irregular} patterns of access to distributed data.  The PCRC run-time
%kernel described above has some support for irregular patterns of array
%access, but this is not its main emphasis.  As with GAs, we see no
%fundamental problem in making CHAOS callable from our system, although
%additional interfacing code may be necessary for subscripting
%HPF-like arrays.

%\subsection{ZPL}

\begin{thebibliography}{99}
\bibitem{hpf:1}
HPFF, High Performance Fortran Language Specification (version 1.0).
May 3, 1993.

\bibitem{pcrc:1}
Parallel Compiler Runtime Consortium,
``Common Runtime Support for High Performance Data Parallel Languages'',
Supercomputing `93, IEEE Computer Society Press, 1993.

\bibitem{Mer96}
John Merlin, Bryan Carpenter and Tony Hey,
``shpf: a Subset High Performance Fortran compilation system,''
Fortran Journal, pp 2-6, March 1996.


%\bibitem{Nie94}
%J. Nieplocha, R. Harrison and R. Littlefield,
%``Global Arrays: A portable `shared memory' programming model for
%distributed memory computers,'' Supercomputing 1994, pp340-349,
%IEEE Computer Society Press, 1994

\bibitem{AdlibLang}
D.B. Carpenter, ``{\em Adlib} Language Reference'', \\
URL: http://www.npac.syr.edu/users/dbc/Adlib

\bibitem{zpl}
{\tt http://www.cs.washington.edu/research/projects/zpl/}

\bibitem{Num97}
R.W. Numrich and J.L. Steidel, ``F--: A simple
parallel extension to Fortran 90,'' SIAM News, 30, 1997

\bibitem{NPACker}
D.B. Carpenter, Guansong Zhang and Yuhong Wen,
``NPAC PCRC Runtime Kernel Definition'',
in preparation.  For current draft, see\\
http://www.npac.syr.edu/projects/pcrc/July97/doc.html

\bibitem{Zha97}
G. Zhang, D.B. Carpenter, G.C. Fox, X. Li, X. Li and Y. Wen
``PCRC-based HPF Compilation''
10th International Workshop on Languages and Compilers for Parallel Computing,
1997

\end{thebibliography}

\end{document}

