\section{Code for SOR Problem}
This appendix provides sketches of the Java source code
for sequential Java and PAGS-based implementations of the SOR problem.

\subsection{SOR Kernels}
\label{sec:sor-kernels}
\begin{center}
{\tt \footnotesize
\begin{tabular}{lcl}
\begin{minipage}[t]{2.5in}
\begin{tabbing}
m\=m\=m\=m\=m\=m\=m\=\kill
public class SparseGrid \{\\
\>  public static void main( String args[] ) \{\\
\>\>    int problemDim;\\
\>\>    float tolerance;\\
\>\>      double[][] aGrid, bGrid, tmp;\\
\>\>        double change, maxChange = 0;\\
\\
\>\>    // Read problem parameters\\
\\ 
\>\>      aGrid = new double[problemDim+2][problemDim+2];\\
\>\>      bGrid = new double[problemDim+2][problemDim+2];\\
\\
\>\>      for(int i=0; i\verb|<|problemDim+2; i++) \{\\
\>\>\>        aGrid[0][i] = 5;\\
\>\>\>        bGrid[0][i] = 5;\\
\>\>      \}\\
\\
\>\>      while (maxChange \verb|>|= tolerance) \{\\
\>\>\>        maxChange = 0;\\
\\
\>\>\>        // Compute new values into tmp\\
\>\>\>        for(int i=1; i\verb|<|problemDim+1; i++) \\
\>\>\>\>          for(int j=1; j\verb|<|problemDim+1; j++) \{\\
\>\>\>\>\>            // 4-point stencil\\
\>\>\>\>\>            bGrid[i][j] = (\=aGrid[i-1][j]+aGrid[i+1][j]+\\
\>\>\>\>\>\>                           aGrid[i][j-1]+aGrid[i][j+1])/4;\\
m\=m\=m\=m\=m\=m\=m\=\kill
\\
\>\>\>\>\>            if(bGrid[i][j]\verb|>|aGrid[i][j])\\
\>\>\>\>\>\>              change = bGrid[i][j]-aGrid[i][j];\\
\>\>\>\>\>            else\\
\>\>\>\>\>\>              change = aGrid[i][j]-bGrid[i][j];\\
\>\>\>\>\>            if( change \verb|>| maxChange ) maxChange = change;\\
\>\>\>\>          \}\\
\\\
\>\>\>        // swap tmp and subgrid values\\
\>\>\>        tmp = aGrid; aGrid = bGrid; bGrid = tmp;\\
\>\>      \}\\
\>  \}\\
\}
\end{tabbing}
\end{minipage}
&  &
\begin{minipage}[t]{2.5in}
\begin{tabbing}
m\=m\=m\=m\=m\=\kill
import ca.replicatedworkers.*;\\
import pags.*;\\
\\
class SubGrid \=extends PartitionImpl \\
              \>implements Partition, Work \{\\
m\=m\=m\=m\=m\=m\=m\=\kill
\>  private SubGrid north, south, east, west; \\
\>  public double[][] aGrid, bGrid;\\
\>  ...\\
\>  public boolean doWork(\=Vector newWork,\\
\>                       \>Vector theResults) \{\\
\>\>  ...\
\>    for (int steps=0; steps\verb|<|runAhead; steps++) \{ \\
\>\>      for(int i=1; i\verb|<|size+1; i++) \\
\>\>\>        for(int j=1; j\verb|<|size+1; j++) \{\\
\>\>\>\>          // 4-point stencil\\
\>\>\>\>          bGrid[i][j] = (\=aGrid[i-1][j]+aGrid[i+1][j]+\\
\>\>\>\>\>                       aGrid[i][j-1]+aGrid[i][j+1])/4;\\
m\=m\=m\=m\=m\=m\=m\=\kill
\>\>\>\>          if(bGrid[i][j]\verb|>|aGrid[i][j])\\
\>\>\>\>\>            change = bGrid[i][j]-aGrid[i][j];\\
\>\>\>\>          else\\
\>\>\>\>\>            change = aGrid[i][j]-bGrid[i][j];\\
\>\>\>\>          if( change \verb|>| maxChange ) maxChange = change;\\
\>\>\>        \}\\
\>\>\>      tmp = aGrid; aGrid = bGrid; bGrid = tmp;\\
\>\>    \} \\
\>\>    doneComputing = maxChange\verb|<|tolerance;\\
\>\>    newWork.addElement(this);\\
\>\>    return false;\\
\>  \}\\
\\
\>  public void updateShadow(Border b) \{\\
\>\>    SubGridBorder sgb =  (SubGridBorder)b;\\
\\
\>\>    if ( sgb.thePartition() == north ) \\
\>\>\>      for(int j=1; j\verb|<|size; j++) aGrid[0][j]=sgb.val[j];\\
\>\>    else if ( sgb.thePartition() == south ) \\
\>\>\>      for(int j=1; j\verb|<|size; j++) aGrid[size+1][j]=sgb.val[j];\\
\>\>    else if ( sgb.thePartition() == east ) \\
\>\>\>      for(int j=1; j\verb|<|size; j++) aGrid[j][size+1]=sgb.val[j];\\
\>\>    else if ( sgb.thePartition() == west ) \\
\>\>\>      for(int j=1; j\verb|<|size; j++) aGrid[j][0]=sgb.val[j];\\
\>\>    if ( runAhead\verb|>|sgb.theLookahead() ) \\
\>\>\>      runAhead = sgb.theLookahead();\\
\>  \}\\
\}
\end{tabbing}
\end{minipage}\\
\end{tabular}}
\end{center}

