\documentstyle[11pt,epsf]{article}
\setlength{\topmargin}{-0.5in}
\setlength{\oddsidemargin}{.3in}
\setlength{\evensidemargin}{.3in}
\setlength{\headheight}{.25in}
\setlength{\headsep}{.5in}
\setlength{\footheight}{.75in}
\setlength{\footskip}{0.75in}
\setlength{\textheight}{8in}
\setlength{\textwidth}{6.25in}
\setlength{\marginparwidth}{0in}
\setlength{\marginparsep}{0in}
\setlength{\marginparpush}{0in}

\parskip=5.0pt plus 1.0pt

\pagenumbering{arabic}

\renewcommand{\baselinestretch}{1.3}
\renewcommand{\topfraction}{.9}
\renewcommand{\bottomfraction}{.9}
\renewcommand{\textfraction}{0.1}
\renewcommand{\floatpagefraction}{.9}

\begin{document}
\input{psfig}
\date{}

\title{JPVM: Network Parallel Computing in Java}

\author{ Adam Ferrari \\
Department of Computer Science \\
University of Virginia, Charlottesville, VA 22903, USA\\
ferrari@virginia.edu\\
}

\maketitle

\begin{abstract}
     The JPVM library is a software system for explicit
message-passing based parallel programming in Java. The library
supports an interface similar to the C and Fortran interface of the
Parallel Virtual Machine (PVM) system, with modifications to better
suit Java programming styles. The similarity between JPVM and the
widely used PVM system supports a quick learning curve for experienced
PVM programmers. At the same time, JPVM offers novel features not
found in standard PVM such as thread safety, multiple communication
end-points per task, and default-case direct message routing. JPVM is
implemented entirely in Java, and is thus highly portable among
platforms supporting a version of the Java Virtual Machine. This feature
opens up the possibility of utilizing resources such as Macintosh and
Windows based workstations, which are commonly excluded from network
parallel computing systems. Initial applications performance results
achieved with a prototype JPVM system indicate that the Java-implemented
approach can offer good performance at appropriately coarse
granularities.


\end{abstract}

\section{Introduction} \label{Introduction}
     The use of networks of heterogeneous computing systems
interconnected as a single logical computational resource has become
a widespread approach to high-performance computing. Network parallel
computing systems allow individual applications to harness the
aggregate power of increasingly powerful, well-networked,
heterogeneous, and often largely under-utilized collections of
resources available to many users~\cite{now}. Results obtained with network
parallel computing systems have been encouraging~\cite{nas}, but the
utilization of distributed, heterogeneous, shared resources
connected by commodity networks as a single, virtual parallel computer
poses serious problems for both the application and system
software programmer. For example, from the application perspective, it
has been found that successful network parallel programs will almost
always exhibit medium to coarse granularity and will be tolerant of
network latency, but these attributes can be difficult to achieve in
some applications. From the system implementation perspective,
heterogeneity results in difficult problems such as task to platform
matching and system portability.

     The Java language provides a number of features that appear to be
promising tools for addressing some of the inherent problems
associated with network parallel programming. For example, from the
application perspective, Java provides a portable, uniform interface
to threads. Using threads instead of traditional heavy-weight
processes has been found to be an avenue for increasing latency
tolerance and allowing finer-grained computations to achieve good
performance in distributed memory parallel processing
environments~\cite{tpvm}.
From the system implementation perspective, Java supports a high
degree of code portability and a uniform API for operating system
services such as network communications.

     The JPVM (Java Parallel Virtual Machine) library~\cite{jpvm} is a
