

\begin{slide}{Title}

\begin{center}
{\large \bf Towards a Java Environment for SPMD Programming}
\\ \vspace{0.25in}
{\bf Bryan Carpenter}, Guansong Zhang, Geoffrey Fox, Xiaoming Li,
Xinying Li, Yuhong Wen\\ \vspace{0.25in}
{\em Northeast Parallel Architectures Centre,} \\
{\em Syracuse University,} \\
{\em Syracuse, New York} \\ \vspace{0.25in}
\{{\bf dbc},zgs,gcf,lxm,xli,wen\}@npac.syr.edu
\end{center}

\end{slide}

\begin{slide}{Introduction}

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

\begin{itemize}
\item
HPJava is an environment for SPMD (Single Program, Multiple
Data) parallel programming.
\item
Acronym ``HPJava'' coined in a draft white paper
produced by members of the PCRC consortium early in 1996.
\item
Eventually incorporate bindings for
general MIMD programming libraries, and
preprocessor for an extended dialect of Java:
recently released first component---{\bf mpiJava}.
\item
This talk emphasizes {\bf language} extensions.
\end{itemize}

\end{slide}

\begin{slide}{Language}

\begin{center}
\large \bf Language issues
\end{center}

\begin{itemize}
\item
Widely assumed that data-parallel programming has an important role in HPC.
\item
``Production'' parallel computing still dominated by low-level SPMD
programming.  So far HPF has made limited inroads.
\item
HPJava takes 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.
\end{itemize}

\end{slide}

\begin{slide}{Advantages}

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


\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}
\large \bf Problems with HPF
\end{center}

\begin{itemize}
\item
Promise of semantic equivalence between an HPF program and a
sequential Fortran program leads to difficult implementation
problems.
\item
Works best for algorithms that have essentially SIMD
parallelism---identical updates across whole arrays.  Many algorithms
easier to express with looser coupling between updates of the
local array elements.  End up doing contortions.
\end{itemize}

\end{slide}

\begin{slide}{HPJava Goals}

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

%\small

Aim for a flexible hybrid of the data parallel and SPMD approaches,
combining some 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}{HPJava Features}
%
%\begin{center}
%\bf Features
%\end{center}
%
%\small
%
%\begin{itemize}
%\item
%{\bf Data parallel}: Generalized, HPF-like distributed arrays as language
%primitives.
%\item
%{\bf MIMD}: processors have freedom to independently execute complex
%procedures on local data.
%\item
%{\bf Distributed Memory}: All access to non-local array elements goes
%through library functions.
%\item
%{\bf Distributed Control} constructs facilitate access to local elements
%of arrays, and simplify parallel array traversals.
%\end{itemize}
%
%\end{slide}

\begin{slide}{HPJava language features}

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

\begin{itemize}
\item
Distributed array model semantically equivalent to to the HPF array model.
\item
Add {\bf distributed control} constructs.  HPF 2.0 has comparable
mechanisms ({\tt ON HOME}) as {\bf optional} directives.
\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}{HPJava semantics}

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

%\small

\begin{itemize}
\item
Semantics influenced by ad++, a C++ user-level interface to
NPAC/Southampton runtime library.
\item
HPJava introduces a more convenient syntax, and an intelligent
preprocessor to optimize distributed array subscripting.
\item
{\bf Unlike HPF}, underlying model is simply SPMD programming.
Other libraries for manipulating distributed arrays can be integrated
into the same framework.
\end{itemize}

\end{slide}

\begin{slide}{HPJava Communication}

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

\small

Ultimately would like, say:
\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}
Initially will have Adlib and MPI.

\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 NPAC during PCRC project.
%\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}{ad++}
%
%\begin{center}
%\bf ad++
%\end{center}
%
%\small
%
%\begin{itemize}
%\item
%C++ user-level interface to Adlib.
%\item
%Prototype of HPJava 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 Arrays}

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

\begin{itemize}
\item
Distributed arrays flagged by double brackets.  Unrelated to ordinary
Java arrays.
\item
Distribution expressed in terms of {\tt Group} (subclass {\tt Procs2})
and {\tt Range} (subclass {\tt BlockRange}).  
\item
Comparable with HPF processor arrangements and templates.
\end{itemize}

\end{slide}

\begin{slide}{HPJava Array example}

\begin{center}
\large \bf Distributed array construction
\end{center}

Example:
\small
\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{slide}


\begin{slide}{MatMul}

\begin{center}
\large \bf Accessing elements: matrix example
\end{center}

\small

\begin{verbatim}
  on(p) {
    float [[,]]  c = new float [[x, y]] ;

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

    ... initialize `a', `b'

    overall(i = x)
      overall(j = y) {

        float sum = 0 ;
        for(int k = 0 ; k < N ; k++)
          sum += a [i, k] * b [k, j] ;

        c [i, j] = sum ;
      }
  }
