

\begin{slide}{Cases}

\begin{center}
{\Large Java as a Language for Scientific Parallel Programming} \\ \vspace{0.25in}
Bryan Carpenter, Yuh-Jye Chang, Geoffrey Fox, Xiaoming Li \\
\em Northeast Parallel Architectures Centre, \\
\em Syracuse University, \\
\em Syracuse, New York
\end{center}

\end{slide}

\begin{slide}{Cases}

\begin{center}
\bf Why Java?
\end{center}

\small

From the Java whitepaper:
\begin{quote}
\em Java is designed to meet the challenges of application development in
the context of heterogeneous, network-wide distributed environments.
Paramount among these challenges is secure delivery of applications
that consume the minimum of system resources, can run on any hardware
and software platform, and can be extended dynamically.
\end{quote}
Goals of Java include
\begin{itemize}
\item
Portability (cf, P4, MPI, HPF,\ldots)
\item
Support for heterogenous networks (cf, PVM, MPI,\ldots)
\item
Efficiency.
\end{itemize}
all major concerns in HPC.

\end{slide}

\begin{slide}{Cases}

\begin{center}
\bf Why Java?
\end{center}

\small

\begin{itemize}
\item
Java is a descendant of C++---used increasingly in scientific programming.
Many variations on the theme of C++ for parallel computing (eg, CC++, pC++,
A++/P++, \ldots).
\item
Java omits
features of C and C++ considered ``difficult''---eg, pointers.
Suggests Java (like Fortran) may be a suitable
source language for highly optimizing compilers.
\item
Java comes with builtin multithreading.  On a shared memory platform
threads may be scheduled on different processors.  In any case,
very convenient in explicit message-passing styles (cf occam, Fortran M, \ldots)
\end{itemize}

\end{slide}

\begin{slide}{Options}

\begin{center}
\bf Approaches to Parallelism in Java
\end{center}

\small

\begin{itemize}
\item
Explicit parallelism through Java thread mechanism,
scheduled on SMP.
\item
Automatic or semi-automatic parallelization (eg JAVAR).
\item
Language extensions (eg SPAR, pizza) or directives?
\item
Task parallelism.  Applets as tasks (or task servers---eg Javelin)?
Interacting ``applications'' as tasks?
\end{itemize}

\end{slide}

\begin{slide}{Options}

\begin{center}
\bf Approaches to communication in Java
\end{center}

\small

\begin{itemize}
\item
Message-passing.  Internet sockets?
Higher-level class libraries---Channels?  MPI?
\item
Communication through shared objects (Nexus, Linda, \ldots).
\item
Distributed shared memory (Java/DSM).
\item
Data parallelism.  High level ``array syntax'' with implicit
communication (cf A++/P++)?  Global SPMD style---explicit collective
operations on distributed array classes (cf Adlib)?
\item
Libraries in Java?  Libraries in native code?
\end{itemize}
This talk will focus on traditional message-passing and data-parallel
approaches.

\end{slide}

\begin{slide}{Message Passing}

\begin{center}
\bf Part 1.  Message passing in Java
\end{center}

\small

Approaches investigated
\begin{itemize}
\item
Application programming with {\tt java.net} sockets.
\item
Fortran-M-like dynamic channels, implemented as a class library on top of
{\tt java.net}.
\item
``Native-methods'' interface to standard MPI implementation.
\end{itemize}
Will only discuss the last approach.

\end{slide}

\begin{slide}{MPI}

\begin{center}
\bf MPI Interface
\end{center}

\small

Have produced an experimental {\em native methods} interface to (subset
of) MPI.

Interface modelled on proposed C++ bindings of MPI, eg
\begin{verbatim}
  public class Comm {
    public int Size();
    public int Rank();

    void Send(Object buf, int offset, int count,
              Datatype datatype, int dest, int tag) ;

    Status Recv(Object buf, int offset, int count,
                Datatype datatype, int dest, int tag) ;
    ...
  }
\end{verbatim}

\end{slide}