software system for explicit message-passing based distributed memory
MIMD parallel programming in Java. The library supports an interface
similar to the C and Fortran interfaces provided by the Parallel
Virtual Machine (PVM) system~\cite{pvm}, but with syntax and semantics
enhancements afforded by Java and better matched to Java programming
styles. The similarity between JPVM and the widely used PVM system
supports a quick learning curve for experienced PVM programmers,
thus making the JPVM system an accessible, low-investment target for
migrating parallel applications to the Java platform. At the same
time, JPVM offers novel features not found in standard PVM such as
thread safety, multiple communication end-points per task, and
default-case direct message routing. JPVM is implemented entirely in
Java, and is thus highly portable among platforms supporting some
version of the Java Virtual Machine. This feature opens up the
possibility of utilizing resources such as Macintosh and Windows
based workstations, which are commonly excluded from network
parallel computing systems.

\section{Programming Interface} \label{ProgrammingInterface}
     The programming interface provided by the JPVM system is
intentionally similar to that supported by PVM, with the addition of
enhancements to better exploit the potential benefits of Java as a
language for network parallel programming. As in PVM, the programmer
decomposes the problem to be solved into a set of cooperating
sequential task implementations. These sequential tasks execute on a
collection of available processors and invoke special library
routines to control the creation of additional tasks and to pass
messages among tasks. In JPVM, task implementations are coded in Java
(as applications with a static public {\tt main()} method), and support for
task creation and message passing is provided by a library of JPVM
Java classes.

%     The interface through which most JPVM interaction takes place is
     The most basic JPVM interface is
exported by the {\tt jpvmEnvironment} class (see Figure~\ref{figure-one}),
instances of which are declared by JPVM tasks to connect to
and interact with the JPVM system and other tasks.
Objects of this class represent
communications end-points within the system, and are identified by
system-wide unique identifiers of the opaque type {\tt jpvmTaskId}
(analogous to a PVM task identifier). JPVM allows tasks to maintain
a logically unlimited number of communication connections simply by
allocating multiple instances of {\tt jpvmEnvironment}. This feature
simplifies the process of developing separate linkable modules that
need to perform communication.

\begin{figure}[htbp]
\renewcommand{\baselinestretch}{1}
\begin{small}
\begin{verbatim}
    class jpvmEnvironment {
    // Constructor registers task with the JPVM system
        public jpvmEnvironment();

        public void pvm_exit();
        public jpvmTaskId pvm_mytid();
        public jpvmTaskId pvm_parent();

    // Task creation:
        public int pvm_spawn(String task_name, int num, jpvmTaskId tids[]);

    // Send messages:
        public void pvm_send(jpvmBuffer buf, jpvmTaskId tid, int tag);
        public void pvm_mcast(jpvmBuffer buf, jpvmTaskId tids[], int ntids, int tag);

    // Receive messages, blocking (non-blocking versions not depicted):
        public jpvmMessage pvm_recv(jpvmTaskId tid, int tag);
        public jpvmMessage pvm_recv(jpvmTaskId tid);
        public jpvmMessage pvm_recv(int tag);
        public jpvmMessage pvm_recv();
    };
\end{verbatim}
\end{small}
\caption{Excerpt from the {\tt jpvmEnvironment} interface.\label{figure-one}}
\end{figure}


     Task creation in JPVM is supported by the {\tt pvm\_spawn()} method,
which takes a string parameter indicating the name of a valid Java
class visible in the {\tt CLASSPATH} environment variable, as well as the
number of tasks to spawn. Each task created through {\tt pvm\_spawn()}
executes in its own instance of the Java Virtual Machine, avoiding
issues such as conflicting usage of system services among tasks. These
newly created instances of the Java Virtual Machine are placed
throughout the set of processors available to JPVM, and each runs an
object of the specified Java class.

     Message passing in JPVM is performed using the {\tt pvm\_send()} and
{\tt pvm\_recv()} methods of the {\tt jpvmEnvironment} class. Before
data can be
sent, it must be collected into a {\tt jpvmBuffer} object. Analogous to
PVM buffers, {\tt jpvmBuffer} objects are the message content containers
of JPVM. The {\tt jpvmBuffer} interface (see~\ref{figure-two})
contains two basic
groups of methods: those to pack data into a buffer, and those to
extract data from a buffer. Where possible, overloading is used in the
interface to simplify application code. Scalar and vector pack and
unpack operations are provided for all basic Java types as well as
{\tt String} and {\tt jpvmTaskId} objects.
The JPVM buffer interface differs from
standard PVM in its use of explicit buffer objects (as compared to the
use of implicit send and receive buffers in PVM). This design is an
example of JPVM's changes to the standard PVM interface to better
support multithreaded programming.

