\section{Measurements}
\label{sec-measure}

\newcommand{\MW}{M $\to$ W}
\newcommand{\WM}{W $\to$ W}

This section illustrates the differences between and advantages of the
various approaches with matrix multiplication as an example for
measurements. Matrix multiplication was deliberately chosen as a
problem with only moderate granularity. Problems with very high
computation/communication (e.g., computing prime numbers), which are
often used as examples for Web-based computing, suffer from
the problems addressed by the  extensions proposed here only to a much
smaller degree, but such a focus also limits the application scope.

The environment used for experiments consists of a
number of PentiumPro 200 machines at the Distributed Systems Laboratory of
New York University connected by a 100 MBit/sec Ethernet and two
Pentium 90 at Humboldt University Berlin. A ping between these two
sites typically takes about 130 msec.  All machines were running Linux
2.0. Sun's Java Development Kit Version 1.1.3  and the
Kaffe Virtual Machine Version 0.92 \cite{kaffe:97} (a Java
Just-In-Time (JIT) compiler) were used to run the
programs.  Runtimes for a purely sequential implementation are shown in
Table~\ref{tab-seqtimes}.


\begin{table}[htbp]
\centering
\begin{tabular}{c|d{1}|d{1}} 
        & \multicolumn{1}{c|}{JDK} & \multicolumn{1}{c}{Kaffe} \\
\hline 
Pentium 90 & 16.5 & 8.1 \\ \hline
PentiumPro 200 & 9.0 & 2.3 \\ 
\end{tabular}
\caption{Sequential runtimes (in sec.) for multiplying two 200x200
integer matrices. 
\label{tab-seqtimes}}
\end{table}



The first question asked of an enhancement for a parallel system if of
course the one regarding improvements in runtime.
Figure~\ref{fig-timesmp_int} shows the runtime for a 200x200 matrix
multiplication with up to four workers, measured on the local network
at NYU (all numbers are averaged over 10 runs) using JDK,
Figure~\ref{fig-timesmp} shows the same times using the Kaffe
JIT-compiler. In both figures, as in all the following ones,
\texttt{Dint} refers to standard Charlotte, \texttt{Dint+A} to
annotated Charlotte with correctness check, \texttt{Uint} indicates
the use of the unchecked class and \texttt{int} sharing primitive
integers instead of objects.\footnote{The actual programs are slightly
  more complicated than shown in Figure~\ref{fig-code-stdmm}.  Using
  one routine per matrix row is too inefficient---grain sizes of 5,
  10, 25 and 50 rows per routines were used in the experiments and the
  best of these results is reported.  As is to be expected, for more
  workers, optimal grain sizes are decreasing.}  Times for a message
passing implementation of matrix multiplication (implemented directly
on top of Java IOStreams) are given in both figures.



\begin{figure}[htbp]
\centerline{\includegraphics*[width=\figwidth]{timeint.eps}}
\caption{Run time of Matrix Multiplication on local network (NYU) with
JDK.
\label{fig-timesmp_int}
}
\end{figure}

\begin{figure}[htbp]
\centerline{\includegraphics*[width=\figwidth]{timesmp.eps}}
\caption{Run time of Matrix Multiplication on local network (NYU)
with JIT-compiler.
\label{fig-timesmp}
}
\end{figure}

Both for the interpreted and the compiled version the improvements in
runtime using annotations are striking. Since the JIT-compiler gives
considerably better results, and JIT-compiler are more and more
commonly available in most browsers, only these times will be
discussed in the following. Nevertheless, it is worthwhile to point
out that the interpreted case behaves in general very similar to the
compiled case.  Note that with {\tt int}, one worker executes almost
as fast as the sequential version and shows actual speedup with two or
more workers in the interpreted version---the message passing
implementation suffers from only negligible overhead with one worker.
The times for message passing and the Charlotte program with primitive
data types are practically identical,\footnote{ Actually, in some
  circumstances the Charlotte version is faster than the message
  version. While this may be due to statistical fluctuations,
  Charlotte's load balancing capabilities give it an advantage over a
  straightforward message passing program.}  proving the claim that
