171 - 電子情報通信学会

平成 20 年度電子情報通信学会東京支部学生会研究発表会
講演番号：171
PS3 を用いた交換モンテカルロ法の実装
D-1 Exchange Monte Carlo Method Using PS3
三木 拓史 1
Takushi Miki
原 一之 2
Kazuyuki Hara
東京都立工業高等専門学校 1
Tokyo Metropolitan College of Technology
東京都立産業技術高等専門学校 2
Tokyo Metlopolitan College of Industrial Technology
まえがき
交換モンテカルロ法は計算量が膨大であるが、並列計
算が有効なアルゴリズムになっている。そこで、複数の
演算プロセッサを内臓したマルチコアプロセッサの一つ
である Cell を用いて、高速化の検証を行った。Cell を
内臓しているソニー・コンピュータエンタテイメント社
製ゲーム機 PLAYSTATION3(PS3) に交換モンテカルロ
法を実装し、Core2Duo プロセッサ搭載のパーソナルコ
ンピュータ (PC) と比較し 1.9 倍の高速化を確認した。
1
1
0.8
0.7
m
0.6
0.3
交換モンテカルロ法
交換モンテカルロ法はマルコフ連鎖モンテカルロ法
(MCMC 法) の一種である。MCMC 法とはある分布に
従う乱数を生成するアルゴリズムで、期待値を計算する
ことが目的である。今回は強磁性モデルの磁化を交換モ
ンテカルロ法により計算する。
N 個のスピン確率変数からなる強磁性モデルを考え
る。スピン確率変数 S は ±1 の値をとるものとする。
X = {Si } として磁化は
�
m = XP (X|T )dX
(1)
3
で与えられる。P (X|T ) は温度 T での X の確率分布で
あり
4
1
E(X)
exp(−
)
Z(T )
T
(2)
である。Z(T ) は規格化定数、E(X) はエネルギーである。
X のあるスピンを確率
�
�
P (X � )
min 1,
(3)
P (X)
により反転して X � を生成する操作を繰り返すことによ
り式 (2) から標本を得るアルゴリズムを MCMC 法とい
い、標本の平均を計算することで磁化 m を推定する。
交換モンテカルロ法は複数の温度 T に対して MCMC
法を適用し、隣り合う温度の状態を確率
�
�
P (Xb+1 |Tb )P (Xb |Tb+1 )
min 1,
(4)
P (Xb |Tb )P (Xb+1 |Tb+1 )
0.5
0.4
0.2
2
P (X|T ) =
PC
PS3
0.9
0.1
0
0.01
0.1
図1
1
10
T
磁化の温度特性
Cell プロセッサ
Cell は制御用のプロセッサである PPE を一つと演算
用のプロセッサである SPE を複数搭載している。PS3
では六基の SPE を使用できる。交換モンテカルロ法の
実装には IBM が配布している SDK[1] を使用し、SPE
の制御に SONY が配布しているライブラリ [2] を使用
した。
結果
スピンの数 N は 2,048 個、温度の種類 B は 36、式 (3)
により標本を 10,000 個得て式 (4) により状態を交換す
る操作を 500 回行い、各温度で計 5,000,000 個の標本に
より磁化を計算した。PC の仕様は CPU が Core2Duo
1.83GHz、OS は MacOSX、プログラムは Xcode 上で
release モードでコンパイルした。計算結果を図 1 に示
す。計算時間の比は 1.9(PC/PS3) となった。
参考文献
[1] http://www.ibm.com/developerworks/power/cell/
により交換するという操作繰り返すことにより、MCMC
法の収束を改善する。
式 (3) の計算は各温度で独立に計算できるため、並列
計算に適したアルゴリズムになっている。
-171-
[2] http://ftp.uk.linux.org/pub/linux/SonyPS3/mars/
[3] 伊庭幸人他「計算統統計 II マルコフ連鎖モンテ
カルロ法とその周辺」(統計科学のフロンティア 12) 岩波書店 (2005)
[4] 福島考治「モンテカルロ法の前線 ーサイコロ振っ
て積分する方法ー」『確率的アルゴリズムによる情
報処理』講演集 (2003)
[5] 永田 賢二「交換モンテカルロ法とその応用」
『JNNSDEX-SMI 玉川公開講座』(2008)
Copyright © 2009 IEICE