

\begin{slide}{Title}

\begin{center}
{\large \bf Language-bindings for a Data-Parallel Runtime} \\ \vspace{0.25in}
Bryan Carpenter, Geoffrey Fox, Xinying Li, \\
Yuhong Wen, Guansong Zhang\\ \vspace{0.25in}
{\em Northeast Parallel Architectures Centre,} \\
{\em Syracuse University,} \\
{\em Syracuse, New York} \\ \vspace{0.25in}
\{dbc,gcf,xli,wen,zgs\}@npac.syr.edu
\end{center}

\end{slide}

\begin{slide}{Introduction}

\begin{center}
\large \bf Introduction
\end{center}

\begin{itemize}
\item
Widely accepted that data-parallel programming has a vital role in HPC.
\item
``Production'' parallel computing still dominated by low-level SPMD
programming.  So far HPF has had limited impact.
\item
Will suggest a middle road between HPF and SPMD programming, combining
some data parallel language features of HPF with free use of
established SPMD libraries for distributed arrays---{\bf HPspmd}.
\end{itemize}

\end{slide}

\begin{slide}{Libraries}

\begin{center}
\large \bf Libraries
\end{center}

\end{slide}

\begin{slide}{PCRC}

\begin{center}
\bf PCRC
\end{center}

\small

{\bf Parallel Compiler Runtime Consortium}
\begin{itemize}
\item
DARPA supported.
\item
Aimed to develop a public domain infrastructure for runtime
support of high-level parallel languages.
\item
Targetted languages include parallel versions Fortran and C++.
\item
Common library should be shared by different languages and
programming models.
\item
Partners: NPAC, Rice, Maryland, Austin, Indiana, CSC, Rochester, Florida.
\end{itemize}

\end{slide}

\begin{slide}{PCRC libraries}

\begin{center}
\bf PCRC-related libraries
\end{center}

%\small

Data-parallel run-time libraries developed by PCRC collaborators include
\begin{itemize}
\item
Multiblock PARTI
\item
CHAOS
\item
Meta-Chaos
\item
DAGH
\item
Adlib
\end{itemize}

\end{slide}

\begin{slide}{PARTI}

\begin{center}
\bf Multiblock PARTI
\end{center}

\small

\begin{itemize}
\item
Developed at University of Maryland
\item
Library to support applications involving structured
meshes---eg nested meshes for multigrid codes or irregularly coupled,
multiblock codes.
\item
Basic collective communication primitives are {\tt Regular\_Section\_Copy}
and {\tt Overlap\_Cell\_fill}.
\item
Was integrated with the Syracuse Fortran 90D compiler.
\end{itemize}

\end{slide}

\begin{slide}{CHAOS}

\begin{center}
\bf CHAOS
\end{center}

%\small

\begin{itemize}
\item
Subsumes PARTI, with emphasis on irregular problems.
%\item
%Typical CHAOS-amenable algorithm looks like
%\footnotesize
%\begin{verbatim}
%do i = 1, n_step
%  ...
%  do j = 1, nedge
%    n1 = edge1 (i)
%    n1 = edge2 (i)
%    y (n1) = y (n1) + f(x(n1), x(n2))
%    y (n2) = y (n2) + g(x(n1), x(n2))
%  end do
%end do
%\end{verbatim}
%\small
\item
Arrays preprocessed
(data arrays repartitioned to improve locality, indirection arrays reduced
to local subscripts, etc) and communication schedule computed in {\bf inspector}
phase.  
\item
Arithmetic performed in series of {\bf executor} loops.
\end{itemize}

\end{slide}

\begin{slide}{Meta-Chaos}

\begin{center}
\bf Meta-Chaos
\end{center}

%\small

\begin{itemize}
\item
Developed at Maryland during PCRC.
\item
Library for transferring data between distributed data structures
owned by different data-parallel runtime libraries.
\item
Currently has interfaces for HPF, the PARTI/CHAOS libraries, and Tulip.
\end{itemize}

\end{slide}

\begin{slide}{DAGH}

