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

飲み会翌日は年次とってダラダラする、が座右の銘です。

裏、とか問題表現を用いております。何かT*COSチームあたりからクレーム来そうな。

６）マルチコア

FPGA思考エンジンを複数個使って並列処理で性能上げることを考えます。

まずFPGA１チップにどのくらい入るのか？です。今のAリーグはCyclone IIIのEP3C120というチップ(1個)が載ってるボードを使ってます。FPGAチップの規模は、LUTという基本単位の数で表されますが、このEP3C120には120K個のLUTが載ってます。ただFPGA上のLUTはすべて100%使いきることはまず不可能で、せいぜい85%くらいです。つまり120K個のうち100K個くらいしか使えない。で、今のAリーグは約70K LUT使ってます。なので、２コアも載りません。

これをマルチコア化するには、A)もっと大きいFPGAチップ（が載ってるボード）を使う、B)FPGAが複数チップ載ってるボードを使う、C)ボードを複数枚つなげる、という３つの方向があると言えます。これらは排他的ではなく、組み合わせることも考えられます。

まずA)チップ巨大化の方から。
CycloneIIIだと120K LUTが最大のチップですが、上級シリーズであるStratixIIIでは最大はEP3SL340。340K LUT相当です。正確に言うとStratixIIIとCycloneIIIでは基本のLUT自体が異なるのですが、StratixIIIの方の340という数字はCycloneIIIのLUT換算、の模様です。このチップが使えると、70K LUTのエンジンは3-4個入りそう。

ただ、お値段も張ります。EP3SL340を搭載したボードはTerasicから出ていますが、代理店の立野電脳（株）のページには以前、90万円と載ってました。うーん…ちょっと手が出ないですね。まあ車買うと思えばまったく出せないってことはないかもしれませんが、これ使えば大会で優勝できるというならまだしも、２次予選１５位が１０位になる、くらいでは90万出す気はしないでしょう。なおEP3SL340を搭載したボードは他にもあるのですが、このTerasicのがいちばん安いそうです。

最近発表されたStratixIVは、IIIより集積度が上がっています。まだ価格等は不明ですが、おそらく290K LUT相当のチップが今のEP3SL150と同じ程度の価格で出てくるのではないかと思われます（チップサイズ等からして）。EP3SL150搭載のボードは30万円強。290Kだと3コアくらい入りそうです。ただ新製品は発表から実際の出荷まで１年近くかかるので、StratixIVは来年の大会には間に合わなさそう。

B)複数チップ搭載ボードというのは、あることはあるのですが、最低でも100万近くします。あと、チップ間の結合がボードによって変わってくるので、汎用的な設計ができないというのもつらいところ。上述の立野電脳ページを見ると、EP3SL340を60個(!)搭載のボード、なんてのもありますね。これだともしかして決勝行けるかも？でも、数千万かかりそうです。
またC)複数ボードも価格ネック。150のボード１枚が約30万なので、３枚で約90万。これもちょっと現状検討対象外です。

ということで、普通に考えると再来年にStratixIVでマルチコア、というのが現実的な線になりそうです。…などと言いつつ、実はここがもう少し何とかならないかと、多少裏技的な話を進めたりもしてたりします。まあまだちょっとどうなるかわからないので、うまくいくようならまた後ほど書きます。

なお大きいチップを使うとすると、ツールも強化が必要です。今のEP3C120用にはコンパイル用のＰＣにCore2Duo 1.86GHz + 2GBメモリ + WinVista 32bitを使ってますが、これで70K LUTの回路のコンパイルに約６時間かかってます。３コアチップのコンパイルには、メモリは6GB程度必要な見込み。必然的にＯＳも64bit版が必須。ツール(QuartusII)はたしか並列化対応してるはずなので、今だとCore2Quadくらい使いたいところ。周波数もできるだけ速いの。コンパイルに数日、なんてなった日にゃたまらないので。などと言ってると、今のＰＣは自作で５万円くらいだったんですが、次は私がいまだかつて使ったことないようなモンスターマシンを使うことになりそうです。我が家はウサギ小屋なのでサーバなんぞは置けませんが、デスクトップの幅広いのになるんでしょうね。…机狭くなりそう…

<並列化時のソフト>

コン将での並列化というと、Crafty流がおそらくいちばんポピュラーでしょう。ですがこれはＡリーグでは使えない。Crafty方式はスレッド間でメモリ共有を前提にしていますが、うちは共有メモリないし。なので、クラスタ並列のモデルを想定してます。

実はクラスタ並列化は、５年くらい前にDeep Purpleで試してました。なので、ソフトはこう作ればよいだろう、というのはある程度イメージできてます。とはいえ性能上げるにはかなりのチューンが必要になるでしょうが。

工数的には、ハードよりもソフトの方が大半になるでしょう。だってマルチコアのハードなんて、メモリ共有しないなら「並べるだけ」みたいなもんですからね。クラスタ並列探索の実装とチューンに何か月かかるか…というところ。来年５月にできるかはちと疑問。まあハードが来年は揃わんだろうというのもあるので、再来年にStratixIV＋並列化ソフトでマルチコア、というくらいの気分でおります。

