インテルによる「ポーカーの手の判別の並列化」について


概要:インテル デベロッパー・ゾーンで公開されている「C++ 11 でマルチスレッド・コードを記述する」という記事の,「ポーカーの手の判別は並列化しても速くならない」という主張について調べた結果,私の環境で4.9秒かかる元記事の処理が,0.68秒で終わるようになりました.(コード

計測すべし。計測するまでは速度のための調整をしてはならない。(ロブ・パイク)

オリジナルのpokereval/pokereval.cppを見ながら作業しましょう.

Step 1:実験の意義

タスクの中でスリープするのはやめましょう.そういうことをすればマルチスレッド版がシングルスレッド版より速くなるのは当然ですが,意味がありません.105行目を書き換えます.

//Sleep(1);

Step 2:データセット

2万件(正確には19981件)ではすぐに終わってしまうので,100万件のデータを使いましょう.207行目を書き換えます.

std::ifstream filein("hands1million.txt");

Step 3:シングルスレッド版の実行時間

シングルスレッド版はこれで動くので,この実行時間を基準にチューニングします.

筆者のPC(i7-4930K,Visual Studio Community 2017,Win32 Releaseモード)では,4.9秒でした(シングルスレッド版・オリジナル).

Step 4:バグ修正

マルチスレッドのコードにバグが2個あるので修正します.(補足:この修正はpull requestしました.)

(1) 入力の終わりの判定が間違っていて,hands1million.txtの最後の空行をカウントしています.283, 284行目の,

if (filein.eof()) break;
std::getline(filein, str);

を次で置き換えます.

if (!std::getline(filein, str)) break;

(2) スレッド数の倍数だけ処理したところで出力していますが,最後に余った分を出力し忘れています.299行目の#elseの前に,次を挿入しましょう.

if (count != MaxThreads - 1) {
  for (int i = 0; i < count; ++i) {
    fileout << futures[i].get() << '\n';
  }
}

Step 5:マルチスレッド版の実行時間

269行目の#define Multi 1を有効にして,マルチスレッド版の実行時間を計ります.

筆者のPCでは5.7秒でした(マルチスレッド版・オリジナル).

マルチスレッド版がシングルスレッド版(4.9秒)より遅いと悔しいのは確かです.

Step 6:計測

Visual Studioの,デバッグ→パフォーマンス プロファイラーで,関数ごとのCPU使用率を計測します.

測定結果の上位は次のようなものでした.

プロファイル結果

std::basic_istreamに一番時間がかかっています.もう少しよく見ると,その大部分は,std::endlで費やされているようです.

Step 7:パフォーマンスチューニング

『C++の教科書』の8.2.3項に,endlはバッファをフラッシュさせると書いてあります.100万件のデータの出力する際に,1件ごとにフラッシュするのはまずいでしょう.294行目のstd::endl'\n'に置き換えます.

fileout << e.get() << '\n';

筆者のPCでは2.5秒でした(マルチスレッド版・修正後).

残念ながら,これでシングルスレッド版(4.9秒)を上回ったわけではありません.シングルスレッド版のコードでもstd::endl'\n'に置き換えて(256行目),実行時間を計ります.

筆者のPCでは1.4秒でした(シングルスレッド版・修正後).

依然として,マルチスレッド版よりシングルスレッド版の方が高速です.

とはいえ,元記事の「評価の実行時間が短すぎて、タスクを非同期に呼び出すオーバーヘッドが原因である」という考察は疑問です.ここで解いているのはいわゆる embarrassingly parallel というやつで,並列化の効果が,「あって当然」だからです.

Step 8:OpenMP

OpenMPを使いましょう.『C++の教科書』の12.4節に使い方が載っています.

マクロで場合分けしてもかまいませんが,シングルスレッド版のコード(300から306行目)を書き換えます.データをメモリに読み込んで,OpenMPで並列に判別し,結果を出力します.

std::vector<std::string> hands;
while (std::getline(filein, str)) {
  hands.push_back(str);
}
rowCount = hands.size();

std::vector<std::string> results(rowCount);
#pragma omp parallel for
for (int i = 0; i < rowCount; ++i) {
  PokerHand pokerhand(hands[i]);
  auto result = EvaluateHand(pokerhand);
  results[i] = pokerhand.GetResult(result);
}

for (int i = 0; i < rowCount; ++i) {
  fileout << results[i] << '\n';
}

筆者のPCでは0.68秒でした(OpenMP版).これでシングルスレッド版・修正版(1.4秒)より速くなりました.シングルスレッド版・オリジナル(4.9秒)よりはかなり速いです.ちなみに,OpenMPを有効にしない状態でのこのコードの実行時間は1.7秒でした.

まとめ:ポーカーの手の判別は並列化で速くなります.

本を書きました。『基礎からしっかり学ぶC++の教科書』


4822298930
『基礎からしっかり学ぶC++の教科書』(日経BP, 2017)

プログラミング言語なんて,Python一択になるんじゃないの?という向きは,TensorFlowのコードや,世界コンピュータ将棋選手権の参加チームの使用言語をご覧になるといいでしょう。「どうしてJavaやC++よりも遅いPythonが機械学習で使われているの?」などという話もあります。

『文法からはじめるプログラミング言語 MS Visual C++入門(マイクロソフト公式解説書)』(日経BP, 2009)の改訂版という位置付けですが,かなりの部分を書き直しました。

新しい話

  • C++11, C++14に対応しました。新しい話題は,型推論・ラムダ・ムーブ・新しい標準ライブラリ(ハッシュテーブル・並列処理・乱数・時間)などです。
  • Visual C++に加えて,GNU C++とClangでも,サンプルコードの動作を確認しています。
  • (実用的かどうかはともかく)C++の高速性が活きる例として,組み合わせパズルを解きます。(何を勘違いしたか,初刷では幅優先探索の英語が間違ってますな!)

なくしたもの

  • GUI(GUIアプリを作るならC++でなくてもいいだろうと考えてのことです。)
  • C++/CLI(旧版で,マネージ拡張という失敗例を紹介したわけですが・・・)

C++入門書の執筆は,プログラミング初心者からは「難しい」,C++のプロからは「いいかげん」と言われる,負けの決まった戦いです。(いいわけ)

(インテルとAMDのCPUの)三角関数は不要


インテルとAMDのCPUには,三角関数を数値的に計算するための命令が備えられていますが,その結果は正しくありません。たとえば,CPUの命令FCOSの結果とstd::cosでソフトウェア的に計算した結果を比べると,後者の方が真の値に近くなります。

再現のためのコード(FCOSを使う部分だけインラインアセンブラを使っています。)

Core i5 6600とg++ 4.8.4で試した結果はこんな感じです。

x = 0.98233490762409514385
c1 = fcos(x)     = 0.55508189550073283591
c2 = std::cos(x) = 0.55508189550073294694
c  = mp::cos(x)  = 0.555081895500732891425063460345544265145531916268
abs(c - c1) = 5.5512e-17
abs(c - c2) = 5.551e-17

c1 is better: 0
c2 is better: 25
total: 100000

(その正しさをどうやって確かめるのかという問題はありますが)Boost.Multiprecisionで計算した結果と比較すると,命令`FCOS`より`std::cos`の方が正確なようです(Visual Studioの場合はまた違った結果になるようです)。

Pentiumが割り算を間違うといって大騒ぎになったことがありましたが(Pentium FDIV バグ),数値計算はどうせ近似値だからでしょうか,この問題は,ドキュメントに注意書きが追記されただけで,根本的な解決はされないままのようです。

参考:サイン、コサインをインテルの CPU で計算すると少しバグっているらしい

魔方陣の解の数を一瞬で求めるプログラム


以前、「スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す(C++)」という記事を書きましたが、解を列挙するのではなく、解の数を数えるだけなら一瞬で終わらせるプログラムがあります。

4×4の魔方陣の場合

clang++ -O3 -std=c++11 magicsquare4.cc」などとしてコンパイルしてから実行します。実行時間は一瞬です。

このプログラムの欠点は、コンパイルにかなりの時間がかかることです(TANSTAAFL)。手元の環境では、コンパイルに4分くらいかかりました(説明するのは野暮ですが、これはネタです)。

C++のconstexprを使っています。複数のコンパイラがconstexprをサポートしていますが、このコードをコンパイルできるのは、私が試したところではClang 3.3のみです(Ubuntuでは「sudo apt-get install clang-3.3」などとしてインストールできます)。ステップ数に上限が導入されたClang 3.4以降や、途中経過を記憶してメモリを圧迫するgccではコンパイルできません。

Clang 3.3でサポートされるconstexprの関数には、大ざっぱに言えばreturn文しか書けないので、マスに数が入るかどうかをチェックする関数を作り、「数がすでに使われていなければ次のマスを試し、使われていれば1だけ大きい数を再帰的に試す」ということを、return文の条件演算子で実現しています。

このコードは私が直接書いたものではなく、私が書いたプログラムが生成したものです(手で直接書くのは大変です)。同じプログラムで5×5の場合も生成しましたが、試すのはやめた方がいいでしょう(constexprを消してコンパイル・実行すれば、正しいことは確認できます)。

スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す(C++)


追記:対称性の活用法をコメントで教えていただきました。それを採用すると本稿の結果よりもかなり高速になります(10分→6分)。(コード

筑波大学のスパコン「T2K-Tsukuba」で約2時間36分かけて5×5の魔方陣(≠魔法陣)の全解を求めたというニュースがありました。

「スパコン」ではなく「パソコン」だったらどうなのだろう、と思って試してみたら、10分でした(Core i7 4930K)。

解の「数」がわかればいいだけ、つまり全解をディスクに書き出さなくてももいいならもう少し早くなります。

コードはこちら(最初のバージョン)。頭の悪そうなコードですが、スクリプトで生成した枠組みを手直しして作れば、そんなに大変ではないかと。理想は全自動生成ですが。Visual Studio 2013 ExpressとICC 14.0.2、GCC 4.6.3、Clang 3.4で動作を確認しています。ClangはOpenMPに対応させるのが面倒なうえに、ちょっと試したところでは、GCCより遅かったです。(実際に試す場合は、OpenMPを有効にしてください。計算中のCPU使用率は100%になるはずです。)

多重for文(笑)ですべての場合を探索するというのが基本方針ですが、それではさすがに終わらないので、次のような工夫をします(工夫というほどのものではありませんが)。

  • 各行・各列・対角線の和は65。(1から25までの和 / 5)
  • (カンで)効率が良くなりそうなところから順番に埋めていく(下図の番号順)。
  • 回転と裏返しで同一になるものを重複して数えないように、下図の緑部分に、「左上<右上<左下」かつ「左上<右下」のような制約を入れる。左上は22以下としてよい。
  • a+b+c+d+eのうち、a,b,c,dが決まったら、e=65-a-b-c-dになる(下図の紫部分)。
  • a+b+c+d+eのうち、a,b,cが決まったら、dはmax(1,65-a-b-c-25)からmin(25,65-a-b-c-1)の範囲で調べればよい。max(un,65-a-b-c-ux)からmin(ux,65-a-b-c-un)にするとさらに速くなる(unは未使用の最小数,uxは未使用の最大数。これを調べるのに時間をかけると効果はなくなる)。

この方針の場合、ループを関数で表現したり、盤面をコンテナで表現したりすると遅くなります。

数を埋める順番
6 10 11 12 8
20 1 18 2 21
22 13 5 16 23
24 3 19 4 25
9 14 17 15 7

魔方陣の解の列挙は並列化しやすそうな問題ですが、ここでの方針では、探索効率を上げるためには条件分岐が不可欠なので、(「数」を求めるだけだとしても)GPGPUでうまくやる方法がわかりません。そこで、CPUに載っているコアのみで並列化します(Xeon Phiなら簡単なのでしょうか→追記参照)。

一番外側の、0から(1<<25)-1まで変化する変数iのループをOpenMPで並列化します。変数iは上の図の緑の部分(カンで5個にしました)を各数5ビットで表現し、つなげたものです。マスに入りうる数は1から25までなので、5ビットというのはちょっと冗長ですが、とりあえずはよしとしましょう。

一番外側の、0から(N – 3) * N * N * N * NN^4 + N^3 + 2N^2 + 3N + 4から(N – 4)N^4 + (N – 1)N^3 + (N – 2)N^2 + (N – 3)N + (N – 4)まで変化する変数iのループをOpenMPで並列化します(schedule(guided)では遅くなります。schedule(auto)はVisual C++でサポートされたら試します)。変数iは上の図の緑の部分(カンで5個にしました)を掛けたものです。

出力はバイナリ形式で、1つの解に25バイト使います(1つのマスに入る数を1バイトで表現する)。これはちょっと冗長ですが、テキスト形式よりは小さくて速いはずなので、とりあえずはよしとしましょう。

解は全部で2億7530万5224個、1つの解を25バイトで表現するので、(スレッド数と同数できる)出力ファイルのサイズの合計は275305224 x 25 = 6882630600バイト(約6.4GB)になります。

最初のバージョンの実行時間は以下の通りです。最終的には、先述の通り、もう少し速くなります。

Core i7 4930K(12スレッド・出力先はRAMディスク)
  • Windows 7 64 bit, Visual Studio 2013 Express, 593秒(約10分)(ターゲットはx64。/openmp /Ox /arch:AVX
  • Fedora 20 64 bit, Intel C++ Compiler 14.0.2, 471秒(約8分)-fopenmp -O3 -xHost
  • Fedora 20 64 bit, GCC 4.8.2, 583秒(約10分)-fopenmp -O3 -march=native
Core i7 4700MQ(8スレッド・出力先はSSD)
  • Windows 7 64 bit, Visual Studio 2013 Express, 1156秒(約20分)/openmp /Ox /arch:AVX

4535786569大森清美『魔方陣の世界』(日本評論社, 2013)(参考文献リストあり・索引あり)を見たら、a+b+c+d+e=65のとき、(26-a)+(26-b)+(26-c)+(26-d)+(26-e)=65なので、解の、すべての数xを(26-x)に置き換えたものもやはり解になるということが載っていました。変数x7を13以下に限定して、「x17 < 13 && x19 < 13」のときのcountsの増分を2にすれば、私のコードでもこの知識を活用できますが、やっても速くはなりませんでした。この知識を使えばもっと速くなるでしょう(ここでは試しませんが)。コメントでご指摘いただいたように、この知識を使って、真ん中のセルに入る数字を1から13までに限定し、そこが13ではない解が見つかったら、すべての数xを(26-x)に置き換えたものも解として出力するようにするとさらに速くなります(同条件でちょうど6分)。

『魔方陣の世界』では、この問題のためのコードも紹介されていますが、並列化されていないこともあって、解の「数」を調べる場合は約5000秒(確認済み)、全解を出力する場合は約3日(未確認)と、あまりふるいません。

この問題は、パソコン・プログラミングに最適の題材である。(p.111)

今日では、5次方陣の総数検索問題は、パソコンに最適な題材となった。(p.124)

パソコンに最適とも、スパコンに不適とも思いませんが、興味深い題材であることは確かです。

追記

  • 正解の数(2億7530万5224個)を知っているから速いのか? 正解の数は1981年にはすでに知られていましたが、ここで試した方法では、その知識は使っていません。ディスクの空き容量は小さくてよいことがわかっているとか、下に書くような理由で、正解が既知だと試すのが気楽だということはあります。
  • 結果の正しさをどうやって確認したのか? 確認していません。解の数は既知なので、それと同じ数が出てくればまあいいかなと。正しさを確認するためには、(1)得られたものが本当に解であること、(2)結果に重複がないこと、(3)すべての場合を調べていること、の確認が必要です。(1)はループの最も内側で解になっているかどうかをチェックすることによって、(2)は得られた解をハッシュテーブル等に格納することによって確認できますが、ある程度のメモリと時間(上のマシンだと約200秒)が余分に必要です(コード)。(3)はここでは難しいですね。
  • アルゴリズム? 穴埋め問題の穴を多重for文(笑)で埋めているだけなので、アルゴリズムというほどのものはありません。(参考:Puzzles for Hackers
  • 10分くらいならやってみようかなという人が、きれいな書き方やGPUで解く方法、効率的な方法を見つけてくれればと思います。(参考:Toy problemsは役立たずか
  • Xeon Phiなら(ほぼ)そのままのコードが動いて、計算は5分で終わるそうです。(スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙をXeon Phiで試す - パラレルに恋して