\documentstyle[11pt]{article}

\input epsf

\begin{titlepage}

\baselineskip=18pt


\begin{center}

{\Huge 
CSE763  Project\\}
\bigskip
\bigskip
{\LARGE \bf
Parallel Wolff Cluster Algorithms for Two-Dimension Spin Model\\}
\bigskip
\bigskip

{\Large 
Sung-Hoon Ko\\}
{\large \sl
(shko@npac.syr.edu)}

\smallskip
\bigskip
{\it
School of Computer Science, Syracuse University,\\
111 College Place, Syracuse, NY 13244, U.S.A.\\}
%

\smallskip
\bigskip
April, 1994 \\
\end{center}
\bigskip


\vspace{1.0in}

\begin{abstract}
\noindent
The Wolff single-cluster algorithm is the most efficient method known
for Monte Carlo simulation of many spin models. 
Due to the irregular size, shape and position of the Wolff clusters,
this method does not easily lend itself to efficient parallel
implementation, so that simulations using this method have thus far
been confined to workstations and vector machines.
Here two parallel implementations of this algorithm(SIMD and MIMD) 
are presented, and show that one gives fairly good performance on 
a MIMD parallel computer. To improve load balance on MIMD machine,
scattered domain(cyclic) decomposition is adopted in this project.

\end{abstract}

\end{titlepage}

\vspace{1.0in}

\textwidth=5.5in
\textheight=8.5in
\topmargin=-0.5in
\oddsidemargin=0.25in

\begin{document}

\baselineskip=17pt

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Monte Carlo simulation is a very important numerical method for 
studying spin models in physics~\cite{MONTECARLO}. However, 
the performance of traditional Monte Carlo algorithms, 
like Metropolis algorithm\cite{MONTECARLO,METROPOLIS}, is poor. 
One of the acceleration 
algorithms to overcome poor performance and accelerate the 
dynamics of Monte Carlo update are Cluster algorithms
~\cite{SOKALREV,LAT89REV,SWREV,CLIVEREV}.

Cluster algorithms are non-local Monte Carlo update schemes 
which can greatly increase the efficiency of computer simulation 
of spin models. The most well known sequential algorithms in 
Monte Carlo cluster update algorithms are Swendsen-Wang algorithm 
~\cite{SW} and Wolff algorithm~\cite{WOLFF}.

The Wolff single cluster algorithm is a variation of the Swendsen-Wang 
cluster algorithm for the Ising model. 

In the Swendsen-Wang algorithm for the Ising model, 
bonds are placed with probability ${1-e^{-2\beta}}$ between 
all neighboring sites of the lattice that have the same spin value,
where $\beta$ is the inverse temperature parameter.
This procedure creates clusters of bonded sites of the same spin.
The spins are updated by assigning a random spin value to each
cluster.

In the Wolff algorithm, only a single cluster is created.
A site is chosen at random and a cluster is constructed around it,
using the same bond probabilities as for the Swendsen-Wang algorithm.
All the spins in this cluster are then flipped, that is, collectively
changed to the alternate spin value. 

However, cluster algorithms which are non-local algorithms are more 
difficult to implement efficiently on parallel machines than local 
algorithms such as Metropolis algorithm. Specially, parallel Wolff 
algorithm suffers from irregular communication and load imbalance 
because the cluster is very irregular in size and shape although 
only one cluster is grown during one sweep. To improve load balance
on MIMD machine, scattered(cyclic) domain decomposition is adopted 
in this project.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Computational Algorithms}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The major computational task for the Swendsen-Wang algorithm is the
identification and labeling of the clusters of connected sites, 
given the configuration of bonds. 
This is an instance of a connected component labeling problem
for an undirected graph~\cite{COMPSCI}, where the vertices are the 
lattice sites and the edges are the bonds between connected sites.
The goal of the component labeling algorithm is to end up with the 
same label on all connected sites, and different labels for all 
disconnected clusters.