\begin{figure}[htbp]
\renewcommand{\baselinestretch}{1}
\begin{small}
\begin{verbatim}
    class jpvmBuffer {
        public jpvmBuffer();
        public void  pack(float v[], int n, int stride);
        public void  pack(float s);
        public void  unpack(float v[], int n, int stride);
        public float upkfloat();

        // ...Analogous functions for other data types
    };
\end{verbatim}
\end{small}
\caption{Excerpt from the {\tt jpvmBuffer} interface.\label{figure-two}}
\end{figure}


     After the contents of a message have been marshaled into a
{\tt jpvmBuffer} object, the buffer can be sent to any task in the JPVM
system using the asynchronous {\tt pvm\_send()}
method of the {\tt jpvmEnvironment}
class. Parameters to {\tt pvm\_send()} specify the buffer to be sent, the
identity of the task to which to the message should be delivered,
and an integer identification number for the message (called the
message tag).

     To receive messages, tasks call the {\tt pvm\_recv()} method of the
{\tt jpvmEnvironment} class. Using the various versions of {\tt pvm\_recv()},
tasks can request messages based on the identity of the message sender, the
identification number (tag) of the message, both of these, or neither
(i.e. receive any message). Receive operations block until a message
of the requested type is available, at which point a {\tt jpvmMessage}
structure is returned containing the received message (non-blocking
versions are also supported, but are not depicted in Figure~\ref{figure-one}).
Besides containing a {\tt jpvmBuffer} with the message contents, a received
{\tt jpvmMessage} object contains the identity of the sender of the message
as well as the message tag.

\section{Implementation} \label{Implementation}
     Although current execution environments for Java limit
performance significantly, the use of Java as a system
implementation language provides a number of distinct advantages,
foremost amongst which is the ability to employ services such as
threads and sockets through a portable interface across a wide range
of platforms. In this section we describe the key features of our
entirely Java-based JPVM implementation.

     The JPVM message passing implementation is based on communication
over TCP sockets. The use of direct task-to-task TCP connections has
been found to significantly outperform the older UDP-based daemon-routed
message passing implementation in PVM~\cite{nas}. Each {\tt jpvmEnvironment}
instance creates a server socket during initialization and embeds the
host name and port number needed to connect to it within its
{\tt jpvmTaskId} identity. Internally, JPVM uses threads to manage
connections and message delivery. Each {\tt jpvmEnvironment} creates a
dedicated thread to listen for and accept peer connections, as
depicted in Figure~\ref{figure-three}.
When a connection is accepted by this special
dedicated connection management thread, it creates a new message
receiver thread dedicated to the new connection. As the receiver
thread receives messages, it enqueues them on an internal message
queue (illustrated in Figure~\ref{figure-three}).
Thus, when user threads perform
{\tt pvm\_recv()} operations, instead of performing any network input
directly, they simply consult the internal message queue. An important
attribute of the JPVM communications system implementation is thread
safety. As depicted in Figure~\ref{figure-three}, multiple user threads can
concurrently perform {\tt pvm\_recv()} operations--the internal message
queue structure is a synchronized data type that may safely be
manipulated by any number of reader (user) and writer (internal
receiver) threads. The {\tt pvm\_send()} operations are also
synchronized to support thread safety.

\begin{figure}[htbp]
\centerline{\epsfysize=3.0in\epsfbox{fig3.eps}}
\caption{JPVM message-passing implementation.\label{figure-three}}
\end{figure}


     The ability to spawn new tasks, to determine and extend system
