\subsection{Replicated Workers Coordination Abstraction}
\label{sec:CA}

The notion of a coordination abstraction is very broad.
For example, coordination abstractions can be defined to capture the
essence of peer-group, master-slave, heartbeat, tree, ring,
and pipelined computations.  
In this section, we describe one flexible
coordination abstraction that is a key component of the PAGS framework.

\begin{figure*}
\epsfxsize=4.00in
\epsfverbosetrue
\centerline{\epsffile{rw-ca.eps}}
\caption{Replicated Worker Abstraction}
\label{fig:rw-ca}
\end{figure*}
Collections of replicated workers \cite{andrews:91} can
be applied to solve a wide variety of problems in parallel.
Figure \ref{fig:rw-ca} illustrates the topology of a collection
of replicated workers.
All replicated workers computations share the notion of a group
of computational elements, $C_i$, mapped to separate
processes, called {\em workers}.  
Sub-problem data, $D_{in}$, is fed as input to the computation and is stored in
a shared repository, called a {\em work pool}.  
Execution proceeds as workers
repeatedly consume, process, and produce data elements 
stored in the work pool.
Conceptually, the computation terminates when all of the
data elements have been consumed at which point the result
of the computation is returned.  Alternate termination semantics can
also be supported; for example, one could allow individual
workers to signal for the termination
of the computation depending on the results of a local computation.
Worker computations in the replicated workers abstraction
are typically thought of as being identical, but this need
not be the case.  
For example, one can define a heterogeneous collection of
replicated workers where the work
computation is determined by the type of the data element
being processed. 
Replicated worker computations can be defined
to operate in either shared-memory or distributed-memory
environments.  From the user's perspective there is little
difference between the two, although design and implementation 
decisions will differ  in order to achieve high-performance.

\subsection*{Replicated Workers in Java}
We describe the replicated workers abstraction as the collection of 
Java class and interfaces sketched in Figure \ref{fig:rw-interface}.
\begin{figure*}[t]
\begin{center}
{\tt \footnotesize
\begin{tabular}{lcl}
\begin{minipage}[t]{2.5in}
\begin{tabbing}
m\=m\=m\=m\=m\=\kill
package ca.replicatedworkers;\\
\\
public interface WorkPool \{\\
\>  public abstract int size();\\
\>  public abstract Object take();\\
\>  public abstract void add(Object o);\\
\}\\
\\
public interface Work \{\\
\>  public abstract boolean doWork(\=Vector newWork,\\
\>                                 \>Vector results);\\
\}\\
\\
public interface Result \{\\
\>  public abstract boolean doResult();\\
\}\\
\\
public class Configuration \{ \\
\>  public final static int \=EXCLUSIVE = 1, \\
\>                          \>CONCURRENT = 2, \\
\>                          \>NONE = 3;\\
\>  public final static int SYNCHRONOUS = 1,\\
\>                          \>ASYNCHRONOUS = 2;\\
\>  public int resultSemantics;\\
\>  ...\\
\}
\end{tabbing}
\end{minipage}
%
& ~~ &
\begin{minipage}[t]{2.5in}
\begin{tabbing}
m\=m\=m\=m\=m\=\kill
package ca.replicatedworkers;\\
\\
public final class ReplicatedWorkers \{\\
\>  protected boolean done;\\
\>  ...\\
\\
\>  public Replicated\=Workers(Configuration theConfig,\\
\>\>                           WorkPool workCollection,\\
\> \>                          WorkPool resultCollection, \\
\>  \>                         int numWorkers, int numItems) \{...\\
m\=m\=m\=m\=m\=\kill
\>  public final synchronized void destroy() \{...\\
\\
\>  public final synchronized void putWork(Vector v) \{...\\
\>  public final synchronized void putWork(Work w) \{...\\
\\
\>  public final synchronized Vector getResults() \{...\\
\>  public final synchronized Result getResults() \{...\\
\\
\>  public final synchronized void execute() \{...\\
%%\>\>    done = false; \\
%%  \> \> mainWorkerBarrier.await();\\
%%\\
%%  \> \> if ( theConfig.executeConfig == Configuration.SYNCHRONOUS ) \{\\
%%\>\> \>     theCoord.mainAwaitTerminate();\\
%%\> \>\>     done = true; \\
%%\>\>\>      theCoord.notifyDoneChange();\\
%%\\
%%\>\>\>      mainWorkerBarrier.await();\\
%%\>\>    \} \\
%%\>  \}\\ 
\>  public final synchronized void awaitTermination() \{ ...\\
\}
\end{tabbing}
\end{minipage}\\
\end{tabular}}
\end{center}
\caption{Java Replicated Worker Interfaces and Class}
\label{fig:rw-interface}
\end{figure*}
A more detailed presentation of this coordination abstraction
is given in \cite{dwyer:97b}.

To define the meaning of the RWCA interface
we map components of the abstract view of the coordination
abstraction illustrated in Figure \ref{fig:rw-ca} onto parts of the interface.
The data, $D_i$, stored in the work pool and processed
by the workers are defined as a class that implements the {\tt Work}
interface.  All such classes also provide the {\tt doWork} method
which corresponds to the $C_i$ in the figure.
Result data, $Results$, are processed independently from work pool
data and are defined by a class that implements the {\tt Result}
interface.  These classes provide the {\tt doResult} method
which corresponds to the result processing part of $C_i$.
The pool in the figure is defined by a class that implements
the {\tt WorkPool} interface.  This interface provides the
minimal capabilities needed to implement the semantics of 
the coordination workers abstraction.

The operations of the {\tt ReplicatedWorkers} class allow
for creation, configuration and destruction of a replicated
workers computation.  Such a computation can be initialized
by inserting work data into the pool via calls to {\tt putWork}.
After initialization the computation can be started
by calling {\tt execute}.  If the abstraction is configured
to have synchronous semantics this call will not return
until the computation terminates.  Under asynchronous
execution semantics, {\tt execute} calls return immediately and user threads
can poll for results, by calling {\tt getResults},
or block for termination, by calling {\tt awaitTermination}.
A computation is said to terminate if all workers are
blocked waiting for more work to process and there is no
more work in the pool.  Alternatively, the {\tt doWork}
or {\tt doResult} can return a {\tt true} value which
will initiate the termination of the computation.
Explicit result processing is not required by this abstraction.
For example, for a {\tt NONE} configuration of {\tt resultSemantics}
the result {\tt WorkPool} may be null and no calls to {\tt doResult}
will be made.  Computations of this type are free to leave
results in the work {\tt WorkPool} which will be available
to the application upon termination.