さて性能向上ですが、StratixIVの290K LUTに３コア入ったとして、「ルート仮説」を信じると1.7倍。レーティング+70くらいかな。StratixIVの最大チップは680Kだそうですが、もし裏技等でそれが使えると7－8コア入って2.5倍？レーティング+150か。

　＊　＊　＊

長々と書いてきましたが、以上の1)-6)が2008年大会以降の主な実装改良アイデアです。まとめると、1),2)は既に入ってますんで、グレードアップで2倍/R+100、P&Rで1.4倍/+50、パイプラインで1.4倍/+50、マルチコアで1.7倍/+70？ぜんぶ合わせて6.8倍/R+270くらいでしょうか。まあいろいろ仮定入れてますんで、誤差だいぶあるでしょうけど。仮にこのとおりとして、今のマイムーブにやっと追いつくくらいですか。2年たてばまわりも強くなるでしょうから、結局順位はあまり変わらないのかな？

「高速化の話ばっかじゃん！他にないのかよ？！」と思われるかもしれません。いやまったくそのとおり。ただ、高速化は定量的に見積りやすいんですよ。レーティングいくら上がるか、まである程度予想つきますから。もちろん評価パラメタのチューンというのもあるんですよ？これはこれで多少やることにはなると思いますが、これやってどんだけ強くなんのよ？というのがさっぱり予想つかない。なのでどうしても優先度低くなってる、という状況です。記事に書きづらい、というのもあるし。

高速化以外で強くなりそうなこととしては、
　１）評価パラメタのチューン、の他に
　２）定跡チューン
　３）水平線対策
があります。

定跡に関しては、今は１４手めまではれさぴょんまかせ、それ以後は定跡の続くかぎりれさぴょんが指し、定跡から外れるとFPGAで指します。最初のころは３０手までとかしてたんですが、急戦になると２０手めくらいから切りあいになることもけっこうある。れさぴょんは戦いでなければかなりまともな手を指すんですが、ちょっと強い（２次レベル以上の）ソフトと戦いで競り合うとあっさり読み負けて駒取られることも多かったため、切りあいになる前にFPGAに移るように、多少安全めにみて１４手としてます。

しかし１４手では、囲いきってくれない。矢倉系だと、７八金、７七銀くらいまで動かしたところでFPGAに移ります。FPGAは囲うなんてことは考えてません。王が金銀に寄る、くらいはやってくれるので、５九から６八に行く、くらいはやります。その後右金が４九->５八くらいにも時々来てくれる。でもそこまで。王が８八に入ったりは絶対せず、６八のまま戦いに入る、というのが現状のパターンです。ですのでこれをちゃんと８八まで囲うようになんらかの工夫をすれば、けっこう強くなるだろうとは思っております。

ただ、定跡ははっきり言ってやる気ありません。FPGAでなくソフトでやるところなので、「俺のやることじゃねーよ」とか思ってるんですよね。大会参加というのを気にしなければ、極端な話、序盤は今のれさぴょんのかわりにもっと強いソフト使って、また途中からFPGA、とすればよいわけです。一から十まで全部自分で作ろう、という気ははなっからないので。実際、大会でなくfloodgateならこれで十分なわけですよ。いやどっかからひんしゅく買いそうな気もしますが。

水平線対策というのは、ハッシュコードを実装したので、同一盤面のチェックができるようになった。なので、たとえば歩を打ち捨ててその後同一盤面に戻った（持駒減っただけ）、を検出して評価マイナス無限大にしようか、そうすりゃ打ち捨てしなくなるだろう、ということです。今のAリーグを見てると、ちょっと相手の注文にはまって若干の損が必須となったとき、その損を受け入れてそこからベストを尽くせばまだそう致命的に悪くはないのに、そこで無駄に歩を打ち捨てたりして決定的に形勢損ねる、というのがけっこうあるんですよ。これは（ハッシュ入れた今となっては）そう難しくないはずなので、やりたいとは思っているんですが、これまた効果が定量的に見えないため、目に見える高速化の方を優先していて、いつになるかわからん、という状況です^^;;;

これ以外は、大きく効果期待できそうなものは今のところ思いつかないです。探索系は、王手や取り返しの延長は入ってるし、けっこういろいろ試してもみたし。末端近くで手を刈るのもけっこうやったし。ネタがない、です。まあこれまで挙げたものだけでおなかいっぱいではあるんですが。

　＊　＊　＊

話変わってFPGA-MC囲碁の方ですが、中断してます。いろいろ検討してたんですが、今のやり方に限界を強く感じるようになってきたため、別のアプローチで検討を始めたところ。これもそのうち書く予定です。

　　　＊

…という記事を書き上げて、さあこれから投稿しようか、というところで、例の情報処理の記事のコピーを入手しました。Ａリーグのことも多少書いてあって、ありがたいことです。名前違ってましたが^^; それはともかく、鶴岡さんの「ＡＳＩＣにしたら」に、……！！！　フラグ立ってしまいました。不覚にもぜんぜん考えてなかったですが、うーむ。よいですねぇ。むふふふ。検討してみましょう。

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

久しぶりに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くらいですか。

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

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