
%
%  $Description: Author guidelines and sample document in LaTeX 2.09$ 
%
%  $Author: dbc $
%  $Date: 1999/01/25 19:08:52 $
%  $Revision: 1.1 $
%

%\documentstyle[times,art10,twocolumn,latex8]{article}
\documentstyle[twocolumn,latex8,psfig]{article}

%------------------------------------------------------------------------- 
% take the % away on next line to produce the final camera-ready version 
%\pagestyle{empty}

%------------------------------------------------------------------------- 
\begin{document}

\title{Automatic Object Serialization in the mpiJava Interface to MPI}

\author{Bryan Carpenter, Geoffrey Fox,
Sung Hoon Ko and Sang Lim \\
NPAC at Syracuse University\\ Syracuse, NY 13244 \\
\{dbc,gcf,shko,slim\}@npac.syr.edu\\
}

\maketitle
\thispagestyle{empty}

\begin{abstract}
The paper discusses use of the Java object serialization model for
marshalling communication data in Java bindings of the Message Passing
Interface standard, MPI.  This approach is compared with a Java
transcription of the derived datatype mechanism used for buffer
description in C and Fortran bindings of MPI.  We describe an
implementation of the {\em mpiJava} interface to MPI incorporating
automatic object serialization.  The programming model is
attractive, though benchmark results show that the current
JDK implementation of serialization is not fast enough for high performance
applications.  Strategies to improve this situation are discussed.
\end{abstract}

\section{Introduction}

In the few years since the Fortran, C and C++ bindings of the Message
Passing Interface, MPI, were
defined \cite{MPIStandard}, Java has emerged as a major language for distributed
programming.  There are various indications
\cite{Java_for_CSE,Java_for_CSE_II,Java98} that Java may also become
an important language for scientific and parallel computing.  Not
surprisingly, therefore, several groups have independently developed
Java bindings to MPI and Java implementations of MPI subsets.  In the
absence of a standarized Java API for MPI, everyone implements a
different interface.  In a move to remedy this situation, with support
of several groups working in the area, the Java Grande Forum
drafted an initial proposal for a common Java interface to MPI
\cite{MPIposition}.

Three major issues arising in the design of a
Java interface to MPI are: the class hierarchy, the detailed argument lists
for methods, and mechanisms for describing message buffers.  The
proposal in \cite{MPIposition} attempts to follow the standardized
language bindings for MPI as closely as practical, while conforming to
Java's object-oriented programming model and following programming
conventions commonly adopted by Java programmers.  MPI, even in its
original C and Fortran instantiations, deliberately followed
object-oriented design principles.  The subsequent addition of a C++
binding for MPI \cite{MPIStandard} already defined a detailed class hierarchy.
The Java binding suggested in \cite{MPIposition} adopts that
hierarchy as it stands.  At the level of detailed argument lists there
are many small differences between the Java interface and the
established C or C++ interfaces.  These differences are either enforced
by restrictions of the Java language (for example the lack of
call-by-reference arguments), or exploit obvious features of Java to
simplify the interface (for example, explicit array-size arguments can
often be omitted because they can be extracted from run-time
information in a Java array).  These details are quite important in practise,
but they are relatively superficial.  More fundamental questions occur
at the level of buffer description.

A characteristic feature of MPI is its flexible
method for describing message buffers consisting of mixed
primitive fields scattered, possibly non-contiguously, over
the local memory of a processor.  These buffers are described through
special objects called {\em derived datatypes}---run-time analogues
of the user-defined types supported by languages like C.  The standard
MPI approach does not map very naturally into Java, because Java does
not expose the the physical memory layout of user data, or necessarily
implement a fixed, linear address space internally\footnote{For
example, the garbage collector is allowed to relocate objects
unpredicably at runtime, so the absolute and relative addresses of
objects are effectively ill-defined.}.

In \cite{Experiments_HPJava,NPACJavaMPI97a,MpiJava} we suggested a
Java-compatible restriction of the general MPI derived datatype
mechanism, in which all primitive elements of a message buffer have the
same type, and they are selected from the elements of a one-dimensional
Java array passed as the buffer argument.  This approach preserves some
of the functionality of the original MPI mechanism---for example the
ability to describe strided sections of a one dimensional buffer
argument, and to represent a subset of elements selected from the
buffer argument by an indirection vector.  But it does not allow
description of buffers containing elements of mixed primitive types.

