インサイド・ボンクラーズ

今作っているクラスタ並列将棋ソフト「ボンクラーズ」の中身について少し書いてみます。（CSA提出文書ドラフト？）

[概要]
１個の「マスター」プロセスと、１個以上任意個の「スレーブ」プロセスが協調して動作します。マスターはルートから探索木を展開していき、適当な深さでノードの探索をスレーブに「ディスパッチ」します。スレーブはそのノードの下の探索を行い、結果をマスターに返します。

マスターとスレーブはそれぞれ別個のプロセスとして動きます。（「スレッド」ではありません。）これらのプロセスは、同一マシン上でもよいですが、別のマシン上で動いていてもかまいません。マスターとスレーブ間の通信は（必要なら）ネットワークを介して、MPI(Message Passing Interface)規格に基いて行います。今の実装では通信はマスター～スレーブ間のみで、スレーブどうしの通信はありません。

[メリット]
複数個のスレーブを使うことで並列処理ができます。スレッドを用いる(Craftyのような)並列処理と異なり、共有メモリを前提としないため、数百、数千といった大規模な並列処理が可能となります。またXeonやOpteronのようなサーバ用CPUを必要とせず、普通のデスクトップ用のCPUが使えるため、コスト的にも有利になります。

[ソフトウェア構成]
マスター側プログラムは大きく以下の部分から成ります。
　a) フロントエンド（サーバとの通信、ユーザインタフェース）
　b) マスター探索エンジン
　c) MPI通信

b),c)は今回新しく作った、全くの新規プログラムです。a)はボナンザのフロントエンドを流用して作っています。A級リーグ指し手１号ではれさぴょんのフロントエンドを使っていましたが、floodgateの連続対戦の対応、ponderの実装等の面でボナンザの方が多機能だったため今回はこちらにしました。

マスターではボナンザの探索エンジンは基本的に使いません。ボナンザのiterate()を改造してあり、searchr()のかわりに並列探索ルーチンを呼ぶようになっています。

スレーブ側プログラムは
　d) MPI通信
　e) スレーブ探索エンジン
に分かれます。d)は新規プログラム、e)はボナンザを流用しています。スレーブ側はマスターとは逆に、ボナンザのフロントエンドは使わず、探索部(search())のみ使います。

MPI通信部がマスターからのコマンドを受け取ります。コマンドには（局面、α、β、深さ）の情報が含まれます。MPI通信部はこのコマンドを解読して、ボナンザのsearch()を呼びます。探索が終了するとマスターへ結果を返します。

今の実装では、マスターもスレーブもボナンザベースのため、バイナリは共通です。MPIの'rank'によってマスターかスレーブかを切り分けます。ただこれは必然性があってそうしているわけではなく、マスターとスレーブを別バイナリにすることも可能でしょう。