\begin{center}
\bf DAGH
\end{center}

%\small

\begin{itemize}
\item
Developed at Texas, Austin.
\item
Distributed Adaptive Grid Hierarchy.
\item
Application-oriented library for integrating time-dependent
PDEs, using adaptive grids.  Exploits space (and time) locality.
\item
Directly manages memory and exchange of sub-mesh boundaries
for a hierarchy of grids of differing refinement.
\end{itemize}

\end{slide}

\begin{slide}{Adlib}

\begin{center}
\bf Adlib
\end{center}

\small

\begin{itemize}
\item
Early development in {\bf shpf} project at Southampton, UK.
Reimplemented at Syracuse in PCRC.
\item
Designed specifically as runtime support for HPF translation.
\item
Kernel is C++ class library, using MPI.  Fortran, C++ and Java interfaces
available or under development.
\item
Communication primitives similar to Multiblock PARTI, plus
all F90-style transformational intrinsic for array arithmetic
(and gather/scatter for irregular).
\item
Array descriptor and communication library supports full HPF 1.0
distributed array model.
\end{itemize}

\end{slide}

\begin{slide}{DAD}

\begin{center}
\bf Distributed Array Descriptor
\end{center}

\small

Designing an effective DAD for HPF is non-trivial.  Must describe
\begin{itemize}
\item
Many distribution formats: simple block, simple cyclic, block-cyclic,
collapsed, (general block, ...)
\item
Various alignment options: alignments to arbitrary regular sections of
templates including embedded alignments, collapsed and replicated alignment.
\item
Regular array sections constructed with arbitrary combinations of
scalar and triplet subscripts.
\end{itemize}

\end{slide}

\begin{slide}{DAD}

\begin{center}
\bf Adlib DAD
\end{center}

%\small

DAD includes
\begin{itemize}
\item
Type and rank information.
\item
Description of process subgroup to which array is mapped
\item
For each dimension, distribution format and alignment information.
\item
For each dimension, local memory stride.
\end{itemize}

\end{slide}

\begin{slide}{Benchmarks}

\begin{center}
\bf Early Benchmarks
\end{center}

\small

Compared the new NPAC compiler with the PGI HPF compiler, version 2.0.
The programs were run on the IBM SP2 at NPAC.

The Laplace benchmark performs Jacobi relaxation on $256 \times 256$,
$512 \times 512$ and $1024 \times 1024$ arrays, distributed blockwise.

Compilers achieve about the
same performance on a single node, but generally our compiler exhibits
better speedup on multiple processors, presumably due to more effective
handling of communication.

\end{slide}

\begin{slide}{Runtime}

\begin{center}
\bf Laplace Update
\end{center}
\vspace{0.3in}

\centerline{\psfig{figure=laplace.ps,width=6in}}

\end{slide}

\begin{slide}{HPspmd}

\begin{center}
\large \bf HPspmd
\end{center}

\end{slide}

\begin{slide}{Advantages}

\begin{center}
\bf Advantages of HPF
\end{center}

%\small

\begin{itemize}
\item
Easy to understand semantics: equivalent to conventional Fortran program.
Directives only change performance.
\item
Parallelism can be expressed explicitly through whole-array operations of 
Fortran 90/95.
\item
Performance can be tuned by changing a few directives to alter
the distribution format of arrays.
\end{itemize}

\end{slide}

\begin{slide}{Disadvantages}

\begin{center}
\bf Problems with HPF
\end{center}

\small

\begin{itemize}
\item
Works best for algorithms that have essentially SIMD
parallelism---identical updates across whole arrays.
Many algorithms---even data parallel ones---easier to express with
looser coupling between updates of the individual array elements.
\item
Many algorithms have completely irregular patterns of access to
the elements of (nevertheless regular) arrays.  May be expressible using
(eg) FORALL, but hard for compiler to generate good code.
\item
Other applications simply don't have such regular arrays as major
data structures---more general meshes needed.
\end{itemize}

\end{slide}

\begin{slide}{HPspmd Goals}

\begin{center}
\bf HPspmd Goals
\end{center}

