\subsection{An Associative Work Pool}
\label{sec:AW}
\begin{figure*}
\epsfxsize=5.00in
\epsfverbosetrue
\centerline{\epsffile{partitions-shadows.eps}}
\caption{Work Pool Components}
\label{fig:pa}
\end{figure*}

The associative work pool is a data structure that manages
dependences between sub-problems in a grid simulation.
Dependences can arise from a number of different sources, including,
data flows, causal and temporal relationships.
Data flows across sub-problem boundaries in a simulation to allow
convergence of a global solution, as opposed to a collection of
local solutions.
Causal orderings are induced when simulation entities represent
real-world events that stand in some cause-effect relationship.
Temporal relationships are expressed in traditional grid computations as
dependences across iterations that correspond to different time-steps.
A correct simulation, and consequently a correct computed result,
arises when all problem dependences are honored.
The associative work pool encodes dependences, dynamically tracks the state
of all sub-problem dependences and releases sub-problems
for computation when their dependences are honored.
In this way, the AW works much
like an adaptive scheduling mechanism for sub-problem computations.

\subsection*{Partitions, Borders and Shadows}
The AW takes a problem independent view of sub-problems and their
dependences.  There are three components to this view:
\begin{description}
\item[Partitions]{are the set of sub-problems that constitute the
simulation.  A partition is considered to be a unit of data
and associated computation and implicitly defines the finest granularity
of the simulation.}
\item[Borders]{are those portions of a partition that are referenced
by the computation performed in some neighboring partition.  Depending
on the simulation problem borders may range from single "representative"
values to the entire partition.  In
addition, we may define the portion of a partition's border that is
shared with a designated neighbor and think of a partition
as having a collection of borders.}
\item[Shadows]{are copies of neighboring border values stored locally
in a partition so as to enable complete local computation of a simulation step.
Shadows typically are defined to be easily integrated with the
representation of local partition data, so as to allow seamless
computation of simulation steps.}
\end{description}
Figure \ref{fig:pa} illustrates these components
and the flow of data between them for an irregularly 
shaped collection of three partitions.
Dependences are expressed as a directed graph of partitions and border.
Traditional data dependences and causal dependences
are expressed as individual directed edges between a border
and the partition that depends on it; temporal
dependences are handled by an explicit representation of simulation time.


