
\documentstyle[psfig]{article}

%\documentstyle[psfig]{llncs}

%\input{psfig} 

\begin{document}

\bibliographystyle{plain}

%\sloppy

%\pagestyle{plain}
\pagestyle{empty}

\title{\vspace{2in}Java as a Language for Scientific Parallel Programming}

%\author{Bryan Carpenter, Yuh-Jye Chang, \\
%        Geoffrey Fox, Xiaoming Li}
%
%\institute{Northeast Parallel Architectures Centre,
%           Syracuse University, Syracuse, NY 13244}

\author{Bryan Carpenter, Yuh-Jye Chang, \\
        Geoffrey Fox, Xiaoming Li \vspace{5mm} \\
        \em Northeast Parallel Architectures Centre, \\
        \em Syracuse University, Syracuse, NY 13244 \\
        \em \{dbc,yjchang,gcf,lxm\}\@npac.syr.edu
}

\date{August, 1997}

\maketitle

\begin{abstract}
Java may be a natural language for portable parallel programming.
We discuss the basis of this claim in general terms, then 
illustrate the use of Java for message-passing and data-parallel
programming through series of case studies.  In the process
we introduce some proposals for a Java binding of MPI, and
describe the use of a Java class-library to implement HPF-style
distributed data.  Prospects for future Java-based parallel
programming environments are discussed.
\end{abstract}

\newpage

\section{Introduction}

The explosion of interest in Java over the last year has been driven largely by
its r\"{o}le in bringing a new generation of interactive pages to
the World Wide Web.
Undoubtedly various features of the language---compactness, byte-code
portability, security, and so on---make it particularly attractive as
an implementation language for applets embedded in Web pages.  But it
is clear that the ambitions of the Java development team go well beyond
enhancing the functionality of HTML documents.  Many of their concerns,
such as portability, execution in a heterogenous network environment,
and efficiency, mirror developments in High Performance Computing world
over a number of
years\cite{p4Book,MPIStandard,HPFStandard,PVMBook,WebComputing}.

With Java positioned to become a standard programming language
on the Internet, and scientific parallel processing
edging towards network-based computation, it is natural to ask how these
two technologies will interact.  How suitable is Java for scientific
computing, and do lessons from research in parallel computing have
implications for the development of Java?

Popular acclaim aside, there are some reasons to think that Java may
be a good language for scientific and parallel programming.
\begin{itemize}
\item
Java is a descendant of C++.  C and C++ are used increasingly in
scientific programming.  In recent
years numerous variations on the theme of C++ for parallel computing
have appeared.  See, for example
\cite{ParallelCPlusPlus,CCPlusPlusArticle,LapackPlusPlus,Pooma,KeLPGuide,Mentat}.
\item
Java omits various
features of C and C++ that are considered ``difficult''---notably,
pointers.  Poor compiler analysis has often been blamed on these
features.  The inference is that Java, like Fortran, may be a suitable
source language for highly optimizing compilers (although direct evidence for
this belief is still lacking).
\item
Java comes with builtin multithreading.  On a shared memory platform
independent threads may be
scheduled on different processors by a suitable runtime.  In any case
multithreading can be very convenient in explicit
message-passing styles of parallel programming \cite{occam}.
\end{itemize}
We will return to the question of whether parallel computing may
have implications for the development of Java in section \ref{discussion}.

Section \ref{issues} of this article outlines various options for
parallel programming in Java---possible ways to express parallelism,
and ways to handle inter-process communication.

The main technical content of the paper is in sections \ref{message}
and \ref{data}.  Section \ref{message} contains some case studies in which
we explore the message-passing style of programming in Java.  We cover
parallel programming using sockets directly, and describe our Java
interface to MPI.  In section \ref{data} we discuss approaches to
data-parallel programming in Java, and outline one of our demo programs.

In this article our emphasis is more on language bindings and interface
issues, and less on performance.  Java compilers are in an early stage
of development, and we assume that current performance figures are not
indicative of future potential.


\section{\label{issues}Issues}

\subsection{Approaches to Parallelism in Java\label{parallelism}}

Java already supports concurrency through the thread mechanism and
monitor synchronization built into the language.  In this article we
are interested in truly {\em parallel} computation, involving multiple
CPUs.  Such parallelism could be introduced into Java in a number of
ways.