\end{verbatim}

\end{slide}

\begin{slide}{MatMul2}

\begin{center}
\large \bf Matrix multiplication---details
\end{center}

\begin{itemize}
\item
Matrix {\tt c} distributed in blocks.
\item
Processes contain complete rows of {\tt a}, replicated over
horizontal process dimension.
\item
Processes contain complete colums of {\tt b}, replicated over
vertical process dimension.
\item
For arbitrary distribution pattern of input data, could
initialize {\tt a}, {\tt b} by
\small
\begin{verbatim}
  Adlib.remap(a, a_in) ;
  Adlib.remap(b, b_in) ;
\end{verbatim}
\end{itemize}

\end{slide}


\begin{slide}{on}

\begin{center}
\large \bf The {\bf on} construct
\end{center}


\begin{itemize}
\item
In SPMD programming, often necessary to restrict execution
of a block of code to processors in a particular {\bf active process group},
{\tt p}.
\item
HPJava provides a special construct for this:
\small
\begin{verbatim}
  on(p) {
    ...
  }
\end{verbatim}
\small
\end{itemize}

\end{slide}

\begin{slide}{locations}

\begin{center}
\large \bf Subscripting and locality of reference
\end{center}

\begin{itemize}
\item
Integer subscripts in distributed dimensions of arrays disallowed.
\item
A {\bf location} is an abstract element, or ``slot'',
of a distributed range.
\item
Distributed dimensions of arrays can {\bf only} be subscripted using
locations in the appropriate range of the array, scoped by
{\tt at} or {\tt overall} constructs.
\end{itemize}

\end{slide}

\begin{slide}{at}

\begin{center}
\large \bf The {\bf at} construct
\end{center}

\begin{itemize}
\item
Analogous to {\bf on}, except that its
body is executed only on processes that hold the specified location.
\item
Construct scopes a named location, which can be used for subscripting:
\small
\begin{verbatim}
  at(i = x [17])
    at(j = y [23])
      a [i, j] = 13 ;
\end{verbatim}
\end{itemize}

\end{slide}

\begin{slide}{overall}

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

\begin{itemize}
\item
Last and most important distributed control construct
is called {\tt overall}.  Implements a distributed parallel loop.
\item
Due to rules on use of subscripts, {\tt overall} can
usually only combine elements of arrays with some simple alignment
relation.
\end{itemize}

\end{slide}

\begin{slide}{overall example}

\begin{center}
\large \bf Use of {\tt overall}
\end{center}

Example:
{\small
\begin{verbatim}
  float [[,]] a = new float [[x, y]],
              b = new float [[x, y]] ;

  overall(i = x)
    overall(j = y)
      a [i, j] = 2 * b [i, j] ;
\end{verbatim}
}

\end{slide}

\begin{slide}{Locality}

\begin{center}
\large \bf Locality of reference
\end{center}

\begin{itemize}
\item
General rule: {\em a variable can only be accessed if the active
process group is a subset in the home group of the variable.}
\item
In many cases, this rule is enforced by scope of scalar variables
and syntactic and semantic constraints on subscripting.
\item
In other cases, run-time checks can be added.
\end{itemize}

\end{slide}

\begin{slide}{Coherence}

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

\begin{itemize}
\item
Advisory rule: {\em a variable should only be updated if the active
process group is identical to the home group of the variable.}
\item
Applied globally, this rule will ensure that values in variables
are replicated consistently over all processes that hold a copy.
\end{itemize}

\end{slide}

\begin{slide}{translation}

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

\begin{itemize}
\item
HPJava translator is implemented as a source-to-source
translator, converting HPJava program to a Java node program.
\item
Initial implementation uses an ad++-like interface to Adlib, called
{\bf adJava}, as runtime support for distributed arrays.
\item
Generate Java classes representing each kind
of distributed array used in the program, on-the-fly.
\end{itemize}

\end{slide}

\begin{slide}{HPJava Examples}

\begin{center}
\large \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}
\large \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

  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(l = x [k + 1 : ])
      for(int i = x.idx(l) ; i < N ; i++)
        a [i, l] -= b [i] * b [x.idx(l)] ;
  }

  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}
  for (int parity = 0; parity < 2; parity ++) {

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

    overall(i = x)
      overall(j = y [(parity + x.idx(i)) % 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}
\large \bf Conclusions
\end{center}

\vspace{0.3in}

\begin{itemize}
\item
HPJava language provides much of the expressive power of HPF, in an
object-oriented, SPMD environment.
\item
Allows programs to combine data parallel code and SPMD library
calls directly.
\item
Similar Fortran extensions have been suggested (FAST proposal).
\end{itemize}

\end{slide}