The derived datatype mechanism is retained in the initial draft of
\cite{MPIposition}, but its usefulness seems to be limited.  In the
context of Java, a more promising approach may be the
addition a new basic datatype to MPI representing a serializable object.
The buffer array passed to communication functions is still a
one-dimensional array, but as well as allowing arrays with elements of
primitive type, the element type is allowed to be {\tt Object}.  The
serialization paradigm of Java can be adopted to transparently
serialize buffer elements at source and unserialize them at
destination.  An immediate application is to multidimensional arrays.
A Java multidimensional array is an array of arrays, and an array is an
object.  Therefore a multidimensional array is a one-dimensional array of
objects and it can be passed directly as a buffer array.
The options for representing sections of such an array are limited, but
at least the one can communicate whole multidimensional arrays without
explicitly copying them (of course there may well be copying inside the
implementation).

\subsection{Overview of this article.}

This article discusses our current work on use of object serialization
to marshal arguments of MPI communication operations.  It
builds on earlier work on the {\em mpiJava} interface to MPI \cite{MpiJava},
which is implemented as a set of JNI
wrappers to native C MPI packages for various platforms.
The original implementation of mpiJava supported MPI derived datatypes,
but not object types.

Section \ref{review} reviews the parts of the API of \cite{MPIposition}
relating to derived datatypes and object serialization.  Section
\ref{implementation} describes our prototype implementation of
automatic object serialiation in mpiJava.  In section \ref{benchmarks}
we describe some benchmarks for this initial implementation.  The
results imply that naive use of existing Java serialization technology
does not provide the performance needed for high performance message
passing environments.  Possible remedies for this situation are outlined
briefly in the final discussion section.

\subsection{Related work}

Early work by the current authors on Java MPI bindings is
reported in \cite{Experiments_HPJava}.  A comparable
approach to creating full Java MPI interfaces has been taken by Getov
and Mintchev \cite{Mintchev,Getov}.
A subset of MPI is implemented in the DOGMA system for Java-based
parallel programming \cite{DOGMA}.
MPI Software Technology, Inc have announced their intention to deliver
a commercial Java interface to MPI called JMPI \cite{JMPI}.
Java implementations of the related PVM message-passing environment
have been reported in \cite{Yalamanchilli} and \cite{JPVM}.
A pure Java implementation of MPI built on top of JPVM has been
described in \cite{Dincer}.

For an extensive discussion of performance issues surrounding
object serialization see section 3 of \cite{JGFreport} and references
therein.  The discussion there mainly relates to serialization in the
context of fast RMI implementations.  The cost of serialization is
likely to be an even more critical issue in MPI, because the
message-passing paradigm usually has lower overheads.

\section{Review of an API for derived datatypes and
Object datatypes\label{review}}

The MPI standard is explicitly object-based.  The C++ binding
specified in the MPI 2 standard collects these objects into suitable
class hierarchies and defines most of the library functions as class
member functions.  The Java API proposed in \cite{MPIposition}
follows this model, and lifts its class hierarchy directly from the C++
binding.  The major classes are illustrated in Figure
\ref{hierarchy}.

\begin{figure*}[t]
\centerline{\psfig{figure=mpiJava.eps,width=4.5in}}
\caption{Principal classes of MPI\label{hierarchy}}
\end{figure*}

The class MPI only has static members.  It acts as a module containing
global services, such as initialization of MPI, and many global
constants including the default communicator {\tt
COMM\_WORLD}\footnote{It has been pointed out that if multiple MPI
threads are allowed in the same Java VM, the default communicator
cannot be obtained from a static variable.  The final version of the
API may change this convention.}.  The communicator class {\tt Comm} is
the single most important class in MPI.  All communication functions
are members of {\tt Comm} or its subclasses.  Another class that is
relevant for the discussion below is the {\tt Datatype} class.  This
describes the type of the elements in the message buffers passed to
send, receive, and other communication functions.  Various basic
datatypes are predefined in the package.  These mainly correspond to
the primitive types of Java, shown in figure \ref{basic}.

