開発道路地図（西日本編）

久しぶりにfloodgateやりましたが、６月末のバージョンとまったく変わってません。みさきと一度も当たってなかったのでいっぺんやってみたいなー、と。１勝２敗（実質）ならまあまあでしょうか。ちなみに私は先週田舎に引きこもってまして、既に夏休みは終わってます;_; 夏休みカムバーーーック！

さて、３回前の記事の続きです。何で西日本が後なんだ、という声が聞こえてきそうですが、まあ気にしないで。実はここしばらく囲碁ばかりやってるんですが、ちょっとしたイベントが発生しつつあって、そのからみで将棋に戻るかも、という状況で。で、「戻ったら何をやるか」の話。

前回までのあらすじ：
１）時間制御　…　済。成功。
２）ハッシュ　…　いちおう済だが、期待はずれ？
３）デバイスグレードアップ　…　これから。予算次第。レーティング＋１００？
と来て、その次。

４）P&R
P&Rとは（LSI）業界用語でPlace & Route、配置配線のことです。回路内の各論理モジュールを、FPGAチップ内の然るべき位置に配置し、端子どうしをメタル層で配線（結合）する、という作業です。この前段階として、モジュールごとに大まかな位置を決めることをfloorplanと言いますが、この作業も（ここでは）広い意味でP&Rに含めます。

今はQuartusIIのWeb Editionを使ってますが、このツールではfloorplanやP&Rの作業は「お任せモード」のみとなります。つまり、手動でのチューニングは一切できません。CycloneIIIからStratixIII（の大規模チップ）に移行すると、Web Edition（無料）は使えず、（有料の）Subscription Editionを使わざるを得なくなります。Subscription Editionには手動でfloorplan, P&Rをやる機能があります。別にCycloneIIIでもお金出してSubscription Editionを買えばP&Rできるのですが、まあ無料で済むなら無料のツールを使おう、ということでケチってたわけです。StIIIに行くならどのみちSubscription Editionを買わざるを得ないので、それならついでにP&Rもできるようになるからやろうか、ということです。

P&Rやると何がメリットかというと、回路が速くなることです。お任せP&Rで30MHz出るとすると、P&Rをチューンすれば、まあやってみないとわからない面はありますが、たぶん40-45MHzになると思います。速度２倍でレーティング＋１００とするなら、1.4倍だと+50くらい？

P&Rというのは、けっこう泥臭い、「土方作業」です。ツールの助けを借りるとはいえ、先の見えない試行錯誤を何度もやる羽目になり、正直気が重いです。私は十何年前LSI設計チームの新人でしたが、ほとんど徹夜でLSIの端から端まで手動で配線を引く、みたいなことをやった経験があります。まああまり楽しいものではない。もっとも最近はツールも発達したので全部手動なんてことはないはずですが。LSIの端から端までってのは実距離でいうと1-2cmなんですが、CADツールで拡大して見ながらやると、もう果てしなく遠いわけですよ。あれをまたやるのか…なお業界用語で配線を「引く」と言います。で私は、当時徹夜作業をやりながらこんな歌を口ずさんでました。

♪君の引く道は　　果てしなく遠い
　だのになぜ　　　歯を食いしばり
　君は引くのか　　そんなにしてまで

工数どのくらいかかるかもまああんまりわからないんですが、ざっと２、３か月くらいかな。このくらいやればかなり速くなるんじゃないかと思います。これは来年の大会までにはできればやりたいですね。まあ予算とモチベーション次第なんですが。工数はかかりますが、あまり頭使う話ではないので（まったくってことはないんですが）、やってみたけどできないってことはたぶんないと思います。

５）パイプライン

FPGAの動作周波数は、flip flop間の最長パスで決まります。そのパス上に別のflip flopを置いてパスを区切れば、周波数を上げられます。これを「パイプライン化」と言います。（正確に言うとちょっとあれですが、まあおおざっぱに言うと。）もちろん単にflip flopを置けばよいというわけではなく、論理がうまく動くように周辺の回路もいじる必要があります。

パイプライン化の方向として、大きく２つに分かれます。１つは、単一の探索「スレッド」の効率を上げる方向。もう１つは、切ったパイプラインの各ステージをそれぞれ別スレッドと考える方向です。後者は概念的にはマルチコアにするのと大差ありません。ちょっと違いますが、Pentium 4のHyper Threadingみたいなもの、といえばイメージ湧くでしょうか。ハード的にはこの方が簡単。ただ、αβ探索の並列化がそうすんなり行くものではないというのは、コン将に詳しい方ならよくご存知の通りです。

じゃあ単一スレッドをどうやってパイプラインで効率上げるのか？というと、実はまだあまりちゃんと考えてません^^; ま一応漠然としたアイデアくらいはあるのですが、果たしてうまく行くかどうか。これがうまく行かなければ、複数スレッドでしょう。

パイプラインもそう無制限に切れるわけではないですが、まあ今までの感触だと３段くらいには切れそうかと思ってます。ただ周波数３倍ときれいには行かず、ま2.5倍くらいでしょうか。仮に複数スレッド方式としましょう。３スレッドになって性能どのくらい上がるかもまあよくわからんですが、全く根拠ないながら経験的にこのくらいか？というのは、「ルートの法則」。N並列で、性能がsqrt(N)倍になる、という仮説です。仮にこうだとすると、sqrt(3) * 2.5/3 ~= 1.4。性能1.4倍なら、レーティングはやはり+50くらいですか。

かかる工数は、単一スレッド方式の方はまだよくわかりません。だって何をどうやるかわかってないし。ってそんなんでできるのかね。複数スレッドにするなら、ハードの変更はまあ２か月もあれば十分できそうな気がします。ただこれだとソフトを並列化にしないといけないので、こっちの方で３か月以上はかかりそうです。

…何か書いてるとどうも長くなるな^^; 続きは「開発道路地図：裏日本編」で書くことにしませう。残るは　６）マルチコア、です。