Altera DE0 nanoで実装できるか？
DE0 nanoのSDRAMについて
DE0 nanoには32MBのSDRAMが搭載されています。Terasicの評価ボードのうち、これだけ大容量のSDRAMが搭載されているモデルは珍しく、その点はなかなか良いと思うのです。
出来れば、DE0 nanoで動作速度は遅くとも一通り思考ルーチンが動作すれば今後の開発意欲も湧いてくるというものです。
Nois IIに専用命令を拡張していき実装することを考えていたのですが、Nois IIは論理合成にそこそこ時間がかかるのでターンアラウンドタイムが非常に時間が悪くなってしまいます。まだverilog初心者の私が採るべき方法ではないと判断しました。
そこでまずはDE0 nanoのSDRAMについて少し調べてみます。
DE0 nanoに搭載されているSDRAMのデータシートはこちら。
ftp://ftp.altera.com/up/pub/Altera_Material/11.0/Tutorials/Verilog/DE0-Nano/Using_the_SDRAM.pdf
データバスは16bitのようで、16bitずつしか読み書きできないようですが…置換表は128bitの読み書きがしたいのでどうせならばこのSDRAM8個ついてくれているとすごく良かったのですが…ついてないものはどうにもなりませんね。
ピンヘッダー自体は出ていますからSDRAMのドーターボードがあれば良いのですが…何故か売られていないようです。
指し手生成がボトルネックになる？
局面を進めたあと、置換表を参照しに行く必要があり、通常、そのメモリアクセスがボトルネックになるでしょうから、その間に指し手生成をしておけば指し手生成に要する時間は相対的には無視できるのかも知れません。(よくわかりません)
ただ、局面を1つ戻して(探索深さを1つ戻して)次の指し手について調べるようなときに、その再度すべての指し手生成が必要になり、このときは置換表を調べに行く必要がないのでこの間の時間もすこぶるもったいないです。
未生成の指し手のうちオーダリングで2番目に来るべき指し手についてもピックアップできていれば良いのですが、コンパレーターツリーの出力付近に2番目がいるとは限らず(早い段階で1番目の値と比較され、出力付近まで残れていない可能性があります)、2番目を求めるためのコンパレーターツリーを別途用意するかという話になるのかも知れません。それとも、次の局面に進め、置換表を見に行っている時間に指し手生成部では局面を進めずに2番目の指し手を生成だけやっておくのはアリなのではないでしょうか。
もしそういうことが可能なのであれば、結局、置換表への読み書き部分がボトルネックであるということになるのかも知れません。置換表に評価値が書かれていないときは評価値を評価関数で計算しますが、しかしそれは置換表を調べに行く程度の時間でおそらく出来るはずです。
探索部も考えてみますと…
・ある局面を展開したとき、最初に置換表を調べる
case 1) 置換表に載っている → 既知の局面なのでまず置換表の指し手を試す。置換表の指し手を生成済みにしたあと指し手生成をしておく。そのあと局面を進める。置換表は先行して調べておく。
case 2) 置換表に載っていない → 未知の局面なので評価関数を呼んで評価値を取得。その間に指し手生成。評価値によってはβcutがなされる。
・ある局面に戻ってきたとき
case 3) 枝刈りの条件を満たしている → 局面をさらに戻る。置換表に書き出すならば書き出す。またbest moveとして生成した指し手のhistoryを加点する(指し手生成器がこの点数を保持している)
case 4) 枝刈りの条件を満たしていない → 次の指し手を生成する必要がある。(ここに時間がかかる。他に何もできない！馬鹿らしい！)
つまりはcase 4でストールするわけです。ここでストールする割合がどれくらいあるのかよくわかりませんが結構あるような気がします。複数コアで探索していれば、置換表の読み書き自体がボトルネックになるでしょうからそうでもないと思うのですが、LEが余っているのであれば複数コアにするよりは少しでも評価関数の充実を図りたいのでcase 4が許せないのです。
case 4の割合がどれくらいあるのか考えてみますと、置換表の指し手がある場合は普通その手で枝刈りがされますから、たいてい遅延表に指し手が書かれていなかったケース、すなわち新規局面なのだと思うのですが、新規局面は全体の半分以上が新規局面だと思うので、この部分が時間がかかりますと非常に苦しいものがあります。
こうして見ますと2番目の指し手も同時に生成してしまうのはアリではないかと思えてきます。2番目の値を抽出するコンパレーターをうまく書く方法がよくわからないのですが、N個ずつ組みにして値を比較して、上位2個ずつ残していけば、最後に残るのは上位2個ですかね…。コンパレーターツリー、何段必要なのでしょうか。わけがわかりません。簡単にできそうにないですね。これをやるぐらいなら、指し手生成をもっと並列化するほうが現実味がありそうです。
そんなわけでして、指し手生成は極めて難しいということは前回の考察から理解できたのですが、まずはDE0 nanoに収まるように書きたいので、まずは81セルの指し手生成器を用意して17クロック固定で使用して6段のコンパレーターツリーで実装してみるところからやってみたいと思います。
Noisが150MHz程度で動作するところを見ますと(5段パイプラインですが…)、6段のコンパレーターツリーと言えども100MHz程度では動作するのでしょうから(なんなら分割すれば…)、指し手生成が17+3クロック程度で終わるとしまして…他の処理に要する時間は相対的に無視できるとしまして…。5Mnps程度。DE0 nanoで(このLE数で合成できるかどうかは知りませんが)5Mnps程度！
いまどきたいした数字ではないのでしょうけども、1Mnpsでもなんでも動けばこっちのものです。あとは指し手生成をさらに並列化するなり、評価関数を充実させるなり、もっと速いFPGAボードに移行するなり、探索コアを複数載せるなり、なんでもできます。
そのためには動くことを第一段階目の目標にせねばなりません。
DE0 nanoに搭載されているSDRAMについて
SDRAMの型番 → ISSI IS42S16160B-7
データシート
http://pdf1.alldatasheet.com/datasheet-pdf/view/153633/ISSI/IS42S16160B-7B.html
100MHz動作でCAS latency = 2のようです。つまりはREADコマンドが発行されたクロック信号の立ち上がりから数えて、2つ目のクロック信号の立ち上がりでデータがもらえるようです。
つまりは、最悪でも1/50M秒でデータが取り出せていると考えていいわけですかね。8回の読み出しには10回要することになりますね。置換表を1ノードに1回、読み書きするならばこのメモリの読み書きに要する時間だけでおおよそ1/5M秒。ああ、置換表への書き出しはそのノードの評価値が確定したときのみですので、それよりはマシだとしまして…それでも1/10M秒。指し手生成などが時間0としましても10Mnpsしか出ません。なかなかメモリアクセスだけでも大変ですね。
SDRAMが8つ載っているならおおよそ1/8で済むのでしょうけども。16bitずつの読み書きはさすがに遅すぎますね。内蔵RAMにcacheすることも考えられますが、そんなに訪問済みのノードばかりに当たるわけでもなくその部分ではそんなに効率化は図れないでしょうね。なんとももどかしいものがあります。
コンピューター将棋に適したFPGAボード
Altera DE4 Development and Education Board
http://www.terasic.com.tw/cgi-bin/page/archive.pl?Language=English&CategoryNo=138&No=501
Terasicの評価ボードには、Stratix IVが載っていてSO-DIMM(64bit幅で転送できるみたい？)が2本載っているものがあります。お値段$2,995。228KLE,FPGA内蔵メモリ17,133Kbit(おおよそ2MB)。Stratix IVとVはさほど速度に違いはないようですし、内蔵メモリ的にも現時点で最大級です。LE的にもちょうどいい感じだと思いますし、この評価ボードならばうまくすれば50Mnpsぐらい出せるのではないでしょうか。
DE5-NET
こちらはまだTerasicからは買えないみたいですが(国内代理店では立野電脳が「短納期です」とアナウンスしています)、DDR3 SO-DIMMが2本載るのでよさげですが、5SGXEA7N2F45C2が載っていて、これが5SGXA7だと思うのですが、
を見ますと622,000LEの製品でして、おそらく80万円ぐらいするのだと思います。
高額なFPGAボードが欲しいかも
現時点では私には指し手生成器と評価関数にどれくらいのLE数が必要なのかがよくわからないため、FPGAボード選びに苦労します。DE0 nanoである程度実験してみたいと思います。(そもそもDE0 nanoのLE数で足りるのかどうか…)
それはそうと、指し手生成を完全に並列化した場合、仮に150K LEでそれが出来るとしまして、探索自体にはさほどLEは必要ありませんから、あとのLEはすべて評価関数のために使うことが出来るという意味はあります。内蔵メモリが少ないので大きなテーブルを用いる評価関数は載らないとは思いますが、しかし、評価項目が増えてもLE数が余分にいるだけで、動作速度はそれほど遅くはならないでしょうから、LE数の限界まで評価関数を大きくしてみるのも面白いのではないでしょうか。
置換表がSDRAMを食いつぶす
仮に100Mnps出るとしまして、1秒間に100M回×16バイト(128bit)書き続けますと4GBのメモリですとものの数秒で溢れてしまいます。4GBはもしかすると少ないのかも知れません。まあ、探索ノードすべてで置換表に書き出すわけではありませんがそれにしても…。
そういう意味では内蔵メモリや搭載できるSDRAMのメモリ量の上限が決まっている評価ボードですと置換表に書き出すメモリが足りなくて困るということはありえるのでしょうね。なかなか難しいですね。