\begin{figure}[bt]
\centerline{
\begin{tabular}{| l | l |} \hline
MPI datatype & Java datatype \\
\hline
MPI.BYTE     & {\tt byte} \\
MPI.CHAR     & {\tt char} \\
MPI.SHORT    & {\tt short} \\
MPI.BOOLEAN  & {\tt boolean} \\
MPI.INT      & {\tt int} \\
MPI.LONG     & {\tt long} \\
MPI.FLOAT    & {\tt float} \\
MPI.DOUBLE   & {\tt double} \\
MPI.OBJECT   & {\tt Object} \\
\hline
\end{tabular}
}
\caption{Basic datatypes in proposed Java binding\label{basic}}
\end{figure}

The standard send and receive operations of MPI are members of
{\tt Comm} with interfaces
\small
\begin{verbatim}
  void send(Object buf, int offset, int count,
            Datatype datatype, int dst, int tag)

  Status recv(Object buf, int offset, int count,
              Datatype datatype, int src, int tag)
\end{verbatim}
\normalsize
In both cases the {\em actual} argument corresponding to {\tt buf}
must be a Java array with element type determined by the {\tt datatype}
argument.  If the specified type corresponds to a primitive type,
the buffer will be a one-dimensional array.  Multidimensional arrays
can be communicated directly if an object type is specified, because
an individual array can be treated as an object.  Communication of
object types implies some form of serialization and unserialization.
This could be the built-in serialization provided in current Java
environments, or it could be some specialized serialization optimized for
MPI (or some combination of the two).

Buffer array arguments are followed by offsets that specify the element
in the array where the message actually starts.

Besides object types the draft Java binding proposal retains a model of
MPI derived datatypes.  In C or Fortran bindings of MPI, derived
datatypes have two roles.  One is to allow messages to contain mixed
types.  The other is to allow noncontiguous data to be transmitted.

The first role involves using the {\tt MPI\_TYPE\_\-STRUCT} derived
data constructor, which allows one to describe the physical layout of, say,
a C {\em struct} containing mixed types.  This will not work
in Java, because Java does not expose the low-level layout of its
objects.    In C or Fortran {\tt MPI\_TYPE\_\-STRUCT} also allows one
to incorporate displacements computed as differences between absolute
addresses, so that parts of a single message can come from separately declared
arrays and other variables.  Again there is no very natural way to do
this in Java.  Effects similar to of these uses of {\tt
MPI\_TYPE\_\-STR\-UCT} can be achieved by using {\tt
MPI.OBJECT} as the buffer type, and relying on object serialization.

We conclude that in the Java binding the first role of derived dataypes should
probably be abandoned---derived types can only include elements of a
single basic type.  This leaves description of noncontiguous buffers as
the essential role for derived data types.

Every derived data type constructable in the Java binding has a
uniquely defined {\em base type}.  This is one of the 9 basic types
enumerated above.  A {\em derived datatype} is an object that specifies
two things:  a base type and a sequence of integer displacements.  In
contrast to the C and Fortran bindings the displacements can be
interpreted in terms of subscripts in the buffer array argument, rather
than as byte displacements.

For example the type constructor {\tt indexed} is a member of
{\tt Datatype} with interface
\small
\begin{verbatim}
  Datatype indexed(int [] arrayOfBlocklengths,
                   int [] arrayOfDisplacements)
