\section{Introduction}
\label{sec-intro}

The Internet has been described  as a potential source for an
immense computational capacity. A vast number of often idle machines
are connected and provide---in principle---enormous resources to
tackle large problems. But distributed computing in the Internet is
faced with a number of challenges that have prevented this vision from
realization so far. Among these obstacles are heterogeneity, security
concerns, the need to install programs on remote computers, high
communication latencies, and the inherent unreliability of remote
machines and the Internet itself.

The Java programming language successfully addresses the
heterogeneity and security concerns and removes the need to install
programs remotely other than standard execution environments
(typically, a Java-enabled browser). This makes Java a prime choice
for building environments to execute parallel programs distributed
over the Internet or, more precisely, the World Wide Web.

A number of research efforts use Java to build such an environment. Some
of them use message-passing interfaces, others provide Distributed
Shared Memory (DSM) semantics (cp.~Section~\ref{sec-relwork} for
details). 
\emph{Charlotte} \cite{Bar:Charlotte} is such a DSM system---it
uses a reliable parallel machine as programming model and the runtime
system implements this model on top of unreliable machines.  Charlotte
provides an object-based shared memory for objects of certain
distributed classes.  Main advantages of Charlotte are easy
programmability, fault tolerance with regard to crash faults of
workers, and adaptive parallelism that makes use  of slow
machines. Fault tolerance in particular can be regarded as
indispensable for a parallel system using the World Wide
Web. Additionally, Charlotte is completely implemented in Pure Java
and runs on standard Java virtual machines.

But compared to simpler message-passing systems, Charlotte pays a high
overhead for maintaining correct memory semantics.  In a
message-passing system on the other hand, this overhead is avoided by
having the  programmer  provide
precise information which data is transferred where and when---which
is automated by a DSM system. Additionally, it is a difficult task for
a programmer to provide Charlotte-like capabilities using only
message-passing primitives. A programmer finds himself thus faced with
the difficult choice between easy programmability and automatic fault
tolerance provided by a DSM system like Charlotte and high performance
obtainable by using simpler message-passing abstractions. Therefore,
a solution is needed that maintains Charlotte's advantages for the
programmer and improves its efficiency to be competitive with
message-passing systems; of course, such a solution should be
implemented in Pure Java as well.  The need for such a solution is
particularly felt in a Web-based environment using Java: high
latencies and the unavailability of hardware support for detecting
memory access make low-overhead solutions necessary, the complexity of
Web-based network computing calls for higher, fault-tolerant
programming models.


This paper presents an annotation-based solution that bridges the gap
between Charlotte's DSM semantics and message-passing systems by
allowing stepwise refinements of Charlotte programs. In a first step,
a Charlotte-program can be enhanced with annotations that describe the
data requirements of routines (Charlotte's unit of parallel
execution). The runtime system can use this information to improve the
communication efficiency; the standard Charlotte distributed classes
guarantee the correctness of the computation even if the annotations
are wrong. In a second step, after the annotations' correctness has
been established, efficiency can be further improved by removing the
consistency checks for shared data. In a third step, primitive data
types can be used as a basis for sharing, additionally foregoing the
overhead of accessing objects. This combines efficient
communication and direct data access with Charlotte's advantages
without the programmer having to worry about low-level communication
issues. This gradual incorporation of semantic knowledge closes the
gap between the programmability advantages of DSM and the
communication efficiency of message-passing programs. Additionally, it
is also conceivable to generate annotations automatically be means of
a data flow analysis within a compiler.

The next section presents related work. Section~\ref{sec-system}
introduces the annotation-based extensions for Charlotte and
Section~\ref{sec-measure} gives experimental results for the various
extensions---both sections use matrix multiplication as a common
example. Section~\ref{sec-future} discusses possible extensions of this
work and Section~\ref{sec-concl} gives some conclusions. 

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "frame"
%%% End: 
