
NEW ALGORITHMS FOR MONTE CARLO SIMULATION OF SPIN MODELS
========================================================

Paul Coddington, Ofer Biham, Enzo Marinari, John Apostolakis,
Leping Han, Zheung-You Su.



Physics problems
----------------

Some materials can become magnetized due to interactions between the
spins of electrons. These materials can have a {\it phase transition} 
between a low temperature magnetized phase, and a high temperature 
demagnetized phase. The behavior at this phase transition can be well
described by very simple models of interacting spins on a lattice, such
as the Ising model. Numerical simulations of these models provide insight 
into the behavior of real magnets, as well as the general theory of phase
transitions, which is applicable to a huge variety of systems.

Recently some new, non-local Monte Carlo algorithms for spin models have
been introduced [1,2,3]. These {\it cluster algorithms} have attracted 
great interest, since they are much more computationally efficient than 
standard Monte Carlo methods such as the Metropolis algorithm. Standard 
Monte Carlo algorithms make small, local changes to the spin configuration, 
which means that many iterations are required to generate an independent, 
uncorrelated configuration. This is known as {\it critical slowing down}, 
and is a major problem in computer simulations in many different fields, 
which has lead to the development of a number of new multi-scale algorithms, 
such as multi-grid and FFT methods for solving differential equations.

We have been making quantitative studies of these cluster algorithms [4,5].
However we are especially interested in investigating new types of cluster 
algorithms, in particular those which might be applied to systems other 
than the types of spin models to which these algorithms are currently 
limited.

There has recently been some progress in applying cluster algorithms to
simple, regular models with frustration, for which the usual cluster
algorithms will not work [3]. We are currently trying to generalize these
methods to other frustrated systems [6], and to spin glasses, which have
random frustration. These are also the systems for which local algorithms 
suffer the most severe critical slowing down, and thus cluster algorithms 
would be of the greatest value. 



Optimization
------------

Finding the ground state of a spin glass is a classic hard (NP-complete)
optimization problem. A common approach to this problem is simulated 
annealing, which uses the Metropolis algorithm. Because this algorithm
can only make small, local changes, this method suffers from critical 
slowing down, and often becomes stuck in local minima. 

This would not be the case for a non-local cluster algorithm. Simulated 
annealing is now a widely used method for many different types of 
optimization problems, and by studying and trying to generalize the
replica cluster algorithm for spin glasses [7,8], we hope to gain insight 
into how non-local algorithms may be used in general optimization problems.



Parallel algorithms
-------------------

The main computational task in cluster algorithms is the identification
and labeling of the clusters. This is what is known in computer science 
as connected component labeling, and is a very difficult problem to
implement efficiently on a parallel machine. 

There are a number of algorithms in the computer science literature for 
tackling this problem. We are studying and implementing some of these 
algorithms, and have also developed our own algorithms, for both MIMD and 
SIMD machines [9,10]. The problem of identifying clusters in spin models 
provides a good test of component labeling algorithms, since the regions
to be labeled are very irregular and of all sizes, including very large 
clusters (of the order of the lattice size).

Our aim is to find the simplest and most efficient algorithms for this
problem for a number of different parallel architectures, such as
massively parallel SIMD machines (e.g. the Connection Machine) and
MIMD machines (e.g. the nCUBE). We are now also investigating the 
performance of these algorithms on small numbers of very powerful 
processors, such as in tightly coupled networks of workstations. 

The replica cluster algorithm uses a number of interacting copies 
(replicas) of the lattice, each at different temperatures. This can be 
parallelized most effectively by putting each replica on a different 
processor [11]. Since the number of replicas is fairly small (of order 10), 
and the ratio of computation to commumication is high, this is a good 
candidate for parallelism over a network of powerful workstations.



Visualization
-------------

In order to invent new algorithms, and to better understand those which 
are already known, it is extremely helpful to be able to visualize the 
clusters, so we can get a much better idea of their sizes and shapes,
and of how effectively the cluster update changes the spin configurations. 
In some cases it is possible to tune parameters in order to change the 
average size of the clusters. Being able to see exactly how the clusters
change for different parameters or different methods will also help 
in optimizing these algorithms for a particular model.

We are constructing a computational environment which will display the 
evolution of the clusters and spins through each iteration of any cluster
algorithm for any given spin model [12]. Visualizing the clusters is simple 
and works very well in two dimensions, but creating an effective and 
useful visualization of the clusters in three dimensional models is a much
more difficult problem, which we are also aiming to investigate.