A number of methods have been developed for implementing the 
Swendsen-Wang algorithm on parallel
\cite{BURKITT,DMCC5,CPE,BROWER,TAMAYO,SIMDLETTER,SIMDPAPER,ROSSI}
and vector~\cite{MINO} computers.
Most of these methods are variations on parallel algorithms that
were developed for the general problem of connected component 
labeling of a graph~\cite{SHIVISH,EMBRECHTS,WOO}.  
Parallel Swendsen-Wang algorithms can be quite efficient,
especially for large lattice sizes on coarse-grain MIMD machines.
The Swendsen-Wang algorithm seems inherently better suited to a
parallel implementation than the Wolff algorithm, since clusters
are constructed for all the sites in the lattice, so a data 
parallel algorithm using standard domain 
decomposition~\cite{THEBOOK} can be used. 
This is not the case for the Wolff algorithm,
for which only a (random) subset of the sites are updated at 
every iteration, so a standard domain decomposition would give
extremely poor load balance between processors.

Constructing (or labeling) a single cluster of connected sites is 
done sequentially by a simple breadth-first-search 
algorithm~\cite{WOLFF,COMPSCI,CPE,ANTS,EVERTZ}.
Two data structures are used:
a list {\tt C} of sites that belong to the 
cluster and a queue {\tt Q} of sites that have been added to the cluster
but not yet used in the search.
The algorithm is described by the pseudo-code in 
Fig.~\ref{fig:SeqAnts}.

\begin{figure}[tbh]
\vspace{6mm}
\begin{tabbing}
xx\=xx\=xx\=xx\=XXXXXXXXXXXXXXXXXXXXXXXXXXX\= \kill
 \>  Chose a site {\tt i} at random 
\>\>\>\>  {\it First site in the cluster} \\
 \>  {\tt C $\leftarrow$ \{i\} }
\>\>\>\>  {\it Initialize the cluster list} \\
 \>  {\tt Q $\leftarrow$ \{i\} }
\>\>\>\>  {\it Initialize the queue} \\
 \>  {\tt WHILE Q $\neq$ \{\} DO }
\>\>\>\>  {\it Search over sites still in queue} \\
 \>  \>  {\tt j $\leftarrow\:$} next element in {\tt Q}
\>\>\>    {\it Get the next site from the queue} \\
 \>  \>  {\tt Q $\leftarrow$ Q - j}
\>\>\>    {\it Remove this site from the queue} \\
 \>  \>  Find the set {\tt\{n\}} of connected neighbors of {\tt j} 
\>\>\>    {\it Identify bonds to neighbors} \\
 \>  \>  {\tt FOR} each {\tt n $\!\epsilon\!$ \{n\} DO}
\>\>\>        {\it For all connected neighbors} \\
 \>  \>  \>  {\tt IF n $\!\not\!\epsilon\!$ C THEN} 
\>\>          {\it If neighbor is not in cluster list} \\
 \>  \>  \>  \>  {\tt C $\leftarrow$ C + n}
\>              {\it Add it to the cluster list} \\
 \>  \>  \>  \>  {\tt Q $\leftarrow$ Q + n}
\>              {\it Add it to the queue} \\
 \>  \>  \>  {\tt END IF} \\
 \>  \>  {\tt END DO} \\
 \>  {\tt END WHILE} \\
\end{tabbing}
%\vspace*{2cm}
\protect\caption{\protect\label{fig:SeqAnts}
The breadth-first-search algorithm for creating a single cluster.
For the Wolff algorithm, the spin is also changed to the new value 
($s_n \leftarrow - s_n$ for the Ising model) 
when a site $n$ is added to the cluster.
}
%\vspace{1cm}
\end{figure}

The sites in the queue can be visualized as a ``wavefront''
expanding outwards from the initial site. 
It is possible to rewrite the loop over sites in the queue as
a double loop: one loop over all sites in a particular wavefront,
and another loop over successive wavefronts. 

We will refer to these successive wavefronts as {\it generations} of
sites, with the first site being the parent (the first generation), 
the set of sites connected by a bond to this site being its
children (the second generation), 
the set of sites connected to these children (and not already
part of the cluster) being the next generation, 
and so on~\cite{CPE,ANTS}.
In this algorithm, the loop over all sites in a particular 
generation can be done in parallel~\cite{CPE,ANTS,EVERTZ}. 
This parallel breadth-first-search is implemented by splitting the
queue {\tt Q} into two data structures, the current generation
{\tt G} and the next generation {\tt G$^\prime$}.
The algorithm is described by the pseudo-code in 
Fig.~\ref{fig:ParAnts}.