\end{verbatim}
\normalsize
This is a binding of the standard MPI operation {\tt MPI\_TYPE\_INDEXED}.
It constructs a new datatype representing replication of the original
datatype (to which the method is applied) into a sequence of blocks.
Each block can contain a
different number of copies and have a different displacement.
The base type of the new datatype will be the same as the base type of
the original type.  If the displacement sequence of the original type was
\begin{displaymath}
\{ \mbox{\em disp}_0, \ldots, \mbox{\em disp}_{n - 1} \}
\end{displaymath}
with extent\footnote{The {\em extent} of a dataype
is a measure of the distance between its smallest and largest
displacement.} {\em ex}, and {\tt B} is {\tt arrayOfBlocklengths}
argument and {\tt D} is {\tt arrayOfDisplacements} argument,
the new datatype will have displacement sequence
\begin{displaymath}
\{
\begin{array}[t]{l}
\mbox{\em disp}_0 + \mbox{\tt D}[0] \cdot \mbox{\em ex},
\ldots,
\mbox{\em disp}_{n - 1} + \mbox{\tt D}[0] \cdot \mbox{\em ex}, \\
\mbox{\em disp}_0 + (\mbox{\tt D}[0] + 1) \cdot \mbox{\em ex},
\ldots,
\mbox{\em disp}_{n - 1} + (\mbox{\tt D}[0] + 1) \cdot \mbox{\em ex}, \\
\ldots , \\
\mbox{\em disp}_0 +
   (\mbox{\tt D}[0] + \mbox{\tt B} [0] - 1) \cdot \mbox{\em ex},
\ldots, \\
\quad \quad \quad \quad \quad \mbox{\em disp}_{n - 1} +
   (\mbox{\tt D}[0] + \mbox{\tt B} [0] - 1) \cdot \mbox{\em ex}, \\
\\
\ldots , \\
\\
\mbox{\em disp}_0 + \mbox{\tt D}[c - 1] \cdot \mbox{\em ex},
\ldots,
\mbox{\em disp}_{n - 1} + \mbox{\tt D}[c - 1] \cdot \mbox{\em ex}, \\
\mbox{\em disp}_0 + (\mbox{\tt D}[c - 1] + 1) \cdot \mbox{\em ex},
\ldots, \\
\quad \quad \quad \quad \quad \mbox{\em disp}_{n - 1} +
   (\mbox{\tt D}[c - 1] + 1) \cdot \mbox{\em ex}, \\
\ldots , \\
\mbox{\em disp}_0 +
   (\mbox{\tt D}[c - 1] + \mbox{\tt B} [c - 1] - 1) \cdot \mbox{\em ex},
\ldots, \\
\quad \quad \quad \quad \quad \mbox{\em disp}_{n - 1} +
   (\mbox{\tt D}[c - 1] + \mbox{\tt B} [c - 1] - 1) \cdot \mbox{\em ex}
\,\, \}
\end{array}
\end{displaymath}
Here, {\em c} is the number of blocks.

In Java the derived dataype constructed by {\tt indexed} has a
potentially useful role.  It allows to send (or receive) messages
containing values scattered randomly in some one-dimensional array.  The
draft proposal incorporates versions of other type constructors from
MPI including {\tt MPI\_TYPE\_VECTOR} for strided sections.
We note, though, that the value of providing strided sections is reduced
because Java has no natural mapping between elements of its
multidimensional arrays and elements of equivalent one-dimensional
arrays.  This thwarts one common use of strided sections, for representing
portions of multidimensional arrays.

\section{Implementation issues for Object datatypes\label{implementation}}

As described in the previous section the proposal of \cite{MPIposition}
includes a restricted, Java-compatible version of the general datatype
mechanism of MPI.  The proposal retains much of the complexity of
the standard MPI mechanism, but its value is apparently reduced in
Java.  In this section we will discuss the other
option for representing complex data buffers in the Java
binding---introduction of an {\tt MPI.OBJECT} datatype.

It is natural to assume that the elements of arrays passed as buffer
arguments to {\tt send} and other output operations are objects
whose classes implement the {\tt Serializable} interface.
There are at least two ways one may consider communicating object types
in the MPI interface
\begin{enumerate} 
\item
Use the standard {\tt ObjectOutputStream} 
to convert the object buffers to byte vectors, and communicate
these byte vectors using the same method as for primitive
byte buffers (for example, this might involve a native method
call to C MPI functions).  At the destination, use the
standard {\tt ObjectInputStream} to rebuild the objects.
\item
Replace calls to the {\tt writeObject}, {\tt readObject} methods on the
standard streams with specialized functions that use platform specific
knowledge to communicate data fields more efficiently.  For example, one
might replace {\tt writeObject} with a native method
that creates an MPI derived datatype structure describing the
layout of data in the object, and passes this buffer descriptor to
a native {\tt MPI\_Send} function.
\end{enumerate} 
In the second case our implementation is responsible for prepending a
suitable type descriptor to the message, so that objects can be
reconstructed at the receiving end before the data fields are copied to
them.  This complexity is hidden in the first approach.

Evidently the first implementation scheme is more straightforward, and
only this approach will be considered in the rest of this section.  We
discuss an implementation based on the {\em mpiJava} wrappers,
combining standard JDK object serialization methods with a JNI
interface to native MPI.  Benchmark results presented in the next
section suggest, however, that something like the second approach (or
some suitable combination of the two) deserves serious consideration.