It could be achieved through automatic parallelization of sequential
code, but it is unclear why this would be easier
for Java than for other languages.  Alternatively, the Java virtual
machine for a shared memory multiprocessor can schedule the threads of
a multi-threaded Java program on different processors.  Some success
with these approaches is reported in \cite{automatic}.
For computation on a network (or distributed memory
computer) realistic options include language extensions or directives
akin to HPF, or provision of libraries---class libraries---to support
task parallelism or data parallelism.

A popular approach in C++ has been to defer language extensions and
concentrate on class library support for parallel programming.  The
similarities between the two languages suggest this may be a fruitful
avenue in Java too.  The success of this analogy is by no
means automatic, however.  Features such as {\em templates}
and user-defined {\em operator overloading} make the C++ language
inherently more customizable than Java.  In C++ library-defined types
can be used on an identical footing to primitive types---{\em inline}
methods mean they can be almost as efficient
as primitive types.  Less importantly, but conveniently,
new control constructs can often be simulated in C or C++ through use
of macros.  On grounds, presumably, of simplicity and transparency
many of these features have been omitted from Java.

Such caveats notwithstanding, this article will concentrate on class
libraries rather than language extensions.  We will be working with
class libraries implemented in the standard Java development
environment.

\subsection{Communication in Java}

The standard Java API provides a simplified interface to Internet
sockets.  This interface hides much of the ugly detail involved in
socket-programming at the at the traditional C/UNIX level.  The {\em
java.net} interface provides less flexibility than using the system
calls directly.  On the other hand, Java's built-in support for threads
adds some flexibility in scheduling communications that is missing from
raw C.

We will give an example of socket programming in section
\ref{sockets}, but traditionally this has not been a popular paradigm
in the parallel processing world, where more succesful schemes include
\begin{itemize}
\item
Message-passing through language-level support \cite{occam,FortranM}
or higher-level library interfaces \cite{MPIStandard}.
\item
Data parallelism, which we take to mean the style of programming in which
parallelism is achieved through operations on distributed arrays, with
synchronization typically limited to bulk synchronization occuring
naturally through collective array operations.
\item
Communication through shared memory or shared objects,
involving some more or less intricate mechanism for inter-process
synchronization.
% In this category we include Linda [\ldots].
\end{itemize}
The case studies in the rest of this article restrict themselves to
message-passing and data parallelism.  As observed in the previous
section, communication through true shared memory is already implicit
in the Java thread model.  Communication through remote objects is
undoubtedly a natural and important paradigm in Java, especially for
access to remote services \cite{CORBA,RMI,Mentat}, but it is not
specifically tied to scientific parallel programming and we will not
discuss it further here.

\section{\label{message}Message-passing case studies}

Message-passing remains one of the most effective and widely used
communication paradigms in parallel computing.  In this section we
compare two approaches to message-passing in Java, in the context of a
``scientific'' application.  The first approach is to use the socket
interface in the standard Java API.  The second is to work through a
Java interface to the message-passing standard, MPI \cite{MPIStandard}.

To minimize distracting details, our application will be elementary:
Conway's Life automaton.

\subsection{Java sockets\label{sockets}}

The UNIX socket model is most suitable for programming client-server
applications.  Typical scientific parallel programs do not fit directly
into this model.  Before a SPMD program can start two conditions must
obtain:  a pool of symmetric peer processes must have been created, and
each peer must be able to address a message to any other.  Bootstrapping
this situation typically involves one host starting remote invocations
of the program (for example by using {\em rsh} or a specialized daemon).
All the peers will create listening sockets, and all the port numbers
must be broadcast somehow, then socket connections will be made.

\begin{figure}[hbtp]
\footnotesize
\begin{verbatim}
class life_java {
  static public void main(String[] args) throws Exception {
    hpj HPJava = new hpj(args);

    int np = HPJava.num_processor();
    int id = HPJava.my_id();

    ... compute local `blockSize', `blockBase' (avoiding empty blocks).

    // `block' has `blockSize + 2' columns.  This allows for ghost cells.

    byte block[][] = new byte[blockSize+2][N];

    ... initialize local block with some pattern

    // Main update loop.

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

    for(int iter = 0 ; iter < NITER ; iter++) {

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

      HPJava.Output(next).write(block[blockSize]);
      HPJava.Output(next).flush();
      HPJava.Input(prev).read(block[0]);

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

      HPJava.Output(prev).write(block[1]);
      HPJava.Output(prev).flush();
      HPJava.Input(next).read(block[blockSize+1]);

      ... Calculate a block of neighbour sums.
      ... Update block of board values.
    }
  }
}
\end{verbatim}
\caption{\label{lifeSocket}Skeleton of socket-based Life program.}
\end{figure}
Figure \ref{lifeSocket} gives a schematic outline of
a distributed Life program using {\em java.net}.
The fairly intricate code sketched above for
initialization and establishment of socket connections has been absorbed
into the definition of an auxilliary class {\em hpj}.
The members {\em Input} and {\em Output} return streams associated
with sockets connected to peer processes.  In the example an {\em N}
by {\em N} Life board is divided blockwise in one dimension, each
processor holding a local block of width {\em blockSize}.

