OpenMPによる将棋木探索の並列化 (2015/06/07)

OpenMPは共有メモリー環境(マルチコア、マルチCPU)において、 ソースコードにdirectiveを挿入することによって簡単にプログラムを並列化する技術です。
ここではOpenMPを用いて将棋思考プログラムの木探索を並列化する方法について述べます。

1. 単純分散

リスト1.1にαβ探索の基本形を示します。 反復深化は必須ではありませんが、ここでは説明の便宜上、反復深化を用いています。
各深さにおいてsearch関数によって木探索が行われます。 ここではnegaMax表記を用いています。
このsearch関数は以下で述べる並列化の作業において変更は不要です。 このために既存のプログラムを容易に並列化することができます。

リスト1.1 αβ探索の基本形
// 反復深化
iterate() {
	for (depth) {
		alpha = -infinity;
		beta = infinity;
		value = search(depth, alpha, beta);
	}
}
// αβ探索(この関数は以降変更不要)
int search(depth, alpha, beta) {
	if (!depth) return quies();  // 静止探索
	generate_moves();  // 合法手生成
	for (move) {  // 合法手に関する繰り返し
		makemove(move);  // 一手進める
		value = -search(depth - 1, -beta, -alpha);  // 探索(再帰呼び出し)
		unmakemove(move);  // 一手戻す
		if (value >= beta) return beta;  // βカット
		if (value > alpha) alpha = value;  // α更新
	}
	return alpha;
}

リスト1.2に並列化のための準備プログラムを示します。
反復深化iterateは直接searchを呼び出さずにルート局面を探索するsearchr関数を呼び出します。
このsearchr関数の中で並列化のための作業を行います。
リスト1.2のsearchr関数がリスト1.1のsearch関数と異なる点は以下の2点です。
・木の末端の処理は不要
・ルート局面ではβカットは発生しないので省略する

リスト1.2 並列化のための準備
// 反復深化(並列版)
iterate() {
	for (depth) {
		value = searchr(depth);  // ルート局面を呼び出す
	}
}
// ルート局面の探索
int searchr(depth) {
	alpha = -infinity;
	beta = infinity;
	generate_moves();
	for (move) {
		makemove(move);
		value = -search(depth - 1, -beta, -alpha);  // 探索
		unmakemove(move);
		// ルート局面ではβカットは発生しない
		if (value > alpha) alpha = value;
	}
	return alpha;
}

リスト1.2の計算時間の主要部はsearchr関数のfor文であり、 この部分はアルゴリズム的に並列処理が可能なので、 OpenMPを用いて簡単に並列化することができます。
リスト1.3がOpenMPを用いた並列プログラムです。 for文の直前に"#pragma omp parallel for"と記入するとfor文が並列処理されます。
OpenMP注意点は以下の通りです。

  1. #pragma omp parallelの直後の領域が並列領域になり、指定した数のスレッドが実行されます。 領域は{}で囲みます。for文は一種の領域なので改めて{}で囲む必要はありません。
  2. 並列領域の外は一つのメインスレッドが実行されます。
  3. 並列領域の外で宣言された変数は並列領域のすべてのスレッドから参照できます。以下これをグローバル変数と呼びます。
  4. 並列領域の中で宣言された変数はスレッド毎に別のアドレスを持ちます。以下これをスレッド変数と呼びます。
  5. スレッド数を指定しないときは全論理コア数に等しい数のスレッドが起動されます。
  6. スレッド数を指定するにはOpenMP関数であるomp_set_num_threads関数を用います。 OpenMP関数を呼び出すときは"#include <omp.h>"が必要です。 omp.hはOpenMP関数のプロトコル宣言を含むだけであり、OpenMP関数を呼び出さないときは不要です。
    omp_set_num_threads関数は一度呼び出せば有効なのでここで呼ぶ必要はないので以降は省略します。
    なお、スレッド数は環境変数OMP_NUM_THREADSで指定することもできます。
  7. while文、do文は並列処理できません。
for文の注意点は以下の通りです。
  1. for (A; B; C) のA,B,Cは空ではいけません。
  2. break文は使用できません。continue文は使用できます。 ルート局面ではβカットは発生しないので問題ありません。
  3. ループのindexは符号付整数(int)でなければなりません。(OpenMP2.5まで)
