Parallelaその後

並列プロセッサーであるParallelaは、Kickstarterで資金を集めていたようなのですが、その期日が16時間後に迫ってきました。

http://www.kickstarter.com/projects/adapteva/parallella-a-supercomputer-for-everyone


昨日の時点では予定額である$750,000に$100,000ほど満たなかったのですが、ようやく$750,000を超えたので$99払う人は16コア版が来年の5月ごろに届くことが確定的になりました。



しかしもうひとつの設定額である$3Mには満たないので64コア版は今回はリリースされないのだと思います。これについては、もう2,3年待たないといけないのかも知れません。


コンピューター将棋にParallelaのようなNUMA(Non-Uniform Memory Access)型のプロセッサーが適合するかどうか考えてみましょう。


NUMA型というのは、よくあるモデルとしてはタイル状にCPUを配置して、隣合うCPU(上下左右)同士をつないでやるというものです。


この上下左右の接続は比較的低い遅延で接続されていますが、それでも64個接続の場合で左上から右下へは下に7回、右に7回で14回のバケツリレーが必要なので14サイクル分の遅延はあります。結果データを回収するときも左上で回収するならば同様に14サイクルの遅延があります。往復で28サイクルです。CPU数が64個ではなく256個(16×16個)ですと往復60サイクルです。


いくらなんでも小さいタスクを投げて結果を回収するだけで60サイクルもかかるのは厳しいものがあります。また256個もCPUが接続されていますとデータを投げるだけで256回も投げないといけないのではメインのCPUに負担がかかりすぎます。


そこで、普通はメインのCPUの負担を減らすためにすべてのCPUに対してデータを投げる(ブロードキャストする)ための特殊な命令を用意します。左上のプロセッサーから伝達していくとして、このデータを受け取ると右側と下側に接続されているCPUにも同じデータを伝達するものとします。(Parallelaにそのような命令があるのかどうかは知りませんが。)


次に、タスク内容を左上のCPUからブロードキャストするのであれば、結果データの回収を右下のCPUからしたいのは言うまでもないことで、(計算は左上のCPUから終わるのでそれを右下に向かって伝達して右下で回収するほうが時間のロスが少ない)、NUMA型では上下左右のCPUと接続するだけではなく、リング状に接続することもよくあります。IntelのMany CoreであるKnights Cornerがこのようなリング状の接続をしていると言われています。(来年ぐらいには発売されるのでしょうか…)


コンピューター将棋に限って言えば、与えられるタスクはすべてのCPUにおいて同一だとして、例えば指し手生成であれば前回局面からの差分(次の1手の指し手情報)をブロードキャストして、そしてそれぞれのCPUが自分に割り振られた指し手を生成するという仕組みを取ります。そう考えますとブロードキャストは頻発するのでブロードキャストは少しでも速いほうが良く、本当にバケツリレーで伝達していいのかという問題はありそうです。


データの回収も、例えばそれぞれのCPUが局面の部分的な評価値を計算して結果を右下のCPUに伝達するのであればその伝達するときに足し算もして欲しい気はします。すなわち、CPU間で情報を伝達するときに足し算マークがついていれば、左のCPUから来た情報と上のCPUから来た情報を足し算したものを次のCPUに伝達するというような仕組みです。


そう考えますと、コンピューター将棋にとって望ましいのは64コア版のParallelaではなく、FPGAでNUMA型の汎用プロセッサーを実装するほうがいいのではないかとも思えます。少なくとも局面の評価値を計算するだけでしたら乗算・割算はもとより引き算も不要ですので、汎用プロセッサーと言えども命令数はかなり少なくて済みますから、Z80が1200LE(LE = Logic Element)程度で収まることを考えますと、一つのCPUはそれ以下のLE数で収まることは間違いなく、300K LEぐらいの製品でも256CPUは可能なのではないでしょうか。


FPGAでNUMA型の汎用プロセッサーを実装する利点としまして、一度論理合成をしてしまえばそのあとはその汎用プロセッサー用の命令でプログラムを書いていけばいいので以降は論理合成をする必要はなく、また、その汎用プロセッサー用のエミュレーターを実装すれば効率的にデバッグが出来るようになるということです。


FPGAのほうは、いまであればVirtex-7あたりが良いと思うのですが、300K LE規模の評価ボードで$3500程度。1M LE規模の評価ボードはおそらくその3倍ぐらいのお値段です。コンピューター将棋の探索部もまるごとFPGA化しようと思いますと、FPGA上に汎用CPUを実装してその汎用CPU用に実装するのであればそれ自体は難しいことではないのですが、Intelの最新のプロセッサーに比べて1/4程度の速度にすることすら難しいのが実状で、なかなか厳しいものがあります。


局面の評価値の計算だけFPGAでやらせるようなソリューションもありだとは思うのですが、PCIe、もしくはHyperTransportで接続したとしてもCPUとFPGA間での往復だけで0.5ms程度かかるらしく*1、他の部分の時間がすべてゼロで済んでも2Mnpsしか出ません。実際はゼロでは済まないので500Knpsすら厳しいと思います。


このような場合、CPU側は並列探索して、FPGA側からの結果を待たずにどんどん局面を投げてlatencyを隠匿させるのが普通ですが*2、仮にFPGA上では局面の評価を1秒に20M回ぐらい出来ていたとしても、1Mnps程度の実効速度すら出るのかどうか…。



Parallelaにもっとローカルメモリーがあれば普通にそれぞれのCPUに探索を割り振って並列探索をさせたほうが良さそうですが、そんなにローカルメモリーはありません。IntelのKnights Cornerの場合、それが出来そうですが、1GHz程度とアナウンスされていますので√N程度の実効しか出ないとすれば、50CPUでも…。計算したくありませんね。並列探索の効率は√Nほど悪くないと思うのですが、それでも1GHzでは萎えますね。


ただ、FPGA上に汎用CPUを作る場合、ASICに比べると動作周波数は低いはずで、500MHz程度ですら出るかどうかわからず、さらに厳しいです。



結局のところ、凄く時間のかかる局面評価だけをFPGAに投げて、メインCPUとのやりとりにかかるlatencyを隠匿するためにメインのCPU側では並列探索(100並列ぐらい?)を行なうのがいいような気はするのですが、そうしますとメインCPU側から渡す局面図が前回からの差分で済みませんから…いやはや考えたくもないですね。


ヘテロジニアス型のマルチコアでの並列コンピューティングはコンピューター将棋にはあまり向いてないのでしょうね。少なくとも普通のハイエンドCPUと同等のnpsで同等の処理が出来るということだけを目標としたとしても非常に厳しいものがありそうです。