We note
\begin{itemize}
\item
Initialization is a complex procedure and clearly it should not be
coded anew for each application program.
\item
In this example the messages
were contiguous byte vectors that could be transmitted efficiently
through the {\em read} and {\em write} methods of the Java socket API.
In general the messages will have more complex types and the data may
not be contiguous in memory.  Using the typed primitives of the
standard API may then incur extra costs of copying and type-conversion.
\end{itemize}
For reasons such as these we suspect that direct socket programming
will remain unattractive to scientific parallel programmers, even with
the simplified Java socket API.

\subsection{\label{MPI1}MPI Interface}

We have produced a Java interface to an existing MPI implementation
\cite{MPICH} using Java {\em native methods}.  The interface has
been tested on a cluster of UltraSparc workstations running
Solaris\footnote{Interfacing Java to MPICH/P4 was not
straightforward, due to unpleasant interactions between the Java
run-time and the underlying P4 implementation.  For example, standard
implementations of both use the UNIX {\em SIGALRM} signal.  We found it
necessary to patch the MPICH 1.0.13 release to work round these
incompatibilities.  The necessary patches are available from us on request.}.
Our interface is modelled on the proposed C++ bindings of MPI\footnote{See
the article by Skjellum et al in \cite{ParallelCPlusPlus}.}.
For example, many of the most basic functions of the library are
members of the communicator class, {\em Comm}:
\small
\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}
\normalsize

Using these members, the socket-based program in the last section
can be transcribed straightforwardly to MPI.  To save space we omit this
naive
trans\-literation\footnote{We remark that use of standard mode {\em send} in such a contex is ``unsafe'', and could
deadlock if the system does not provide enough buffering.
The same caveat applies to the socket-based version}.
In the next section
we illustrate some of the added value that an MPI interface brings.

\subsection{\label{MPI2}Derived data types and higher-level MPI features}

\begin{figure}[hbtp]
\footnotesize
\begin{verbatim}
class Life {
  void main(String args) {
    MPI.Init(args) ;

    int dims [] = new int [2] ;
    ... Set `dims', etc
    Cart p = new Cart(MPI.WORLD, dims, periods, false) ;

    int coords = new int [2] ;
    p.Get(dims, periods, coords) ;
    ... Compute `blockSizeX', `blockBaseX', `blockSizeY', `blockBaseY'.

    // Create `block', allowing for ghost cells.

    int sX = blockSizeX + 2 ;
    int sY = blockSizeY + 2 ;
    block = new byte [sX * sY] ;
    ... Define initial state of Life board

    // Precompute parameters of shift communications.

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

    Datatype edgeYType = MPI.BYTE.Vector(sX, 1, sY) ;
    edgeYType.Commit() ;

    CartShift pX = p.shift(0,  1) ;
    CartShift nX = p.shift(0, -1) ;
    CartShift pY = p.shift(1,  1) ;
    CartShift nY = p.shift(1, -1) ;

    // Main update loop.

    for(int iter = 0 ; iter < NITER ; iter++) {
      ... Execute shifts.

      ... Calculate block of neighbour sums.
      ... Update block of board values.
    }

    MPI.Finalize();
  }
  ...
}
\end{verbatim}
\caption{\label{lifeMPI2}Life program using full MPI.}
\end{figure}
\begin{figure}[hbtp]
\footnotesize
\begin{verbatim}
      // Execute shifts...

      // Shift local upper x edge into next neighbour's lower ghost edge

      p.Sendrecv(block, blockSizeX * sY, 1, edgeXType, pX.dst, 0,
                 block, 0,               1, edgeXType, pX.src, 0) ;

      // Shift local lower x edge into prev neighbour's upper ghost edge 

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

      // Shift local upper y edge into next neighbour's lower ghost edge

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

      // Shift local lower y edge into prev neighbour's upper ghost edge

      p.Sendrecv(block, 1,              1, edgeYType, nY.dst, 0,
                 block, blockSizeY + 1, 1, edgeYType, nY.src, 0) ;