The original version of mpiJava was a direct Java wrapper for standard
MPI.  Apart from adopting an object-oriented framework, it added only a
modest amount of code to the underlying C implementation of MPI.
Derived datatype constructors, for example, simply called the datatype
constructors of the underlying implementation and returned a Java
object containing a representation of the C handle.  A {\tt send} operation or
a {\tt wait} operation, say, dispatched a single C MPI
call.  Even using standard JDK object serialization and a native
MPI package, uniform support for the {\tt MPI.OBECT} basic type
complicates the wrapper code significantly.

In the new version of the wrapper, every send, receive, or collective
communication operation tests if the base type of the datatype argument
describing a buffer is {\tt OBJECT}.  If not---if the buffer element
type is a primitive type---the native MPI operation is called directly,
as in the old version.  If the buffer is an array of objects, special
actions must be taken in the wrapper.  If the buffer is a send buffer,
the objects must be serialized.  To support MPI derived datatypes as
described in the previous section, we must also take account of the possibility
that the message is actually some subset of the of array of objects
passed in the buffer argument, selected according to the displacement
sequence of the derived datatype\footnote{To clarify: at this point we
are supporting {\em both} MPI derived datatypes (allowing
non-contiguous buffers) {\em and} objects as basic MPI types.
Uniformity requires support, in particular, of derived types whose
base type is {\tt Object}.  When only buffers of primitive type were
supported, the wrapper code never dealt with displacement sets in
derived types directly---they were handled inside the native MPI.  But of
course the native MPI cannot deal with derived types that have objects
as their basic components.}.  In the implementation, a method
\small
\begin{verbatim}
  byte [] Object_Serialize(Object   buf,
                           int      offset,
                           int      count,
                           Datatype type)
\end{verbatim}
\normalsize
takes the send buffer and descriptor, and returns a byte vector
containing the serialized data.  At the receiving end a corresponding
{\tt Object\_deserialize} method is called.
Making the Java wrapper responsible for handling derived data types
when the base type is {\tt OBJECT} requires additional state in the
Java-side {\tt Datatype} class.  In particular the Java object
explicitly maintains the displacement sequence as an array of
integers.

A further set of changes to the implementation arises because the size
of the serialized data is not known in advance, and cannot be computed
at the receiving end from type information available there.  Before
the serialized data is sent, the size of the data must be communicated
to the receiver, so that a byte receive buffer can be allocated.
We send two physical messages---a header containing size information,
followed by the data\footnote{In simple cases it would be possible to
use {\tt MPI\_PROBE} to find out the physical message size at the
receiving end before posting the receive, but this approach does not
work well for all non-blocking communication modes (or for collective
communication).}.
This, in turn, complicates the implementation of the various {\tt wait}
and {\tt test} methods on communication request objects, and the {\tt
start} methods on persistent communication requests.  A {\tt wait}
operation, for example, can no longer simply dispatch a native {\tt
MPI\_WAIT} call.  Instead it must check what kind of non-blocking
communication the request object was created for.  If it
was a receive operation involving objects, the {\tt wait} method makes
an {\tt MPI\_WAIT} call to wait for the header, followed by a blocking
{\tt MPI\_RECV} call to accept the data.  This implies the introduction
of extra state to the Java {\tt Request} class, storing the argument
list of the operation that created the request object.

Finally, comparable changes are needed in the collective communication
wrappers.  A {\tt gather} operation, for example, involving object
types is implemented as an {\tt MPI\_GATHER} operation to collect all
message lengths, followed by an {\tt MPI\_GATHERV} to collect possibly
different-sized data vectors.

\section{Benchmark results for multidimensional arrays\label{benchmarks}}

We assume that in the kind of {\em Grande} applications where MPI is
most likely to be used, some of the most pressing performance issues
about buffer description and object communication will concern arrays
and multidimensional arrays of small objects---most especially arrays
with primitive elements such as {\tt int}s and {\tt float}s.  For
initial benchmarks we concentrated on the overheads
introduced by object serialization when the objects contain many arrays
of primitive elements.  Specifically we concentrated on communication
of two-dimensional arrays with primitive elements.

The immediate goal, therefore, was to understand the overheads in
communicating multidimensional Java arrays using generic object
serialization technology.  The ``ping-pong'' method was used to time
point-to-point communication of an $N$ by $N$ array of primitive
elements treated as a one dimensional array of objects, and compare it
with communication of an $N^2$ array without using serialization.  As
an intermediate step we also timed communication of a $1$ by $N^2$
arrey treated as a one-dimensional (size 1) array of objects.
This allows us to extract an estimate of the overhead to ``serialize''
an individual primitive element.

