NPAC Technical Report SCCS-279
New SIMD Algorithms for Cluster Labeling on Parallel Computers
John Apostolakis, Paul Coddington, Enzo Marinari
Submitted September 09 1992
Abstract
Cluster algorithms are non-local Monte Carlo update schemes which
can greatly increase the efficiency of computer simulations of spin models
of magnets.
The major computational task in these algorithms is connected component
labeling, to identify clusters of connected sites on a lattice. We have
devised some new SIMD component labeling algorithms, and implemented them on
the Connection Machine. We investigate their performance when applied to
the cluster update of the two dimensional Ising spin model.
These algorithms could also be applied to other problems which use connected
component labeling, such as percolation and image analysis.