\begin{slide}{MPI}

\begin{center}
\bf Simple message passing
\end{center}

\tiny

\begin{verbatim}
  int np = MPI.WORLD.Size();
  int id = MPI.WORLD.Rank();

  int next = (id + 1) % np;
  int prev = (id + np - 1) % np;

  byte block[][] = new byte [blkSize + 2] [N] ;
  ...

    // Shift upper edge into next's lower ghost edge

    MPI.WORLD.Send(block [blkSize],    N, MPI.BYTE, next, 0);
    MPI.WORLD.Recv(block [0],          N, MPI.BYTE, prev, 0);

    // Shift lower edge into prev's upper ghost edge

    MPI.WORLD.Send(block [1],           N, MPI.BYTE, prev, 0);
    MPI.WORLD.Recv(block [blkSize + 1], N, MPI.BYTE, next, 0);
  ...
\end{verbatim}

\end{slide}

\begin{slide}{MPI}

\begin{center}
\bf Derived data types
\end{center}

\small

Description of user data buffers presents special problems in Java.
Existing MPI bindings assume a flat, linear memory model.

MPI derived types expressible in Java binding have a uniquely
defined {\em base type}---a Java primitive type.
\begin{itemize}
\item
Interfaces to MPI\_TYPE\_HVECTOR and MPI\_TYPE\_HINDEXED provided, but
strides and displacements in units of base type, not bytes.
\item
Interface to MPI\_TYPE\_STRUCT provided, but all component types
must have same base type.
\end{itemize}

\end{slide}

\begin{slide}{MPI}

\begin{center}
\bf Send and receive buffers
\end{center}

\small

Interface to standard mode send is
\begin{verbatim}
    void Send(Object buf, int offset, int count,
              Datatype datatype, int dest, int tag) ;
\end{verbatim}
\begin{itemize}
\item
Formal {\tt buf} argument presented as a generic Java {\em Object}.
Actual argument must be 1d array of elements of primitive type---the
base type of {\tt datatype}.
\item
{\tt offset} argument is the offset in {\tt buf} of first element of
the message (cf {\tt arrayCopy} in standard Java API).
\item
Other arguments as for conventional {\tt MPI\_Send} bindings.
\end{itemize}

\end{slide}

\begin{slide}{MPI}

\begin{center}
\bf Programming with derived data types
\end{center}

\tiny

\begin{verbatim}
int sX = blkSizeX + 2, sY = blkSizeY + 2 ;
block = new byte [sX * sY] ;

Datatype edgeXType = MPI.BYTE.Contiguous(sY) ;

Datatype edgeYType = MPI.BYTE.Vector(sX, 1, sY) ;
...
  p.Sendrecv(block, blkSizeX * sY, 1, edgeXType, pX.dst, 0,
             block, 0,             1, edgeXType, pX.src, 0) ;

  p.Sendrecv(block, sY,                  1, edgeXType, nX.dst, 0,
             block, (blkSizeX + 1) * sY, 1, edgeXType, nX.src, 0) ;

  p.Sendrecv(block, blkSizeY, 1, edgeYType, pY.dst, 0,
             block, 0,        1, edgeYType, pY.src, 0) ;

  p.Sendrecv(block, 1,            1, edgeYType, nY.dst, 0,
             block, blkSizeY + 1, 1, edgeYType, nY.src, 0) ;
\end{verbatim}

\end{slide}

\begin{slide}{Wrapper}

\begin{center}
\bf Availability of ``Java wrapper'' for MPI
\end{center}

\small 

A Solaris version of the software, tested with MPICH/P4, is
available from
\begin{verbatim}
http://www.npac.syr.edu/users/yjchang/javaMPI
\end{verbatim}
This software has also been ported to the IBM/SP2.

Prototype software, made available in the hope of stimulated further
development---not as a finished product!

\end{slide}

\begin{slide}{Data Parallel}

\begin{center}
\bf Part 2.  Data Parallelism in Java
\end{center}

\small

Work to date based on a simplified version of the distributed
data model of HPF. 