The code to send the $N^2$ float vector, for example, looks schematically like
\small
\begin{verbatim}
  float [] buf = new float [N * N] ;
  MPI.COMM_WORLD.send(buf, 0, N * N, MPI.FLOAT,
                      dst, tag) ;
\end{verbatim}
\normalsize
and the code to receive it looks like
\small
\begin{verbatim}
  float [] buf = new float [N * N] ;
  MPI.COMM_WORLD.recv(buf, 0, N * N, MPI.FLOAT,
                      src, tag) ;
\end{verbatim}
\normalsize
For the $N \times N$ float arrays we have
\small
\begin{verbatim}
  float [] [] buf = new float [N] [N] ;
  MPI.COMM_WORLD.send(buf, 0, N, MPI.OBJECT,
                      dst, tag) ;
\end{verbatim}
\normalsize
and
\small
\begin{verbatim}
  float [] [] buf = new float [N] [] ;
  MPI.COMM_WORLD.recv(buf, 0, N, MPI.OBJECT,
                      src, tag) ;
\end{verbatim}
\normalsize
For the $1 \times N^2$ float arrays we have
\small
\begin{verbatim}
  float [] [] buf = new float [1] [N * N] ;
  MPI.COMM_WORLD.send(buf, 0, 1, MPI.OBJECT,
                      dst, tag) ;
\end{verbatim}
\normalsize
and
\small
\begin{verbatim}
  float [] [] buf = new float [1] [] ;
  MPI.COMM_WORLD.recv(buf, 0, 1, MPI.OBJECT,
                      src, tag) ;
\end{verbatim}
\normalsize
As a crude timing model for these benchmarks, one can assume that there
is a cost $t^{\mbox{\scriptsize T}}_{\mbox{\scriptsize ser}}$ to
serialize each primitive element of type {\tt T}, an additional cost
$t^{\mbox{\scriptsize vec}}_{\mbox{\scriptsize ser}}$ to serialize each
subarray, similar constants
$t^{\mbox{\scriptsize T}}_{\mbox{\scriptsize unser}}$ and
$t^{\mbox{\scriptsize vec}}_{\mbox{\scriptsize unser}}$ for
unserialization, and a cost
$t^{\mbox{\scriptsize T}}_{\mbox{\scriptsize com}}$ to 
physically tranfser each element of data.
Then the total time for benchmarked communications should be
\begin{eqnarray}
t^{\mbox{\small \tt T[$N^2$]}}     & = & c +
    t^{\mbox{\scriptsize T}}_{\mbox{\scriptsize com}} N^2 \label{eqn:mod1} \\
t^{\mbox{\small \tt T[1][$N^2$]}} & = & c' +
   (t^{\mbox{\scriptsize T}}_{\mbox{\scriptsize ser}} +
    t^{\mbox{\scriptsize T}}_{\mbox{\scriptsize com}} +
    t^{\mbox{\scriptsize T}}_{\mbox{\scriptsize unser}}) N^2
                                                        \label{eqn:mod2} \\
t^{\mbox{\small \tt T[$N$][$N$]}} & = & c'' +
   (t^{\mbox{\scriptsize vec}}_{\mbox{\scriptsize ser}} +
    t^{\mbox{\scriptsize vec}}_{\mbox{\scriptsize unser}}) N + \nonumber \\
&& (t^{\mbox{\scriptsize T}}_{\mbox{\scriptsize ser}} +
    t^{\mbox{\scriptsize T}}_{\mbox{\scriptsize com}} +
    t^{\mbox{\scriptsize T}}_{\mbox{\scriptsize unser}}) N^2
                                                        \label{eqn:mod3}
\end{eqnarray}
These formulae do not attempt to explain the constant initial overhead,
don't take into account the extra bytes for type description that
serialization introduces into the stream, and ignore possible
non-linear costs associated with analysing object graphs, etc.
Empirically these effects are small for the range of $N$ we consider.

All measurements were performed on a cluster of 2-processor, 200 Mhz
UltraSparc nodes connected through a SunATM-155/MMF network.  The
underlying MPI implementation was Sun MPI 3.0 (part of the Sun HPC
package).  The JDK was jdk1.2beta4.  Shared memory results quoted are
obtained by running two processes on the processors of a single node.
Non-shared-memory results are obtained by running peer processes in
different nodes.