\end{verbatim}
\caption{\label{lifeMPI3}Full MPI Life program (detail).}
\end{figure}

Description of the data buffers passed to communication operations
presents some special problems in Java.  Existing MPI bindings
depend on a linear memory model and explicit or implicit use of
pointers.  Java does not have such a linear memory model.  Even behind
the scenes a Java array has no uniquely defined address in
memory, because the garbage collector is allowed to relocate objects
unpredicatably during program execution to avoid fragmentation of
its workspace.
Our Java interface tries to retain as much of the MPI derived data-type
mechanism as practical, but some functionality has been
sacrificed.  The buffer argument passed to a send or receive operation
must be a one-dimensional array of primitive type.  Any offset
specified in a derived type argument then refers to a displacement
within this one-dimensional array, never a displacement in
memory\footnote{Run-time relocation of data causes at least one
unresolved problem in making a Java binding to a standard MPI implementation.
In such implementations the {\em request} objects for non-blocking
communications will probably retain pointers to the user buffer area.
But the data address for the Java array could be moved during the
lifetime of the request object.  Our current Java binding omits
non-blocking communication, so we have not addressed this problem.}.

All MPI derived types expressible through our interface have a uniquely
defined {\em base type}---a Java primitive type.  Interfaces to
MPI\_TYPE\_HVECTOR and MPI\_TYPE\_HINDEXED are provided, but the
strides and displacements are in units of the base type, not bytes.  An
interface to MPI\_TYPE\_STRUCT is provided, but all component types in
the ``struct'' must have the same base type.

In the concrete Java binding of the {\em send} function, for example,
\small
\begin{verbatim}
    void Send(Object buf, int offset, int count,
              Datatype datatype, int dest, int tag) ;
\end{verbatim}
\normalsize
the formal {\em buf} argument is presented as a generic Java {\em Object}.
As explained above, the actual argument must be a linear array.  The
second argument is the offset in this array of the first element of
the message\footnote{This offset is in units of the 
{\em buf} array element---or the base type of {\em datatype}---not of any
compound type.  The {\em Object} $+$ {\em offset} presentation is
reminiscent of the interface of the {\em arrayCopy} utility in the
standard Java API.}.  The remaining arguments correspond directly to
arguments of MPI\_Send.  The base type of the {\em datatype} argument
must be the type of the elements of {\em buf}.

Figures \ref{lifeMPI2}, \ref{lifeMPI3}
sketch a version of the Life
program illustrating several of these features.  As well as derived types,
this program uses the Cartesian topologies of MPI.  The {\em Cart} class
is derived from {\em Comm}.  In the example, the topology {\em p}
represents a two dimensional periodic grid of processes.  The {\em Get}
member returns the coordinates of the local process.  From
these the parameters of the local array block are computed.

The values {\em sX}, {\em sY} represent the sides of the locally held
array segment, including ghost regions.  This segment is created as a
one-dimensional Java array, {\em block}.  The derived type {\em edgeXType}
describes the structure of ghost area on the upper or lower {\em x}
sides: contiguous regions of the {\em block} array of extent {\em sY}.
The type {\em edgeYType} describes the {\em y}-side ghost areas:
non-contiguous regions of count {\em sX}, regular stride {\em sY}.

The {\em shift} member of {\em Cart} corresponds to the MPI function
MPI\_CART\_SHIFT: it returns the source and destination processors for
a cyclic shift.  The Java binding returns these values in an object
of class {\em CartShift} which just contains two integers.
Finally, in the main loop, the shifts are executed by using the
{\em Comm} member {\em Sendrecv}, which corresponds to the standard
MPI function MPI\_Sendrecv.  This performs a send and a receive concurrently
(avoiding a potential deadlock in the implementations given in the
previous sections).

The mechanism for accessing global resources used in our MPI interface is
slightly different to the sockets example---static members on an {\em
MPI} class rather than dynamic members of a {\em jpi} class---but this
difference is not very important.

\section{\label{data}Data parallellism in Java}