configuration, and to determine which tasks are executing in the
system is based on services provided by a set of JPVM daemon processes
executing on each host in the system. The current daemon
implementation is layered on the standard JPVM communication
mechanism--i.e. the implementation simply comprises a normal JPVM
program using the interface described in Section~\ref{ProgrammingInterface}.
The daemon employs
a server style organization, repeatedly blocking for and servicing new
requests. For most client requests (e.g. task status, system
configuration information) the daemon can respond immediately.
However, for task creation requests the daemon creates a thread to
start the new local process avoiding slow response to other client
requests while tasks are being created. The ability to use multithreading
in the design of responsive server processes is one example of the
value of JPVM's thread-safe interface.

\section{Performance} \label{Performance}
     To evaluate the performance of the current JPVM implementation we
conducted a set of experiments to quantify the costs of the basic
library primitives and to measure actual application performance. The
testbed used for these experiments was a set of five dual-processor
Pentium Pro hosts connected by 100 megabit ethernet. Each host in the
system contained two 200 MHz Pentium Pro processors and 128 MB of
memory, and was running Linux 2.0. The version of Java used was the
Linux JDK version 1.1.3 \cite{jdk}.

     In Figure~\ref{table-one} we present the time to create various
numbers of tasks on a single host system and in the full five host system.
Since each host is a dual processor machine, the difference in time to
create one or two hosts is negligible. The cost for task creation is not
small--when creating more than one task, approximately 0.5 seconds per
task in the single host system, and between 0.5 and 1.5 seconds per
task in the multi-host system are required. Spawn is somewhat less
expensive for small numbers of tasks in the single host system because
less communication is required. For larger numbers of tasks the
multi-host system begins to perform better as it can amortize
communications costs by parallelizing the creation of a set of tasks.
In all cases, the high cost of task creation is primarily due to the
time required to start and initialize a new instance of the JVM to host
the task object.

\begin{figure}[htbp]
\begin{center}
\begin{tabular}{||c|r|r||} \hline
Tasks & 1 Host & 5 Hosts \\ \hline \hline
1     &  886   & 2437    \\ \hline
2     &  1075  & 2509    \\ \hline
4     &  2092  & 2574    \\ \hline
8     & 4042   & 3683    \\ \hline
16    & 7938   & 6156    \\ \hline
\end{tabular}
\caption{Task creation time, milliseconds.\label{table-one}}
\end{center}
\end{figure}
     In Figure~\ref{table-two} we present round-trip message times between
two tasks for a range of message sizes. We performed these measurements
on messages containing integers and raw bytes to examine the overhead
associated with the requirement of masking byte ordering differences.
As might be expected, the message passing overheads introduced by the Java
implemented JPVM system are somewhat high--approximately two orders of
magnitude of latency are added to small messages as compared to the 
round-trip time reported by the Unix {\tt ping} utility. Bandwidth is
not as badly affected; for large messages, we achieve approximately
half of the bandwidth measured for native-code processes using the
raw Unix TCP sockets interface for communication.

\begin{figure}[htbp]
\begin{center}
\begin{tabular}{||c|r|r||} \hline
       & Integer & Byte   \\ \hline \hline
4 B    & 32.3    & 30.3   \\ \hline
1 KB   & 55.8    & 52.9   \\ \hline
10 KB  & 68.0    & 62.4   \\ \hline
100 KB & 325.5   & 309.4  \\ \hline
1 MB   & 2940.2  & 2386.9 \\ \hline
\end{tabular}
\caption{Round-trip message-passing time, milliseconds.\label{table-two}}
\end{center}
\end{figure}

     Given the relatively high costs associated with the basic JPVM