\begin{figure}[tb]
%\vspace*{2cm}
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=XXXXXXXXXXXXXXXXXXXXXXXXXX\= \kill
 \>  {\tt G$\;$ $\leftarrow$ \{\} }
\>\>\>\>\>  {\it Initialize the current generation} \\
 \>  Chose a site {\tt i} at random 
\>\>\>\>\>  {\it First site in the cluster} \\
 \>  {\tt C$\;$ $\leftarrow$ \{i\} }
\>\>\>\>\>  {\it Initialize the cluster list} \\
 \>  {\tt G$^\prime$ $\leftarrow$ \{i\} }
\>\>\>\>\>  {\it Initialize the next generation} \\
 \>  {\tt WHILE G$^\prime$ $\neq$ \{\} DO }
\>\>\>\>\>  {\it Loop over generations} \\
 \>  \>  {\tt G$\;$ $\leftarrow$ G$^\prime$ }
\>\>\>\>  {\it Go to new generation} \\
 \>  \>   {\tt G$^\prime$ $\leftarrow$ \{\} }
\>\>\>\>  {\it Initialize the next generation} \\
 \>  \>   {\tt WHILE G $\neq$ \{\} DO IN PARALLEL}
\>\>\>\>  {\it Loop over this generation of sites} \\
 \>  \>  \>   {\tt j $\leftarrow\:$} next element in {\tt G}
\>\>\>    {\it Get the next site from the queue} \\
 \>  \>  \>   {\tt G $\leftarrow$ G - j}
\>\>\>    {\it Remove this site from the queue} \\
 \>  \>  \> Find the set {\tt\{n\}} of connected neighbors of {\tt j} 
\>\>\>    {\it Identify bonds to neighbors} \\
 \>  \>  \>   {\tt FOR} each {\tt n $\!\epsilon\!$ \{n\} DO}
\>\>\>        {\it For all connected neighbors} \\
 \>  \>  \>  \>   {\tt IF n $\!\not\!\epsilon\!$ C THEN} 
\>\>          {\it If neighbor is not in cluster list} \\
 \>  \>  \>  \>  \>   {\tt C$\;$ $\leftarrow$ C$\;$ + n}
\>              {\it Add it to the cluster list} \\
 \>  \>  \>  \>  \>   {\tt G$^\prime$ $\leftarrow$ G$^\prime$ + n}
\>              {\it Add it to the next generation} \\
 \>  \>  \>  \>  {\tt END IF} \\
 \>  \>  \>  {\tt END DO} \\
 \>  \>  {\tt END WHILE} \\
 \>  {\tt END WHILE} \\
\end{tabbing}
%\vspace*{2cm}
\protect\caption{\protect\label{fig:ParAnts}
The parallel breadth-first-search algorithm for creating a single
cluster. 
}
\vspace{1.5cm}
\end{figure}


For the Wolff algorithm only nearest-neighbor information is 
required, so the communication overhead for the parallel 
algorithm is not great. However this method performs poorly on the 
type of fine-grain, massively parallel SIMD machine for which it 
was originally proposed~\cite{ANTS}. 
This is because at any point in the algorithm, 
the current generation of sites will occupy at most O($L$)
sites of a lattice of size $L \! \times \! L$, 
and much less than that in the early
generations when the cluster is small.
If there is a single processor per lattice site, 
the load balance will be extremely poor.
The situation is little better for a coarse-grain parallel machine
with many sites per processor. This parallel breadth-first-search
algorithm is well suited to a vector machine, for which the 
degree of parallelism (the vector length of the machine) is much
smaller~\cite{EVERTZ}.
However on a Cray YMP this method achieves speed-ups of less than 10
over non-vectorized algorithms that realize only the scalar
performance of the machine~\cite{WOLFFCRAY,EVERTZ}.

Methods for implementing the Wolff algorithm in parallel on MIMD 
machines have so far been confined to the trivial parallelism of 
running independent simulations, with different parameters or
random number streams, on different processors~\cite{DMCC5,CPE}.
In this case the size of the system that can be simulated is
limited by the memory and speed of a single node of the parallel
machine. In the next two sections we introduce two methods for
parallelizing a single simulation over many processors using 
domain decomposition. The second method performs quite well
on coarse-grain MIMD parallel computers.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The single-cluster Swendsen-Wang algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The Swendsen-Wang algorithm requires the identification of clusters
of connected sites.
This is done using a connected component labeling algorithm to give
each site a number that labels the cluster to which it belongs.
All of the parallel connected component labeling algorithms use
an iterative procedure for updating the cluster label of each site.
At the end of each iteration, a test is performed to see if the 
label of any site has been changed. 
If no change has been made, then all sites have received the label
of their cluster, and the procedure terminates. 

