Connected component identification and cluster update on GPU

Martin Weigel
Institut fur Physik, Johannes Gutenberg-Universitat Mainz, Staudinger Weg 7, D-55099 Mainz, Germany
arXiv:1105.5804v1 [physics.comp-ph] (29 May 2011)


   author={Weigel}, M.},

   title={"{Connected component identification and cluster update on GPU}"},

   journal={ArXiv e-prints},




   keywords={Physics – Computational Physics, Condensed Matter – Statistical Mechanics, High Energy Physics – Lattice},




   adsnote={Provided by the SAO/NASA Astrophysics Data System}


Download Download (PDF)   View View   Source Source   



Cluster identification tasks occur in a multitude of contexts in physics and engineering such as, for instance, cluster algorithms for simulating spin models, percolation simulations, segmentation problems in image processing, or network analysis. While it has been shown that graphics processing units (GPUs) can result in speedups of two to three orders of magnitude as compared to serial codes on CPUs for the case of local and thus naturally parallelized problems such as single-spin flip update simulations of spin models, the situation is considerably more complicated for the non-local problem of cluster or connected component identification. I discuss the suitability of different approaches of parallelization of cluster labeling and cluster update algorithms for calculations on GPU and compare to the performance of serial implementations.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: