NEW SIMD ALGORITHMS FOR CLUSTER LABELING ON PARALLEL COMPUTERS

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 conne cted component labeling, to identify dusters of connected sites on a l attice. We have devised some new SIMD component labeling algorithms, a nd implemented them on the Connection Machine. We investigate their pe rformance when applied to the cluster update of the two-dimensional Is ing spin model. These algorithms could also be applied to other proble ms which use connected component labeling, such as percolation and ima ge analysis.