A parallel Wolff algorithm can be implemented using a simple 
change to a parallel Swendsen-Wang algorithm, which creates
a single-cluster version of the algorithm.
As in the sequential Wolff algorithm, a random site is chosen, 
around which the cluster will grow.
The iterative procedure mentioned above remains the same, 
however now the termination condition is not that the labels of 
{\it all sites} are unchanged,
but rather the labels of {\it all sites in the single cluster 
containing the initial random site} are unchanged.
This allows all sites of the Wolff cluster to be worked on in
parallel, rather than just the expanding wavefront. 
However in this method the computation is being done for all clusters
at the same time, not just the single Wolff cluster,
so there is a lot of wasted effort. 

This method was implemented using a SIMD Swendsen-Wang 
program~\cite{SIMDPAPER}
written in CMFortran~\cite{CMF} for the Thinking Machines CM-5 
computer.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The scattered strip partitioning algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Parallel algorithms with local data dependencies generally use a 
regular domain decomposition in order to minimize communications.
However for some dynamic irregular problems, the computational
load tends to be concentrated in different regions of the domain
at different times. In order to balance the load, some kind of 
dynamic data partitioning is often required. However in some cases
a much simpler static approach can be adopted, in which the data
in neighboring regions is scattered among the processors. 
This scattered domain decomposition has a higher communications
cost since data locality is sacrificed,
however this may be more than compensated for by
the improvement in load balance when the computational load is
concentrated in a certain region of the domain, since now all 
processors contain part of that domain. This method has been very
effective in many parallel algorithms, including certain types of
matrix solvers, irregular finite element problems, and problems
with dynamic data distributions~\cite{THEBOOK}.

The strategy of scattered decomposition which 
is used in this project is illustrated in Figure~\ref{fig1}.


%**********************************************************
\begin{figure}[t]
  \begin{center}
  \leavevmode
  \epsfxsize=4.5in
  \epsfbox{decom.ps}
  \end{center}
  \caption{The scattered strip(cyclic) decomposition}
  \label{fig1}
\vspace{10mm}
\end{figure}
%*********************************************************


The lattice is split into N partitions, where N is chosen to be 
an integer multiple of the number of processor P to ensure 
load balancing. Each partition contain W(partition width) columns of 
the lattice. For a lattice size os size $L \times L, L=WN$ and 
$1 \le W \le L/P$.  Partition M is assigned to processor M mod P.

The mapping of data to processors is;

\begin{itemize}
  \item Global lattice coordinate(i,j) is assigned to processor 
       (j mod WP) div W.
  \item Local lattice coordinate(a,b) is given by 
  \begin{list}{}
    \item  a=i 
    \item  b=(j mod WP) mod W+W$\times$(j div WP)
  \end{list}
\end{itemize}

The important factor is the partition width W. As W becomes smaller, 
we can expect better load balancing, but a larger communications overhead. 
Therefore, it is important to find out the optimal partition width W.

Each processor maintains a queue which store the sites in the local 
lattice which are in the current generation, and also maintains a 
communication buffer to collect all communication requests. 
During local expansion, each site in the current generation is 
fetched from the queue, and used as a parent site to expand the 
cluster. Bonds are made with the appropriate probability  between 
the parent site and all its neighboring sites, unless the neighboring site
is already an element of the cluster. At this time, if the parent 
site is on boundary of a partition(the left or right edge),
communication with the left or right processor may be needed. 
Such a communication request is saved into te communication buffer 
for collective communication. 

After local expansion, the communication buffer is sent to the destination 
processor. Each site in the received buffer is checked to see whether 
it can become a new element of the cluster. If so, the site is added 
to the local cluster list and the queue for the next generation, 
and its spin value is updated. The final step checks whether there 
are any sites in the new generation. This can be done easily by using 
a global reduction function such as logical AND. If every processor has the 
empty queue, the algorithm halts. 