以上の注意点を踏まえてリスト1.3を見ると以下のことがわかります。
  1. 局面はスレッド毎に別のアドレスを持つ必要があるので、スレッド変数にコピーします。
  2. 評価値(value)はスレッド毎に異なるのでprivate宣言する必要があります。 なお、private句を使用せずに別途スレッド変数を宣言しても同じです。
  3. 局面(tree)はスレッド変数なのでunmakemoveする必要はありません。
  4. 合法手を逐次生成するプログラムはOpenMPのfor文と相性がよくないので、 ルート局面では全合法手を生成して(必要なら)並び替えるように変更する必要があります。 ルート局面の計算時間は無視できますので性能的には問題ありません。
リスト1.3ではαがグローバル変数であるために、 あるスレッドがαを更新するときにアクセスが競合します。 それを防ぐためにOpenMPにはcritical/flush/atomic等が用意されていますが、 原因は不明ですがこれらを使用しても時々不具合が発生します。 αを安全に随時更新できれば高い並列性能が得られますが、 現状ではリスト1.3は採用しません。

リスト1.3 最初の並列プログラム(時々不具合が発生する)
#include <omp.h>  // OpenMP関数を呼び出すとき必要
int searchr(tree_t *ptree, int depth) {
	int alpha = -infinity;  // グローバル変数であることに注意
	int beta = infinity;
	int value;
	int moves[MAXLEGALS];
	int nummove = generate_moves(ptree, moves);
	omp_set_num_threads(nthread);  // スレッド数を指定する
#pragma omp parallel for private(value)  // 以下のfor文を並列処理する
	for (i = 0; i < nummove; i++) {
		tree_t tree = *ptree;  // 局面を各スレッドにコピーする
		makemove(&tree, moves[i]);
		value = -search(&tree, depth - 1, -beta, -alpha);
		// treeは局所変数なのでunmakemoveは不要
		if (value > alpha) alpha = value;  // α更新がスレッド間で競合する
//#pragma omp flush(alpha)  // これが機能すればいいが..
	}
	return alpha;
}

リスト1.3の問題を踏まえ、リスト1.4ではαをスレッド変数としてスレッド毎に持ちます。
αを配列とし(配列の大きさはスレッド数)とし-infinityで初期化します。 並列領域ではomp_get_thread_num関数によりスレッド番号(tid)を取得しα配列を更新します。 最後にα配列の最大値を返します。
このようにαをスレッド別に持つと最適と言えないαによって枝刈りを行うために枝刈りの効率が下がります。
なお、将棋プログラムでは評価値以外に指し手も必要です。 またデバッグ用に読み筋も必要です。 これらを構造体にしてスレッド毎に持つと便利です。
またsearch関数の中でグローバル変数を書き換えるときはスレッド間の競合に注意してください。

リスト1.4 単純分散並列プログラム(αをスレッド別に持つ、schedule使用)
#include <omp.h>
int searchr(tree_t *ptree, int depth) {
	int *alpha; // α:スレッド配列、-infinityで初期化しておく
	int beta = infinity;
	int value;
	int moves[MAXLEGALS];
	int nummove = generate_moves(ptree, moves);
//#pragma omp parallel for private(value) // 既定値
//#pragma omp parallel for private(value) schedule(static, 1)  // 等間隔スケジュール
#pragma omp parallel for private(value) schedule(dynamic, 1)  // 動的スケジュール
	for (i = 0; i < nummove; i++) {
		int tid = omp_get_thread_num();  // スレッド番号を取得
		tree_t tree = *ptree;
		makemove(&tree, moves[i]);
		value = -search(&tree, depth - 1, -beta, -alpha[tid]);
		if (value > alpha[tid]) alpha[tid] = value;  // スレッドαを更新
	}
	return alpha[]の最大値;
}

OpenMPにおいてはforループをスレッドに分割する方法がいくつかあります。 これはリスト1.4の通り"schedule"句によって指定します。 図1.1に一例を示します。
"schedule"句を使用しないときは既定値となり1番上のようになります(ブロック分割)。 for文の各要素の負荷が均等なときはこれでも構いませんが、 将棋の木探索ではfor文の最初の方に負荷が集中しますのでこれは不適切です。
そこで"schedule(static,1)"とすると2番目のようになり各スレッドが等間隔で処理を担当します。 しかし将棋の木探索ではまだ不十分です。
"schedule(dynamic,1)"とすると3番目のように負荷が動的に調整され、 空いたスレッドに次の処理が与えられます。これが最も適しています。 なお、このときは各要素のスレッド番号が不定であることに注意してください。 最初がスレッド0である保証もありません。


