NPAC Technical Report SCCS-279
New SIMD Algorithms for Cluster Labeling on Parallel Computers
John Apostolakis, Paul Coddington, Enzo Marinari
September 1992
Published in Int. J. Mod. Phys. C 4, 749 (1993).
© Copyright World Scientific Publishing.
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.
PostScript version
(gzip compressed)
PDF version