

\documentstyle{article}

\input{psfig} 

\begin{document}

\sloppy

\pagestyle{plain}

\title{HPJava: Work in progress}

\author{Bryan Carpenter, Yuh-Jye Chang}

\maketitle

Emphasis to date has been on providing class libraries to
facilitate communication and parallel computation within the framework
of Java.  For now this means communicating Java {\em applications}, but
eventually it should be possible provide class libraries which allow
Java applets downloaded from a common server to communicate (for
example, by having their server transparently through-route
communications).

We have prototyped a class library for Fortran-M-like {\em channel
communication} to support a message-passinge style or programming.
Presently we are experimenting with class library interfaces to
directly support the {\em data parallel} programming style.

The existing software for both these approaches has been layered
directly on the Java socket interface.  For the next stage of
development we plan to produce a Java interface to a
run-time library being developed in the PCRC project.  By interfacing
to an existing body of software through Java {\em native methods} we
will avoid reimplementing the complex collective operations needed in
data parallel applications.  We also expect to obtain better efficiency.

\section{Parallel arrays and data parallel computation}

Our experimental implementation of parallel arrays for Java is similar
to the array model of the C++ library, Adlib, developed by one us.
(A similar model is also being used in the NPAC PCRC library---it
is based on the HPF distributed data model.)

In Java the distribution of an array is parametrized by a member of the
\verb$Array$ class (as it turns out the Java \verb$Array$ object is more
akin to an HPF {\em template} than a data array).  An \verb$Array$ object is
defined in terms a target group of processes and a set of distributed
index ranges, one per array dimension.  The group of processes is some
multi-dimensional process grid represented by an object from the
\verb$Procs$ class.  Each distributed index range is represented by an
object from the \verb$Range$ class.

Any parallel Java application is written as a a class extending the
library class \verb$Node$.  The \verb$Node$ class maintains some global
information and provides various collective operations on arrays.  The
code for the ``main program'' goes in the \verb$run$ member of the
application class.

\subsection{Example data parallel Java program}

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 xys = r.seg();
    byte[] w = new byte[xys];

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

    // Initialize the Life board

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

    // 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(int i=0; i<w.length; i++) {
        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 \verb$p$ represents a 2 by 2 process grid.  In
this simplified example we assume that the program executes
on exactly four processors.  More generally the library provides
a member function on \verb$Procs$ to determine whether the local
process holds any member of the virtual process grid.  The
\verb$Procs$ constructor takes the current \verb$Node$ object as
an argument, from which it obtains information on the available
physical processes.

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

The object \verb$r$ represents the shape and distribution of a two
dimensional array.  Note that this ``template'' can be shared by
several actual arrays because it does not contain a data vector.
The limited polymorphism of Java makes it awkward to create
true container classes for primitive data types.
The data vectors that hold the local segments of arrays are created separately
using the inquiry function \verb$seg$ which returns the number of
locally held elements.
In the example the elements of the main data array are held in
\verb$w$.  The extra arrays \verb$cn_, cp_, ..., cnn, ...$
will be used to hold arrays on neighbour sites.

The ``forall loop'' initializing \verb$w$ should be read as something like
\begin{verbatim}
  forall(i in range x, j in range y)
    w(i, j) = fun(i, j)
\end{verbatim}
where \verb$fun$ is some function of the global indices defining the
initial state of the life board.  The members \verb$forall$,
\verb$test$, \verb$next$ update the state of \verb$r$ and the range
structures contained in it so that \verb$r.sub()$ returns the local
subscript for the current iteration, and \verb$x.idx()$ and
\verb$y.idx()$ return the global index values for the current iteration

The main loop uses cyclic \verb$shift$ operations to obtain neighbours,
communicating data where necessary.  The \verb$shift$ operation is a
member of the \verb$Node$ class.  Eventually it will be overloaded to
accept data vectors of any primitive type---here the array elements are
\verb$byte$s.