The parallel code to implement this message passing program was written 
in Express Fortran. Unlike CMMD which runs only on CM5 machine, Express 
is portable. Therefor it can be run on many machines with minor 
modifications.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Results}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The algorithm have been run on a Intel Machine(iPSC) using lattice of size
$64^2$ to $512^2$. The results were compared with a program written in C
with CMMD reduction functions~\cite{BaeKoPaul,CMMD} and with a SIMD program 
~\cite{BaeKo} written in CM Fortran on CM-5 Machine. 

The inverse temperature $\beta$ was taken to be the critical inverse 
temperature, where the cluster are most irregular in size and shape. 

To measure the average execution time, 100 iterations were performed to 
thermalize the system, and then measured the execution time for at least
1000 iterations. The time for each iteration depends on the size of 
the cluster that is grown. 

For the scattered strip partitioning algorithm, various partition widths W
were tested to find the optimal width for each lattice size. 
Figure~\ref{fig2} - Figure~\ref{fig5} shows the scaled time for different 
values of W using Express.
The performance is very sensitive to partition width.

Figure~\ref{fig6} shows the scale time for different lattice sizes using 
SIMD and MIMD algorithms. The MIMD graphs are ploted with the optimal 
partition width. As shown in figure~\ref{fig6} the Express version 
outperformed SIMD version when the lattie size is bigger than 256.

The scattered strip partitioning algorithm successfully overcomes the load 
balance problem which is the main difficulty in constructing a parallel
Wolff cluster algorithm. 



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Two parallel implementations of the Wolff single-cluster Monte Carlo 
algorithm have been introduced.

The first method involves a simple change to a parallel
Swendsen-Wang cluster algorithm, so that the iterative procedure
for identifying the clusters is halted as soon as the single Wolff
cluster is identified.
This method performs about as well as the parallel Swendsen-Wang
algorithms on which it is based,
however neither of these parallel cluster algorithms are well-suited
to implementation on massively parallel SIMD machines.

The scattered strip partitioning algorithm successfully alleviates
the load balance problem that is the main difficulty in constructing
a parallel Wolff cluster algorithm. This is done by partitioning the
lattice using a scattered type of decomposition, so that the 
expanding wavefront is distributed over almost all processors.
This method of distributing the data produces reasonable speed-ups 
for the parallel breadth-first-search algorithm for growing
a single cluster, as long as the linear dimension of the lattice
is much greater than the number of processors, and the number of
processors is not too great. 

On a massively parallel machine, parallelism could be extracted
by a combination of the strip partitioning algorithm and the
independent (or job-level) parallelism of running independent 
Monte Carlo simulations with different random number streams on
different groups of processors. For example, one might run 16 
independent simulations, each of which use 16 processors.
In this scenario, the main advantage of using the parallel 
algorithm is that it avoids the memory limitations of a single 
processor, and allows the use of larger lattice sizes.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{00}
%
\bibitem{MONTECARLO}
K.~Binder ed., 
 Monte Carlo Methods in Statistical Physics, 
(Springer-Verlag, Berlin, 1986);
K.~Binder and D.W.~Heermann,  Monte Carlo Simulation in 
Statistical Physics, (Springer-Verlag, Berlin, 1988);
H.~Gould and J.~Tobochnik,
 An Introduction to Computer Simulation Methods, Vol. 2,
(Addison-Wesley, Reading, Mass., 1988).
%
\bibitem{METROPOLIS}
N.~Metropolis  et al., 
 J. Chem. Phys. 21 (1953) 1087.
%
\bibitem{SOKALREV}
A.~D.~Sokal, in Computer Simulation Studies in Condensed Matter
Physics:  Recent Developments, eds.\ D.~P.~Landau et al.
(Springer-Verlag, Berlin, 1988);
A.~D.~Sokal, % How to Beat Critical Slowing Down: 1990 Update,
in Proc. of the International Conference on Lattice Field Theory,
Tallahassee, October 1990,  Nucl. Phys. B (Proc. Suppl.) 
20 (1991) 55.
%
\bibitem{SW}
R.H.~Swendsen and J.-S.~Wang, 
% Nonuniversal critical dynamics in Monte Carlo simulations,
 Phys. Rev. Lett. 58 (1987) 86.
