\chapter{Applications and Performance}
\label{chap:applications}

\pagestyle{myheadings}
\markright{CHAPTER~\ref{chap:applications}.  APPLICATIONS AND PERFORMANCE} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We have implemented several SPMD style parallel applications using
mpiJava. These applications were included in the mpiJava software
package.     
In this chapter we discuss two parallel Monte Carlo simulations which
can be used for educational purposes and experimental performance
evaluation of mpiJava with a real application.

In the first section, we briefly introduce a Java version of parallel
random number generator which is used in two Monte Carlo spin model
simulations---the Ising model and the Potts model.
Then we discuss 
the mpiJava version of Monte Carlo simulation of the
Ising model implemented with two different algorithms, Metropolis and
cluster algorithms.
This Ising model simulation can be used as a full
application Java benchmark, with comparable native MPI-C and MPI-Fortran
codes for performance comparison. This is presented in the last section.
We also present a graphical Potts model simulation in Section
~\ref{sec:Graph_sim}.  
The Potts model is a generalized extension of the two-state Ising model to an
arbitrary number, Q, of discrete states. It has a 
richer phase structure, which makes it a richer graphical visualization.
%This parallel version of Potts model can be used for 
%education since it has implemented using Java AWT for GUI and also
%provides graphical visualization of updating configurations. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Parallel Random Number Generator}
Random number generators are widely used for simulations in 
computational science and engineering application. For some
Java Grande applications, such Monte Carlo simulations,
it is crucial that the random number generator have good randomness
properties. 
%However in many of the problems for which random numbers are most
%In many of the problems for which random numbers are most
%heavily used, such as Monte Carlo simulation, the quality of the
%random number generator is crucial. 
This is especially true in large-scale simulations on parallel
supercomputers, which consume huge quantities of random numbers, and
require parallel algorithms for random number generation. 
The techniques for testing the quality of parallel random number are
presented in \cite{KO}.

Random number generators use iterative deterministic algorithms for
producing a sequence $X_i$ of pseudo-random numbers that
approximate a truly random sequence.
Probably the most commonly-used algorithms for sequential 
random number generators are Linear Congruential Generators (LCGs).
LCGs produce a sequence $X_{i}$ of random integers using the relation
\begin{equation}
X_{i} = (a * X_{i-1} + b)  \bmod M,
\label{eqn:LCG}
\end{equation}
where $a$ is known as the multiplier, $M$ is the modulus, and $b$ is
an additive constant. If $b=0$, these are termed Multiplicative Linear
Congruential Generators (MLCG).  
The parameters ($a,b,M$) must be chosen carefully to ensure a large
period and good uniformity and randomness properties.  
Standard random number generators return a floating point number $x_{i}$ 
in the interval [0,1), which can be obtained by dividing $X_{i}$
by $M$.  

Many different parallel random number generators have been proposed
\cite{ANDERSON,Coddington},  
but most of them use the same basic concept, which is to parallelize a 
sequential generator by taking the elements of the sequence of 
pseudo-random numbers it generates and distributing them among the 
processors in some way. 
One of the method to achieve this goal is to split
%Another method for parallelizing random number generators is to split
the sequence into non-overlapping contiguous sections, each of which
is generated by a different processor. This also utilizes the fact
that this type of generator allows an arbitrary element of the
sequence to be calculated. One can therefore simply divide the period
of the generator by the number of processors, and jump ahead in the
sequence by this amount for each processor. Alternatively, the length
of each section of numbers could be chosen much larger than could be
used by any processor. If the length of the sections is $L$, then
processor $P$ would generate the sequence
\begin{displaymath} 
X_{PL}, X_{PL+1}, X_{PL+2}, \ldots,  
\end{displaymath}  
This method requires the ability to jump ahead in the sequence by
a given amount.

%A simple way to achieve this goal is for processor $P$ of an $N$
%processor 
%A simple way of generating the same sequence of random numbers for
%different 
Another simple method for parallelizing random number generators is
for processor $P$ of an $N$ processor machine to generate the
sub-sequence 
\begin{displaymath} 
X_{P}, X_{P+N}, X_{P+2N}, \ldots,  
\end{displaymath} 
so that the sequence is spread across processors in the same way as a deck
of cards is dealt in turn to players in a card game. This is known as
the leapfrog technique, since each processor leap-frogs by $N$ in the
sequence. In order to use this method we need to be able to easily
jump ahead in the sequence.
Linear congruential generators are simple enough that it is
possible to specify analytically an arbitrary element in the
sequence. By recursively applying equation ~\ref{eqn:LCG}, it is easy
to show that the element $X_{P+N}$ is given by
\begin{eqnarray}
X_{P+N} &=& (A * X_{P} + B)  \bmod M 
\label{eqn:LCG2}
\end{eqnarray}
with
\begin{eqnarray}
\label{eqn:arbitary}
A &=& a^N  \\
B &=& \sum_{k=0}^{N-1} a^k = (a^N - 1)/(a - 1) \nonumber
\end{eqnarray}
Thus moving through the sequence with stride $N$, rather than 1, is
simply accomplished by specifying a different multiplier and additive
constant for the generator. 
%\afterpage{\clearpage}
\begin{figure}[t]
\footnotesize
%\small
\Line 
\begin{verbatim}
    // Parallel mpiJava MLCG program.

    class Prand { 
      final static int MULT = 1103515245;
      final static int ADD  = 12345;
      final static int MASK = 0x7fffffff; 
      final static double twoto31 = 2147483648.0;
      static long AAA, BBB, randx;

      // Initialize random number generator.
      static void randinit(int seed) {
        AAA = 1;
        BBB = 0;
        for (int proc = 0 ; proc < total_procs ; ++proc) {
          AAA = (MULT * AAA) & MASK;
          BBB = (MULT * BBB + ADD) & MASK;
          if (proc == My_procnum) randx = (AAA*seed + BBB) & MASK;
        }
      }
  
      // Return a random double in [0, 1.0).
      static double rand()  {
        double retvalue = randx / twoto31;
        randx = (AAA*randx+BBB)&MASK;
        return(retvalue);
      }
    }
\end{verbatim}
\normalsize
\Line 
\caption{Parallel Multiplicative Linear Congruential Generators (MLCG).
   \label{prand}}
\end{figure}


