（様式 20）成果報告書

TSUBAME 共同利用 平成 26 年度 学術利用 成果報告書

利用課題名 TSUBAME2 GPU によるスピン系のクラスターアルゴリズム・モンテカルロシミュレーション
英文：Cluster algorithm Monte Carlo simulations of spin systems using TSUBAME2 GPU
利用課題責任者 岡部 豊
Yutaka Okabe所属 首都大学東京理工学研究科
Graduate School of Science and Engineering, Tokyo Metropolitan University

物質内の相転移現象を解析するモデルとして，格子スピンモデルがある．格子スピンモデルの解析にはマルコフ連鎖モンテカルロ法がよく用いられており，我々はこれまでマルコフ連鎖モンテカルロ法の一つ，Swendsen-Wang マルチクラスターアルゴリズムの GPU アルゴリズムの開発を行ってきた．本年度は今まで提案した方法の根本的な問題の解決に取り組み，シングル GPU およびマルチ GPU での新たなアルゴリズムを考案した．
新たなシングル GPU のアルゴリズムでは従来のアルゴリズムよりも計算速度が 2 倍向上することを確認し，マルチGPU のアルゴリズムでは 3 次元系の計算で問題であった GPU 間のデータ転送量を 90％削減した．

The classical spin model is one model for understanding mechanisms of phase transition. The
classical spin model is often analyzed by using a Markov Chain Monte Carlo simulation, and wehave developed the Swendsen-Wang multi-cluster algorithm, which is an algorithm of Markov
Chain Monte Carlo simulations, with GPUs. In this paper, we identify the bottlenecks of previous
methods with a single GPU and multiple GPUs, and we propose the new methods with a single GPUand multiple GPUs. As a result, the computation time of the new method with a single GPU is about
half that of the previous method for all system sizes. In the new method of multiple GPU, the data
communication between each GPU is reduced by 90%, and the number of communications between
each GPU decreases by about half.

Keywords: Monte Carlo simulation, Union-Find algorithm, Ising model

アルゴリズム[1]の GPU アルゴリズムの開発を行って背景と目的物質内の相転移現象を解析するモデルとして，格子きた．本年度は今まで我々か提案してきた手法の根本スピンモデルがある．格子スピンモデルを解析する標的 な 改 良 を 行 い ， シ ン グ ル GPU[2] 及 び ， マ ル チ

準的な手法として，モンテカルロ法は広く用いられておGPU[3]の新たなアルゴリズムを考案した．

り，局所的な情報を用いて更新が行われるメトロポリス法は格子スピンモデルに限らず，様々な分野で使用さ概要れている．メトロポリス法のようなシングルスピンフリッ

シングル GPU の Union-Find アルゴリズムは大きく

プのモンテカルロ法には転移温度付近で緩和時間が2 つに分類される．一つは全体を小領域のブロックに分急激に大きくなる問題がある．これを解決する一つの割し，各ブロックでのクラスターを形成後にブロック間の手法としてクラスターアルゴリズムが提唱されている[1]．

クラスターを接合するアルゴリズムである．もう一つはクラスターアルゴリズムは Union-Find アルゴリズムを全領域のクラスターを直接形成する方法である．小領使用することで，スピンのクラスターを生成し，各クラス域でのクラスター形成と全領域でのクラスター形成のアター内の全てのスピンを一度に更新するアルゴリズム

ルゴリズムとして，label equivalence アルゴリズム[4]である．そのため，局所的な情報ではなく，全体の繋がが広く用いられている．このアルゴリズムは近接サイトりの情報が必要となる．我々はこれまでクラスターアルとのラベルの比較と更新をラベルの更新がなくなるまでゴリズムの 1 つ，Swendsen-Wang

繰り返し実行するアルゴリズムである．しかし，この繰りマルチクラスター

（様式 20）成果報告書返しの際，更新しないラベルの計算も多数含まれてお

3 次元イジングモデルの転移温度直上での 1 モンテカ

り，この部分が無駄な計算となっていた．そこで，我々ルロステップあたりの計算時間を示している．表 1，表 2

は更新する可能性があるラベルのみが計算を実行し，よ り ， 提 案 手 法 の 計 算 時 間 は 従 来 の label

かつ近接サイトとのラベルの比較が一度で済む新たなequivalence アルゴリズム[4]の計算時間の半分程度アルゴリズムを考案した．この新たなアルゴリズムではになっていることにわかる．

4 つのカーネル関数を実行するのみで計算が完了する．
このアルゴリズムの詳細については[2]の文献を参照し

L

512

1024

2048

4096て欲しい．

従来手法[4]2.99 ns

2.28 ns

2.09 ns

2.07 ns

提案手法[2]

1.29 ns

1.10 ns1.01 ns

0.93 ns