primitives, it is tempting to conclude that the overhead introduced by the
strategy of using a Java-implemented system as runtime support for
parallel Java applications outweighs the potential benefits. In fact,
the high costs of these operations does essentially rule out JPVM as a
platform for network-intensive applications, or programs with a high
dynamic task-creation rate. However, for
applications that exhibit medium to coarse granularities,  and also
exhibit some tolerance of network latencies, JPVM may provide
sufficiently efficient services to allow good speedup. To verify
this claim, we measured the performance of a parallel matrix
multiplication algorithm implemented in JPVM and compared to a
sequential version of the program also implemented in Java.
In Figure~\ref{table-three}
we present the results of these experiments for three problem sizes.
Times are presented for both the complete program (including task
creation time), and for the multiplication algorithm alone (excluding
task creation time).

\begin{figure}[htbp]
\begin{center}
\begin{tabular}{||c|c|c|c|c|c||} \hline
Problem&  Tasks &  Multiply & Speedup & Total & Speedup \\
Size   &        &  Time     &         & Time  &         \\ \hline \hline
  128  &   1    &   3.2     &   N/A   & 3.2   &   N/A   \\ \hline
  128  &   4    &   2.2     &   1.4   & 6.6   &   0.5   \\ \hline
  128  &   9    &   1.1     &   2.1   & 6.7   &   0.5   \\ \hline \hline
  256  &   1    &   26.7    &   N/A   & 26.7  &   N/A   \\ \hline
  256  &   4    &   7.7     &   3.5   & 10.3  &   2.6   \\ \hline
  256  &   9    &   4.6     &   5.9   & 8.9   &   3.0   \\ \hline \hline
  512  &   1    &   223.3   &   N/A   & 223.3 &   N/A   \\ \hline
  512  &   4    &   59.7    &   3.7   & 64.3  &   3.5   \\ \hline
  512  &   9    &   28.9    &   7.7   & 33.5  &   6.7   \\ \hline \hline
\end{tabular}
\caption{Matrix multiply performance, times in seconds.\label{table-three}}
\end{center}
\end{figure}

As might be expected, at the smallest problem
size, poor speedup is achieved for the multiplication algorithm, and
slowdown is observed for the program as a whole. This problem size is
simply too fine grained given the basic costs associated with JPVM. At
the middle problem size we find that the multiplication algorithm
begins to speed up well, but the program as a whole has poor
efficiency due to the high cost of task creation. Finally, at the
largest problem size, both the multiplication algorithm and the
program as a whole speed up well. As expected, better speedups are
achieved for the program when task creation costs are excluded.
Although this may seem like an unfair comparison, it demonstrates that
for long-running JPVM programs that can amortize task creation costs,
good efficiency is possible for the compute/communicate phases of the
program.

\section{Related Work} \label{RelatedWork}
     A number of other systems have been developed to support network
parallel programming in Java. One common approach to this problem is
the use of volunteer-based systems such as Bayanihan~\cite{bayanihan}
and Javelin~\cite{javelin}.
As opposed to JPVM which is based on stand-alone Java
applications, these systems are based on the decomposition of
programs into applets that are downloaded by volunteer clients,
execute within the context of a web browser, and solve some
sub-portion of a larger problem. These approaches are attractive in
that they can potentially employ the vast array of processing power
available in the form of client machines connected to the web. The
primary drawback of these approaches is the significant restriction
placed on communications by the Java security model for applets, which
rules out many potentially successful network parallel applications.

     A system similar to JPVM in its programming interface and model
is the JavaPVM library~\cite{javapvm}. This system also provides a PVM-like
interface for Java applications. The primary difference between
JavaPVM and JPVM is in implementation. Unlike JPVM which is
implemented entirely in Java, JavaPVM is based on the Java Native
Methods mechanism, providing native method wrappers around the
existing standard PVM routines. Whereas this approach has advantages
in terms of performance (at least in the short term) and interoperability,
by using native methods, this system is restricted in its
portability--JavaPVM can be used only on platforms where standard PVM
is available. Furthermore, in being a simple wrapper around the
standard PVM implementation, JavaPVM is limited by the semantic and
syntactic features of PVM. For example, JavaPVM programs retain the
less thread-friendly buffer interface provided by PVM.

     Another software package for network parallel computing in Java
