\section{The Bridge}
\label{sec-system}

This section describes the original Charlotte system and 
extensions to it that constitute a possible bridge between Charlotte's DSM
semantics and  message-passing semantics.
 
\subsection{Standard Charlotte} 
\label{ssec-standard}

A Charlotte program consists of alternating sequential and parallel
steps. A manager application (running as a stand-alone process)
executes the sequential steps and administers the parallel steps. In
such a parallel step (delimited by {\tt parBegin()} and {\tt
parEnd()}), a number of \emph{routines} are defined and picked up by
any number of workers (which are applets running in a browser). The
end of a parallel step is a barrier synchronization for all the
routines in this step. The current Charlotte implementation does not
allow nested parallel steps. The memory is logically partitioned
in private (local to a routine) and shared segments.  The shared
memory has \emph{concurrent read, exclusive write}
semantics.\footnote{\emph{Concurrent read, concurrent write} semantics
is possible with somewhat higher overhead in the manager.} Charlotte
deliberately chooses this conservative semantics to make the
programming model as simple as possible.

The shared memory is implemented at the data type level. For a Java
primitive type like, e.g., {\tt int}, there is a corresponding
Charlotte class {\tt Dint} (distributed int) that provides the correct
distributed semantics. The actual data access happens via member
functions {\tt get()} and {\tt set()}, since Java does not allow
implicit type conversion.  If, upon a read-access, a data item is
detected to be invalid at a worker,\footnote{Workers have no valid
  data at the beginning of a parallel step.} this worker sends a
request for this data item to the manager and declares it valid upon
reception. During a write access, the object is marked as modified;
all modified objects are sent back to the manager at the end of a
routine. Since the Java applet security restrictions impose a
star-like topology on communication, this master-worker structure fits
especially well.


Additionally, Charlotte's memory semantics allows the use of
\emph{eager scheduling}. A routine can be given to multiple workers
without jeopardizing the correctness of the computation. Thus, crashed
or slow workers can be compensated for by re-scheduling their routines
on other workers while still guaranteeing ``exactly once'' execution
(for implementation details, please cp.\ \cite{Bar:Charlotte}). This
entails Charlotte's fault tolerance and adaptive parallelism
properties. As an example, Figure~\ref{fig-code-stdmm} shows the
skeleton of a matrix multiplication program in Charlotte; {\tt drun}
is the actual implementation of a routine.

\begin{figure}[htb]
\rule{\columnwidth}{.05pt}
\small
%[
  // multiply  two SizexSize matrices: C = A*B
  public class Matrix extends Droutine {
    // this is executed by the workers:
    // compute row `myId' of C
    public void drun (int numRoutines, int myId) {
      int sum;
      for(int col=0; col<Size; col++)  {
        sum = 0;
        for(int k=0; k<Size; k++)
          sum += A[myId][k].get() * B[k][col].get();
        C[myId][col].set(sum);
      }
    }
    ...
    // this is executed by the manager:
    public void run () {
      ...
      // a parallel step with Size routines 
      // (one for each row):
      parBegin();
      addRoutine (this, Size);
      parEnd();
      ...
    }
  }
%]
\rule{\columnwidth}{.05pt}
\caption{Matrix Multiplication in Charlotte (abbreviated)
\label{fig-code-stdmm}}
\end{figure}


It is important to point out that Charlotte only uses standard Java
mechanisms and does not require a modified Java Virtual Machine or
low-level libraries. In particular, the distributed classes like
\texttt{Dint} are standard Java classes.

\subsection{Annotating Routines}
\label{ssec-hints}

Requesting data from the manager upon read access can be very
time-consuming, particularly in a high-latency environment. Charlotte
tries to amortize this overhead  by copying, for each request, a set of
objects (a ``page''---not to be confused with virtual memory pages)
from the manager to the worker. Choosing page sizes is difficult:
large pages reduce the frequency of data requests, small page sizes
reduce redundant communication. Since Charlotte has
no way of predicting which data is going to be used, any page
size is merely a heuristic.

If, on the other hand, the programmer gave Charlotte some hints which
data is actually going to be used by a routine, Charlotte could send
this ``read set'' along with the routine itself. The advantage of
doing this is two-fold: there is no latency wasted for data requests and no
communication bandwidth is wasted  (if the hints
given are correct). If the hints turn out to be wrong, the correctness
of the program is still guaranteed since a read-access to data which
was not sent in advance is still detected and served by standard
Charlotte mechanisms. In this sense, these hints are
correctness-insensitive. Additionally, it is possible to generate a
warning if hints turn out to be redundant or incomplete.

Hints are given by annotating a routine: a method {\tt dloc\_read} is
defined which is called by the runtime system to obtain the read set
for a given routine (see Figure~\ref{fig-code-presend} for an
example).\footnote{In the base class {\tt Droutine}, {\tt dloc\_read}
just returns {\tt null}.  The class {\tt Locations} handles
descriptions of data sets. In the current implementation, individual
objects, arrays, subarrays and matrixes of primitive types and
Charlotte's distributed classes can be
added directly. Objects that implement  {\tt
Serializable} can be treated in a similar fashion. It is also possible
to extend {\tt Locations} to handle other, application-specific
classes.}  Since both {\tt drun} and {\tt dloc\_read} are methods of
the same object, the association between a routine and its
annotations poses no problem. Similar hints can be given for the data
written by a routine.