我々はマルチ GPU の Union-Find アルゴリズムを提案しており[5]，そのアルゴリズムを用いて格子スピン

表 1 : 2 次元イジングモデルの転移温度直上の計算時間モデルの一つ，2 次元 XY モデルに対し，大規模計算を行った[6]．[6]の計算は 2 次元格子の計算であるため，

L96

128

192256

GPU 間の通信の影響はそこまで大きくはなかった．し従来手法[4]2.91 ns

2.35 ns

2.83 ns2.38 ns

かし，3 次元の計算では通信の影響が大きくなり，GPU

提案手法[2]

1.18 ns

1.13 ns

1.11 ns

1.12 ns

間の通信が全体計算時間の 80％を占める[3]．そのた

表 2 : 3 次元イジングモデルの転移温度直上の計算時間め，高速な計算を実現するためにはこのデータ通信量を削減する必要があった．[5]で提案したアルゴリズム[5]のマルチ GPU を用いた Union-Find アルゴリズ

は各 GPU の袖領域ラベルを隣接 GPU に転送し，各ムとマルチ GPU を用いた提案手法の比較を図 1 に示

GPU 内のラベルを更新する方法を用いている．このデす．図 1 では 3 次元イジングモデルの転移温度直上のータ転送とラベルの更新は全ての GPU のラベル更新

計算時間と繰り返し回数をプロットしており，1GPU 当がなくなるまで繰り返される．この繰り返し回数は 50 をたりの大きさは 5123 である．図 1 の棒グラフは 1 モンテ

超え，袖領域のデータもこの回数分転送するため，デカルロステップあたりの計算時間を表しており，GPU 間ータ通信の影響が大きくなっていた．そのため，我々はクラスター形成の計算時間，重複ラベルの抽出とラベ改良アルゴリズムとして，通信と更新の計算を行う前にル再調整の計算時間，その他の計算時間毎に分割し各 GPU の袖領域部分の重複したラベルをまとめ，まと表示している．また，図中の点は繰り返し回数を表してめたラベルのみを転送する方法を考案した．また，近隣いる．図 1 より，GPU 間クラスター形成の計算時間が領域を担当している GPU の重複したラベル情報を元大幅に減少していることがわかる．また 1 反復当たりのに，各 GPU のラベルを再調整することで繰り返し回数データ転送量は約 90％削減しており，反復回数も約半の削減も行う．このアルゴリズムの詳細については[3]分になっている．の文献を参照して欲しい．また，重複ラベルの抽出の際には逐次計算を使用する必要がある．逐次計算での抽出アルゴリズムでは袖領域の二乗の計算量が必要となるが，本研究では GPU 上で実装可能な重複ラベルの抽出アルゴリズムを新たに考案した[3]．このアルゴリズムは袖領域程度の計算量で抽出が完了する．

結果および考察シングル GPU での結果を表 1， 表 2 に示す．表 1
は 2 次元イジングモデルの転移温度直上での 1 モンテカルロステップあたりの計算時間を示しており，表 2 は

図 1: マルチ GPU を用いた 3 次元イジングモデルの転（様式 20）成果報告書
移温度直上の計算時間と反復回数の比較

まとめ，今後の課題本課題ではシングル GPU 及びマルチ GPU を用いた Union-Find アルゴリズムの改良に取り組んだ．
従来提案していた手法の問題点を明らかにし，共有メモリ型のシングル GPU 及び，分散メモリ型のマル
チ GPU での根本的な部分を修正した新たなアルゴリズムを提案した．
GPU を用いた Union-Find アルゴリズムの適用は正方格子，立方格子などの定形格子に限られている．
しかし，本課題で提案したシングル GPU のアルゴリ
ズムは任意格子への拡張が可能な手法であり，現在その拡張手法を考案している．この任意格子のアルゴリズムはマルチ CPU や Xeon Phi に適さない．
これは任意格子のアルゴリズムはランダムメモリアクセスが主要な計算部分であるため，マルチコア CPUや Xeon Phi ではキャッシュミスやキャッシュコヒーレンスの影響によって計算時間が遅くなることが予想されるためである．
[1] R.H. Swendsen and J.S. Wang, Phys. Rev.
Lett. 58 (1987) 86.
[2] Y. Komura, Comp. Phys. Comm. 194 (2015) 54.
[3] Y. Komura, (2015). Comp. Phys. Comm. 195,84.

[4] O. Kalentev, A. Rai, S. Kemnitzb, and R.
Schneider, (2011) J. Parallel Distrib. Comput.
71 615.
[5] Y. Komura, and Y. Okabe, (2013). Comp. Phys.
Comm. 184, 40.
[6] Y. Komura, and Y. Okabe, (2012). J. Phys. Soc.
Jpn. 81, 113001.