図1.1 for文のscheduleについて(ループ長16を4スレッドに分割するとき)

2. 並列化のテスト

前節の方法で並列化したプログラムの計算時間をテストします。
プログラムの仕様は以下の通りです。

ハードウェアの仕様は以下の通りです。

テストした局面はプロの一棋譜から適当に取った20局面です。 探索深さを固定して計算時間を計測します。
Nスレッドのときの各局面の速度比および平均速度比を次式で計算します。

速度比(Nスレッド) = 1スレッドの計算時間 / Nスレッドの計算時間
平均速度比(Nスレッド) = Σ各局面の速度比(Nスレッド) / 局面数

図2.1は各局面の計算時間です(基本探索深さ4+静止探索深さ6)。
探索深さを固定すると、局面によって計算時間に大きな差が見られます。 しかし図2.2より速度比で見ると局面による差は小さくなります。
図2.3はscheduleを変えたときの速度比の違いです。上で述べたように"schedule(dynamic,1)" のとき最も速くなります。以下ではすべて"schedule(dynamic,1)"として計算を行います。


図2.1 各局面の計算時間

図2.2 各局面の速度比

図2.3 scheduleによる速度比の違い(4スレッド)

図2.4に探索深さを変えたときの平均速度比とスレッド数の関係を示します。 8〜12スレッドまでは速くなりますがそれ以上は逆に遅くなります。 また探索が深くなると速度比が低下しており、単純分散は実用的ではないことがわかります。


図2.4 平均速度比とスレッド数の関係(単純分散)

3. YBWC

本節ではより高速化が期待できるYBWC(Young Brothers Wait Concept)法について考えます。
以下では探索木の左端をPV、それ以外をYBと呼びます。
YBWC法では最初にPVを1スレッドで探索し、得られたαを共有してYBを並列探索します。 PVのαは良質であると期待できますので、 並列計算時の探索量の増大を抑えることが期待できます。
まず初めにYBWCのための準備プログラムをリスト3.1に示します。 これはリスト1.2のループをi=0とそれ以外に分割しただけです。

リスト3.1 YBWCのための準備(逐次版)
int searchr(tree_t *ptree, int depth) {
	int alpha = -infinity;
	int beta = infinity;
	int value;
	int moves[MAXLEGALS];
	int nummove = generate_moves(ptree, moves);

	// PVを探索
	makemove(ptree, moves[0]);
	value = -search(ptree, depth - 1, -beta, -alpha);
	unmakemove(ptree, moves[0]);
	if (value > alpha) alpha = value;

	// YBを探索
	for (i = 1; i < nummove; i++) {  // i = 1 から始まることに注意
		makemove(ptree, moves[i]);
		value = -search(ptree, depth - 1, -beta, -alpha);
		unmakemove(ptree, moves[i]);
		if (value > alpha) alpha = value;
	}

	return alpha;
}

次にリスト1.4に従ってαをスレッド配列にし、YBのfor文を並列化したものをリスト3.2に示します。
YBの前にPVのαを全スレッドで共有しています。

リスト3.2 YBWC並列プログラム
#include <omp.h>
int searchr(tree_t *ptree, int depth) {
	int *alpha; // α:スレッド配列、-infinityで初期化しておく
	int beta = infinity;
	int value;
	int moves[MAXLEGALS];
	int nummove = generate_moves(ptree, moves);

	// PVを探索(逐次計算)
	makemove(ptree, moves[0]);
	value = -search(ptree, depth - 1, -beta, -alpha[0]);
	unmakemove(ptree, moves[0]);

	// ここまでに時間切れのときは何もせずにreturnする

	// 全スレッドのαにPVのαを代入する
	for (n = 0; n < nthread; n++) {
		alpha[n] = value;
	}

	// YBを探索(並列計算)
#pragma omp parallel for private(value) schedule(dynamic, 1)
	for (i = 1; i < nummove; i++) {
		int tid = omp_get_thread_num();  // スレッド番号
		tree_t tree = *ptree;  // スレッド変数
		makemove(&tree, moves[i]);
		value = -search(&tree, depth - 1, -beta, -alpha[tid]);
		if (value > alpha[tid]) alpha[tid] = value;
	}

	return alpha[]の最大値;
}