Rather than language extensions, have taken a pure class library
approach (cf A++/P++, HPC++ parallel STL, Adlib, \ldots)

Take a relatively low-level approach---essentially SPMD, with
classes for distributed arrays, plus collective communications.

\end{slide}

\begin{slide}{Containers}

\begin{center}
\bf Problems with container classes
\end{center}

\small

Lack of parametric polymorphism (in C++, templates)
makes container classes difficult.  Rules out parallel STL approach.

Options:
\begin{itemize}
\item
Container holds items of type {\tt Object}.  But then no
array elements of primitive type; no compile-time
type-checking (cf {\tt void*} in C).
\item
Separate container class for each allowed type of element.
Ad hoc and unnatractive.
\end{itemize}
Another worry: lack of operator overloading makes access to contents of
container verbose.

\end{slide}

\begin{slide}{DAD}

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

\small

For now we have taken a lower level approach.  Provide array
descriptor (DAD) class, but allocate space for local elements
in separate vector
\begin{verbatim}
  Procs p = new Procs(this, 2, 2) ;

  Range x = new Range(N, p, 0) ;    // distrib over 1st dim
  Range y = new Range(N, p, 1) ;    // distrib over 2nd dim

  Array r = new Array(p, x, y) ;    // DAD

  byte [] w = new byte [r.seg()] ;  // main data array
\end{verbatim}
{\tt seg()} returns number of elements in local segment.

\end{slide}

\begin{slide}{Update}

\begin{center}
\bf Programming with parallel arrays.
\end{center}

\small

Fragment of a ``life'' demo program:
\begin{verbatim}
  shift(cn_, w, r, 0,  1, CYCLIC);
  shift(cp_, w, r, 0, -1, CYCLIC);
  ... etc, copy arrays for 8 neighbours

  // Life update rule

  for(r.forall(); r.test(); r.next()) {
    int i = r.sub() ;
    switch (cn_[i] + cp_[i] + c_n[i] + c_p[i] +
            cnn[i] + cnp[i] + cpn[i] + cpp[i]) {
      case 2 : break;
      case 3 : w[i] = 1; break;
      default: w[i] = 0; break;
    }
  }
\end{verbatim}
Neighbour arrays {\tt cn\_}, \ldots allocated similarly to {\tt w}.

\end{slide}

\begin{slide}{Comments}

\begin{center}
\bf Data-parallel example: comments
\end{center}

\small

Characteristics of the data-parallel style of programming:
\begin{itemize}
\item
Distribution format of arrays can be changed by altering a few
parameters at start of program (eg, change \verb$Range$ to
\verb$CRange$ for cyclic distribution).  Main program insensitive to
these details.
\item
Low level message-passing abstracted into high-level collective
operations on distributed arrays.
\end{itemize}

\end{slide}

\begin{slide}{Lessons}

\begin{center}
\bf Data-parallel example: lessons
\end{center}

\small

\begin{itemize}
\item
Need much more general collective operations than {\tt shift}
to make this idiom useful.
\item
Absence of templates and operator overloading make implementing
arrays through a library less attractive than in C++.
\item
Using iterator functions {\tt forall}, {\tt test}, {\tt next}
to implement distributed loops is elegant but inefficient.
Adds multiple procedure calls per iteration---in
a compiled language perhaps one to two orders of magnitude
performance hit for tight loops.
\end{itemize}

\end{slide}

\begin{slide}{Future}

\begin{center}
\bf Future work
\end{center}

\small

\begin{enumerate}
\item
We are making a Java interface to the NPAC PCRC library.
This provides array descriptors for the complete HPF 1.0 array model
and very general collective communications and array intrinsics.
\item
Plan a Java-to-Java translator adding minimal data parallel language
extensions---parallel
arrays and efficient implementation of the distributed loop.
\end{enumerate}
Hope to provide a useful data-parallel programming environment for
Java.  Will also be a proving ground for general ideas on ``global
SPMD'' language extensions.

\end{slide}