In a series of measurements, element serialization and unserialization
timing parameters were estimated by independent benchmarks of the
serialization code.  The parameters $t^{\mbox{\scriptsize
vec}}_{\mbox{\scriptsize ser}}$ and $t^{\mbox{\scriptsize
vec}}_{\mbox{\scriptsize unser}}$ were estimated by plotting the
difference between serialization and unserialization times for {\tt
T[1][$N^2$]} and {\tt T[$N$][$N$]}.  The raw communication speed was
estimated from ping-pong results for $t^{\mbox{\small \tt T[$N^2$]}}$.
Table \ref{tab:params}
contains the resulting estimates of the various parameters for {\tt byte},
{\tt int} and {\tt float} elements.  

\begin{table}[tb]
\centerline{
\begin{tabular}{ r @{\hspace{0.1in}=\hspace{0.1in}} l @{\hspace{0.4in}}  r @{\hspace{0.1in}=\hspace{0.1in}} l }
$t^{\mbox{\scriptsize byte}}_{\mbox{\scriptsize ser}}$    & 0.043 &
$t^{\mbox{\scriptsize int}}_{\mbox{\scriptsize ser}}$     & 0.74 \\[0.07in]
$t^{\mbox{\scriptsize byte}}_{\mbox{\scriptsize unser}}$  & 0.027 &
$t^{\mbox{\scriptsize int}}_{\mbox{\scriptsize unser}}$   & 0.42 \\[0.07in]
$t^{\mbox{\scriptsize byte}}_{\mbox{\scriptsize com}}$    & $0.062^\dag$ &
$t^{\mbox{\scriptsize int}}_{\mbox{\scriptsize com}}$     & $0.25^\dag$ \\[0.07in]
$t^{\mbox{\scriptsize byte}}_{\mbox{\scriptsize com}}$    & $0.008^\S$ &
$t^{\mbox{\scriptsize int}}_{\mbox{\scriptsize com}}$     & $0.038^\S$ \\[0.25in]
$t^{\mbox{\scriptsize float}}_{\mbox{\scriptsize ser}}$   & 2.1 &
$t^{\mbox{\scriptsize vec}}_{\mbox{\scriptsize ser}}$     & 100 \\[0.07in]
$t^{\mbox{\scriptsize float}}_{\mbox{\scriptsize unser}}$ & 1.4 &
$t^{\mbox{\scriptsize vec}}_{\mbox{\scriptsize unser}}$   & 53 \\[0.07in]
$t^{\mbox{\scriptsize float}}_{\mbox{\scriptsize com}}$   & $0.25^\dag$ \\[0.07in]
$t^{\mbox{\scriptsize float}}_{\mbox{\scriptsize com}}$   & $0.038^\S$ \\[0.07in]
\end{tabular}
}

\caption{Estimated parameters in serialization and communication timing
model.  The $t^{\mbox{\scriptsize T}}_{\mbox{\scriptsize com}}$ values
are respectively for non-shared memory ($\dag$) and shared memory ($\S$)
implementations of the underlying communication.  All timings are in
microseconds.\label{tab:params}}
\end{table}

Figures \ref{fig:nonshmem} to \ref{fig:shmem} plot actual measured
times from ping-pong benchmarks for the mpiJava sends and receives of
arrays with {\tt byte}, {\tt int} and {\tt float} elements.  In the
plots the array extent, $N$, ranges between 128 and 1024.  The measured
times for $t^{\mbox{\small \tt T[$N^2$]}}$, $t^{\mbox{\small \tt
T[1][$N^2$]}}$ and $t^{\mbox{\small \tt T[$N$][$N$]}}$ are compared
with the formulae given above (setting the $c$ constants to zero).  The
agreement is good, so our parametrization is assumed to be realistic in
the regime considered.

\begin{figure*}[p]
\centerline{\psfig{figure=nonsh_byte.eps,width=3in}}
\centerline{\psfig{figure=nonsh_int.eps,width=3in}}
\centerline{\psfig{figure=nonsh_float.eps,width=3in}}
\caption{Communication times from Pingpong benchmark in non-shared-memory
case, compared with model defined by Equations \ref{eqn:mod1} to
\ref{eqn:mod3} and Table \ref{tab:params}.\label{fig:nonshmem}}
\end{figure*}