%\small

Aim for a flexible hybrid of the data parallel and SPMD approaches,
bringing together some of the established technologies for parallel
processing.

Incorporates two complementary sectors:
\begin{itemize}
\item
Syntax extensions for description of, and access to elements of,
distributed arrays.
\item
Class library bindings for various communication paradigms.
\end{itemize}

\end{slide}

\begin{slide}{HPspmd Features}

\begin{center}
\bf Features
\end{center}

\small

\begin{itemize}
\item
{\bf Data parallel}: Generalized, HPF-like distributed arrays as language
primitives.
\item
{\bf SPMD}: processors have freedom to independently execute complex
procedures on local data.
\item
{\bf SPMD}: All access to non-local array elements goes through library
functions.
\item
New {\bf distributed control} constructs facilitate access to local elements
of arrays, and simplify parallel array traversals.
\end{itemize}

\end{slide}

\begin{slide}{HPspmd Language}

\begin{center}
\bf Language Model
\end{center}

\small

\begin{itemize}
\item
Distributed array model semantically equivalent to to the HPF array model.
\item
Add {\bf distributed control} constructs.  HPF 2.0 and precursors have similar
mechanisms ({\tt ON HOME}) as {\bf optional} directives.  HPspmd generally
{\bf requires} specification of execution location.
\item
Switch between data-parallel and low-level SPMD programming is a
change in point of view---no {\bf extrinsic interface} barrier.
\end{itemize}

\end{slide}

\begin{slide}{HPspmd Communication}

\begin{center}
\bf Communication Libraries
\end{center}

\small

Need at least:
\begin{itemize}
\item
Regular collective (Adlib-like)
\item
Irregular collective (CHAOS-like)
\item
One-sided access to array sections (GA-like)
\item
Low-level SPMD (MPI)
\item
Bindings to higher-level application-oriented libraries
(DAGH, ScaLAPACK, \ldots)
\end{itemize}

\end{slide}

\begin{slide}{HPspmd Bindings}

\begin{center}
\bf Language Bindings
\end{center}

%\small

Prototyped, in progress, or suggested:
\begin{itemize}
\item
C++: ad++
\item
Java: HPJava
\item
Fortran: FAST Fortran
\end{itemize}

\end{slide}


\begin{slide}{ad++}

\begin{center}
\bf ad++
\end{center}

\small

\begin{itemize}
\item
Native user-level interface to Adlib.
\item
Prototype of our language model.  It extends C++ only by
class libraries and macros.
\item
Distributed arrays implemented as container classes.
\item
Introduces the three distributed control constructs, {\bf on},
{\bf at} and {\bf overall}, implemented as macros.
\item
The current ad++ is inefficient (and concrete syntax is quite clumsy)
compared with what could be achieved with a purpose-built compiler or
preprocessor.
\end{itemize}

\end{slide}


\begin{slide}{ad++ Fragment}

\begin{center}
\bf ad++ Fragment
\end{center}

\tiny

\begin{verbatim}
  Procs2 p(2, 2) ;

  ON(p) {
    BlockRange x(100, p.dim(0)), y(10, p.dim(1)) ;

    Array2<float> a(x, y) ;

    Index i(x), j(y) ;
    OVERALL(i) {
      OVERALL(j) {
        a(i, j) = i + j ;
      } ALLOVER(j) ;
    } ALLOVER(i) ;

  } NO(p) ;
\end{verbatim}

\end{slide}

\begin{slide}{HPJava}

\begin{center}
\bf HPJava
\end{center}

%\small

\begin{itemize}
\item
Fix the efficiency problems of ad++ by using a preprocessor
to optimize the parallel loops.
\item
Modelled semantically on ad++, but with a more readable syntax.
\item
Implementation by a simple translator from HPJava to Java (in progress).
\end{itemize}

\end{slide}

\begin{slide}{HPJava Arrays}

\begin{center}
\bf Distributed Arrays
\end{center}

\small