図3.1にYBWCで探索深さを変えたときの速度比とスレッド数の関係を示します。
図2.4の単純分散に比べれば全体的に速度比が向上しています。 特に探索が深いときの速度比の低下が抑えられています。


図3.1 YBWCの平均速度比とスレッド数の関係

4. 2段YBWC

前節でYBWCにより並列計算性能が向上することがわかりましたがまだ不十分です。 原因としては以下のことが考えられます。

  1. PVを逐次計算しているので並列計算の速度向上には限度がある。
  2. スレッド数が増えるとYBでのα更新が不十分であり枝刈りの効率が落ちる。 (YB内の良い手がスレッド間で共有されない)
  3. スレッド数が増えると合法手の数に近くなり並列処理の効率が下がる。
このうち2.と3.は将棋の性質に起因するもので解決することは難しいですが、 1.については図4.1のようにPVをもう一段YBWCで処理することが考えられます。 これを2段YBWCと呼びます。


図4.1 2段YBWCの概念図

リスト3.1を2段YBWC用に書き換えたものをリスト4.1に示します。
合法手の配列は1手目と2手目の二つを持つ必要があります。
1手目のPVで局面を進めた後、2手目のPVとYBの探索を行い、その後1手目のYBの探索を行います。

リスト4.1 2段YBWCのための準備(逐次版)
int searchr(tree_t *ptree, int depth)
{
	int moves0[MAXLEGALS], moves1[MAXLEGALS];
	int alpha = -infinity;
	int beta = infinity;
	int value;

	// 1手目合法手生成
	nummove0 = generate_moves(ptree, moves0);

	// 1手目のPVで進める
	makemove(ptree, moves0[0]);  // *

	// 2手目合法手生成
	nummove1 = generate_moves(ptree, moves1);

	// 2手目のPV探索
	makemove(ptree, moves1[0]);
	value = -search(ptree, depth - 2, -beta, -alpha);
	unmakemove(ptree, moves1[0]);

	// 2手目のPVの結果でαを更新
	alpha = value;

	// 2手目のYB
	for (i1 = 1; i1 < nummove1; i1++) {
		makemove(ptree, moves1[i1]);
		value = -search(ptree, depth - 2, -beta, -alpha);
		unmakemove(ptree, moves1[i1]);
		if (value > alpha) alpha = value;
	}

	unmakemove(ptree, moves0[0]);  // *に対応
	value = -alpha;  // negaMax

	// 1手目のPVで時間切れのときは何もせずにreturnする

	// 1手目のPVの結果でαを更新
	alpha = value;

	// 1手目のYB
	for (i0 = 1; i0 < nummove0; i0++) {
		makemove(ptree, moves0[i0]);
		value = -search(ptree, depth - 1, -beta, -alpha);
		unmakemove(ptree, moves0[i0]);
		if (value > alpha) alpha = value;
	}

	return alpha;
}

次にリスト3.2と同様にαをスレッド配列にし、 YBのfor文を並列化したものをリスト4.2に示します。
YBの前にPVのαを全スレッドで共有しています。

