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

今作っているクラスタ並列将棋ソフト「ボンクラーズ」の中身について少し書いてみます。（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まで上がってました。なんで？よくわかりませんが、「２週間レーティング」なので、２週間前にぼろ負けしてたのがカウントされなくなったりとかするんでしょうかね。