\begin{figure}[htb]
\rule{\columnwidth}{.05pt}
%[
  public class Matrix extends Droutine {
    ...
    public Locations dloc_read (int numRoutines, int myId)
    {
      // compute the read set and store it in loc
      Locations loc = new Locations();

      // all of B:
      loc.add (B);

      // row ``myId'' of A:
      loc.add (A[myId]);
        
      return loc;
    }
    ...
  }
%]
\rule{\columnwidth}{.05pt}
\caption{Annotating a Charlotte routine with its read set.
\label{fig-code-presend}}
\end{figure}

The manager keeps track of which data is currently valid at which
worker. Thus,  if two routines with overlapping read sets are given
to a worker, only the missing data is sent with the second
routine. 

\subsection{Relying on Annotations}
\label{ssec-rely}

Assuring the local availability of data at a worker is costly:
essentially, an if-statement has to be executed for every read access
to a shared object and a flag has to be set for a write access. If the
programmer is sure that the annotations describe the read and write
behavior of a routine correctly (e.g., after sufficient testing), or
if they are generated by a compiler, there is no longer any reason for
this overhead since the manager takes care of sending the required
data and the worker knows which data to return to the manager.

This can be accomplished by using unchecked counterparts of
Charlotte's distributed classes (\texttt{Uint} instead of
\texttt{Dint}, etc.), retaining the exact same interface as the
correctness-guaranteeing classes. Moving from checked to unchecked
classes is a mere syntactic change of class name and constructor.


\subsection{Sharing Primitive Types}
\label{ssec-primitive}

For these unchecked classes, the {\tt get()} and {\tt set()} methods
for such unchecked data are completely trivial---there
is no longer any reason to pay the overhead for their invocation. As a
matter of fact, primitive data types like {\tt int} can be used
directly---the runtime system uses the annotations to move data back
and forth between manager and worker as needed. Thus, the shared
memory semantics of Charlotte can be implemented on top of primitive
data types allowing direct access without Java's high method invocation overhead
(much as it would be done in a message passing program).

Unlike the unchecked classes, using primitive data types does change
the interface, e.g., the \texttt{get()} and \texttt{set()} method
invocations have to be removed. In particular, objects are passed by
reference, primitive types by value. This can make the transition to
primitive types awkward for single variables. But since the overhead
for single variables is small in either case, the main advantages lie
in the use of annotations for arrays. And arrays of objects or arrays
of primitive types do have the same passing semantics. Nevertheless,
this step requires careful consideration.

Note that it is of course possible to mix objects of the original
Charlotte classes (with or without annotations) and shared primitive
types at will. This allows a programmer to use Charlotte's
distributed classes for data with complicated access patterns and
primitive types for more straightforward data. 


\subsection{Additional Optimizations}
\label{ssec-caching}

Since the manager keeps track of which data is currently valid at a
worker, it is possible to use this information for two additional
optimizations.

First, the manager can use the difference between a worker's valid
data set and a routine's read set as a criterion for choosing which
routine to give to a worker. Choosing the routine which minimizes this
difference also minimizes the amount of data the manager has to
sent.\footnote{Assuming the routine is correctly described by the
annotations. Otherwise, this is the best guess the manager can make
regarding the amount of communication for a given worker/routine
combination.} In a sense, a routine is given to a worker that already
has ``co-located'' data for this routine (hence ``colocation'' as a
short term  for this heuristic).


Second, for the unchecked shared objects, data movement to the workers
is solely the managers responsibility. It is therefore possible to
leave all the workers' local data intact at the end of a parallel step
(instead of declaring them invalid as in standard Charlotte) and to
overwrite them with new values only if necessary. If a program
declares shared data as unchanged at the beginning of a parallel step,
the manager will not remove this data from the workers' valid data set
and therefore not send it again. This mechanism constitutes inter-step
caching. It also allows colocation to take advantage of data send in a
previous step and not to be restricted to overlapping data within one
step.


\subsection{Discussion}
The most important thing to note for these extensions is that they
 allow a gradual improvement of a program: From
Charlotte's pure DSM to DSM plus hints to shared objects without
 correctness checks to sharing primitive data types
the correctness of which is completely based on annotations (cp.\
Figure~\ref{fig-outline}).  Access to these primitives types is direct
without any method invocations and therefore equivalent to what is
commonly used in message-passing systems.

\begin{figure*}[htbp]
\centerline{\includegraphics*[width=\textwidth]{bubbles.eps}}
\caption{Steps between Charlotte's DSM and a message-passing system.
\label{fig-outline}
}
\end{figure*}

The annotations for read and write data sets of a routine do look a
little like reading and writing data from and to the network. But
since only the data sets are described, the programmer does not have
to worry about streams, I/O-exceptions, etc. Additionally, only one
description is necessary as opposed to code for sending and receiving
data---by comparison, a message-passing program actually over-specifies
the communication. It is possible to transform these descriptions into
direct send/receive calls, but the gain should be minimal; e.g., it is
difficult to avoid redundant data transmission with pure
message-passing calls. While this
approach does generate some overhead for the runtime system, the
following section will show that this overhead is well invested.

All Charlotte's initial advantages like fault tolerance and adaptive
parallelism are maintained---capabilities that would be laborious to
implement using message-passing primitives alone. Additionally, a
flexible mixture of purely DSM-based and annotation-supported objects
is possible.

In comparison to related work, CRL and Cid are close
relatives. But Charlotte's simpler programming model and the direct use
of objects make these annotations easier to use for a programmer than
having to worry about mapping and locking memory regions, plus having
the additional possibility to use pure DSM
objects. Jade's annotation technique is also very similar to the
approach proposed here, but it lacks the capability to mix different
levels of correctness guarantees; Jade completely relies on the
correctness of the given annotations.  The flexibility to mix
different levels of guarantees and switch back and forth between them
is the particular strength of this approach.






