

\begin{slide}{Title}

\begin{center}
{\large \bf Considerations in HPJava language design and implementation}
\\ \vspace{0.25in}
Guansong Zhang, {\bf Bryan Carpenter}, Geoffrey Fox, Xinying Li,
Yuhong Wen\\ \vspace{0.25in}
{\em Northeast Parallel Architectures Centre,} \\
{\em Syracuse University,} \\
{\em Syracuse, New York} \\ \vspace{0.25in}
\{zgs,{\bf dbc},gcf,xli,wen\}@npac.syr.edu
\end{center}

\end{slide}

\begin{slide}{Introduction}

\begin{center}
\large \bf Introduction
\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}
\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}{HPJava Goals}

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

\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.  HPJava 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}{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 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}{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}

\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 manageable 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 Procs2})
and {\tt Range} (subclass {\tt BlockRange}).
\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}{MatMul}

\begin{center}
\bf Motivating example: matrix multiplication
\end{center}

\tiny

\begin{verbatim}
  Procs2 p = new Procs2(P, P) ;
  on(p) {
    Range x = new BlockRange(N, p.dim(0)) ;
    Range y = new BlockRange(N, p.dim(1)) ;

    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}
\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, initialize {\tt a}, {\tt b}
by
\tiny
\begin{verbatim}
  Adlib.remap(a, a_in) ;
  Adlib.remap(b, b_in) ;
\end{verbatim}
\end{itemize}

\end{slide}


\begin{slide}{on}

\begin{center}
\bf The {\bf 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}{locations}

\begin{center}
\bf Subscripting and Locations
\end{center}

\small

\begin{itemize}
\item
Distributed array access such as
\tiny
\begin{verbatim}
  a [17, 23] = 13 ;
\end{verbatim}
\small
forbidden, because typical process does not hold the element.
\item
Introduce idea of a {\bf location}---abstract element, or ``slot'',
of a distributed range.
\item
Distributed dimensions of arrays can only be subscripted using
locations in the appropriate range of the array.
\item
Furthermore, locations used in simple subscripting must be {\em named
locations}, and named locations can only be scoped by {\bf at} and {\bf
overall} constructs.
\end{itemize}

\end{slide}

\begin{slide}{at}

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

\small

\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:
\tiny
\begin{verbatim}
  at(i = x [17])
    at(j = y [23])
      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}.  Implements a distributed parallel loop.
\item
Example:
\tiny
\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}
\small
\item
Body of construct executes, conceptually in
parallel, for every location in the range of its index.
\item
Due to rules on use of subscripts, {\bf overall} can
usually only combine elements of arrays with some simple alignment
relation.
\end{itemize}

\end{slide}

\begin{slide}{translation}

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

\small

\begin{itemize}
\item
Forseeable HPJava compilers will be implemented as a source-to-source
translators, converting HPJava program to a Java node program with
calls to runtime functions and communication libraries.  
\item
Initial implementation uses an ad++-like interface to Adlib, called
{\bf adJava}, as runtime support for distributed arrays.
\item
Translator generates Java wrapper classes representing each kind
of distributed array actually used in the program, on-the-fly.
\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

  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}
\bf Conclusions
\end{center}
\vspace{0.3in}

\small

\begin{itemize}
\item
HPJava 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
Similar Fortran extensions have been suggested (FAST proposal).
May be implemented by Peking collaborators\ldots
\end{itemize}

\end{slide}