\subsection*{Associative WorkPool in Java}
We describe the associative workpool abstraction as a collection
of Java classes and interfaces sketched in Figure \ref{fig:aw-interface}.
\begin{figure*}[t]
\begin{center}
{\tt \footnotesize
\begin{tabular}{lcl}
\begin{minipage}[t]{2.2in}
\begin{tabbing}
m\=m\=m\=m\=m\=\kill
package pags;\\
\\
import ca.replicatedworkers.*;\\
\\
public interface Indexable \{... \\
public class IndexableImpl implements Indexable \{\\
\>  private int theIndex;  \\
\>  public void setId(int i) \{theIndex = i;\}\\
\>  public int Id() \{return theIndex;\}\\
\}\\
\\
public interface Partition \{... \\
public class PartitionImpl \=extends IndexableImpl \\
\>                           implements Partition, Work \{\\
m\=m\=m\=m\=m\=\kill
\>  private int maxLA;\\
\>  protected int borderLA;\\
\>  protected int runTo = maxLA;\\
\>  protected boolean doneComputing;\\
\\
\>  public PartitionImpl(int m) \{maxLA=m;\}\\
\\
\>  public boolean doWork(...\\
\\
\>  public boolean done() \{return doneComputing;\}\\
\\
\>  public Vector neighbors() \{return new Vector();\};\\
\>  public void setLookahead(int i) \{borderLA=i;\}\\
\>  public Border getBorder(Partition p) \{return null;\}\\
\\
\>  public int minShadowLookahead() \{return runTo;\}\\
\>  public void resetShadowLookahead() \{runTo=maxLA;\}\\
\>  public void updateShadow(Border b) \{\}\\
\}\\
\\
final class PartitionInfo \{\\
\>  protected int lvt;\\
\>  protected int status; \\
\>  protected boolean done;\\
\>  protected Partition thePartition;\\
\}
\end{tabbing}
\end{minipage}
%
& &
\begin{minipage}[t]{2.5in}
\begin{tabbing}
m\=m\=m\=m\=m\=\kill
final public class AssociativePool implements WorkPool \{\\
\>  private Partition[] work;\\
\>  private PartitionInfo[] workInfo;\\
\\
\>  public AssociativePool(Vector v, int waterMark) \{...\\
\\
\>  public final synchronized int size() \{...\\
\>  public final synchronized Object take() \{...\\
\>  public final synchronized void add(Object o) \{\\
\>\>    Partition p = (Partition)o;\\
\>\>    workInfo[p.Id()].lvt += p.minShadowLookahead();\\
\>\>    p.resetShadowLookahead();\\
\>\>    ...\\
\>\>    if\= ( waterMark \verb|>| size() ) \\
\>\>      \>updateReadyPartitions();\\
m\=m\=m\=m\=m\=\kill
\>  \} \\
\\
\>  public final synchronized void updateReadyPartitions() \{\\
\>\>  ... for all partitions waiting for neighbor values ..\\
\>\>    vEnum = current.neighbors().elements();\\
\>\>    while ( vEnum.hasMoreElements() ) \{\\
\>\>\>      neigh = (Partition)vEnum.nextElement();\\
\>\>\>      nId = neigh.Id(); \\
\>\>\>      if ( \=workInfo[nId].lvt \verb|>|= workInfo[curId].lvt \verb+||+ \\
\>\>\>           \>workInfo[nId].status == CONVERGED ) \{\\
m\=m\=m\=m\=m\=\kill
\>\>\>\>        current.updateShadow(neigh.getBorder(current));\\
\>\>\>      \} else \{\\
\>\>\>\>        currentReady = false;\\
\>\>\>\>        break;\\
\>\>\>      \}\\
\>\>    \}\\
\>\>    if (currentReady) \{\\
\>\>\>      workInfo[cId].status = READY;\\
\>\>\>      ready.insertLast(current); \\
\>\>\>      potential.exclude(current); \\
\>\>\>      numReady++; \\
\>\>    \}\\
\>\>    ...\\
\>  \} // end void updateReadyPartitions() \\
\}
\end{tabbing}
\end{minipage}\\
\end{tabular}}
\end{center}
\caption{Java Associative WorkPool Interfaces and Class}
\label{fig:aw-interface}
\end{figure*}
The PAGS framework provides interfaces and partially defined
compliant base classes that define the requirements of
application defined partitions and borders.  The philosophy of
PAGS is to leave performance critical decisions in the
hands of the simulation developer.  For this reason, users
must define the concrete data types for partitions and 
borders.  In addition, they must define the partition work
method, called {\tt doWork}, and the border creation
and shadow updating routines, {\tt  getBorder} and {\tt updateShadow}.
The {\tt AssociativePool} complies with the replicated workers
coordination abstraction {\tt WorkPool} interface by providing
{\tt add}, {\tt size} and {\tt take} operations.
Unlike common collection types an instance of the {\tt AssociativePool}
is immutable.  Once created it manages a fixed set of {\tt Partitions}.  
Its collection-like operations only reflect the number of partitions
that are {\tt READY} to have their local computations performed.
We note that the separation of {\tt Border} and {\tt Partition}
types serves to implement a kind of double-buffering, thus allowing
computation on a {\tt Partition} and use of its
border values to update a neighbor's shadows to proceed in parallel.
Finally, we note that the {\tt updateReadyPartitions} is factored
out of the {\tt take} routine to allow updating of
{\tt AssociativePool} contents in parallel with {\tt Partition} computations;
thereby providing a mechanism for hiding work pool overhead.

