
\documentstyle{article}

\input{psfig} 

\begin{document}

\bibliographystyle{plain}

%\sloppy

\pagestyle{plain}

\title{Experiments with ``HPJava''}

\author{Bryan Carpenter, Yuh-Jye Chang, \\
        Geoffrey Fox, Donald Leskiw, Xiaoming Li, \\
        \em Northeast Parallel Architectures Centre, \\
        \em Syracuse University, \\
        \em Syracuse, New York
}

\maketitle

\begin{abstract}
We consider the possible r\"{o}le of Java as a language for
High Performance Computing.  After discussing reasons why Java
may be a natural candidate for a portable parallel programming
language, we describe several case studies.
These cover Java socket programming, message-passing through
a Java interface to MPI, and class libraries for data-parallel
programming in Java.
\end{abstract}

\newpage

\tableofcontents

\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.  According to
\cite{JavaWhitePaper}
\begin{quote}
``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}

Several of these concerns are mirrored in developments in the
High Performance Computing world over a number of years.  A decade ago
the focus of interest in the parallel computing community was on
parallel hardware.  A parallel computer was typically built from
specialized processors integrated through a proprietary high-performance
communication switch.  If the machine also had to be
programmed in a proprietary language, that was an acceptable price for
the benefits of using a supercomputer.  This attitude was not
sustainable as one parallel architecture gave way to another, and the
cost of porting software became exorbitant.  For several years now,
portability across platforms had been a central concern in parallel
computing \cite{p4Book,p4Article,MPIStandard,HPFStandard,HPFBook}.

More fundamentally, the assumption that high performance computing will
be done primarily on specialized supercomputers is questioned increasingly.
Rapid strides in performance and connectivity of ordinary workstations
and PCs make it look equally possible that the future of parallel
computing will be on local area networks, or even the Internet
\cite{PVMBook,WebComputing}.

With Java positioned to become a standard programming language
on the Internet, and scientific parallel processing
%apparently moving
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; they are already used almost universally by
{\em implementers} of parallel libraries and compilers.  In recent
years numerous variations on the theme of C++ for parallel computing
have appeared.  See, for example
\cite{CCPlusPlusArticle,CCPlusPlusTutorial,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.  Independent threads {\em 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}.

The acronym ``HPJava'' was coined in a draft white paper produced by
members of the PCRC consortium in the first half of 1996
\cite{HPJava}.  At NPAC we have been experimenting with some of the
ideas put forward there.

\subsection{Overview of this article.}

Section \ref{issues} 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 more successful
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 has already been demonstrated \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.

%[Something about the words from Texas
%in the HPJava white paper, if can make sense of them]

%Fine grain parallelism through extended Java thread mechanism.
%Interacting objects.

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\footnote{Of course we could run a preprocessor over Java, but
this is not a natural procedure in existing Java
environments}.  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.

Another open question is how multiple interacting Java tasks are to
be initiated.  Conventionally in network computing, instructions to execute
a particular user task are sent to a specialized daemon or secure
server running on the target host.  Alternatively standard
operating system daemons ({\em rshd}, {\em rexecd}, \ldots) can be used
to the same effect.  Java brings some options of its own.  One
is to use standard or enhanced Web servers to execute Java byte-codes.
This approach is predicated on the existence of cooperative servers,
probably running suitable CGI scripts.  Another option is to exploit
Java-enabled browsers.  Applets downloaded from a particular server can
perform computations and return the results to that server.  In any
case the substantive improvement over conventional network computing is
that the byte-codes can be downloaded on the fly to target hosts, even
in heterogenous networks.  Conventionally, it was often necessary to
install and compile an application on each target host before starting
the task remotely.


\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.  Scientific programmers have
expected to program inter-process communication at a higher level, if
at all.  More successful schemes include
\begin{itemize}
\item
Message-passing through language-level support \cite{occam,FortranM}
or higher-level library interfaces \cite{MPIStandard}.
\item
Data parallelism.
We restrict the definition of ``data parallelism'' to cover algorithms
that achieve parallelism through operations on distributed arrays.
Synchronization is usually limited to bulk synchronization occuring
naturally through collective operations.
\item
Communication through shared memory or shared objects.
Some more or less intricate mechanism for inter-process synchronization
is usually provided.
% 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 we will not
discuss it further here.

An orthogonal issue is whether the high-level libraries used to
implement these paradigms (presuming class-library implementations)
should be written in Java on top of the standard API, or whether
they should be implemented as direct interfaces to native code.  We
will have more to say about this later.

\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.  This
situation is typically bootstrapped as follows.  The program is invoked
on one host.  This host creates a listening socket.  It sends
instructions to servers on some other hosts (either explicitly or
through a command such as {\em rsh}) to start remote invocations of the
program (somehow sending the number of the port on which it is
listening in the initiation message).  Each new process creates a
listening socket and sends its port number to the original process.
The original process broadcasts these address to all its slaves.  At
this point each process knows the port number on which each of its
peers is listening.  Either they establish all-to-all connections now,
before entering the SPMD main program, or the main program starts
immediately, and connections are established dynamically when a message
needs to be sent.

\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 this block's 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 this block's 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}
\begin{figure}[hbtp]
\footnotesize
\begin{verbatim}
    int sums[][] = new int[blockSize][N];

    ....

      //  Calculate block of neighbour sums.

      for(i = 0, ib = 1 ; i < blockSize ; i++, ib++)
        for(y = 0 ; y < N ; y++) {
          int y_n = (y+N-1) % N ;
          int y_p = (y+1) % N ;
          sums[i][y] =
              block[ib - 1][y_n] + block[ib - 1][y] + block[ib - 1][y_p] +
              block[ib]    [y_n] +                    block[ib]    [y_p] +
              block[ib + 1][y_n] + block[ib + 1][y] + block[ib + 1][y_p];
        }

      // Update block of board values.

      for(i = 0, ib = 1 ; i < blockSize ; i++, ib++)
        for(y = 0 ; y < N ; y++)
          switch (sums[i][y]) {
            case 2 : break;
            case 3 : block[ib][y] = 1; break;
            default: block[ib][y] = 0; break;
          }