\subsection{PAGS SOR Driver}
\label{sec:sor-driver}
\begin{center}
{\tt \footnotesize
\begin{tabbing}
m\=m\=m\=m\=m\=\kill
public class SparseGrid \{\\
\>  public static void main( String arg[] ) \{\\
\>\>    ...\\
\>\>    // read Problem parameters \\
\>\>    //   numWorkers, waterMark, numIn,\\
\>\>    //   problemSize, SubGrid.size, SubGrid.tolerance\\
\>\>    numSubGrids = (problemSize/SubGrid.size)*(problemSize/SubGridSize);\\
\\
\>\>    // Create partitions\\
\>\>    for (int i=0; i\verb|<|numSubGrids; i++) \{\\
\>\>\>      partitions.addElement(new SubGrid(i));\\
\>\>    \}\\
\\
\>\>    // Configure partition topology\\
\>\>    for (int i=0; i\verb|<|numSubGrids; i++) \{  \\
\>\>\>      current = (SubGrid)partitions.elementAt(i);\\
\>\>\>      if(i\verb|>|(sqrtNumSG-1))\\
\>\>\>\>        current.setSouth((SubGrid)partitions.elementAt(i-sqrtNumSG));\\
\>\>\>      if(i\verb|<|(numSubGrids-sqrtNumSG))\\
\>\>\>\>        current.setNorth((SubGrid)partitions.elementAt(i+sqrtNumSG));\\
\>\>\>      if((i\%sqrtNumSG)!=0)\\
\>\>\>\>        current.setWest((SubGrid)partitions.elementAt(i-1));\\
\>\>\>      if((i\%sqrtNumSG)!=(sqrtNumSG-1))\\
\>\>\>\>        current.setEast((SubGrid)partitions.elementAt(i+1));\\
\>\>    \}\\
\\
\>\>    // Initialize partition values\\
\>\>    for (int i=0; i\verb|<|sqrtNumSG; i++)\\
\>\>\>      for(int j=0; j\verb|<|SubGrid.size+2; j++) \{\\
\>\>\>\>        ((SubGrid)partitions.elementAt(i)).aGrid[0][j] = 5;\\
\>\>\>\>        ((SubGrid)partitions.elementAt(i)).bGrid[0][j] = 5;\\
\>\>\>      \}\\
\\
\>\>    // Create partition association structure\\
\>\>    workPool = new AssociativePool(partitions, waterMark);\\
\\
\>\>    theConfig = new Configuration(...\\
\>\>    theInstance = new ReplicatedWorkers(\=theConfig, workPool, null, \\
\>\>                                        \>numProcessors, numIn);\\
\>\>    theInstance.execute();\\
\>\>    ...\\
\> \}\\
\}
\end{tabbing}}
\end{center}