%
\bibitem{WOLFF}
U. Wolff, 
 Phys. Rev. Lett. 62 (1989) 361.
%
\bibitem{LAT89REV}
U.~Wolff,
in Proc. of the Symposium on Lattice Field Theory, Capri, September
1989,  Nucl. Phys. B (Proc. Suppl.) 17 (1990) 93. 
%
\bibitem{SWREV}
J.-S.~Wang and R.~H.~Swendsen,  Physica A 167 (1990) 565.
%
\bibitem{CLIVEREV}
C. F. Baillie,
 Int. J. Mod. Phys. C 1 (1990) 91.
%
\bibitem{COMPSCI}
E.~Horowitz and S.~Sahni, Fundamentals of Computer Algorithms,
(Computer Science Press, Rockville, Maryland, 1978);
G.~Brassard and P.~Bratley, Algorithmics: Theory and Practice,
(Prentice Hall, Englewood Cliffs, N.J., 1988). 
% MORE RECENT REFS CONTAINING BOTH CCL and BFS??
%
\bibitem{WOLFFCRAY}
U. Wolff,  Phys. Lett. B228 (1989) 379. 
%
\bibitem{BURKITT}
A.~N.~Burkitt and D.~W.~Heermann,  Comp. Phys. Comm. 54 
(1989) 210.
%
\bibitem{DMCC5}
P.D.~Coddington and C.F.~Baillie, in
Proc. of the 5th Annual Distributed Memory Computing Conference,
Charleston, April 1990, eds. D.W. Walker and Q.F. Stout
(IEEE Computer Society Press, Los Alamitos, California, 1990).
%
\bibitem{CPE}
C.~F.~Baillie and P.~D.~Coddington,
 Concurrency: Practice and Experience 3 (1991) 129.
%
\bibitem{BROWER}
R.~C.~Brower, P.~Tamayo and B.~York,  J. Stat. Phys. 63
(1991) 73.
%
\bibitem{TAMAYO}
M.~Flanigan and P.~Tamayo,  Int. J. Mod. Phys. C 3 (1992)
1235.
%
\bibitem{SIMDLETTER}
J. Apostolakis, P. Coddington and E. Marinari,
 Europhys. Lett. 17 (1992) 189.
%
\bibitem{SIMDPAPER}
J. Apostolakis, P. Coddington and E. Marinari,
 Int. J. Mod. Phys. C 4 (1993) 749.
%
\bibitem{ROSSI}
P.~Rossi and G.~P.~Tecchiolli,  Finding Clusters in a Parallel
Environment, unpublished.
% (REF???)
%
\bibitem{MINO}
H. Mino,
 Comp. Phys. Comm. 66 (1991) 25.
%
\bibitem{SHIVISH}
Y.~Shiloach and U.~Vishkin,  J. Algorithms 3 (1982) 57. 
%
\bibitem{EMBRECHTS}
H.~Embrechts, D.~Roose, and P.~Wambacq, 
in  Proc. First European Workshop on
Hypercube and Distributed Computers, F. Andre and J.P. Verjus eds., 
(North-Holland, Amsterdam, 1989); 
H.~Embrechts, D.~Roose, and P.~Wambacq, 
 Computer Vision Graphics and Image Processing:
Image Understanding, 57 (1993) 155.
%
\bibitem{WOO}
J. Woo and S. Sahni,  J. of Supercomputing 3(1989) 209.
%
\bibitem{ANTS}
R.~Dewar and C.~K.~Harris,  J. Phys. A 20 (1987) 985.
%
\bibitem{EVERTZ}
H.~G.~Evertz,
 J. Stat. Phys. 70 (1993) 1075.
%
\bibitem{THEBOOK}
G.~C.~Fox  et al.,
 Solving Problems on Concurrent Processors,
(Prentice-Hall, Englewood Cliffs, New Jersey, 1988).
%
\bibitem{BaeKo}
S.Bae and S.H.Ko,
Parallel(SIMD) Wolff cluster algorithm,
Unpublished report, May, 1993.
%
\bibitem{BaeKoPaul}
S.Bae, S.H.Ko, and P.D. Coddington,
Parallel Wolff cluster algorithm,
NPAC technical report SCCS-619, March, 1994.
%
\bibitem{CMF}
CMFortran Reference Manual, (Thinking Machines Corporation,
Cambridge, Mass., 1993).
%
\bibitem{CMMD}
CMMD Reference Manual, (Thinking Machines Corporation,
Cambridge, Mass., 1993).

