将棋でのクラスター並列探索

SSPの作者様（マイボナの作者）がMPIを用いた疎結合環境での並列探索をYSSの掲示板で提案されてました。

囲碁ではクラスター探索もやられてるので、将棋でもどうかなあ？　ギガビットイーサで？とか、選手権会場とかGPW会場でも言ってたのですが、
やってみればいいだけですね(^^;

通常の将棋の並列探索は、同じCPUダイ上で、ハッシュメモリを共有する密結合ですが、
疎結合の場合は共有メモリを持たない並列環境。
MPIは並列用の汎用ライブラリ

http://www.geocities.jp/shogi_depot/
こちらから説明のPDFとソースをダウンロードできます

実験結果を見たのですが、
まずは同一マシン上で、プロセス間通信の環境で並列探索をされたようです。
この場合、探索の指示などはMPIのライブラリで、プロセス間通信。ただしハッシュの共有はできない。
2並列で1.5倍とかルート２程度の効率が出ているようで、ちょっと不思議でした。
ハッシュを共有してないし、そんなに効率が出るものでしょうか？　しかもルートのみ分割だし

ただ、探索プログラムの出来次第でこのへんは変わりそうですね。
ルートでの最善手が変化する割合が多ければ、ルートで分割しても効率が出るでしょうし、
（サンプルソースはPVSでも無いようなので、ルートのカットノードでヌルウィドウ探索ってことでもないでしょうし）

肝心の別マシンを使ったギガビットイーサでのクラスター並列探索は、わまり芳しくなかったようです。
残念(^^;
たとえ転送バンド幅がギガでも、重要なのは通信を送って届くまでの時間。レイテンシというんでしたっけ？
やはりこれがあまり良くないのかもしれない。masterからslaveの指示と返事で二倍かかりますし
実験では100μ秒と仮定してましたが、実際どの程度でるもんなのでしょう？

ただ、ルートが手が少ないときは、次の深さで分割すると良いというのは確かにそうですね
王手された場合など手数が極端に少ないですから。
ルートで合法手が10手あって、深さ２で分割するとすると、

１）ルートで1手指す→master分割指示→slaveから返事→返事そろう→深さ２の最善手決定
２）ルートで1手指す→master分割指示→slaveから返事→返事そろう→深さ２の最善手決定
……
１０）ルートで1手指す→master分割指示→slaveから返事→返事そろう→深さ２の最善手決定

ということで、通信の遅延がTとすると、20Tの遅延が出ますね（slave指示はすべてのslaveにほぼ同時に出すと仮定）
（ただ、2手目の並列探索中に誰かがベータカットを起こすとそこで終了）

1コアでも、1秒あれば深さ8とか9ぐらいは読めるので（Bonanzaはもっと読める）
このTが多いとかなり効率が落ちるはず。
これが深さ３とか4になると、展開ノードが増えるので、分割指示を出す回数が増えて、さらに遅延による効率低下は増えるはずで……

ただ、浅いところで分割だと思考時間に余裕があるときは、やらないよりはやるほうが良いはずなので、
決勝戦クラスはやってもいいと思うんだけどねえ(^^;　マシンも余ってるだろうし。
ノートPCなら搬入も楽だろうし

しかし、
MacPro(Xeon4コアdualで8CPU）で密結合8並列探索をやって、ルートだけはMPIでクラスター並列
クラスターが足を引っ張らないかなあ？(^^;　いや、理論上は通信遅延があっても、
思考時間＞遅延*2(指示と返事で）であれば、悪くはならないと思う。
でも、やはり効率は悪そうな気もする。
Lalabie（つづりが違ってそう）がくれば、密結合で100コアなんて時代もすぐそこまで来ているし……

しかし、ハッシュを共有しないでも効率はさほど悪くならないってことはあるのかなあ？
それならロックもいることだし、なくして見て試すのも価値があるかもしれない。

近山研究室の「ゲーム木探索の大規模並列化」
http://www.logos.ic.i.u-tokyo.ac.jp/~miwa/papers/bachelor/zenkoku.pdf
http://www.logos.ic.i.u-tokyo.ac.jp/~miwa/papers/bachelor/sotsuron.pdf