In the mpiJava Potts model and Ising model simulations, we use the
parallel MLCG using leapfrog algorithm as shown in Figure \ref{prand}.
The leapfrog method is consequently very easy to implement on a parallel
machine.
The idea is to take a standard linear congruential algorithm, and have
every processor compute the {\it Nth} iterate of that algorithm (where
{\it N} is the number of processors.) \cite{FoxBook88}.
Each node computes random numbers using Eq. \ref{eqn:LCG2} and 
$A$ and $B$ in Eq. \ref{eqn:arbitary} are calculated only once and
stored. The nodes are given a staggered start, so that their sequences don't
overlap. Let the seed, or 0th random number, be denoted by $Y_0$. Using
this as a seed, a sequential computer would compute the sequence:
\begin{eqnarray}
Y_0 &=& Y_0  \\
Y_1 &=& (aY_0 + b) \bmod M \nonumber \\
Y_2 &=& (aY_1 + b) \bmod M \nonumber \\
& \ldots & \nonumber 
\label{eqn:seed}
\end{eqnarray} 

The seeds in the nodes are set as follows (subscripts denote position
in the random number sequence, superscript denote processing node):
\begin{eqnarray}
X^0_0 &=& Y_0  \\
X^1_0 &=& (aY_0 + b) \bmod M = Y_1 \nonumber \\
& \ldots & \nonumber \\
X^{N-1}_0 &=& Y_{N-1} \nonumber 
\label{eqn:seed2}
\end{eqnarray} 

This defines the staggered start. The node now use Eq. \ref{eqn:LCG2}
to compute the next member of each of their sequences. Therefore
\begin{eqnarray}
X^0_1 &=& Y_{0+N} \\
X^1_1 &=& Y_{1+N} \nonumber \\
& \ldots & \nonumber \\ 
X^{N-1}_1 &=& Y_{N-1+N} \nonumber 
\end{eqnarray}  
and,
\begin{eqnarray}
X^0_2 &=& Y_{0+2N} \\
X^1_2 &=& Y_{1+2N} \nonumber \\
& \ldots & \nonumber \\
X^{N-1}_2 &=& Y_{N-1+2N} \nonumber   
\end{eqnarray} 
and so on.

If the seeds are set up properly (staggered) the processors leapfrog
over one another, and it is just as good as having used the basic
algorithm on a sequential machine.  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{The Monte Carlo Simulations of 2-D Potts model}
\section{Monte Carlo Simulations of Spin Models}
Parallel computers have been very successfully applied to the Monte
Carlo simulation of spin models. Here we present an overview of the
Potts spin models and then outline two different methods, Metropolis
and cluster algorithms, that can be applied for Monte Carlo simulation
of many spin models including Potts models.

\subsection{The Potts  Model}
The Potts model \cite{POTTS,WU} encompasses a number of problems in
statistical physics and lattice theory. It generalizes  the
Ising model so that each spin can have more than two components, and
has been a subject of increasingly intense research interest in recent
years. 
It includes the ice-rule vertex and bond percolation models as special
cases.  

The $Q$-state Potts model consists of a lattice of spins
$\sigma_i$, which can take $Q$ different values, and whose Hamiltonian
is  
\begin{equation}
 H \; = \; K \; \sum_{(i,j)} \; \delta_{\sigma_i\sigma_j},
\end{equation}
where the spins take on the values $\sigma_i = 0,1,2,...,Q-1$, and the sum
is over nearest neighbor pairs on sites on a lattice.
%is over nearest neighbor pairs on sites on a lattice, and $\delta$ is
%the Kronecker delta. 
For $Q = 2$, this is equivalent to the Ising model. The Potts model is
thus a simple extension of the Ising model; however, it has a 
richer phase structure, which makes it an important testing ground for
new theories and algorithms in the study of critical phenomena.

{\sf 
\begin{figure}[t]
\Line
\begin{Code}
\Settab
\> 1. \> Select one spin to flip. \\ \\
\> 2. \> Compute the change in energy resulting from this flip. \\ \\
\> 3. \> Calculate the probability $P = exp( - \beta * \Delta E)$ for this
flip. \\ \\
\> 4. \> Generate a random number $r$ between zero and one. \\ \\
\> 5. \> If $\Delta E \le 0$ or $r < P$, flip the spin to one of values
$0,1,...,Q-1$. \\ \\
\> 6. \> Repeat step 1 to 5 over all sites. \\ \\
\> 7. \> Visualize the updated lattice configuration. \\ \\
\> 8. \> Analyze the resulting configuration. 
\end{Code}
\Line  
\caption{The Main Procedure of Potts Model Simulation using Metropolis
Algorithm: One starts with an initial configuration of spins and
repeats these procedures.
\label{metro}}
\end{figure}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The Metropolis Algorithm}

The Metropolis algorithm \cite{METROPOLIS} was invented by Metropolis
et al  in 1953 for sampling an arbitrary probability distribution.
This  algorithm has been very successful and influential
in many areas of Monte Carlo method.

In the Metropolis algorithm, new states or configurations of the
system are found by systematically moving through all the lattice
sites and updating the spin variables.
A new configuration $\phi'$
is generated by updating a single variable in the old configuration
$\phi$ and calculating the change in energy
\begin{equation}
\Delta E = E(\phi') - E(\phi).
\end{equation}
If $\Delta E \le 0$, the change is accepted; if $\Delta E > 0$ the change
is accepted with probability $\exp(- \beta * \Delta E)$, where $\beta$
is the inverse temperature.
In practice, on a computer, this is done by generating a pseudo-random
number $r$ in the interval [0,1) with uniform probability distribution
and accepting the change if $r < \exp(- \beta * \Delta E)$. 
The algorithm is shown in Figure \ref{metro}.
If the variable is updated by a large amount then the change in energy
will be large and the probability of the update being accepted will be
small. Conversely, if the variable is changed by a small amount then
the changes will usually be accepted but their small size will make
exploration of phase space rather slow. 


The Metropolis algorithm for a spin model is well suited to
parallelism, since it is regular---so one can use standard data
decomposition of the lattice onto the processors to get good load
balance, and local---the update of a site depends only on its
nearest neighbors, so only local communication is required. 
%\afterpage{\clearpage}
\begin{figure}[t]
\centerline{\psfig{figure=Figs/redblack2.eps,width=5in}}
\caption{Checkerboard Partition and Blocked Communication.
\label{fig:redblack}}
\end{figure}
On SIMD computers, we cannot update a site and its neighbors at the
same time, since they are dependent on each other, 
and we would violate {\em detailed balance}. Detailed balance is a
sufficient condition for equilibrium probability distribution and
guarantees a valid Monte Carlo procedure. Therefore  each site must
updated separately. However we can partition the lattice into a
checkerboard of red and black sites, and update all the black sites in
parallel (at once), since they are all independent, followed
by all red sites in parallel. This method is known as {\em
red/black} or {\em checkerboard} update. 

On MIMD computers, we do a
checkerboard partitioning of the lattice to do the data communication
as large blocks of spins rather than single spins, by passing all the
edge data to neighboring processors after each red or black
update. This checkerboard partitioning and blocked communication is
illustrated in Figure ~\ref{fig:redblack}.  
This blocked communication greatly reduces the latency time for
communication, thereby improving efficiency. It is also possible to
overlap communications with computation, by computing edge values
first, and sending them while the interior points are being computed. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The Swendsen-Wang Cluster Algorithm}
The previous Metropolis algorithm can perform poorly because the updates
are {\it local}, that is, one spin at a time is updated.
It doesn't always do badly---only near critical points where correlation
length (correlations between spins) and correlation time (correlations  
between successive Monte Carlo configurations) both diverge in an
infinite system.
Cluster algorithms avoid this problem because clusters can be very
large, of the same order as the correlation length. 
They use a clever way of finding large clusters of sites
that can be updated at once.