Finally \verb$w$ is implemented in terms of its neighbours.  This could
have been done using a ``forall loop'', but since global index values
are not needed here the loop has been optimised for a simple for loop
over the local segment.  This performance-critical inner loop is coded
at least as efficiently as a typical sequential program.

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{Starting an HPJ program}

A \verb$Node$ instance can be started on any host running a suitable
daemon.  A master server process records the pool of slave daemons
currently running.  When a new daemon is started, it registers with
this central server.  Clients may request a list of hosts running
daemons from the main server, then ask for a particular Java object file
to be run on any subset of those hosts.  Typically the client is an
applet running in a browser, and the main HPJ server runs on the same
host as an HTTP server from which the applet was downloaded.

\subsection{Outlook on data-parallel programming in Java}

Although Java is quite a restrictive language, our experiments suggest
that it should be possible develop a useful class library interface for
data parallel programming, without necessarily extending
the basic language.

Java's strict typing regime (the absence, for example, of
castable pointers) makes it difficult to write interfaces to
communication libraries that efficiently accept data of multiple types
(polymorphism).  The I/O and socket communication classes in the
standard API resort to expensive format conversions whenever an object
has to be transfered.  Benchmarking the example presented earlier indicates
that while parallelism gives genuine performance gains
there is an obvious communication penalty even with large problem sizes.
For example, the
following timings were obtained on a grid size of 512 by 512
\begin{verbatim}
              number of          time per
              processors       iteration/ms

                   1               1502
                   2               1011
                   4                784
\end{verbatim}
The volume of data that has to be communicated in an iteration is on
the order of 1\% of the total data set, but speedup is still a long way
from ideal.  Further benchmark results are available on the demo Web
page.

We hope that the efficiency problems can be overcome by taking
a different approach to implementing the interface.  Instead of
implementing the library within Java on top of the standard API we will
call the existing PCRC run-time library through a {\em native methods}
interface.  In any case this approach will be easier than
recoding collective communication operations, some much more complicated
the \verb$shift$, within Java.

\section{Channels}

We have prototyped a Java class library for channel communication.  The
semantics are similar (but not identical) to the dynamic channels of
Fortran M.

The model is quite attractive in Java because
\begin{enumerate}
\item
It is ``connection-oriented'' so ordinary data communications
map directly onto the socket I/O primitives efficiently implemented
for Java and the Web.
\item
It directly supports highly dynamic situations where new
remote processes (eg, applets) come into existence unpredictably,
and may have unpredictable communication demands (eg, determined by
requirements of a remote user).
\item
It provides a layer of abstraction above internet addresses
and socket port numbers, and associated resources to which access
may be limited by Java security models.
\end{enumerate}

\subsection{Overview of the channel model}

In our model
a channel supports bi-directional communication of data (with unbounded
buffering).
Access to logical channels is provided through a Java class called a
{\tt Port}\footnote{The {\tt Port} dresses up and adds functionality to
an internet port, but should not be confused with this lower-level
idea.  The {\tt Port} interface does not provide direct access to port
numbers or internet addresses.}.  
Networks of Java applications connected by channels
are created through the following operations
\begin{itemize}
\item
A pair of locally defined ports can
be {\em connected}, creating a local channel between a
pair of connected {\em channel ends}.
\item
A {\em remote procedure call} mechanism allows initiation of a Java
application on a remote processor, and creates an initial channel
between the parent and the remote application.
\item
Channel ends can be communicated over other channels, on much the
same footing as data.
\end{itemize}
These primitives are sufficient to create sets of processes with arbitrary
channel connectivity.

A functionality similar to the ``merge'' in Fortran-M is provided
through the ``merge pool'' class, \verb$Merge$.  Channel ends can be
added to or removed from the pool by passing their ports to suitable
member functions.  A blocking \verb$select$ operation returns a handle to a
port in the pool which presently has input data ready.  Merge pools
enable non-deterministic patterns of communication.

\subsection{Outlook on channel communication in Java}

This seems like a intersting approach to Java communication, which
could have applications beyond scientific parallel programming.  For
now this line of investigation is being pursued less actively than the
data parallel approach.

\end{document}

