Connected component identification and cluster update on GPU

Abstract

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.

15 pages, 14 figures, one table, submitted to PRE

References in corpus (5)

• Performance potential for simulating spin models on GPU
• Simulating spin models on GPU
• q-State Potts model metastability study using optimized GPU-based Monte Carlo algorithms
• Dynamic critical behavior of the Chayes-Machta-Swendsen-Wang algorithm
• GPU accelerated Monte Carlo simulations of lattice spin models

Cited by in corpus (14)

• Finite-size scaling method for the Berezinskii-Kosterlitz-Thouless transition
• Large-scale Monte Carlo simulation of two-dimensional classical XY model using multiple GPUs
• Performance potential for simulating spin models on GPU
• Random number generators for massively parallel simulations on GPU
• GPU accelerated population annealing algorithm
• GPU-based Swendsen-Wang multi-cluster algorithm for the simulation of two-dimensional classical spin systems
• Massively parallel multicanonical simulations
• Optimized GPU simulation of continuous-spin glass models
• Adaptive Multi-GPU Exchange Monte Carlo for the 3D Random Field Ising Model
• Cluster Monte Carlo and dynamical scaling for long-range interactions
• Multi-GPU-based Swendsen-Wang multi-cluster algorithm for the simulation of two-dimensional q-state Potts model
• Phase diagrams of antiferromagnetic $XY$ model on a triangular lattice with higher-order interactions
• Massively parallel simulations for disordered systems
• Massive-Scale Simulations of 2D Ising and Blume-Capel Models on Rack-Scale Multi-GPU Systems