Cluster algorithms were proposed by Swendsen and Wang \cite{SW} in
1987, for Potts spin models. They have since been generalized to other
models, and other algorithms. In the Swendsen-Wang algorithm, clusters
of spins are created by introducing bonds between neighboring spins
with probability 
\begin{equation}
%P(\sigma_i,\sigma_j) = \delta_{\sigma_i\sigma_j}(1 - \exp^{-\beta})
P(\sigma_i,\sigma_j) = 1 - \exp^{-\beta}
\end{equation}
if the two spins are the same, and zero if they are not.
All such clusters are generated and then updated by choosing a random
new spin value for each cluster and assigning it to all the spins in
that cluster.

A slightly different cluster algorithm has been proposed by Wolff
\cite{WOLFF}. In the Swendsen-Wang algorithm, we generated many
clusters and then flip these clusters. In Wolff algorithm, a spin is
chosen at random and a single cluster constructed around it, using
same bond probabilities as for the Swendsen-Wang algorithm. All
the spins in this cluster are then flipped, i.e, changed to a random
new spin different from the old one.
These parallel Wolff cluster algorithms were developed in several
different languages including C code for the CM-5 using CMMD
\cite{CMMD} which was presented in \cite{BAE}. 


Cluster algorithms have in common the problem of identifying and
labeling the connected clusters of spins. This is very similar to an
important problem in image processing, that of identifying and
labeling the connected components in a binary or multi-colored image
composed of an array of pixels. The only real difference is that in
the spin model case, neighboring sites of the same spin have a certain
{\it probability} of being in the same cluster, while for neighboring
pixels of the same color that probability is one. Unfortunately this is
a large enough difference so that some algorithms which work in image
analysis will not work, or require substantial changes, for spin
models. In our implementation of the Swendsen-Wang cluster algorithm 
for the Ising model, we have used a commonly used cluster
identification algorithm invented by Hoshen and Kopelman.


{\sf 
\begin{figure}[t]
\Line
\begin{Code}
\Settab
\>1.\> Go through each four nearest neighbor connection of the lattice, \\
\> \>  set up a bond between the two neighboring sites $i$ and $j$ \\
\> \>  with probability $p = 1 - \exp^{-\beta}$ only if the spins \\
\> \>  are the same, otherwise $p = 0$.  \\ \\
\>2.\> Identify clusters as a set of sites connected by bonds. \\
\> \>  Two sites are said to be in the same cluster \\
\> \>  if there is a connected path of bonds joining them. \\
\> \>  Every site has to belong to one of the clusters. \\ \\
\>3.\> After the clusters are created, each cluster is assigned a new \\
\> \>  Ising spin chosen with equal probability between +1 and -1. \\ \\
\>4.\> Repeat step 1 to 3 for the next iteration. 
\end{Code}
\Line  
\caption{The Main Procedure of Sequential Swendsen-Wang Algorithm.
\label{fig:sw}}
\end{figure}
}



%\cite{Coddington90} for ants in the labyrinth on MIMD
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Hoshen and Kopelman\label{sec:Hoshen}} 

Hoshen and Kopelman \cite{Hoshen} developed a sequential cluster
identification algorithm which gives each cluster a unique label and
counts the number of sites it contains. Each site $i$ belonging to
cluster $\alpha$ is assigned a cluster label $m^\alpha_i$. The sites
in cluster $\alpha$ may initially be assigned several different
cluster labels.  This is chosen to be the smallest number in the set.
These are given as a set of natural numbers
\{$m^\alpha_1,m^\alpha_2,\ldots,m^\alpha_s,\ldots,m^\alpha_t,\ldots$\}.
In this set only one number is regarded as the {\it proper} cluster
label which we designate as $m^\alpha_s$. This is the smallest number
in the set.

A connection between the label $m^\alpha_t$ at any site, and the
proper cluster cluster label  $m^\alpha_s$, is provided by an array
$N$ as
\{$N(m^\alpha_1),N(m^\alpha_2),\ldots,N(m^\alpha_s),\ldots,N(m^\alpha_t),\ldots$\}.
This is constructed so that $N(m^\alpha_s)$ is the only positive
integer member of the set and
denotes the number of sites in the cluster, while the remaining
$N(m^\alpha_t)$ provide the links between the $N(m^\alpha_t)$ and the
proper cluster label $N(m^\alpha_s)$. To be specific, if a site with label
$m^\alpha_t$ is bonded to a site which has the proper cluster label
$m^\alpha_s$ then
\begin{equation}
N(m^\alpha_t) = -m^\alpha_s\label{eqn:mt}
\end{equation}
However, if a site with label $m^\alpha_p$ is not directly bonded to a
site with the proper cluster label, but is connected to a site with
label $m^\alpha_t$ then
\begin{equation}
N(m^\alpha_p) = -m^\alpha_t\label{eqn:mp}
\end{equation}
Therefore to get the proper cluster label for this site we have to go
through $m^\alpha_t$ using ~\ref{eqn:mp} then ~\ref{eqn:mt}. Similarly
for higher-order indirections, we just need to iterate $-m \leftarrow
N(m)$ until we reach a positive value of $N(m)$, which means that $m$
is the proper cluster label and $N(m)$ the current number of sites in
the cluster. Fortunately in most cases this hierarchy consists to one
or two levels (one or two equations) only \cite{Hoshen}.

