\section{Evaluating the Effectiveness of PAGS}
\label{sec:EVAL}
In this section, we evaluate the application of
PAGS to the SOR problem.
We focus both on qualitative and quantitative
aspects of our efforts. 
We conclude with our assessment of the potential
of Java as a platform for high-performance scientific
computing.

\subsection{Qualitative Evaluation}
The goal of PAGS is to make it easier to program
parallel grid simulations relative to alternative parallel
programming technologies.
There are four different aspects of this that we consider here:
learning curve for PAGS interfaces, cost of mapping applications
to PAGS, ease of tuning performance, and the quality
of the resulting applications.

In working with the RWCA, it has been our experience
that the sequential nature of the {\tt doWork} method of
{\tt Work} objects allows developers to quickly understand
the framework.  The fact that the interfaces are small also
appears to be of benefit; there are eight methods in
the {\tt ReplicatedWorkers} object and a total of
five methods in the three interfaces.  The primary obstacle
to ease of understanding in our experience has been the
meaning  of  the {\tt Configuration} settings.
For the SOR problem this was not a problem since the
default settings were suitable.
The {\tt AssociativePool} introduces an additional layer of
complexity on top of the RWCA.  One difficulty
in using this structure is the need to define explicit
{\tt Border} objects, although, for the SOR problem this
was relatively straightforward.  In addition, in the
current version of PAGS
users must configure the partition topology manually.
This is one area for future work, since one can clearly 
automate the generation of partition topology for
common classes of problems, e.g., stencil problems.

We found the mapping of the SOR problem to the PAGS
framework to be relatively easy.
Working from an existing threads-based implementation of this problem
it took the authors 45 minutes to implement, compile and run
the framework-based solution sketched in Section \ref{sec:sor-kernels}.
Thus, it appears, that once the PAGS framework is understood
it can effectively be used to rapidly construct parallel
versions of well-understood sequential simulations.

In the next section we discuss the effects of using the PAGS
performance tuning parameters.  While all of the implementations
discussed below allow for tuning, for most of them such 
tuning is possible only because the implementations are monolithic.
When component-based implementations are constructed, using for example 
the RWCA or PAGS, performance tuning is only possible when
the components are explicitly designed to expose performance
related attributes.  The {\tt numWorker}, {\tt numIn}, {\tt waterMark}
and {\tt SubGrid.size} parameters are easily accessed
and modified through PAGS interfaces.

Finally, in constructing multiple implementations of the
SOR problem we learned that the reuse of PAGS
components can provide for higher-quality solutions.
For example, in one of the hand-built solutions there was
a coding error that overwrote a border element value
at the wrong time.
The PAGS implementation did not suffer from this problem
since the {\tt AssociativePool} controls the timing
of border construction
after which borders are held internally in a {\tt Partition}.
Another hand-built solution exhibited a deadlock, neither
the RWCA nor PAGS implementations suffered from this problem
because all concurrency related processing is
internal to the framework components.