This computation and visualization environment will be a great help in the 
development, coding, debugging and optimization of new types of cluster 
algorithms, and in the application of these algorithms to different models.

We are also implementing a similar environment on parallel computers 
such as the Connection Machine and the nCUBE. In this case the graphics
enables us to visualize the progress of the component labeling algorithm
in identifying and labeling large clusters which are spread over many
processors.



Benchmarking parallel languages and compilers
---------------------------------------------

Parallel algorithms for spin models offer an interesting challenge to
parallel machines, languages, and compilers. The local Metropolis
algorithm can be easily and efficiently parallelized using standard
domain decomposition, since it is regular and needs only local edge
communication. This is a simple case which should be well handled by 
any parallelizing compiler. The replica cluster algorithm should also
be easily parallelized, by distributing the replicas over different
processors.

The cluster algorithms, on the other hand, offer a very difficult 
challenge to a parallelizing compiler, or even a high level parallel 
language. They do not have the regular structure of other multi-scale 
algorithms, such as multi-grid. Efficient component labeling algorithms 
are rather complicated, and quite different to the sequential algorithms.

We are currently implementing these algorithms in a number of different
sequential and parallel languages, such as C, FORTRAN, Express C, 
Express FORTRAN, C*, CM-FORTRAN, FORTRAN 90D, and PCN, in order to compare
the effectiveness and efficiency of these languages and compilers.



Using the IBM RS/6000 workstations
----------------------------------

In studying cluster algorithms for various spin models, we need to
obtain good data on large lattices in order to get accurate estimates
for critical exponents. For the Swendsen-Wang cluster algorithm, we
can use large parallel machines for the largest lattice sizes, however
the Wolff cluster algorithm is not parallelizable or vectorizable.
The IBM RS/6000 workstation is thus the most suitable computer we know 
for running this algorithm. It has enough memory and power to handle 
large systems, being approximately 3 times faster than a DEC 5000 
workstation, and almost as fast as a CRAY X-MP, for this problem. 

The data we have obtained using these machines was very important in 
helping us to find very surprising and interesting relations between the
static critical exponents of Ising spin model phase transitions, and the 
dynamical exponents which give a measure of the critical slowing down for
cluster Monte Carlo algorithms [5].

We are also planning to configure the machines into a tightly coupled
network with fast (possibly optical) connections. This network would be 
in effect a powerful parallel computer, and using our parallel algorithms
for component labeling, and for the replica cluster algorithm, we hope to 
be able to use it effectively, and to investigate the efficiency of such
networks for distributed computing.



References: 
-----------

[1]  R.H. Swendsen and J.-S. Wang, {\it Phys. Rev. Lett.} {\bf 58}, 86 (1987).
[2]  U. Wolff, {\it Phys. Rev. Lett.} {\bf 62}, 361 (1989).
[3]  D. Kandel, R. Ben-Av and E. Domany, {\it Phys. Rev. Lett.} {\bf 65}, 941
     (1990).
[4]  C.F. Baillie and P.D. Coddington, ``Comparison of Cluster Algorithms for 
     2-D Potts Models'', {\it Phys. Rev.} B {\bf 43}, 10617 (1991).
[5]  P.D. Coddington and C.F. Baillie, ``Empirical relations between static 
     and dynamic exponents for Ising model cluster algorithms'', submitted 
     to {\it Phys. Rev. Lett.}
[6]  P.D. Coddington and L. Han, ``A Cluster Algorithm for the 3-D Fully 
     Frustrated Ising Model'', in preparation.
[7]  J.-S. Wang and R.H. Swendsen, {\it Phys. Rev.} B {\bf 38}, 4840 (1988).
[8]  P.D. Coddington and Z.-Y. Su, ``A Study of the Replica Monte Carlo
     Method'', in preparation.
[9]  C.F. Baillie and P.D. Coddington, ``Cluster Identification Algorithms 
     for Spin Models - Sequential and Parallel'', {\it Concurrency: 
     Practice and Experience} {\bf 3}, 129 (1991).
[10] John Apostolakis, Paul Coddington and Enzo Marinari, ``A Multi-Grid 
     Cluster Labeling Scheme'', to be published in {\it Europhys. Lett.}.
[11] P.D. Coddington and Z.-Y. Su, ``Replica Monte Carlo on Parallel 
     Computers'', in preparation.
[12] Daniel Baumann and Paul Coddington, ``The Visualization of Triangular
     Lattice Spin Models'', in {\it The Journal of Undergraduate Research 
     in Computational Physics and Computer Science at Syracuse University},
     Vol. 1, 1991.