In practice the algorithm works as follows. We sweep through the sites
of the lattice looking at neighbors in the negative directions (there
are $d$ of them for a $d$-dimensional lattice). If
site $i$ has no connected neighbors (or none of its neighbors have been
labeled) then it is assigned a new label $S_i = m^\alpha_t$, and
$N(m^\alpha_t) = 1$. If there is only one connected neighbor, at site
$n$ with label $S_n = m^\alpha_r$, say, then $i$ gets the same label
as $n:$ $S_i = m^\alpha_r$, and $N(m^\alpha_t) = N(m^\alpha_t) +
1$. The good feature of this cluster labeling technique becomes
apparent when site $i$ links two or more previously labeled cluster
fragments into a single cluster, that is, when it is bonded to two or
more of its neighbors. No site belonging to any of these cluster
fragments is relabeled (so that once a site is labeled it retains this
label throughout the labeling process)---instead the readjustments
occur within the $N(m^\alpha_t)$. The number of readjusted
$N(m^\alpha_t)$'s for a site is equal to the number of coalescing
cluster fragments at that site. Let us assume that the connected sites
belong to clusters $\alpha,\beta,\gamma,\ldots$ which have proper
cluster labels $m^\alpha_s,m^\beta_s,m^\gamma_s,\ldots$ with
$m^\alpha_s$ being the smallest. These clusters coalesce at $i$ to
form a single larger cluster so we set label $S_i = m^\alpha_s$ and
readjust 
\begin{eqnarray}
N(m^\alpha_s) &=& N(m^\alpha_s)+N(m^\beta_s)+N(m^\gamma_s)+\ldots+1
\nonumber \\
N(m^\beta_s)  &=& -m^\alpha_s \\
N(m^\gamma_s) &=& -m^\alpha_s\label{eqn:ms} \nonumber \\
              &\ldots \nonumber 
\end{eqnarray}
It is this continual readjustment which keeps the hierarchy of
indirections small. As a final stage in the algorithm we can pass
through the lattice a second time setting the label at each site to be
the proper cluster label $m^\alpha_s$. This makes it easier to pick
out the clusters for updating. 
%An illustration of this algorithm for the 4x4 lattice used in Figure
%~\ref{fig:Hog}.  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Parallel Cluster Algorithm} 

A parallel cluster algorithm involves distributing the lattice onto an
array of processors using the usual domain decomposition. Clearly a
sequential algorithm can be used to label the clusters on each
processor, but we also need a procedure for converting these labels to
their correct {\it global} values.
We need to be able to tell many processors, which may be any distance
apart, that some of their clusters are actually the same. Thus we need
to be able to agree on which of many different local labels for a
given cluster should be assigned to be the global cluster label, and
to pass this label to all the processors containing a part of that
cluster. We will discuss one of the methods called {\em self-labeling} 
\cite{Coddington91,Tamayo} for tackling this problem.

\paragraph{Self-labeling\label{naming}}
We shall refer to this algorithm as self-labeling, since each
site figures out which cluster it is in by itself from local
information. We begin by assigning each site $i$ a unique cluster
label $S_i$. In practice this is simply chosen as the position of that
site in the lattice. At each step of the algorithm, in parallel, every
site looks in turn at each of its neighbors in the positive
directions. If it is bonded to a neighboring site $n$ which has a
different cluster label $S_n$, then both $S_i$ and $S_n$ are set to
the minimum of the two. This is continued until nothing changes, by
which time all the clusters will have been labeled with the minimum
initial label of all the sites in the cluster. Note that to check
termination of the algorithm involves each processors sending a
termination flag (finished or nor finished) to every other processor
after each step, which can become very costly for large processor
array.

\afterpage{\clearpage}
\begin{figure}[t]
\leftline{\psfig{figure=Figs/comp_label.eps,width=6in}}
\caption{MIMD Component Labeling. The bonds are shown as the thick
lines.}
\label{fig:comp_label}
\end{figure}

We can improve this method by using faster sequential algorithm, such
as Hoshen and Kopelman mentioned in previous section, to
label the clusters in the sub-lattice on each processor, and then just
use self-labeling on the sites at the edges of each processor to
eventually arrive at the global cluster labels. 
These are illustrated in Figure ~\ref{fig:comp_label}.
The number of steps required to do the self-labeling will depend on
the largest cluster, which at the phase transition will generally span
the entire lattice. 
The phase transition (or critical point) for the Ising or Potts model
is the point where the system changes from an ordered phase (where the
spins tend to align) to a disordered phase (where they tend to have a
random direction).\footnote{In a real physical system, this is similar
to the change from a magnetized to an unmagnetized state in a magnetic
material such as iron, or to the change from a solid phase (e.g. ice)
to a liquid phase (e.g. water).}
The number of self-labeling steps will therefore be of the order of
the maximum distance between processors, which for a square array of
$P$ processors is just $2\sqrt{P}$. Hence the amount of communication
(and calculation) involved in doing the self-labeling, which is
proportional to the number of iterations times the perimeter of the
sub-lattice, goes like $L$ for an $L \times L$ lattice, whereas the
time taken on each processor to do the local cluster labeling goes
like the area of the sub-lattice, which is $L^2/P$. Therefore as long
as $L$ is substantially greater than the number of processors we can
expect to obtain a reasonable speedup.


%C   Hoshen-Kopelmann algorithm for labeling connected clusters
%C   (J. Hoshen and R. Kopelman, Phys. Rev. B 14 (1976) 3438).
%C
%C   Every site has a pointer N. If this pointer is negative, then 
%C   it points to the label of the root site of the cluster. If it
%C   is positive, then the site is the root, and N refers to the 
%C   number of sites in the cluster, and the label is the given by
%C   the original label of that site. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Graphical Simulation\label{sec:Graph_sim} }

An mpiJava application that performs a Potts Model Monte Carlo
simulation using parallel Metropolis algorithms in two dimensions
running on four processors is shown in Figure \ref{pottsdemo}.     
One of the good feature of mpiJava is that users have full
access to the Java AWT and other Java graphical packages to support GUI
and visualize graphical output of application.  
Visualization of the collected data is a critical element in providing
developers or educators with the needed insight into the system
under study.  
In this Potts model simulation, the different colors represent the Q
different spin states on a lattice. All the options of the simulation
are customizable through a GUI. Processor $P_0$ handles all GUI
input and visualization of output data.  
When users run simulation by clicking start button, input values are
broadcast to other processors and then, after the processors generate
a new configuration, processor $P_0$ gathers all updated data to
plot the output in order to visualize the results.
Measurements of standard quantities such as energy and magnetization
are easily done in parallel by just calculating the quantities locally,
sum over sites in each processor, and then combining the partial sums from
all processors using {\tt MPI.Allreduce}. 