\subsection{Quantitative Evaluating}
We are primarily interested in understanding the performance
penalty, if any, that will be incurred by using a problem-independent
framework, like PAGS, rather than a hand-built problem-specific solution.
To do this we compare the run-times of implementations built 
with the PAGS framework and those built with
different programming techniques for the same problem.
We are also interested in determining whether PAGS applications
are capable of effectively exploiting available problem parallelism
as the number of processors grow.
Towards these ends we implemented six different versions of the 
SOR application described in Section \ref{sec:APPLY}.
Each of the implementations was written to accept the
total problem size, a value to control convergence, and
where appropriate partition sizes and degree of solution parallelism.
The implementations are:
\begin{description}
\item[Sequential C]{Consists of a triple loop nest where the outer
loop continues until convergence and inner pair of loops carry out
a 2-dimensional relaxation step.  
Plots for this implementation are denoted {\bf sequential-C}.}
\item[Sequential Java]{Essentially the same as the C version.
The code is given in Section \ref{sec:sor-kernels}.
Plots for this implementation are denoted {\bf sequential-Java}.}
\item[Hand-built Thread-per-partition Java]{Parallelization
of outer-most loop with barrier synchronization at the end of
each iteration.  Inner loops ranges are adjusted appropriately
depending on the partition size.
Plots for this implementation are denoted {\bf threaded}.}
\item[Hand-built Adaptive Java]{This implementation  uses
a data structure that was implemented
to manage the partition dependences in a 4-point stencil.
As partitions are computed their neighboring partitions
may become ready for their next computation step in which
case they are dispatched to a thread and executed.
Plots for this implementation are denoted {\bf adaptive}.}
\item[Adaptive RWCA]{The data structure from the hand-built
adaptive implementation was implemented as a {\tt WorkPool} and 
used to instantiate the RWCA.
Plots for this implementation are denoted {\bf rwca}.}
\item[Adaptive PAGS]{This is the implementation described
in Section \ref{sec:APPLY}.  We note that the dependence
management data structure in PAGS is more general
than the one used in the previous two implementations;
it can handle any graph of dependences.
Plots for this implementation are denoted {\bf pags}.}
\end{description}
Each of these implementations was constructed by a 
developer with at least one year of threads programming
experience; the implementations each underwent a small
amount of performance tuning.

The platform we used in conducting our evaluations
is a SUN Enterprise 4000 with 10 168Mhz UltraSparc processors and
512Mbytes of RAM running Solaris 5.5.1.
We compiled all Java code with Toba \cite{toba:97}
version 1.06b using the SUN C compiler;
we used the same C compiler for the C implementation.
Toba translates Java code to C code then compiles the C code
and links it with libraries that enforce Java's run-time
semantics.
The version of Toba we used provided a nearly-complete
native implementation of the JDK 1.0.2.
On machines running Solaris, Toba translates
Java threads into SolarisThreads \cite{sun:93}.
By default all threads are mapped onto a single Solaris
process and are scheduled internal to that process.
In order to take full advantage of the Enterprise multi-processor
we modified thread creation to map a single thread
to a single Solaris process.  Furthermore, each Solaris
process was then bound to a separate processor;
if the number of processes exceeds the number of
processors we bind them in a round-robin fashion
to spread processes evenly.
All of these machine specific details are encapsulated
in a run-time library and a single Java native-method.
Thus, our code maintains its portability while providing
for high-performance in a Solaris environment.

We ran each implementation for 4 different problem sizes
with various partition sizes using all 10 available processors.
Note that our scaling of the problem corresponds to increasing
the size of the modeled solid rather than a refinement
of the simulation's mesh.
\begin{figure}
\begin{center}
\begin{tabular}{lcl}
\begin{minipage}[t]{3.1in}
\epsfxsize=3.1in
\epsfverbosetrue
\centerline{\epsffile{plot.64.eps}}
\end{minipage}
&  &
\begin{minipage}[t]{3.1in}
\epsfxsize=3.1in
\epsfverbosetrue
\centerline{\epsffile{plot.128.eps}}
\end{minipage}
\end{tabular}

\begin{tabular}{lcl}
\begin{minipage}[t]{3.1in}
\epsfxsize=3.1in
\epsfverbosetrue
\centerline{\epsffile{plot.256.eps}}
\end{minipage}
&  &
\begin{minipage}[t]{3.1in}
\epsfxsize=3.1in
\epsfverbosetrue
\centerline{\epsffile{plot.512.eps}}
\end{minipage}
\end{tabular}
\end{center}
\caption{Comparative Performance of SOR Implementations}
\label{fig:comparative}
\end{figure}
The plots in Figure \ref{fig:comparative} give the
comparative performance of the implementations.
The data are for four different problem sizes: 64 by 64, 128 by 128,
256 by 256 and 512 by 512 grids.
The sequential C version beats the sequential Java version 
by nearly a factor of two primarily because of array bounds
checks in Java.  More sophisticated Java compiler technology
might be able to remove such checks in cases where array bounds
and index expression ranges are statically bound, as in the 
case of our SOR codes.
In spite of the additional cost of bounds checking
we observe that, as expected, the parallel versions 
beat the sequential versions.  
It is also the case that as problem sizes increased
the adaptive solutions appear to be faster than the
the synchronous iteration solution; this is to
be expected in simulations for which only a small
portion of the problem is in flux during any simulation step.
Of the adaptive versions the best performer depends
on problem size.
For all but the largest problem size, the plots exhibit
a characteristic "upward cup" shape as partition size
is varied.  This can be understood as a 
balancing of communication, computation and parallelism.
For overly fine partitions the overhead
of communication yields reduced overall performance. 
For overly coarse partitions there is insufficient
parallelism and overall performance is reduced.
The troughs of the curves represent a good balance
between the communication and computation  required to solve the instances
of the SOR problem.
PAGS provides a simple mechanism for controlling partition
size, thereby enabling application developers
to easily find a good balance of those problem-specific factors.

