Hydra考 (5)
テーマ：計算機将棋DeepBlueにしろHydraにしろ、探索速度(レート)を稼いでいる要はハード探索に因るものであってソフトは単にその支援を行っているに過ぎない。しかしながら、だからと言って根ノードからハード探索を行って効率を上げられるのかと言えばそうはならない。恐らく根ノードから行えば、どこかの深さでソフトとハードの「実効＝速度と効率の積」が逆転する。まずハード探索では厳密な置換表処理が（出来なくはないだろうが）難しいし、特定の手を延長して探索するといったことも簡単ではなく、探索する手のオーダ制御も同様だ[*1]。それが出来るのか出来ないのかどっちなんだと言われれば「FPGAのリソースが許す限り可能」なのだが、それだと今度は速度が犠牲になってしまいかねない。それらの平衡を保ちながら、最終的に「最も高い棋力を得る」ことが目標になってくる。
さて、DeepBlueの稼動率の悪さは、CPU間通信オーバヘッドとソフト探索側でのハード探索コアの利用の拙さが主原因と思われる。特にDeepBlueの場合、１個のCPUが16個のコアを使用できる仕様になっているが、単に「固定的な深さのノードでしか並列化してない[*2]」のなら、Chrillyの言にもあった通り、高い稼動率を望めない。並列αβ探索で効率を上げるコツは、「(NegaMax表現で)α値が決まっていて、且つβ値が決まっていないノード」部分を並列探索することにある。α値が決まってない（１番目の手を未だ探索してない）ノードでは、他の枝の枝刈が起きにくく無用な探索を行う可能性が高くなるし、β値が決まっているノードでは枝刈によって他の枝の探索が全く無駄になる可能性があるからだ。
またHydraの場合、ChrillyはPCIバスのボトルネックを強調している。これはPCIカードの仕様による制限か、ドライバの仕様に引っ張られて性能を上げられない、あるいは通信プロトコルが拙いのかも知れないが、何れにせよ稼動率を上げる余地は充分あるのではないかと感じている。そもそも論をぶってもしょうがないのだが、グラフ状ゲーム木を並列でαβ探索する場合、先の理由とは別にクラスタ構成では効率を上げにくい[*3]。各CPUが他のCPUと密接に連携して並列実行しないと無駄が生じやすい[*4]。
更に、DeepBlueもHydraも、恐らくCPUから探索コアに対して探索依頼を行った後、その結果がコアから返って来るまでCPUはアイドル状態になっているだけだと思われる。その時間資源を使って「２つ目以降のコア」を効率的に使うために、別系統のノードの探索を行わせて並列数を上げさせることも可能な筈だが、このあたりはChrillyにとっても今現在課題になっているのではないかと思う[*5]。
理想的には、クラスタによる並列実行ではなく、少数のCPUであってもSMPによる協調処理の方が有力な筈で、各CPUが全ての探索コアに対して自在に制御できる構成の方が性能を落としにくいだろう。具体的な例を考えれば次の様になる。
左図は、各CPUが「待機している探索コア」を自在に要求して使用できるという仕様にしたものだ。間にマネージャが入るが、CPU側から見れば処理を依頼する相手はマネージャだけであって、Ready状態のコアをいちいち探す必要はない。マネージャから見れば、処理を要求しているCPU（あるいはスレッド）が誰であるかは、どのアドレスへアクセスされたかで判ることが出来るようにし、結果もそのアドレスから返すようにすれば混乱が起きることはない。マネージャが空いているコアを常時管理して処理を依頼し、コア側でその探索が終了すれば結果をマネージャへ引き渡し、マネージャが代行して依頼主のCPU側へ返すというわけである。更にフライングで探索依頼、または投機的に探索が出来るようにキューを持たせ、必要に応じていつでも探索をキャンセル出来る機能もマネージャ側に欲しい。以上のように出来れば、コアの稼働率を限界まで上げられることを期待できる。
この図は、4CPUs/8cores構成になっているが、FPGA側は8coresである必要はない。仮に32coresに出来るならば、現Hydraと大して変わらないかそれ以上の性能を実現できる可能性がある。CPU-FPGA間通信プロトコルを工夫した上で Memory mapped I/O にすれば、レイテンシはそれほど落ちるものではないし、少なくとも光ネットワークよりは遥かに速い。目指しているのは「車検が通るスポーツカー」ではなく、「サーキットのレコードを叩き出すフォーミュラマシン」なのである。私がもしFPGAを用いて探索を行うのであれば、試してみたいアーキテクチャの最有力候補としてここに記録しておく。
[*1] 例えば「前回の反復深化時の最善手から読む」といった細かな制御に対処しにくい。
[*2] Hydraのコアでは「残３手＋静止探索」、DeepBlueのコアでは「残４手＋静止探索」のようである。但し、DeepBlue場合、静止探索に入る前に延長処理が入ることもあり、固定的に４手全幅＋静止探索というわけではないようだ。
[*3] 正確に言えば、元々の意味での「収穫逓減」が起き易い。
[*4] なお、NUMAの場合は各CPUのバスの利用(主にメモリアクセス)で互いが邪魔をし合わないようにするためのアーキテクチャだが、極端に大きなスレッドローカルストレージ領域が必要でないなら、NUMAであることが有利とはならない。
[*5] もしかすると、ある程度解決している問題なのかもしれないが、そのような論文が見当たらない。