The most comprehensive statement of the data parallel model of
computation is the High Performance Fortran standard
\cite{HPFStandard,HPFBook}.  That document is supposed to embody much of
the collective experience of the scientific parallel programming
community.  Presumably, then, any attempt to incorporate data
parallelism into Java should build on the HPF model where possible.

The HPF definition consists of a large set of directives a small
handful of language extensions, and a library of new array functions.
An initial data-parallel Java may well be implemented through a
class-library.  This library would assume the r\"{o}les of the
directives and language extensions in HPF as well as the HPF library.

We will loosely distinguish two different levels at which a library
implementation of the HPF semantics (or, at least, the HPF distributed
data model) can operate.
\begin{itemize}
\item
The first is the level of the so-called {\em run-time libraries}
\cite{structured,irregular,PCRC,Adlib}.  This kind of library
provides functions for scheduling and executing specific patterns of
collective communication already identified by a compiler (in the
HPF case) or else by an application programmer using the library directly.
Such a library may also provide functions for translating between
global subscripts and local, node-level subscripts---ie, for computing
the mapping of a distributed array into the address spaces of
individual processors.
\item
Alternatively, a library can operate at a higher level that conceals
all aspects of data localization and transfer from the user.  The only
responsibility of the user is to specify the distribution format of
arrays when they are declared.  Subsequently the user just tells the
library to do particular operations on particular distributed arrays.
It is left to the library to work out whether or not a communication is
implied.  In effect the library is operating at the same level as
the HPF language.  An example of such a library is A++/P++
\cite{APlusPlusPPlusPlus}.
\end{itemize}
In either case a {\em class library} version is likely to include
classes to describe the elements of the HPF data model, such as
processor arrangements and the distributed arrays themselves.

\subsection{\label{collective}Parallel arrays and collective communication}

At the run-time level, a class library implementation of the
HPF model is likely to include
\begin{itemize}
\item
Classes to describe process arrays and distributed data arrays.
\item
Classes or functions to simplify access to locally held elements
of a distributed array (including parallel iteration).
\item
Functions for collective communication through operations on
distributed arrays: regular ``copying'' operations including shifts and
transposes, arithmetic reduction operations, irregular gather/scatter
operations, and so on.
\end{itemize}
Our first experiments with a Java binding only touch the surface
of the full HPF semantics, but they provide some hints about a general
framework.  The interface given here borrows from the C++ class library,
Adlib, developed by one of us \cite{Adlib}.

A distributed array is parametrized by a member of the {\em Array}
class.  In C++ {\em Array} would naturally be a {\em template} for a
{\em container class}.  In Java, generic container classes are
problematic.  Without the template mechanism, the obvious options are
that a container holds items of type {\em Object}, the base class
for all non-primitive types, or that a separate container class is
provided for each allowed type of element.  The first option doesn't
allow for array elements of primitive type, and prevents compile-time
type-checking (reminiscent of using {\em void*} in C).  The second
approach presumably involves restricting elements to the finite set of
primitive types ({\em int}, {\em float}, \ldots)\footnote{Perhaps a good
compromise is to provide one container class for each primitive
type and one for {\em Object}.}.  For now we have side-stepped the
issue by leaving the data elements out of the {\em Array} class.
{\em Array} defines the shape and distribution of an array, but
space for elements is allocated in a separately declared vector of the
appropriate type\footnote{Confusingly enough, this makes our {\em
Array} more akin to an HPF {\em template} than an HPF array.
Needless to say, there is no connection between C++ templates and HPF
templates.}.

The constructor for an {\em Array} defines its shape and distribution
format.  This is expressed through two auxilliary classes:  the
{\em Procs} and {\em Range} classes.  The {\em Procs} class
corresponds directly to the HPF {\em processor arrangement}.  It maps
the set of physical processes on which the program is executing to a
multi-dimensional grid.  A {\em Range} describes a single dimension of
an HPF array.  It embodies an array extent (the size of the array in
the dimension concerned), and a mapping of the subscript range to a
dimension of a {\em Procs} grid.

In our pilot implementation any parallel Java application is written as
a class extending the library class {\em Node}.  The {\em Node} class
maintains some global information and provides various collective
operations on arrays as member functions.  The code for the ``main
program'' goes in the {\em run} member of the application
class\footnote{This approach is modelled on the {\em Thread} and {\em
Applet} classes in the standard Java API.  Other approaches to
providing library-wide resources were illustrated in earlier
sections.}.