\end{thebibliography}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\vspace{1in}

\begin{center}
 \bf Table 1 : Scale time(msec) for one sweep(Nproc=8)\\
     Express on iPSC : CMMD on CM-5
\end{center}

\vspace{0.5in}

\begin{tabular}{|c| |c|c|c|c|}  \hline
  &  \multicolumn{4}{|c|}{\it Partition Width} \\ \cline{2-5} 
   \raisebox{1.5ex}{\it N=64} & 1  & 2  & 4  & 8      \\ \hline \hline
   Express & 356.99 & 351.53 & 336.95 & 337.20 \\ \hline
   CMMD    &  77.48 &  72.87 &  72.52 &  73.27 \\ \hline
\end{tabular}

\vspace{0.5in}

\begin{tabular}{|c| |c|c|c|c|c|} \hline
  &  \multicolumn{5}{|c|}{\it Partition Width} \\ \cline{2-6} 
   \raisebox{1.5ex}{\it N=128} & 1  & 2  & 4  & 8  &16    \\ \hline \hline
   Express & 989.78 & 869.67 & 866.77 & 829.31 & 860.99  \\ \hline
   CMMD    & 247.94 & 232.15 & 222.28 & 226.49 & 241.07  \\ \hline
\end{tabular}

\vspace{0.5in}

\begin{tabular}{|c| |c|c|c|c|c|c|} \hline
  &  \multicolumn{6}{|c|}{\it Partition Width} \\ \cline{2-7} 
   \raisebox{1.5ex}{\it N=256} & 1  & 2  & 4  & 8  &16  &32  \\ \hline \hline
   Express & 2700.14 & 2329.39 & 2108.10 & 2090.26 & 2134.93 & 2257.08 \\ \hline
   CMMD    &  878.03 &  766.04 &  735.39 &  752.78 &  814.90 &  885.91 \\ \hline
\end{tabular}

\vspace{0.5in}

\begin{tabular}{|c| |c|c|c|c|c|c|c|} \hline
  &  \multicolumn{7}{|c|}{\it Partition Width} \\ \cline{2-8} 
   \raisebox{1.5ex}{\it N=512} & 1  & 2  & 4  & 8  &16 &32  &64   \\ \hline \hline
   Express & 7423.54 & 6524.95 & 5680.83 & 5461.02 & 5703.26 & 5679.01 &6058.61 \\ \hline
   CMMD    & 3231.68 & 2726.87 & 2499.82 & 2552.45 & 2741.78 & 3024.74 &3377.03 \\ \hline
\end{tabular}


%******************
\begin{figure}[t]
  \begin{center}
  \leavevmode
  \epsfxsize=4.5in
  \epsfbox{64.ps}
  \end{center}
  \caption{The scale time for one sweep with different 
           partition width for $64 \times 64$ lattices}
  \label{fig2}
%\vspace{10mm}
\end{figure}

%******************
\begin{figure}[b]
  \begin{center}
  \leavevmode
  \epsfxsize=4.5in
  \epsfbox{128.ps}
  \end{center}
  \caption{The scale time for one sweep with different 
           partition width for $128 \times 128$ lattices}
  \label{fig3}
%\vspace{10mm}
\end{figure}

%******************
\begin{figure}[t]
  \begin{center}
  \leavevmode
  \epsfxsize=4.5in
  \epsfbox{256.ps}
  \end{center}
  \caption{The scale time for one sweep with different 
           partition width for $256 \times 256$ lattices}
  \label{fig4}
\end{figure}

%******************
\begin{figure}[b]
  \begin{center}
  \leavevmode
  \epsfxsize=4.5in
  \epsfbox{512.ps}
  \end{center}
  \caption{The scale time for one sweep with different
            partition width for $512 \times 512$ lattices}
  \label{fig5}
\end{figure}

%******************
\begin{figure}[t]
  \begin{center}
  \leavevmode
  \epsfxsize=5.5in
  \epsfbox{total.ps}
  \end{center}
  \caption{The scale time for one sweep with different lattice sizes}
  \label{fig6}
\end{figure}




\end{document}