\begin{figure}[t]
\centerline{\epsfig{figure=Figs/pottsdemo.ps,width=5.7in}}
\caption{ The Potts Model Monte Carlo Simulation.\label{pottsdemo}}
\end{figure}

In this demo, the total number of processors is broken up into a 2D grid,
in X and Y directions.
Users can also choose data distribution as row-, column- or block-wise
by selecting the nodes in X direction option in GUI. 
This option is set after the number of
running processors is given at the starting time by execution command 
as follows;
\begin{verbatim}
     prunjava 4 Potts
\end{verbatim}
The \texttt{prunjava} script is a wrapper for the MPICH
\texttt{mpirun} script. The first argument is the number of processors
on which the program will be executed.  
The number of nodes in Y direction is set automatically by total
number of running nodes and the number of nodes in X direction specified
in the GUI.  
A list of available host computers may be given in an MPICH-style
{\tt machines} file in the local directory.

From this simulation, one is able to determine the average
magnetization, the average energy, and the specific heat of the system.
%and numerous other quantities which are experimentally observable.

%reduces the number of red spins. The window is also resizeable. More
%features are coming.  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Ising Model Evaluation\label{ISING_PERORMANCE} }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%We used Ising model Monte Carlo simulation to compare experimental
%performance of mpiJava with that of native MPI-C and MPI-FORTRAN77
%codes.
In this section we evaluate the performance of some applications written in
mpiJava. 
We have developed both sequential and parallel message passing
programs to compare the performance of mpiJava using Monte Carlo
simulation of the two dimensional Ising model.
The sequential programs were written in C, F77 and Java and message
passing programs were written in MPI-C, MPI-F77 and mpiJava.
This Ising model test can also be used for testing the quality of
parallel random number generators ~\cite{KO}.

The two different methods, Metropolis and Swendsen-Wang cluster
algorithms are used with a standard block domain decomposition. As in
Potts model, the red/black updating scheme is used in parallel
Metropolis Ising model simulation ~\cite{FoxBook88}.  

Metropolis is easy to parallelize since it is just local nearest
neighbor communication and standard domain decomposition so it's easy
to load balance, Swendsen-Wang needs non-local communication and has
fairly good load balance.  Therefore we would expect Metropolis to
give the best speedups, then Swendsen-Wang would be not quite as good.
%The metropolis algorithm is regular and local and can
%therefore be easily and efficiently parallelizes using message passing
%language. 