\end{verbatim}
\caption{\label{lifeSocket2}Socket-based Life program (detail).}
\end{figure}
Figures \ref{lifeSocket}, \ref{lifeSocket2} give 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}.  Its interface is
\small
\begin{verbatim}
  class hpj {
    hpj(String[] args) ;

    int my_id() ;
    int num_processor() ;

    DataInputStream Input(int id) ;
    DataOutputStream Output(int id) ;
    ...
  }
\end{verbatim}
\normalsize
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}\footnote{For earlier work
on interfacing Java to PVM see
http://www.isye.gatech.edu/chmsr/JavaPVM/ and
http://www.cs.virginia.edu/\~ajfzj/jpvm.html}

The interface has
been tested on a cluster of UltraSparc workstations running
Solaris\footnote{Interfacing Java to MPICH/P4 was not entirely
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.
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

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

    int np = MPI.WORLD.Size();
    int id = MPI.WORLD.Rank();

    ... 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 this block's upper edge into next neighbour's lower ghost edge

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

      // Shift this block's lower edge into prev neighbour's upper ghost edge

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

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

    MPI.Finalize();
  }
}
\end{verbatim}
\caption{\label{lifeMPI}Simple MPI Life program.}
\end{figure}
Figure \ref{lifeMPI} is a straightforward transcription of the
socket-based program in the last section\footnote{MPI afficionados will
note that the use of standard mode {\em send} is ``unsafe'', and could
deadlock if the system does not provide enough buffering.
The same remark could be made about the socket-based version}.
Our MPI inteface uses a slightly different model for accessing global
resources---static members on an {\em MPI} class:
\small
\begin{verbatim}
  class MPI {
    static Init() ;
    static Finalize() ;

    public static Comm WORLD ;

    public static Datatype BYTE ;
    public static Datatype INT ;
    ...
  }
\end{verbatim}
\normalsize
rather than dynamic members of a {\em jpi} class---but this difference is not
particularly significant (yet another approach will be taken in the
example of section \ref{collective}).  Otherwise the correspondence
between this code and the socket code is direct.  In the next section
we illustrate some of the added value that an MPI interface brings.

We have broken with the usual MPI convention of returning an error status
from every function.  This practice is inconvenient in Java because
arguments cannot be passed by reference and directly modified.  This
makes the return value precious, and using it up on an error value that
everybody ignores is a waste.  Java has a well established
exception mechanism for ignoring error information.


\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 local `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 this block's 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 this block's 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 this block's 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 this block's 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 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.

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).

\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 wherever possible.

The HPF definition consists of a large set of directives that can be
used to annotate a standard Fortran program, a small handful of
language extensions, and a library of new functions for operating on
arrays.  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 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 be 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}
It may be unclear that this framework has the same power as
HPF.  If the distributed array model is extended to the full HPF model,
as it can be, and the {\em shift} operation is augmented by some more
powerful collective operations including gather and scatter
operations parametrized by subscript arrays, we claim that it does.
The proof lies in the observation that this is, as advertised, a simplified
model of the kind of run-time library that various HPF translators
target.  This is not to say that programming in this style is always as
straightforward as the example given here, or as comprehensible as the
corresponding HPF program (if it was, there would be no need for HPF).


\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 particularly 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 that is significantly
different to the hardware-oriented model which 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 (including the work described
in section \ref{data}, which predates the MPI work) 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 might 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 the language can be compiled to code
of efficiency comparable with C or Fortran.  Many approaches are being
taken simultaneously towards a {\em higher performance} Java. Besides
Java chip effort by Sun, it has been reported at
this workshop that IBM is developing an optimizing Java compiler
which 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 observed practice. Besides
IBM JVM released in spring 1996, an implementation of JVM on shared memory 
architectures,  UIUC has newly started a work aiming at parallel 
interpretation of Java bytecode for distributed memory system. 

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 of system of equations.
Under supervision of the virtual machine (II/CVM), 
the actions specified in a frame may be performed in one of the
three ways.
  \begin{trivlist}
  \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{trivlist}
With this approach, optimized binary codes for {\em well formed} computation
subtasks exist in terms of runtime libraries, supporting a high level 
interpretive environment. Task parallelism is observed among different
frames executed by the above three mechanisms simultaneously, while data 
parallelism is observed in the execution of some of the runtime functions.

%\bibitem{ii/cvm}
%Geoffrey C. Fox, Xiaoming Li, Yuhong Wen, and Guansong Zhang, ``Studies of 
%Integration and Optimization of Interpreted and Compiled Languages,'' 
%Technical Report SCCS-780, NPAC at Syracuse University, February 12, 1997.

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 expect, both
in terms of getting a good specification, and in terms of making the
implementation work.  In section \ref{data} we have emphasised that
the lack of features like C++ templates (or any form of parametric
polymorphism) and user-defined operator overloading (available in many
modern languages, from Prolog to Fortran) made it difficult to produce
a completely satisfying interface for a data parallel library.  In the
current state of development of Java one sometimes has the sense of
battling against restrictions of the language.

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 surely
have to acquire some of the facilities taken for granted in those
languages.  Perhaps the necessary extensions will include explicit
syntax for parallel computing.

\bibliography{experiments}

\end{document}