\begin{figure*}[p]
\centerline{\psfig{figure=sh_byte.eps,width=3in}}
\centerline{\psfig{figure=sh_int.eps,width=3in}}
\centerline{\psfig{figure=sh_float.eps,width=3in}}
\caption{Communication times in shared-memory case, compared with model.
\label{fig:shmem}}
\end{figure*}


According to table \ref{tab:params} the overhead of Java serialization
nearly always dominates other communiation costs.  In the worst
case---floating point numbers---it takes around 2 microseconds to
serialize each number and a smaller but comparable time to
unserialize.  But it only takes a few {\em hundredths} of a microsecond to
communicate the word through shared memory.  Serialization slows
communication by nearly two orders of magnitude!  When the underlying
communication is over a fast network rather than through shared memory
the raw communication time is still only a fraction of a microsecond,
and serialization still dominates that time by about one order of
magnitude.  For {\tt byte} elements serialization costs are smaller,
but still larger than the communication costs in the fast network
and still much larger than the communication cost through shared
memory.  Serialization costs for {\tt int} elements are intermediate.

The constant overheads for serializing each subarray, characterized by
the parameters $t^{\mbox{\scriptsize vec}}_{\mbox{\scriptsize ser}}$
and $t^{\mbox{\scriptsize vec}}_{\mbox{\scriptsize unser}}$ are also
quite large, although, for the array sizes considered here they only
make a dominant contribution for the {\tt byte} arrays, where
individual element serialization is relatively fast\footnote{Our timing
model assumed the values of these parameters is independent of the
element type.  This is only approximately true, and the values quoted in
the table and used in the plotted curves are averages.
Separately measured values for {\tt byte} arrays were smaller than
these averages, and for {\tt int} and {\tt float} arrays they were
larger.}.

\section{Discussion}

In Java, the object serialization model for data marshalling has various
advantages over the MPI derived type mechanism.  It provides much
(though not all) of the flexibility of derived types, and is presumably
simpler to use.  Object serialization provides a natural way to
deal with multidimensional arrays.  Such arrays are, of
course, very common in scientific programming.  
The Java mapping of derived datatypes, on the other hand, is
problematic---a significant part of the flexibility in the original
C/Fortran specification is lost in the transcription to Java.  It is at
least arguable that in Java the MPI derived datatypes mechanism should
be abandoned altogether in favour of using object serialization.

Our initial implementation of automatic object serialization in the
context of MPI is somewhat impaired by performance of the serialization
code in the current Java Development Kit.  In our implementation
buffers were serialized using standard technology from the JDK.  The
benchmark results from section \ref{benchmarks} show that this
implementation of serialization introduces very large overheads
relative to underlying communication speeds on fast networks and
symmetric multiprocessors.  Similar problems were reported in the
context of RMI implementations in \cite{JGFreport}.  We find that in
the context of fast message-passing environments (not surprisingly) the
issue is even more critical.  Overall communication performance can
easily be downgraded by an order of magnitude or more.

The standard Java serialization framework allows the programmer to
provide optimized serialization and unserialization methods for
particular classes, but in scientific programming we are often more
concerned with the speed of operations on arrays, and especially arrays
of primitive types.  The documented parts of the standard Java
framework for serialization do not to our knowledge allow a way to
customize handling of arrays.  However the available source code for
{\tt ObjectOutputStream} and {\tt ObjectInputStream} classes includes
the methods for serializing arrays, and we are optimistic that by
tuning these classes it should be possible to greatly improve
performance for cases that concern us here.  In any case the message is
clear: we need much faster implementations of object serialization,
better attuned to the needs of scientific computation.  Especially,
arrays of primitive elements need to be handled much more carefully.

While we expect that there is considerable scope to optimize the JDK
serialization software, an interesting alternative from the point of
view of ultimate efficiency is to replace calls to the {\tt
writeObject}, {\tt readObject} methods with specialized, MPI-specific,
functions.  A call to {\tt writeObject}, for example, could be replaced
with a native method that creates an MPI derived datatype structure
describing the layout of data in the object.  This would allow one to
provide the conceptually straightforward object serialization model at
the user level, while retaining the option of fast, ``zero-copy''
communication strategies (enabled by MPI derived datatypes) inside the
implementation.

We are investigating the practicality of both these approaches to
optimization.

\bibliographystyle{latex8}
\bibliography{Java}

\end{document}