\begin{itemize}
\item
Distributed arrays flagged by double brackets.  Orthogonal to ordinary
Java arrays.
\item
Distribution expressed in terms of {\tt Group} (subclass {\tt Procs})
and {\tt Range}.
\item
Example:
\tiny
\begin{verbatim}
  Procs2 p = new Procs2(3, 2) ;

  Range x = new BlockRange(100, p.dim(0)) ;
  Range y = new BlockRange(200, p.dim(1)) ;

  float [[,]] a = new float [[x, y]] on p ;
\end{verbatim}
\end{itemize}


\end{slide}

\begin{slide}{on}

\begin{center}
\bf The {\em on} construct and the APG
\end{center}

\small

\begin{itemize}
\item
In SPMD programming, often necessary to restrict execution
of a block of code to processors in a particular group, {\tt p}.
\item
HPJava provides a special construct for this:
\tiny
\begin{verbatim}
  on(p) {
    ...
  }
\end{verbatim}
\small
\item
Language incorporates a formal idea of an {\bf active process group}
(APG).  Inside {\tt on(p)}, value of the APG changes to {\tt p}.
\end{itemize}

\end{slide}

\begin{slide}{at}

\begin{center}
\bf Locations and the {\em at} construct
\end{center}

\small

\begin{itemize}
\item
Distributed array access such as
\tiny
\begin{verbatim}
  a [17, 23] = 13 ;
\end{verbatim}
\small
is legal, but {\bf only} if the local process holds the element in
question.
\item
Introduce idea of {\bf location} and {\bf at} construct to alleviate
inconvience of this restriction:
\tiny
\begin{verbatim}
  Location i = x [17], j = y [23] ;
  at(i)
    at(j)
      a [i, j] = 13 ;
\end{verbatim}
\small
\end{itemize}

\end{slide}

\begin{slide}{overall}

\begin{center}
\bf Distributed loops
\end{center}

\small

\begin{itemize}
\item
Last and most important distributed control construct
is called {\bf overall}.
\item
Implements a distributed parallel loop.
\item
Parametrized by member of iterator class {\tt Index}.
Example:
\tiny
\begin{verbatim}
  float [[,]] a = new float [[x, y]], b = new float [[x, y]] ;
  Index i, j ;
  overall(i = x | :)
    overall(j = y | :)
      a [i, j] = 2 * b [i, j] ;
\end{verbatim}
\small
\end{itemize}

\end{slide}

\begin{slide}{HPJava Examples}

\begin{center}
\bf Examples
\end{center}

%\small

Two examples follow:
\begin{itemize}
\item
Cholesky decomposition
\item
Potts update
\end{itemize}

\end{slide}

\begin{slide}{Choleski}

\small

\begin{center}
\bf Choleski decomposition
\end{center}

In pseudocode, sequential algorithm is
\begin{displaymath}
\begin{array}{l}
For\; k=1\; to\; n-1 \\
\;\;\;\; l_{kk}= a_{kk}^{1/2} \\
\;\;\;\; For\; s=k+1\; to\; n \\
\;\;\;\;\;\;\;\; l_{sk}=a_{sk}/l_{kk} \\
\;\;\;\;  For\; j=k+1\; to\; n \\
\;\;\;\;\;\;\;\;    For\; i=j\; to\; n \\
\;\;\;\;\;\;\;\;\;\;\;\;      a_{ij}=a_{ij}-l_{ik}l_{jk} \\
l_{nn}= a_{nn}^{1/2} \\
\end{array}
\end{displaymath}
Note HPJava code should be enclosed by a suitable {\tt on(p)}.

\end{slide}

\begin{slide}{Choleski2}

\tiny

\begin{verbatim}
  Range x = new CyclicRange(N, p.dim(0));

  float [[*,]] a = new float [[N, x]] ;
  float [[*]]  b = new float [[N]] ;  // buffer

  Location l ;
  Index m ;

  for(int k = 0 ; k < N - 1 ; k++) {

    at(l = x [k]) {
      float d =  Math.sqrt(a [k, l]) ;
      a [k, l] = d ;
      for(int s = k + 1 ; s < N ; s++)
        a [s, l] /= d ;
    }

    Adlib.remap(b [[k + 1 : ]], a [[k + 1 : , k]]);

    overall(m = x | k + 1 : )
      for(int i = x.idx(m) ; i < N ; i++)
        a [i, m] -= b [i] * b [x.idx(m)] ;
  }

  at(l = x [N - 1]) a [N - 1, l] = Math.sqrt(a [N - 1, l]) ;