with annotating Charlotte near-message passing efficiency\footnote{Of
  course, the message passing program also communicates only along a
  star-like topology to reflect the constraints imposed by the Java
  security model.} is possible while still maintaining advantages like
fault tolerance.  Figure~\ref{fig-speedupmp} shows the absolute
speedup of the compiled case compared with the sequential execution
time (thus taking Charlotte's overhead into account).


\begin{figure}[htbp]
\centerline{\includegraphics*[width=\figwidth]{speedup.eps}}
\caption{Absolute speedups (compared with sequential program) for the
different parallelized versions using JIT-compiler. 
\label{fig-speedupmp}
}
\end{figure}


It is particularly interesting to compare the runtimes needed by the
different extensions of Charlotte that have been introduced in this
paper and the message passing version. 
Figure~\ref{fig-ratiouint} shows the ratios of runtimes when comparing
standard Charlotte ({\tt Dint}) with annotated Charlotte ({\tt
Dint}+A), Charlotte with unchecked distributed objects (\texttt{Uint})
and primitive types ({\tt int}). The annotations make data requests
unnecessary and send all the data needed for a routine in one
batch---this improves runtime by about a factor of three ({\tt Dint}
vs. {\tt Dint}+A). The \texttt{Uint} version shows another slight
improvement, but the ability to forego the overhead associates with
objects and to share primitive types adds another factor of
two---resulting in an overall improvement of about a factor of nine
over standard Charlotte. 

\begin{figure}[htbp]
\centerline{\includegraphics*[width=\figwidth]{ratio.eps}}
\caption{Ratios of run times of different optimizations (compiled
case). 
\label{fig-ratiouint}
}
\end{figure}


The runtime using connections with high latencies
was tested with two workers running at Humboldt University Berlin;
runtime and ratios between various methods for this setup are shown in
Figure~\ref{fig-remtimes} and Figure~\ref{fig-remratio}
respectively.\footnote{\texttt{Uint} is not shown since, as seen
  above, the major improvements stem from annotations and primitive
  data types.} Again it is obvious that the shared primitives version
attains a performance comparable to the message passing
implementation. Unfortunately, since these machines are considerably
slower than the local machines, the numbers are not directly
comparable and no direct conclusions concerning the respective gains
for low- and high-latency environments are possible.

\begin{figure}[htbp]
\centerline{\includegraphics*[width=\columnwidth]{remtime.eps}}
\caption{Times with master at NYU, workers at Berlin for various
versions of Charlotte and message passing.}
\label{fig-remtimes}
\end{figure}

\begin{figure}[htbp]
\centerline{\includegraphics*[width=\columnwidth]{remratio.eps}}
\caption{Ratios with master at NYU, workers at Berlin for various
versions of Charlotte and message passing.}
\label{fig-remratio}
\end{figure}


The optimization in Subsection~\ref{ssec-caching} where also proposed
with long latencies in mind. For the example of multiplying a matrix
$A$ with two matrixes $B_1$ and $B_2$ in two consecutive parallel
steps, Figure~\ref{fig-cachcol} shows the communication time using
{\tt Dint} plus annotations, additionally caching $A$ between the two
steps, and both caching $A$ and taking the distribution of $A$ among
the workers into account for the second parallel step (colocation).
While in a LAN environment the impact of colocation is only small, for
high-latency connections colocation can save up to 25\% of runtime (in
this particular example).
Perhaps even more important is the fact that the standard deviation of
colocation is roughly a factor of three smaller than the other
methods.'


\begin{figure}[htbp]
\centerline{\includegraphics*[width=\figwidth]{cachcols.eps}}
\caption{Communication times for matrix multiplication with 
{\tt Dint} plus annotations, {\tt Dint} plus annotation and  caching,
and {\tt Dint} plus annotation and  caching and colocation (averaged
over 1000 runs).
\label{fig-cachcol}
}
\end{figure}



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