Spin models provide simple models of magnetism, and in particular of the transition between magnetic and non-magnetic phases as a magnetic material is heated past its critical temperature. In a spin model of magnetism, variables representing magnetic spins are associated with sites in a regular crystalline lattice. Different spin models are specified by different types of spin variables, interactions between the spins, and lattice geometry.

The Ising model is the simplest spin model, where the spins have only two states (+1 and -1), representing magnetic spins that are up or down. Spin models have been intensely studied since an exact solution was found for the 2D Ising model, providing great insight into the physics of magnetism, and in particular, the more general phenomenon of phase transitions.

A configuration of the standard ferromagnetic Ising model with two spin states (represented by black and white) at the critical temperature, where there is a phase transition between the low temperature ordered or magnetic phase (where the spins align) and the high temperature disordered or non-magnetic phase (where the spins are more randomized). As the temperture increases from zero (where all the spins are the same), "domains" of opposite spin begin to appear and start to disorder the system. This is similar to what happens at a liquid-gas phase transition, e.g. bubbles of steam appearing when water is boiled. At the phase transition, domains or clusters of spins appear in all shapes and sizes. As the temperature increases further, the domains start to break up into random individual spins.

* Antiferromagnetic triangular lattice Ising model*

A zero temperature (lowest energy) configuration of an antiferromagnetic Ising model with two spin states (represented by yellow and blue) on a triangular lattice. In a ferromagnet, the energy is lowest when neighboring spins are aligned. In an antiferromagnet, the energy is lowest when neighboring spins are different. The lowest energy state of an Ising antiferromagnet on a square lattice is therefore just a checkerboard. However on a triangular lattice, it is impossible for all neighbors to have opposite spins. The system is said to be "frustrated", since it cannot achieve a state where all the interactions have lowest energy. This graphic shows just one of the many possible ground states (lowest energy states) for this model.

* Antiferromagnetic triangular lattice Potts model*

A zero temperature (lowest energy) configuration of an antiferromagnetic 4-state Potts model on a triangular lattice. If there are more than 2 possible states for the spin, neighboring spins can all be different, so this model is not frustrated.

A zero temperature configuration of the fully frustrated Ising model with two spin states (represented by green and red). Frustrated spin models show interesting behaviour but are difficult to simulate efficiently. There is a lot of ongoing research into improved methods for simulating frustrated spin models.

A configuration of the O(3) spin model. For this model the spins are elements of the group O(3), i.e. real-valued (rather than discrete) 3-vectors with unit length. There are many possibilities for mapping the spins to different colors, this color map gave the best results of the few we tried. Notice that this model still has domains or clusters, but they are not as well-defined or distinct as for the discrete models.

Standard Monte Carlo algorithms for simulating spin models of magnetism, such as the Metropolis algorithm, make regular and local changes to the system, and thus are easy to parallelize efficiently. However it takes many iterations to produce a statistically independent Monte Carlo configuration. The more recent cluster update algorithms provide a much more efficient simulation since they make non-local updates to large clusters of spins, rather than local updates of single spins. However the non-local and irregular nature of these updates means they are difficult to parallelize efficiently.

The Wolff cluster algorithms updates a single cluster at a time. This picture shows a configuration of the Potts spin model with 3 spin states (represented by the 3 colors) at its critical temperature. The single cluster Wolff Monte Carlo algorithm, The bonds connecting the sites that make up the single cluster are shown in yellow.

* Swendsen-Wang cluster algorithm*

The Swendsen-Wang cluster algorithm updates assigns every spin in the lattice to a cluster and updates all the clusters every iteration. The Swendsen-Wang clusters are shown bounded by black lines for the 3-state Potts spin model at its critical temperature (the cluster boundaries are only visible on the full-size image).

The main computational task in cluster algorithms is connected component labeling, to identify the clusters of spins to be updated. We have developed a number of parallel component labeling algorithms, for both the single cluster (Wolff) and multiple cluster (Swendsen-Wang) algorithms, for SIMD and MIMD architectures.

Cluster labels for parallel Swendsen-Wang cluster labeling:

After a scan | After a send | After a few iterations | Final labels |

These pictures show various stages in the parallel algorithm for the identification and labeling of different clusters for the Swendsen-Wang cluster Monte Carlo algorithm running on the Connection Machine. This is an instance of connected component labeling, where we have information on the local connectivity (connections between neighboring sites), and we want to find the global connectivity (the clusters of connected sites). The colors represent the cluster labels, which are initial set to be different for each site. An iterative procedure is then followed to find the connected clusters.

Another image of a stage in the parallel cluster labeling algorithm.

Paul Coddington, University of Adelaide, paulc@cs.adelaide.edu.au