\end{verbatim}

\end{slide}

\begin{slide}{PottsHPJ}

\begin{center}
\bf Potts update pseudocode
\end{center}

\tiny

\begin{verbatim}
  do parity = 0, 1

    forall i, j such that i + j mod 2 = parity
      old  = latt [i, j]

      cand = (old + (int) (rand() * q - 1) + 1) % q

      e_old = (old == latt [i + 1, j]) + (old == latt [i - 1, j]) +
              (old == latt [i, j + 1]) + (old == latt [i, j - 1])

      e_new = (cand == latt [i + 1, j]) + (cand == latt [i - 1, j]) +
              (cand == latt [i, j + 1]) + (cand == latt [i, j - 1])

      if(rand() < exp((e_old - e_new) * cup))
        latt [i, j] = cand
    end forall

  end do
\end{verbatim}

\end{slide}

\begin{slide}{PottsHPJ}

\tiny

\begin{verbatim}
  Index i, j ;
  for (int parity = 0; parity < 2; parity ++) {

    Adlib.writeHalo(latt, w, w, mode) ;

    overall(i = x | :)
      overall(j = y | (parity + x) % 2 : : 2) {
        int old  = latt [i, j] ;

        int cand = (old + (int) (Math.erand48(xsubi) * q - 1) + 1) % q ;

        float e_old =
            (old == latt [i + 1, j]) + (old == latt [i - 1, j]) +
            (old == latt [i, j + 1]) + (old == latt [i, j - 1]) ;

        float e_new =
            (cand == latt [i + 1, j]) + (cand == latt [i - 1, j]) +
            (cand == latt [i, j + 1]) + (cand == latt [i, j - 1]) ;

        if (Math.erand48(xsubi) < Math.exp((e_old - e_new) * cup))
          latt [i, j] = cand ;
      }
\end{verbatim}


\end{slide}

\begin{slide}{Performance}

\begin{center}
\bf Preliminary Performance Data
\end{center}

\small

\begin{itemize}
\item
Examples are Jacobi update for 2d Laplace and Cholesky decomposition.
\item
HPJava code was hand-translated to Java, applying only optimizations that
will be incorporated in the initial translator.
\item
Parallel Java on 4 Ultrasparc processors, using JDK 1.2 JIT compiler
Generated code uses a JNI interface to Adlib, with
MPICH for underlying communications.
\item
Comparisions are with simple Java and C++ versions.
\item
Overhead in parallel case attributable to MPI---SunHPC may reduce
this by an order of magnitude.
\end{itemize}

\end{slide}

\begin{slide}{Performance 1}

\begin{center}
\bf Jacobi Update
\end{center}
\vspace{0.3in}

\centerline{\psfig{figure=Jacobi.eps,width=6in}}

\end{slide}

\begin{slide}{Performance 2}

\begin{center}
\bf Choleski
\end{center}
\vspace{0.3in}

\centerline{\psfig{figure=Choleski.eps,width=6in}}

\end{slide}

\begin{slide}{Conclusions}

\begin{center}
\bf Conclusions
\end{center}
\vspace{0.3in}

\small

\begin{itemize}
\item
HPspmd language extensions 
provide much of the expressive power of HPF, but in a strictly
SPMD enviroment.
\item
Allows programs to combine data parallel code and SPMD library
calls directly.
\item
Initial full binding will be to Java---originally regarded as a prototype,
but rapidly advancing Java performance may make this a
competitive production environment.
\item
Similar Fortran extensions have been suggested (FAST proposal).
May be implemented by Peking collaborators\ldots
\end{itemize}

\end{slide}

