Parallel cluster identification for multidimensional lattices
- 1 January 1997
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 8 (11) , 1089-1097
- https://doi.org/10.1109/71.642944
Abstract
The cluster identification problem is a variant of connected component labeling that arises in cluster algorithms for spin models in statistical physics. We present a multidimensional version of Belkhale and Banerjee's Quad algorithm for connected component labeling on distributed memory parallel computers. Our extension abstracts away extraneous spatial connectivity information in more than two dimensions, simplifying implementation for higher dimensionality. We identify two types of locality present in cluster configurations, and present optimizations to exploit locality for better performance. Performance results from 2D, 3D, and 4D Ising model simulations with Swendson-Wang dynamics show that the optimizations improve performance by 20-80 percent.Keywords
This publication has 20 references indexed in Scilit:
- A robust parallel programming model for dynamic non-uniform scientific computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- SWENDSEN-WANG DYNAMICS ON LARGE 2D CRITICAL ISING MODELSInternational Journal of Modern Physics C, 1992
- A PARALLEL CLUSTER LABELING METHOD FOR MONTE CARLO DYNAMICSInternational Journal of Modern Physics C, 1992
- A Multi-Grid Cluster Labeling SchemeEurophysics Letters, 1992
- Cluster Identification Algorithms for Spin Models — Sequential and ParallelConcurrency: Practice and Experience, 1991
- A parallel multigrid algorithm for percolation clustersJournal of Statistical Physics, 1991
- Parallelization of the Ising model and its performance evaluationParallel Computing, 1990
- Computer Simulation Methods in Theoretical PhysicsPublished by Springer Nature ,1990
- Broken phase of the 4-dimensional Ising model in a finite volumeNuclear Physics B, 1989
- Nonuniversal critical dynamics in Monte Carlo simulationsPhysical Review Letters, 1987