GPU-based cluster-labeling algorithm without the use of conventional iteration: Application to the Swendsen-Wang multi-cluster spin flip algorithm
GPU-based cluster-labeling algorithm without the use of conventional iteration: Application to the Swendsen-Wang multi-cluster spin flip algorithm
复制标题
不使用传统迭代的基于 GPU 的簇标记算法：在 Swendsen-Wang 多簇自旋翻转算法中的应用
DOI：
10.1016/j.cpc.2015.04.015
复制
发表时间：
2015
影响因子：
6.3
通讯作者：
Yukihiro Komura
中科院分区：
文献类型：
--
作者：
Y. Iguchi;Y. Nii;and Y. Onose;高井啓 他;芳賀聡;Jun Sun;Yukihiro Komura
使用单个GPU的集群标记算法大致可以分为直接方法和两阶段方法。到目前为止，这两种类型都使用迭代方法来比较最近邻站点的标签。在本文中，我提出了一种不使用常规迭代的基于GPU的簇标记算法。该方法既适用于直接算法，也适用于两阶段算法。在所提出的方法下，对于二维(2D)系统只需要与最近邻站点进行一次比较，对于三维(3D)系统只需要两次比较。作为新的簇标记算法的一个应用，我考虑了Swendsen-Wang(SW)多簇自旋翻转算法。利用二维和三维伊辛模型，将所提出的方法与其他簇标记算法的性能进行了比较。结果表明，对于2D Ising模型，新算法的计算时间比以前的算法快40%；对于3D Ising模型，在临界温度下，新算法的计算时间比以前的算法快20%。
Cluster-labeling algorithms that use a single GPU can be roughly divided into direct and two-stage approaches. To date, both types use an iterative method to compare the labels of nearest-neighbor sites. In this paper, I present a GPU-based cluster-labeling algorithm that does not use conventional iteration. The proposed method is applicable to both direct algorithms and two-stage approaches. Under the proposed approach, only one comparison with the nearest-neighbor site is needed for a two-dimensional (2D) system, and just two comparisons are needed for three-dimensional (3D) systems. As an application of the new cluster-labeling algorithm, I consider the Swendsen–Wang (SW) multi-cluster spin flip algorithm. The performance of the proposed method is compared with that of other cluster-labeling algorithms for the SW multi-cluster spin flip problem using the 2D and 3D Ising models. As a result, the computation time of the new algorithm is shown to be 40% faster than that of the previous algorithm for the 2D Ising model, and 20% faster than that of the previous algorithm for the 3D Ising model at the critical temperature.