is the IceT system~\cite{icet}. This system addresses a number of concerns not
covered by the JPVM design. Whereas JPVM allows a single user to combine
resources on which that user has access privileges, IceT is an
inherently collaborative, multi-user environment. IceT provides
mechanisms by which resources can be made available to the system for
use by users who do not have log-on privileges. The attractive goals
of this metacomputing-based approach include better utilization of
larger resource bases, as well as an enhanced collaborative
environment for high performance computing. Among the challenges
introduced by this idea are the numerous security issues introduced by
code-upload capabilities for non-privileged uses.

\section{Conclusions} \label{Conclusions}
     We have described the JPVM system, both in terms of programming
model and interface, interactive interface, and implementation. This
system combines the goals of supporting network parallel programming
in Java, providing a familiar and proven-effective programming
interface, and taking advantage of the attractive features of Java as
a system implementation language. The combination of Java as an
applications programming language and system implementation
languages allows the support of a number of powerful features in JPVM,
including thread safety and multiple communication end-points per
process. Initial performance experiments with the system indicate
that the costs associated with the basic JPVM primitives are quite
high, but this is not unexpected given the use of Java for system
implementation. However, we have found that the system can support
good speedup for applications that exhibit an appropriately coarse
level of granularity, tolerance of network latency, and ability to
amortize task creation costs. Furthermore, these are issues already
well known to applications programmers who employ network parallel
programming. Given this observation, we argue that the added costs
associated with a Java-based system do not outweigh the benefits of
the added features, portability, and programming flexibility
afforded by Java.

\begin{thebibliography}{1}

\bibitem{now} T.E. Anderson, D.E. Culler, D.A. Patterson, and the NOW team,
``A Case for NOW (networks of Workstations),''
{\it IEEE Micro}, vol. 15, no. 1, pp. 54-64, February, 1995.

\bibitem{jdk} S. Byrne, Linux JDK, available from: 
{\tt http://www.java-linux.org/}

\bibitem{javelin} P. Cappello, B.O. Christiansen, M.F. Ionescu, M.O. Neary,
K.E. Schauser, and D. Wu,
``Javelin: Internet-based Parallel Computing Using Java,''
{\it ACM Workshop on Java for Science and Engineering Computation},
June, 1997.

\bibitem{jpvm} A.J. Ferrari, JPVM, available from:
{\tt http://www.cs.virginia.edu/jpvm}

\bibitem{tpvm} A.J. Ferrari and V.S. Sunderam, ``Multiparadigm Distributed
Computing with TPVM,'' {\it Journal of Concurrency, Practice and Experience},
(to appear).

\bibitem{pvm} A. Geist, A Beguelin, J. Dongarra, W. Jiang, R. Manchek, and
V.S. Sunderam, {\it PVM: Parallel Virtual Machine}, MIT Press, 1994.

\bibitem{icet} P.A. Gray and V.S. Sunderam, ``IceT: Distributed Computing and
Java,'' available from:
{\tt http://www.mathcs.emory.edu/~gray/abstract7.html}

\bibitem{bayanihan} L.F.G. Sarmenta, ``Bayanihan: Web-Based Volunteer Computing
Using Java,'' available from:
{\tt http://www.cag.lcs.mit.edu/bayanihan/}

\bibitem{javapvm} D. Thurman, JavaPVM, available from:
{\tt http://www.isye.gatech.edu/chmsr/JavaPVM/}

\bibitem{nas} S. White, A. Alund, and V.S. Sunderam, ``Performance of the NAS
Parallel Benchmarks on PVM Based Networks,''
{\it Journal of Parallel and Distributed Computing},
vol. 26, no. 1, pp. 61-71, April 1995.


\end{thebibliography}
\end{document}
