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%.
The cluster identification step is often the bottleneck in multiprocessor simulations of spin models for statistical mechanics. We have applied a connected component labeling algorithm originally developed for VLSI circuit extraction to the cluster identification problem. The algorithm is extended to more than two dimensions, abstracting away unnecessary spatial information to simplify implementation in higher dimensions. We identify two types of spatial locality in cluster configurations, and present optimizations to exploit each type of locality. Performance results are presented from two and three-dimensional Ising model simulations.