A simplified version of the code for the ``Life'' demo is given in figure
\ref{life}.
\begin{figure}[btp]
\footnotesize
\begin{verbatim}
public class Life extends Node implements Runnable {
  ...

  public void run() {
    Procs p = new Procs(this, 2, 2) ;

    Range x = new Range(N, p, 0) ;
    Range y = new Range(N, p, 1) ;

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

    int s = r.seg();
    byte[] w = new byte[s];

    byte[] cn_ = new byte[s];
    byte[] cp_ = new byte[s];
    ... etc, create arrays for 8 neighbours

    // Initialize the Life board

    for(r.forall(); r.test(); r.next())
      w[r.sub()] = fun(r.idx(0), r.idx(1)) ;

    // Main loop

    for (int k=0; k<NITER; k++) {

      // Get neighbours

      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}
\caption{\label{life}Simplified code of the Life demo program.}
\end{figure}
The object {\em p} represents a 2 by 2 process grid.
The {\em Procs} constructor takes the current {\em Node} object as an
argument, from which it obtains information on the available physical
processes.
In this simplified example we assume that the program executes
on exactly four processors.

The objects {\em x} and {\em y} represent index ranges of size
{\em N} distributed over the first and second dimensions of the grid
{\em p}.  The default distribution format is blockwise.  Cyclic
distribution format can also be specified by using a range object of
class {\em CRange}, which is derived from {\em Range} (the pilot
implementation does not provide any more general distribution or
alignment options).

The object {\em r} represents the shape and distribution of a two
dimensional array.  This ``template'' is shared by
several distributed arrays---it does not contain a data vector.
The data vectors that hold the local segments of arrays are created separately
using the inquiry function {\em seg}, which returns the number of
locally held elements.
In the example the elements of the main data array are held in
{\em w}.  The extra arrays {\em cn\_, cp\_, ..., cnn, ...}
will be used to hold arrays of neighbour values\footnote{Here
we will use whole arrays of neighbours and a {\em shift} operation.  This
is arguably the more conventional approach in a data-parallel setting,
but the the ghost-edge mechanism can also be fitted into this framework.}.

The ``forall loop'' initializing {\em w} should be read as something like
\small
\begin{verbatim}
  forall(i in range x, j in range y)
    w(i, j) = fun(i, j)
\end{verbatim}
\normalsize
where {\em fun} is some function of the global indices defining the
initial state of the Life board.  The members {\em forall},
{\em test}, {\em next} update internal state of {\em r} so that
{\em r.sub()} returns the local subscript for the current iteration,
and {\em r.idx(0)} and {\em r.idx(1)} return the global index values
for the current iteration.  We are using {\em r} as an {\em iterator}
class\footnote{Our {\em Array} class is perched somewhere between
STL container and iterator classes.  This is a slightly awkward
position, and it may be more satifactory to separate these
functions into different classes.}.

The main loop uses cyclic {\em shift} operations to obtain neighbours,
communicating data where necessary.  The {\em shift} operation is a
member of the {\em Node} class.  It should be overloaded to accept
data vectors of any primitive type---here the array elements are
{\em byte}s.

Finally {\em w} is updated in terms of its neighbours.

Note some characteristic features of the data-parallel style of programming:
\begin{itemize}
\item
The distribution format of the arrays can be changed just by
altering a few parameters at the start of the program---the main
program is insensitive to these details
\item
low level
message-passing is abstracted into high-level collective operations on
distributed array structures.
\end{itemize}


%\subsection{``Array syntax'' in Java.}
%
%The higher level approach would make {\em Array} classes look like true
%container classes (for a restricted set of types) and {\em all} operations on
%arrays collective, something like:
%\small
%\begin{verbatim}
%  ArrayFloat a = new ArrayFloat(p, x, y) ;
%  ArrayFloat b = new ArrayFloat(p, x, y) ;
%  ArrayInt c = new ArrayInt(p, x, y) ;
%
%  a = MATMUL(b, c) ;
%\end{verbatim}
%\normalsize
%Communication would be handled automatically inside array operations
%like MATMUL.  Individual array elements would not be accessed
%in the Java program except, possibly, through {\em getElement},
%{\em putElement} members.
%
%This scheme can be implemented on top of an SPMD Java array library of
%the kind outlined in the previous section {\em or} by making the Java
%run as a coordination program controlling a parallel back end.  It can
%be compared with \cite{APlusPlusPPlusPlus,HPFInterpreter}.
%
%So far we have not attempted to implement (or specify in detail) such
%an approach for Java.  The lack of user-defined operator-overloading
%may be frustrating here.

\section{Discussion\label{discussion}}

We have explored the practicality of doing parallel computing in Java,
and of providing Java interfaces to High Performance Computing software.
For various reasons, the success of this exercise was not a foregone
conclusion.  Java sits on a virtual machine model significantly
different to the hardware-oriented model that C or Fortran exploit
directly.  Java discourages or prevents direct access to the some of
the fundamental resources of the underlying hardware (most extremely,
its memory).

Our earliest experiments in this direction involved working
entirely within Java, building new software on top of the communication
facilities of the standard API.  The more recent work in sections
\ref{MPI1} and \ref{MPI2} involved creating a Java interface to an
existing HPC package.  Which is the better strategy?  In the long term
Java may become a major implementation language for large
software packages like MPI.  It certainly has advantages in respect of
portability that could simplify implementations dramatically.  In the
immediate term recoding these packages does not appear so attractive.
Java wrappers to existing software look more sensible.  On a cautionary
note, our experience with MPI suggests that interfacing Java
to non-trivial communication packages may be less easy than it sounds.
Nevertheless, we intend in the future to create a Java interface to an
existing run-time library for data parallel computation.

So is Java, as it stands, a good language for High Performance Computing?

It still has to be demonstrated that Java can be compiled to code
of efficiency comparable with C or Fortran.  Many avenues are being
followed simultaneously towards a {\em higher performance} Java. For example,
besides the Java chip effort of Sun, it has been reported
in an earlier workshop \cite{syracuse}
that IBM is developing an optimizing Java compiler
that produces binary code directly, that Rice University and Rochester
University are working on optimization and restructuring of bytecode
generated by {\em javac}, and that Indiana University is working on source
restructuring to parallelize Java.  Parallel interpretation of bytecode
is also an emerging practice.  For example, the IBM JVM, an
implementation of JVM on shared memory architectures, was released in
spring 1996, and UIUC has recently started work aimed at parallel
interpretation of Java bytecode for distributed memory systems.

Another promising approach under investigation \cite{ii/cvm} is to integrate 
interpretation and compilation techniques for parallel execution of
Java programs. In such a system, a partially ordered set of {\em interpretive
frames} is generated by an 
{\em II/CVM compiler}. A frame is a description of some subtask, 
whose granularity may range from a single scalar assignment statement to 
a solver for a system of equations.
Under supervision of the virtual machine (II/CVM), 
the actions specified in a frame may be performed in one of three ways:
\begin{itemize}
\item
Executed by an {\em interpretive module} directly, which also
incorporates JIT compilation capability.
\item
Some precompiled {\em computational library} function is invoked
locally to accomplish the task; this function may be executed
sequentially or in parallel.
\item
The frame is sent to some {\em registered remote system}, which
will get the work done, once again either sequentially or in
parallel.
\end{itemize}
With this approach, optimized binary codes for {\em well formed} computation
subtasks exist in runtime libraries, supporting a high level 
interpretive environment. Task parallelism is observed among different
frames executed by the three mechanisms simultaneously, while data 
parallelism is observed in the execution of some of the runtime functions.

Presuming these efforts satisfactorily address the performance issue,
a second question concerns expressiveness of the Java language.
Our final interface to MPI is quite elegant, and provides much
of the functionality of the standard C and Fortran bindings.  But
creating this interface was a more difficult process than one might
hope, both in terms of getting a good specification, and in terms of
making the implementation work.  In section \ref{data} we noted
that the lack of features like C++ templates (or any form of parametric
polymorphism) and user-defined operator overloading (available in many
modern languages)
made it difficult to produce a completely satisfying interface to a
data parallel library.  The Java language as currently defined imposes
various limits to the creativity of the programmer.

In many respects Java is undoubtedly a better language than Fortran.
It is object-oriented to the core and highly dynamic, and there is
every reason to suppose that such features will be as valuable in
scientific computing as in any other programming discipline.  But to
displace established scientific programming languages Java will probably
have to acquire some of the facilities taken for granted in those
languages.

\bibliography{experiments}

\end{document}