%\subsubsection{Evaluation}
The system environment was as follows:
\begin{itemize} 
\item {CPU: Four dual processor (UltraSparc 200 MHz)  Solaris
workstations with 256 MBytes of DRAM. Each of the two
processors/system has 1MB cache. } 
\item {OS: Solaris 2.5.1 }
\item {Network: 10BaseT Ethernet and SunATM-155/MFiber}
\item {Java VM: Sun's JIT}
\item {Java Compiler: Sun JDK1.2.2}
\item {MPI packages: MPICH1.2.0 and Sun HPC MPI 2.0}
\end{itemize}

%Sequential F77, C and Java versions of the benchmark were also
%measured for comparision. 
For comparison, we have completed experiments for three different
versions of our programming environment---sequential codes, parallel
codes with MPICH and Sun HPC MPI.  
For the sequential F77 and C codes, we use Sun WorkShop FORTRAN 77 5.0
and C 5.0 compilers and Sun JDK1.2.2 for sequential Java code.
For the parallel mpiJava codes, we use MPICH 1.2.0 and Sun HPC MPI 2.0
on 1, 2, 4 and 8 nodes. The MPICH 1.2.0 was compiled with
\texttt{-comm=shared} communication option to permit the use
of communication using both shared memory and TCP/IP, since each
of four our Solaris machines has dual processors. Sun HPC MPI uses the Sun
ATM network which is much faster than p4 device of MPICH. 
For better performance, all sequential and parallel Fortran, C and
Java codes were compiled using \texttt{-O} optimization option and all 
sequential Java and mpiJava codes executed with JIT enabled.

We performed Monte Carlo Ising simulations on simple 2-D lattices with
linear size of L=32 to 1024 and periodic boundary conditions. 
To measure the total execution time, we performed 20 iterations to
thermalize the system and at least 2000  Monte Carlo sweeps. The
inverse temperature $\beta$ was taken to be the critical inverse
temperature $\beta_c = \log(1+\sqrt{2})/2 \approx 0.4406868$ for
the 2-D Ising model.
Timings were measured using \texttt{MPI\_Wtime} for parallel codes and the shell
built-in \texttt{time} command for sequential codes. We have repeated 
the benchmarks several times when there was little network activity
and on quiet machines.

The Metropolis timing results for sequential and parallel tests for different
lattice sizes are shown in Figure ~\ref{fig:met32} through
\ref{fig:met1024} and Swendsen-Wang in Figure ~\ref{fig:sw32} through
\ref{fig:sw1024}.
The results demonstrate as follows;
\begin{itemize} 

\item {\bf MPICH vs SunHPC} \\
In both Metropolis and Swendsen-Wang (SW), for small lattice size $L \le
64$ on node $N \ge 2$, the performance of the mpiJava benchmarks is better
with Sun HPC MPI than MPICH due to faster communication device. On the
other hand, for the larger lattice size $L \ge 512$, the performance
difference is much smaller between SunHPC and MPICH, since the main
overhead is in the computations rather than communications as the size
of sub-lattice increases. 

\item {\bf mpiJava vs serial codes} \\
The sequential Java code is slower than the sequential Fortran and C
codes (see Table \ref{tab:met_ratios} and \ref{tab:sw_ratios}), i.e
the computation time is longer.
%, so we might expect that the mpiJava
%code would give better speeds up than the C and Fortran codes.
The speedup obtained for a variety of lattice sizes using the mpiJava,
as compared with sequential Java, are shown in
Figure ~\ref{fig:met_speedup} and ~\ref{fig:sw_speedup}.
In Metropolis, mpiJava is faster than sequential Java for $L \ge 128$
on $N \ge 2$.
On the largest lattice size plotted ($1024 \times 1024$), mpiJava
provides a speedup up to 5.9 (Metropolis) and
5.2 (SW) over sequential Java on 8 processors. 
Comparing the performance of mpiJava with F77 or C, mpiJava with
SunHPC provides a speedup up to 2.4 (Metropolis) and
4.6 (SW) over sequential F77 and, 2.1 (Metropolis) and 3.7(SW) over
sequential C for $L =1024$ on 8 processors.  
%In Metropolis, mpiJava code is also faster than sequential C or F77 codes
%for $L \ge 256$ on $N = 8$ or $L \ge 512$ on   $N \ge 4$. 
%In Swendsen-Wang, mpiJava code is faster
%than Java for $L \ge 128$ on $N = 8$ or $L \ge 256$ on $N \ge 2$,
%than C for $L \ge 512$ on $N = 8$ and 
%than F77 for $L \ge 512$ on $N \ge 4$ or $L = 1024$ on $N \ge 2$.

\item {\bf mpiJava vs MPI F77 or C} \\
%It is interesting to compare the results of benchmarks written in Java
%with equivalent C or Fortran code.
It is not surprising that mpiJava has lower performance than MPI F77
or C since the performance of Java integer operations, floating point
arithmetic and access of array elements is slower than the performance
of native C or Fortran code \cite{Coddington_javabench}. 
In addition, mpiJava uses wrapper routines to interface between the
Java and the C routines that introduce additional overhead. This
includes message startup latencies discussed in section \ref{sec:startup}.

The sequential and parallel Java to F77 and Java to C run time ratios
of Metropolis and Swendsen-Wang are shown in Table ~\ref{tab:met_ratios}
and ~\ref{tab:sw_ratios} respectively.
It shows that the performance difference between mpiJava and MPI F77 or 
C decreases as the number of processors increases, because 
the main overhead is in the communications rather than computations. 
Relatively the mpiJava codes perform best when $L = 32$ on 8 nodes. 
For this case the execution times are only 8--14\% longer than MPICH
F77 or C, but in this case absolute performance is poor because this
is the regime where communication overhead dominate.
%parallel efficiency decreases as the number of processors increases.
For the largest lattice size $L = 1024$, the results demonstrate that
the performance of the mpiJava is within a factor of two to three of
MPI F77 or C. 
Comparing the performance of mpiJava with MPI F77 or C, it is promising, 
but not acceptable yet. 
An interesting series of papers from IBM
\cite{Moreira98A,Moreira98B,Wu99}, confirmed that the current
generation of Java virtual machines have rather poor performance on
Fortran-like, array-intensive computations, but went on to demonstrate
how to apply aggressive optimizations in Java compilers to obtain
performance competitive with Fortran.
In a recent paper \cite{Moreira99} they described a case study
involving a data mining application that used the Java Array package
supported by the Java Grande Numerics Working Group.  Using the
experimental IBM HPCJ Java compiler they reported obtaining over 90\%
of the performance of Fortran. Therefore we expect that in the future
Java will became quite competive with Fortran.

%For Swendsen-Wang benchmarks, the MPI F77 and C codes are only about
%twice as fast as mpiJava version for the largest lattice size $L =
%1024$.
%It is evident from Fig 2 that mpiJava Metropolis excution times are
%only 5-10% longer than mpi-F77 times.

\end{itemize}


%\afterpage{\clearpage}
\begin{figure}[t]
\centerline{\psfig{figure=Figs/met32log.eps,width=5in}}
\caption{Metropolis Performance with Lattice Size $32^2$.}
\label{fig:met32}

\bigskip \bigskip \bigskip
\centerline{\psfig{figure=Figs/met64log.eps,width=5in}}
\caption{Metropolis Performance with Lattice Size $64^2$.}
\label{fig:met64}
\end{figure}

\afterpage{\clearpage}
\begin{figure}[t]
\centerline{\psfig{figure=Figs/met128log.eps,width=5in}}
\caption{Metropolis Performance with Lattice Size $128^2$.}
\label{fig:met128}

\bigskip \bigskip \bigskip
\centerline{\psfig{figure=Figs/met256log.eps,width=5in}}
\caption{Metropolis Performance with Lattice Size $256^2$.}
\label{fig:met256}
\end{figure}

\afterpage{\clearpage}
\begin{figure}[t]
\centerline{\psfig{figure=Figs/met512log.eps,width=5in}}
\caption{Metropolis Performance with Lattice Size $512^2$.}
\label{fig:met512}

\bigskip \bigskip \bigskip
\centerline{\psfig{figure=Figs/met1024log.eps,width=5in}}
\caption{Metropolis Performance with Lattice Size $1024^2$.}
\label{fig:met1024}
\end{figure}

\afterpage{\clearpage}
\begin{figure}[t]
\centerline{\psfig{figure=Figs/sw32log.eps,width=5in}}
\caption{Swendsen-Wang Performance with Lattice Size $32^2$.}
\label{fig:sw32}

\bigskip \bigskip \bigskip
\centerline{\psfig{figure=Figs/sw64log.eps,width=5in}}
\caption{Swendsen-Wang Performance with Lattice Size $64^2$.}
\label{fig:sw64}
\end{figure}

\afterpage{\clearpage}
\begin{figure}[t]
\centerline{\psfig{figure=Figs/sw128log.eps,width=5in}}
\caption{Swendsen-Wang Performance with Lattice Size $128^2$.}
\label{fig:sw128}

\bigskip \bigskip \bigskip
\centerline{\psfig{figure=Figs/sw256log.eps,width=5in}}
\caption{Swendsen-Wang Performance with Lattice Size $256^2$.}
\label{fig:sw256}
\end{figure}

\afterpage{\clearpage}
\begin{figure}[t]
\centerline{\psfig{figure=Figs/sw512log.eps,width=5in}}
\caption{Swendsen-Wang Performance with Lattice Size $512^2$.}
\label{fig:sw512}

\bigskip \bigskip \bigskip
\centerline{\psfig{figure=Figs/sw1024log.eps,width=5in}}
\caption{Swendsen-Wang Performance with Lattice Size $1024^2$.}
\label{fig:sw1024}
\end{figure}

\afterpage{\clearpage}
\begin{figure}[t]
\centerline{\psfig{figure=Figs/met_speedup.eps,width=5in}}
\caption{Speedup of Metropolis by using mpiJava as compared with serial Java.}
\label{fig:met_speedup}

\bigskip \bigskip \bigskip
\centerline{\psfig{figure=Figs/sw_speedup.eps,width=5in}}
\caption{Speedup of Swendsen-Wang by using mpiJava as compared with serial Java.}
\label{fig:sw_speedup}
\end{figure}


\begin{table}[t]
\begin{tabular}{| c | c|c | c|c || c|c |}  \cline{2-7}
\multicolumn{1}{c|}{} &\multicolumn{2}{c|}{SunHPC}&\multicolumn{2}{c||}{MPICH} &\multicolumn{2}{c|}{Sequential} \\ \cline{1-7}   
Nodes &Java/F77  &Java/C &Java/F77  &Java/C &Java/F77  &Java/C \\
\hline\hline \cline{1-7} 
\multicolumn{7}{c}{} \\ \cline{1-7}
\multicolumn{7}{|c|}{$L=32^2$} \\ \cline{1-7} 
2 & 5.17 & 3.33 & 2.80 & 2.34 & 3.86 & 3.14 \\ \cline{1-7} 
4 & 2.25 & 2.00 & 1.20 & 1.21 &\multicolumn{2}{c}{} \\ \cline{1-5}
8 & 1.34 & 1.23 & 1.13 & 1.14 &\multicolumn{2}{c}{} \\ \cline{1-5}
%\end{tabular}              
%\caption{ 32\label{tab:met32}}
%\end{table}

%\begin{table}[t]
%\begin{tabular}{| c | c|c | c|c || c|c |}  \cline{2-7}
%\multicolumn{1}{c|}{} &\multicolumn{2}{c|}{SunHPC}&\multicolumn{2}{c||}{MPICH} &\multicolumn{2}{c|}{Sequential} \\ \cline{1-7}   
%Nodes &Java/F77  &Java/C &Java/F77  &Java/C &Java/F77  &Java/C \\ \cline{1-7}
\multicolumn{7}{c}{} \\ \cline{1-7}
\multicolumn{7}{|c|}{$L=64^2$} \\ \cline{1-7} 
2 & 4.71 & 2.74 & 3.57 & 2.37 & 3.51 & 2.87 \\ \cline{1-7} 
4 & 2.69 & 2.06 & 1.59 & 1.47 &\multicolumn{2}{c}{} \\ \cline{1-5}
8 & 1.99 & 1.57 & 1.42 & 1.22 &\multicolumn{2}{c}{} \\ \cline{1-5}
%\end{tabular}              
%\caption{ 64\label{tab:met64}}
%\end{table}

%\begin{table}[t]
%\begin{tabular}{| c | c|c | c|c || c|c |}  \cline{2-7}
%\multicolumn{1}{c|}{} &\multicolumn{2}{c|}{SunHPC}&\multicolumn{2}{c||}{MPICH} &\multicolumn{2}{c|}{Sequential} \\ \cline{1-7}   
%Nodes &Java/F77  &Java/C &Java/F77  &Java/C &Java/F77  &Java/C \\
%\cline{1-7} 
\multicolumn{7}{c}{} \\ \cline{1-7}
\multicolumn{7}{|c|}{$L=128^2$} \\ \cline{1-7} 
2 & 4.52 & 2.60 & 4.00 & 2.42 & 3.33 & 2.74 \\ \cline{1-7} 
4 & 3.43 & 2.33 & 2.18 & 1.79 &\multicolumn{2}{c}{} \\ \cline{1-5}
8 & 2.48 & 2.08 & 1.67 & 1.54 &\multicolumn{2}{c}{} \\ \cline{1-5}
%\end{tabular}              
%\caption{ 128\label{tab:met128}}
%\end{table}

%\begin{table}[t]
%\begin{tabular}{| c | c|c | c|c || c|c |}  \cline{2-7}
%\multicolumn{1}{c|}{} &\multicolumn{2}{c|}{SunHPC}&\multicolumn{2}{c||}{MPICH} &\multicolumn{2}{c|}{Sequential} \\ \cline{1-7}   
%Nodes &Java/F77  &Java/C &Java/F77  &Java/C &Java/F77  &Java/C \\
%\cline{1-7} 
\multicolumn{7}{c}{} \\ \cline{1-7}
\multicolumn{7}{|c|}{$L=256^2$} \\ \cline{1-7} 
2 & 3.94 & 2.18 & 4.05 & 2.36 & 3.30 & 2.75 \\ \cline{1-7} 
4 & 3.88 & 2.29 & 2.72 & 1.90 &\multicolumn{2}{c}{} \\ \cline{1-5}
8 & 3.07 & 2.08 & 2.40 & 1.84 &\multicolumn{2}{c}{} \\ \cline{1-5}
%\end{tabular}              
%\caption{ 256\label{tab:met256}}
%\end{table}

%\begin{table}[t]
%\begin{tabular}{| c | c|c | c|c || c|c |}  \cline{2-7}
%\multicolumn{1}{c|}{} &\multicolumn{2}{c|}{SunHPC}&\multicolumn{2}{c||}{MPICH} &\multicolumn{2}{c|}{Sequential} \\ \cline{1-7}   
%Nodes &Java/F77  &Java/C &Java/F77  &Java/C &Java/F77  &Java/C \\
%\cline{1-7} 
\multicolumn{7}{c}{} \\ \cline{1-7}
\multicolumn{7}{|c|}{$L=512^2$} \\ \cline{1-7} 
2 & 3.33 & 2.20 & 3.31 & 2.23 & 3.01 & 2.73 \\ \cline{1-7} 
4 & 3.56 & 2.21 & 2.96 & 2.02 &\multicolumn{2}{c}{} \\ \cline{1-5}
8 & 3.38 & 2.17 & 2.83 & 2.00 &\multicolumn{2}{c}{} \\ \cline{1-5}
%\end{tabular}              
%\caption{ 512\label{tab:met512}}
%\end{table}

%\begin{table}[t]
%\begin{tabular}{| c | c|c | c|c || c|c |}  \cline{2-7}
%\multicolumn{1}{c|}{} &\multicolumn{2}{c|}{SunHPC}&\multicolumn{2}{c||}{MPICH} &\multicolumn{2}{c|}{Sequential} \\ \cline{1-7}   
%Nodes &Java/F77  &Java/C &Java/F77  &Java/C &Java/F77  &Java/C \\ \cline{1-7} 
\multicolumn{7}{c}{} \\ \cline{1-7}
\multicolumn{7}{|c|}{$L=1024^2$} \\ \cline{1-7} 
2 & 2.73 & 2.08 & 2.66 & 2.07 & 2.43 & 2.71 \\ \cline{1-7} 
4 & 2.84 & 2.14 & 2.67 & 2.03 &\multicolumn{2}{c}{} \\ \cline{1-5}
8 & 2.85 & 2.11 & 2.71 & 2.02 &\multicolumn{2}{c}{} \\ \cline{1-5}
\end{tabular}              
\caption{ Metropolis : Comparing Java with F77 and C.\label{tab:met_ratios}}
\end{table}

%%% SW %%%%%%%%%%%%%%%%%%%%%%

\begin{table}[t]
\begin{tabular}{| c | c|c | c|c || c|c |}  \cline{2-7}
\multicolumn{1}{c|}{} &\multicolumn{2}{c|}{SunHPC}&\multicolumn{2}{c||}{MPICH} &\multicolumn{2}{c|}{Sequential} \\ \cline{1-7}   
Nodes &Java/F77  &Java/C &Java/F77  &Java/C &Java/F77  &Java/C \\
\hline\hline \cline{1-7} 
\multicolumn{7}{c}{} \\ \cline{1-7}
\multicolumn{7}{|c|}{$L=32^2$} \\ \cline{1-7} 
2 & 5.16 & 3.49 & 2.37 & 2.13 & 3.60 & 3.48 \\ \cline{1-7} 
4 & 2.27 & 2.10 & 1.11 & 1.10 &\multicolumn{2}{c}{} \\ \cline{1-5}
8 & 1.43 & 1.39 & 1.08 & 1.08 &\multicolumn{2}{c}{} \\ \cline{1-5}
%\end{tabular}              
%\caption{ 32\label{tab:sw32}}
%\end{table}

%\begin{table}[t]
%\begin{tabular}{| c | c|c | c|c || c|c |}  \cline{2-7}
%\multicolumn{1}{c|}{$L=64^2$} &\multicolumn{2}{c|}{SunHPC}&\multicolumn{2}{c||}{MPICH} &\multicolumn{2}{c|}{Sequential} \\ \cline{1-7}   
%Nodes &Java/F77  &Java/C &Java/F77  &Java/C &Java/F77  &Java/C \\ \cline{1-7} 
\multicolumn{7}{c}{} \\ \cline{1-7}
\multicolumn{7}{|c|}{$L=64^2$} \\ \cline{1-7}
2 & 4.27 & 2.71 & 2.92 & 2.21 & 3.29 & 3.13 \\ \cline{1-7} 
4 & 2.37 & 2.11 & 1.24 & 1.22 &\multicolumn{2}{c}{} \\ \cline{1-5}
8 & 1.80 & 1.64 & 1.14 & 1.15 &\multicolumn{2}{c}{} \\ \cline{1-5}
%\end{tabular}              
%\caption{ 64\label{tab:sw64}}
%\end{table}

%\begin{table}[t]
%\begin{tabular}{| c | c|c | c|c || c|c |}  \cline{2-7}
%\multicolumn{1}{c|}{$L=128^2$} &\multicolumn{2}{c|}{SunHPC}&\multicolumn{2}{c||}{MPICH} &\multicolumn{2}{c|}{Sequential} \\ \cline{1-7}   
%Nodes &Java/F77  &Java/C &Java/F77  &Java/C &Java/F77  &Java/C \\ \cline{1-7} 
\multicolumn{7}{c}{} \\ \cline{1-7}
\multicolumn{7}{|c|}{$L=128^2$} \\ \cline{1-7}
2 & 3.75 & 2.39 & 3.24 & 2.24 & 3.21 & 3.18 \\ \cline{1-7} 
4 & 2.88 & 2.08 & 1.51 & 1.38 &\multicolumn{2}{c}{} \\ \cline{1-5}
8 & 2.07 & 1.74 & 1.33 & 1.30 &\multicolumn{2}{c}{} \\ \cline{1-5}
%\end{tabular}              
%\caption{ 128\label{tab:sw128}}
%\end{table}

%\begin{table}[t]
%\begin{tabular}{| c | c|c | c|c || c|c |}  \cline{2-7}
%\multicolumn{1}{c|}{$L=256^2$} &\multicolumn{2}{c|}{SunHPC}&\multicolumn{2}{c||}{MPICH} &\multicolumn{2}{c|}{Sequential} \\ \cline{1-7}   
%Nodes &Java/F77  &Java/C &Java/F77  &Java/C &Java/F77  &Java/C \\ \cline{1-7} 
\multicolumn{7}{c}{} \\ \cline{1-7}
\multicolumn{7}{|c|}{$L=256^2$} \\ \cline{1-7}
2 & 3.07 & 2.31 & 3.16 & 2.41 & 2.63 & 3.18 \\ \cline{1-7} 
4 & 3.10 & 2.12 & 2.00 & 1.67 &\multicolumn{2}{c}{} \\ \cline{1-5}
8 & 2.57 & 1.99 & 1.59 & 1.47 &\multicolumn{2}{c}{} \\ \cline{1-5}
%\end{tabular}              
%\caption{ 256\label{tab:sw256}}
%\end{table}

%\begin{table}[t]
%\begin{tabular}{| c | c|c | c|c || c|c |}  \cline{2-7}
%\multicolumn{1}{c|}{$L=512^2$} &\multicolumn{2}{c|}{SunHPC}&\multicolumn{2}{c||}{MPICH} &\multicolumn{2}{c|}{Sequential} \\ \cline{1-7}   
%Nodes &Java/F77  &Java/C &Java/F77  &Java/C &Java/F77  &Java/C \\ \cline{1-7} 
\multicolumn{7}{c}{} \\ \cline{1-7}
\multicolumn{7}{|c|}{$L=512^2$} \\ \cline{1-7}
2 & 2.52 & 2.32 & 2.57 & 2.39 & 1.73 & 2.98 \\ \cline{1-7} 
4 & 2.45 & 2.12 & 2.03 & 1.86 &\multicolumn{2}{c}{} \\ \cline{1-5}
8 & 2.44 & 2.08 & 1.84 & 1.71 &\multicolumn{2}{c}{} \\ \cline{1-5}
%\end{tabular}              
%\caption{ 512\label{tab:sw512}}
%\end{table}


%\begin{table}[t]
%\begin{tabular}{| c | c|c | c|c || c|c |}  \cline{2-7}
%\multicolumn{1}{c|}{$L=1024^2$} &\multicolumn{2}{c|}{SunHPC}&\multicolumn{2}{c||}{MPICH} &\multicolumn{2}{c|}{Sequential} \\ \cline{1-7}   
%Nodes &Java/F77  &Java/C &Java/F77  &Java/C &Java/F77  &Java/C \\ \cline{1-7} 
\multicolumn{7}{c}{} \\ \cline{1-7}
\multicolumn{7}{|c|}{$L=1024^2$} \\ \cline{1-7}
2 & 1.83 & 2.15 & 1.98 & 2.35 & 1.14 & 2.90 \\ \cline{1-7} 
4 & 1.87 & 2.04 & 1.76 & 1.96 &\multicolumn{2}{c}{} \\ \cline{1-5}
8 & 1.85 & 2.07 & 1.84 & 2.03 &\multicolumn{2}{c}{} \\ \cline{1-5}
\end{tabular}              
\caption{ Swendsen-Wang  : Comparing Java with F77 and C.\label{tab:sw_ratios}}
\end{table}