なお、スレーブ側エンジンは今はボナンザのものを用いていますが、たいていの将棋ソフト(/ハード)はスレーブ用に改造することはおそらく簡単なので、利用できそうなものがあればスレーブ側エンジンとして使ってみることもそう難しくはないでしょう。FPGAやASICのようなハードウェアをスレーブにすることも可能だし、たとえばGPS将棋のような別のソフトを使うことも考えられます。ハードウェアの場合はMPIはないでしょうが、MPIといっても今使っているのはRecv, Send, Probeくらいで、高級な機能(GatherとかAllReduceとか）は使っていないので、MPIなしで直接TCP/IPで実装することも可能と思います。

[アルゴリズム]
スレーブ側の探索アルゴリズムはボナンザまったくそのままです。ボナのsearch()を呼ぶだけです。

マスター側の探索アルゴリズムは今までにない全く新しいものです。ルートから数手はマスターで展開し、その後スレーブに渡す、というのが基本方針ですが、この具体的やり方はいろいろバリエーションが考えられます。どうするのがよいのか、まだわかっていないというのが現状で、今はいろいろ変えながら試行錯誤している状況です。

[現状の実力]
最近floodgateで１コア(shigekuni)と４コア(isane)を時々流しています。今(1/31)１コアでR~2300、４コアでR~2400くらい。本家ボナv4.1.2で同じマシンで、１コアR~2400、４コアR~2700なので、１コアはだいぶ追いついてきましたが４コアはかなり負けています。

ちょっと前は４コアで２倍程度出たと書きましたが、その後バグ修正をしていくうちにだんだんコードが保守的になってきて、今は４コアで1.6-1.8倍くらいしか出ていません。本家は3倍くらい出ているようなので、マスターのアルゴリズムはもっと改善が必要な状況です。まあ、共有メモリでできたことがクラスタ並列でもできるとは限らないのですが。

スレーブ１コアというのは並列化による性能向上という面からは無意味ですが、マスター探索の性能を測るために使っています。本家の１コアより良くなる要素はないですが、「それほど悪化してない」ことを確認するのが目的です。現状R~70差で、まだ多少改善の余地はあるかと思いますが、一時期よりはかなりよくなり、まあまあ合格点のとこまでは来たかなと思っています。

[使用ハードウェア]
今はCore i7 860(4コア)のマシン１台で動かしています。全プロセス同一マシン上で、ネットワークは介していません。以前にちょっと試したところではネットワーク越しにしてもそれほど性能は落ちなかったです。

近々２台めの４コアPCを自作する予定。HTは意味なさそうなので、PhenomII X4あたりになりそうです。一式~\40kかな。大会での使用マシンは未定ですが、おそらく今のi7 860 + 今度のPhenomII、の８コアは使うでしょう。予算とスペースとブレーカーに余裕があれば４コアマシンもう１台くらい使うかも？でもそれ以上は、自前で揃えるのはちょっと難しそうです。

Amazon EC2とかを使って64コアくらいできないかな、などと考えなくもないのですが、EC2だとVMだし場所もどうなっているのか不明なので、ネットワークディレイやプロセススイッチ時間がどうなるか未知数。使い物になるかどうかちょっとわかりません。

（追記）上の記事は１０時間ほど前に書きましたが、今みると（今日午後はfloodgateに出てないのに）isaneのRが2477まで上がってました。なんで？よくわかりませんが、「２週間レーティング」なので、２週間前にぼろ負けしてたのがカウントされなくなったりとかするんでしょうかね。

ボナ実験終了

floodgateでbona412i7860{1t,8t,noht4t} 走らせてみました。どれも60局以上。まだ対局数少ないんでしょうが、あまりいつまでもやってるわけにもいかないので、このくらいあればまあまあ正確でしょう。現在のR(2週間)は

1t         2386
noht4t  2693
8t         2621

でした。くどいようですが、bonanza v4.1.2 そのものです。

問題集もやらせてみました。前回と同じく、「読みの技法」25問、depth 9です。単純に時間を見てるだけで、実はPVとか変わってるかも。25問の回答時間合計で速度を測定。1tを基準として、

8t     2.7 (倍)
noht4t 3.1
noht3t 2.6  (<- floodgateではやってません、問題集のみ)

HT役立たねー。
しかし4コアで３倍超はすごいですね。
また、３倍でR300ですか。なんか出すぎのような。そんなもんなのかな。

ボナ1thr vs 8thr 比較

floodgateで1スレッドと8スレッド走らせてみました。対局数少ないので若干不正確かと思いますが、1t R2376, 8t R2593。R200+差ですね。

問題集もやらせて時間測ってみました。「読みの技法」の25問。以下、第二列が8tの時間（秒）、第三列が1t、第一列がその比です。limit depth 9です。ボナの出す"Elapsed"をみてます。

2.7倍くらいですか。8tといっても4コアのHTなので、ルートN以上出てるといっていいでしょうね。ときどき1を越えたりしてるのは、時間が短いためスレッドのオーバーヘッドが見えたのではないかと思います。

これでR200+か。思ってたより効いてるような。

eiki@burn:~/bonanza$ perl /home/eiki/icc_bonk/timecompare.pl tstlogs tstlogs.old
[1] 0.343221  <-  29.390000 85.630000
[2] 0.877551  <-  0.430000 0.490000
[3] 0.430357  <-  35.470000 82.420000
[4] 0.662162  <-  0.490000 0.740000
[5] 0.435407  <-  1.820000 4.180000
[6] 0.345070  <-  0.490000 1.420000
[7] 0.336976  <-  9.560000 28.370000
[8] 1.058824  <-  0.540000 0.510000
[9] 0.446985  <-  6.450000 14.430000
[10] 0.530612  <-  0.780000 1.470000
[11] 0.709402  <-  5.810000 8.190000
[12] 0.605263  <-  0.690000 1.140000
[13] 0.846154  <-  1.320000 1.560000
[14] 0.291087  <-  3.560000 12.230000
[15] 0.983051  <-  0.580000 0.590000
[16] 0.489247  <-  2.730000 5.580000
[17] 0.775000  <-  0.310000 0.400000
[18] 0.411411  <-  1.370000 3.330000
[19] 0.286744  <-  27.840000 97.090000
[20] 0.375000  <-  8.280000 22.080000
[21] 1.200000  <-  0.540000 0.450000
[22] 0.650485  <-  0.670000 1.030000
[23] 0.962500  <-  0.770000 0.800000
[24] 0.657895  <-  0.500000 0.760000
[25] 0.775000  <-  0.620000 0.800000
total 0.375336  <-  141.010000 375.690000
eiki@burn:~/bonanza$

だめじゃん

とりあえず、これはまずいな。何とかしないと。

マスターがCPU1、スレーブが2-5。CPU固定。

…って、あれぇ？0-7じゃなくて1-8？てことは、マスターが2、スレーブが3-6かな？

だけどこれだけでR400差ってこともないよな。もっといろいろせなあかんのだろうな…

業務連絡

bona412i78608t 走らせてます。bona v4.1.2 まったくそのままです。
元がどのくらい強いのかなーと思って試してみてます。前回記事で自作したマシン使用。8スレッド。コンパイルはbonanzaのMakefileのmake iccそのままです。

ちなみにpgoもちょっと試してみましたが、それほど速くならないですね。2%くらい。

そのうち1スレッドや4スレッドもやるかもしれません。

ボンクラーズ、デビュー

年末にどうやら連続対戦でほぼコケないまでになり、さっそく元旦からfloodgateに投入しました。bonkra_s です。名前からは「もしや、あのお三方の合議システム！？」とか思われた方もいらっしゃるでしょうか。豆ちしきー　うちらの名前は、ボナンザクラスタ、からとってるんやでー

ゆくゆくはFPGA(/ASIC)を念頭に置いて開発してるんですが、並列ソフトデバッグの段階で１２月になってしまったため、ハードの改造までは次の大会には間に合わない。でどうしようかと考えたんですが。マスター側とスレーブ側がありまして、スレーブというのはマスターから（局面、α、β、深さ）を受け取って探索して結果を返す、をひたすら繰り返します。ということは、別にFPGAでなくてもたいていの将棋ソフトならわずかな変更でスレーブになれるんですよね。そこで、ボナをスレーブ向けに改造。ボナソースへの修正量はわずかで、１週間足らずでできました。

ボナ自体を改良するのは私にとっては本題ではないのでやるつもりはありません。あくまで、マスター側開発のスタブとしての位置づけです。GPSもライブラリになるようなので、余力があったらジピクラーズもやってみますかね。（難しいかも^^;）

ＰＣはこのために自作しました。i7 860 \27k, MB \10k, GB \3k, メモリ \5k, HDD \5k, ケース＋電源 \6k。計 \56k。光学ドライブはこんなこともあろうかと外付けを持ってるので不要。OSはLinuxなのでただ。クラスタ並列実験専用と割り切って最小限の構成です。

このＰＣで動かして、現在floodgateでR2300程度。本家ボナ4coreが今R2700近いのでこれではまったく意味ないんですが、いろいろクラスタ化のオーバーヘッドがあったり、まずは動かすために探索をはしょったりしてる部分があるので今のところこうなってます。この辺はこれから改善を試みていく予定。

スレーブ１コア対４コアでざっとですが性能を測ってみたところ、約２倍（問題を解く時間が半分）。いちおうルートＮは出てるので、ひとまず安心です。といってもルートで満足してはいられないので、ここも要改善ですが。せっかくのクラスタ並列なので１００コアとかもやってみたいところですが、これはマシンを使う機会があったら、ですね。なお、floodgateでは運用の手軽さという面から全プロセスi7上ローカルで動かしてますが、マスターを別マシンにしてネットワーク越しに試しても性能はほとんど落ちませんでした。これは良いニュース。まあ、そうなるように工夫して作ったつもりなので、なってくれないと困るんですが。

ちなみにHTで8プロセスにすると４より遅くなりました。たしかGPSでは8の方が速かったと金子さんが話していた記憶がありますが、ここはプログラムによるんでしょうか。

数十局やったところで少し改善を入れてみたらバグで落ちたため、ひっこめて調査中。もうデバッグはいいかげん疲れてるんですが^^; 実はバグがあるうちからfloodgateでお試しで流してました。isaneとshigekuniがそれ。コア数によって分けてます。これらはtime upやらabnormalやらでぼろぼろ負けてます。今後もunstableな改造はテストIDで試してから本IDに投入、の予定。