リスト4.2 2段YBWC並列プログラム
int searchr(tree_t *ptree, int depth)
{
	int moves0[MAXLEGALS], moves1[MAXLEGALS];
	int *alpha; // α:スレッド配列、-infinityで初期化しておく
	int beta = infinity;
	int value;

	// 1手目合法手生成
	nummove0 = generate_moves(ptree, moves0);

	// 1手目のPVで進める
	makemove(ptree, moves0[0]);  // *

	// 2手目合法手生成
	nummove1 = generate_moves(ptree, moves1);

	// 2手目のPV
	makemove(ptree, moves1[0]);
	value = -search(ptree, depth - 2, -beta, -alpha[0]);
	unmakemove(ptree, moves1[0]);

	// 2手目のPVの結果で全スレッドのαを更新
	for (n = 0; n < nthread; n++) {
		alpha[n] = value;
	}

	// 2手目のYB
#pragma omp parallel for private(value) schedule(dynamic, 1)
	for (i1 = 1; i1 < nummove1; i1++) {
		int tid = omp_get_thread_num();
		tree_t tree = *ptree;
		makemove(&tree, moves1[i1]);
		value = -search(&tree, depth - 2, -beta, -alpha[tid]);
		if (value > alpha[tid]) alpha[tid] = value;
	}

	unmakemove(ptree, moves0[0]);  // *に対応
	value = -alpha[]の最大値;  // negaMax

	// 1手目のPVで時間切れのときは何もせずにreturnする

	// 1手目のPVの結果で全スレッドのαを更新
	for (n = 0; n < nthread; n++) {
		alpha[n] = value;
	}

	// 1手目のYB
#pragma omp parallel for private(value) schedule(dynamic, 1)
	for (i0 = 1; i0 < nummove0; i0++) {
		int tid = omp_get_thread_num();
		tree_t tree = *ptree;
		makemove(&tree, moves0[i0]);
		value = -search(&tree, depth - 1, -beta, -alpha[tid]);
		if (value > alpha[tid]) alpha[tid] = value;
	}

	return alpha[]の最大値;
}

図4.2に2段YBWCで探索深さを変えたときの速度比とスレッド数の関係を示します。
図3.1のYBWCと比べると全体的に速度比が向上しています。 特に探索が深いときの速度比が向上しています。


図4.2 2段YBWCの平均速度比とスレッド数の関係

以上から2段YBWCを用いると5-6倍程度の速度比が得られることがわかります。 12スレッドまでは速度比は向上しますが、それ以上のスレッド数では逆に速度比が低下します。 これは将棋木探索の特性によるものと考えられ、 さらに高い速度比を得るためにはより高度な手法が必要と思われます。

A. 付録

OpenMP参考文献

[1] OpenMP, http://openmp.org/wp/
[2] 菅原清文「C/C++プログラマーのための OpenMP並列プログラミング 第2版」カットシステム、2012

OpenMP開発環境

コンパイラーMicrosoft Visual C++GCC
コンパイル・リンクコマンドclgcc
コンパイルオプション/openmp-fopenmp
リンクオプションなし-fopenmp
ヘッダーファイル(注1)omp.homp.h
リンクするライブラリーなしなし
実行時に必要なライブラリーvcomp120.dll(注2)不要?
(注1)ヘッダーファイルの中身はOpenMP関数のプロトタイプ宣言であり、OpenMP関数を呼び出すときのみ必要。
(注2)"120"はコンパイラーのバージョン12.0を意味します。 このファイルはアプリケーションと一緒に再配布することが可能であり、 ファイルは C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\redist\x64\Microsoft.VC120.OpenMP にあります。 なお、64ビット版と32ビット版でファイル名が同じなので注意してください。

private句

#pragma omp parallel に続くprivate句はグローバル変数と同じ名前のスレッド変数を宣言しますが、 グローバル変数と各スレッドの変数のアドレスはすべて異なり、 かつスレッド変数は初期化されません。 スレッド変数をグローバル変数の値で初期化するためにはfirstprivate句を使用する必要があります。 以上の理由により以下のようになります。
	int x = 1;
#pragma omp parallel private(x)
{
	int a = x;  // xが不定なのでwarningが出る
}

	int x;
#pragma omp parallel private(x)
{
	x = 2;  // これはOK
}

	int x = 1;
#pragma omp parallel firstprivate(x)
{
	int a = x;  // これはOK
}

	int x = 1;
#pragma omp parallel
{
	int t_x = x;  // これは正しく動作するがOpenMP的には好ましくない
}

reduction句

全スレッドの集団演算にはreduction句を使用します。 例えば配列の和を並列計算する方法は以下の通りです。
reduction句の:の前が演算、後が演算の対象となる変数名です。
	int sum = 0;
#pragma omp parallel for reduction(+:sum)
	for (i = 0; i < n; i++) {
		sum += a[i];
	}

_OPENMPマクロ

コンパイルオプション/openmpをつけると_OPENMPマクロが定義されます。
またコンパイルオプション/openmpをつけないと#pragma omp行にwarningが出ることがあります。 これを回避するには以下のようにします。
#ifdef _OPENMP
#pragma omp parallel
#endif
{
	並列領域
}

トップページへ