In these runs the PAGS version only consumed a single
work element at a time.  We found that for this problem
this provided the best performance.  Processing of multiple
independent partitions by a worker only served to
sequentialize the computation and reduce performance;
although this is not the case for all problems \cite{dwyer:96d}.

It is clear from these results that for some problems
dependence-directed computation is a significant benefit.
PAGS provides support for this as well as for parallelism.
To try to assess the benefits of parallelism, as
opposed to the dependence-directed feature of PAGS,
we selected good performing partition sizes and 
varied the degree of parallelism.
\begin{figure}
\begin{center}
\epsfxsize=4.5in
\epsfverbosetrue
\centerline{\epsffile{plot.scale.eps}}
\end{center}
\caption{Scaling Performance}
\label{fig:speedup}
\end{figure}
Figure \ref{fig:speedup} plots the speedup versus
number of processors.  
Lines on the plot are annotated with the partition size and the problem
size, e.g., {\tt rwca:64,256} is for 64 by 64 partitions of a 256 by 256 grid
solved with the adaptive RWCA implementation.
Note that the apparent super-linear
speedup exhibited by the PAGS implementations is
a result of both the dependence-directed computation
and the {\tt AssociativePool} watermarks that minimize
the number of pool updates required.  
We note that each pool update for the PAGS pool is
more expensive than for the hand-built and RWCA data
structures.
Since problem dependences determine
the maximum amount of available parallelism, once
that number of processors is applied to the PAGS solution there
is no further speedup.
Without the {\tt AssociativePool}, the RWCA version is slower
to achieve higher performance because of excessive
overhead in managing sub-problem dependences.
As parallelism in the PAGS implementation nears
the available parallelism in the problem, however,
the number of pool updates required for the PAGS and 
RWCA versions converge.  Since, each update is more
expensive for the PAGS implementation its performance
lags behind the RWCA version and its speedup curve tails off.


\subsection{Observations}
We believe that the Java language
can serve as a vehicle for parallel scientific
computing.  Java supports both shared-memory and distributed-memory
models with threads and monitor structures and the {\tt java.net}
package respectively.
Native compilers for Java, such as Toba, are becoming available
with support for true-parallel execution of threaded applications
and these compilers are rapidly maturing to provide high-levels
of program optimization.
To leverage investment in existing codes and to provide
for language inter-operability the Java designers have
defined the Java Native Interface (JNI).  The JNI supports
bi-directional inter-operability between Java and C/C++ program
fragments.  
This will enable use of 
existing scientific libraries, such as PETSc \cite{gropp:94},
in computations embedded in our framework,
for example in {\tt doWork} calls of simulation {\tt Partition} objects.

Based on our experience we believe
that using PAGS saves time and effort
in developing parallel simulation software.  
Savings is gained by reuse of coordination abstraction
and associative workpool components.
One significant advantage of the object-oriented nature of PAGS,
that is not exploited for the  SOR problem,
is its support for
heterogeneity in data and computational components
of an application.  
Because all of the framework components are implemented in
terms of interfaces, the actual partition data used in a simulation
need not all be of the same type.  Thus, we can have widely
differing concrete representations and local computations for
different sub-regions of a problem.  The flexibility
afforded by this heterogeneity does not increase development
effort or execution time.

