汎用Multi-FPGA PCIカード

テーマ:

最近、超ハイエンドFPGAカードを知ったので紹介しようと思う。

左のFPGA カードは、GiDEL というFPGAボードプロバイダが出しているFPGA4個搭載PCIカードPROCStarII である。詳しい諸元についてはHPの方をご覧になっていただくとして、Altera StratixII EP2S60~180までチョイス出来るプロダクトのようである。

2S180[*1]×4だと、そのお値段はR34GTRの新車価格くらいになるようだが、Chrillyのように32セットの古い「Xeon+FPGAカード」を買うよりは安いし、巧く制御出来れば、これ1枚で現Hydraと同等のパフォーマンスは出せそうだ。

今の私には全く手が届かないとしても、最終目標の4~5年後には使ってみたいカードの有力候補である。それまでに等価性能の物が1桁安くなって、せめて(最低でも)133MHz PCI-X Rev2.0 mode1か、(もはや別物だが)PCI Express x16くらいのバスI/F[*2]にして欲しいところだ。いや、今やAGP[*3]が空いているので、それでも可だが。結局バスのボトルネックを克服出来るかどうかは、プロトコルを含めた通信のノウハウと、低水準I/Oにも手を入れる(つまりはデバドラから作る)覚悟があるか否かだと考えている。


[*1] 因みに2S180は2C35の約5倍の規模の回路を組める。以前にも書いたが、このFPGA1つの中にChrillyの探索コアが8個入るしその上速い。熱対策を施せば基準クロック100MHz前後で安定して走れる筈である。

[*2] この手のバス規格はとてつもなく奥が深い。例えば、133MHz PCI-Xと言っても2枚挿しすれば100MHzでしか使えないし、4枚挿しすれば66MHz駆動になる。セカンド・オピニオン第40回 から(今日現在では)第144回まで「バスのアーキテクチャ - 過去から未来へ」が連載されている。興味がある人にとっては面白いコラムだと思うのでご覧になることをお奨めする。

[*3] バス幅は32ビットだが、8倍速モードで2.13[GB/秒]の帯域を遊ばせておくのは勿体無い気がする。


I asked the impression of this card to Marc. He said: "The GiDEL board looks very nice, I see no reason why it would not be good for you, as long as the fpgas are big enough (I don't know Altera much). However, a first step will be to get a single engine working (that fits in a single fpga hopefuly); the parallel engine can come after." Thx for your advices, Marc.
AD

以下の内容について相当迷ったが、やはり計算機将棋界の発展の為に心を鬼にして書くことにした。


進歩5p.173では、▲ハイパー将棋▽KFEnd戦が採り上げられている。これも二次予選からではあるが、まさに関西計算機将棋界の最高峰の将棋で、現実の将棋界に喩えるなら▲内藤▽谷川戦に匹敵する対局だ。


左図は、教授のご指摘通り96手目▽75角と進めた局面。p.174「…筆者の推測では、図から▽75角に対して▲31竜があるからだろう」。私はこの一文を読んで、顔面にハリセンが飛んで来たような衝撃を感じた。


…教授、それ、先手頓死です。


具体的な手順は▽39角成▲同金▽18金!▲同玉▽17銀▲29玉▽39竜▲同玉▽28金までの9手詰だが、ご愛嬌ということで。人間はミスをする。大学教授だろうが専門棋士だろうが人間である。が、KFEndは人間でなく、これを読み落とすことはない。


そもそも▽75角は先手玉に詰めろをかけた手で、仮に▲36金と歩を払っても▽39竜以下頓死になるし、▲26銀と金銀5枚で守っても▽39角成▲同金▽17金▲同銀▽37銀▲同銀▽39竜▲同玉▽37歩成▲同金▽同桂成までの11手必至がある。だからと言って▲57歩と受けても教授の解説の通り▽同角成以下13手必至、▲29金と苦肉の策を使っても▽49銀以下13手必至で後手の勝ちである。


さて話を戻して、何故KFEndが▽75角と指せなかったのか真相は判らないが、単に▽75角以下相当変化の多い必至を短時間では読み切れなかっただけのことだと思う[*1]。後は教授の解説と大同小異で、多少の読みでは▽75角より駒得になる▽37銀、しかも先手玉の守備駒を剥がせるので、その探索値の方が高かったのだろうと推測する。


KFEndの棋風は、概ね局面を単純化しようとする傾向がある。力をためるより駒を取り合う手順を好んで深く読むような気がする。もし、この局面のように▽75角と指せる程読めるとするなら、互角のまま終盤に入って計算機将棋に勝ち切るのは専門棋士と言えども確かに厳しそうだ。


[*1] 因みに謎電では、前稿を含めて本稿の必至問題も(最短手順解を得ようとするなら)[分]の単位では解けない。

AD

今回、新たなテーマを設けてみる。恐れ多くも「専門棋士の棋譜分析結果」の分析である。このことは飯田教授には内緒だ、マジで。


さて、進歩5のp.174には、▲うさぴょん▽ハイパー将棋戦が採り上げられている。さすがは飯田教授、二次予選とはいえ、この将棋に注目されるとは目が高い。私もこの将棋の終盤は▲うさぴょんの勝ちだと思って遥か昔にうさぴょんのだんなにメイルしたし掲示板にも書いた。但し、別の局面なのだが。


左図は、p.175「…こうして先手玉に対する詰めろを受けながら、後手玉に詰めろをかけて勝ちとなる」の局面で、85手目▲68角。正確には、詰めろをかけてるんじゃなくてこれは王手だが、もっと正確に言えば「詰めろ逃れの必至」になる。


頭から手順を書くと▲93銀▽83玉▲92銀不成▽94玉▲95歩▽同玉▲68角▽86桂▲同角▽94玉▲95香▽85玉▲77桂▽96玉▲97銀▽87玉▲69桂▽同飛成▲同金まで19手必至。


教授曰く「プロレベルに追いつくにはまず終盤の本局のような局面では即座に先手の勝ち(具体的な手順でないとしても存在するということ)を発見できるようにコンピュータが[*1]進歩することを期待する」ということらしい。


うう、即座に、ですか。コレ結構大変ですよ。仮に、最後の悪あがきで▽96桂と受けたら、▲89飛▽88角▲同銀▽86玉▲87銀▽95玉▲86銀▽94玉▲83角▽93玉▲94歩▽82玉▲72角成▽同金▲83銀打▽71玉▲72飛成までの17手詰を読み切らないと勝ちであることが判らないんですもの。つまり19+1+17で合計37手先まで読んで初めて勝ちなのであって。しかも「具体的な手順でないとしても存在するということ」って、飯田教授、多少の妥協を許すにせよ要求仕様が高過ぎ。橋本博士はきっと苦労してるんだろうなあ?


[*1] 原文では「コンピュータが」になっているが、恐らく「コンピュータ将棋が」の意だと思われる。更に察するに「TACOSが」ではないかとも思われる、たぶん、きっと。

AD

アマトップクラスに迫る

テーマ:

コンピュータ将棋の進歩5がやっと手に入ったので、とりあえずざっと第1章と第2章と付録を読んでみた。面白いネタが結構転がってるので、時間ができたらその類の謎電的手法をここで書こうと思う。


進歩5を読んで感じたのは、結構同じようなことを皆考えてるんだなあ、ということだ。但し、微妙に実装が違うようで、更に一歩踏み込んでアイデアを練ったか、より突っ込んでbetterな方法を探ったか、も問われるような気はする。そういう意味も含めて、このブログの中で自分の持ちネタを先に書いててよかったなと思った。進歩5が出てから書いてたら、パクったんじゃねえかと疑われそうなアイデアがいくつかあったのには冷や汗が出た(笑)


ところで、この進歩5は1年以上前から執筆が開始されているか、原稿依頼があったのではないかという感じがする。例えば付録で、なぜ第15回ではなく第14回選手権の棋譜分析なのか微妙に疑問に思ったからだ。その勘が正しければ、そろそろ進歩6の製作が開始しても不思議ではない。恐らく出版は再来年になると思われるが、それまでには持時間の短い将棋であっても、専門棋士にせめて1勝しておいて欲しいと思うところである。

アービタ改造 (1)

テーマ:

下に示すソースは、Marcの指手生成器の中のarbiter.vだ。これは、アービトレータ(Chrillyが言うところのコンパレータツリー)を構成する一部品で、指手生成器のクリティカルパスに大きく影響する回路である。ハード探索処理を構成する全てのユニットの中で、指手生成器が最もクリティカルパスが長いとするなら、このロジック如何で探索速度が決まる極めて重要なコンポーネントと言える。


--*** CodeBlue Chess ***
--Arbiter circuit implementation
--------------------------------------------------------------------------------
--fpga express implementation: 20 lut, 0 ff
--replaced if priority structure by comparison
--fpga express implementation: 18 lut, 0 ff
--optimization effort high, optimize for area
--fpga express implementation: 17 lut, 0 ff, 20.64ns delay
--redid priority circuit by hand, optimize high, speed
--fpga express implementation: 16 lut, 0 ff, 14.42ns delay

--tests to perform: noted by "optimize" comment
library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_unsigned.all;
--use ieee.std_logic_arith.all;

entity arbiter is
port (
    invert_pri: in std_logic;
    arb1_in, arb2_in: in std_logic_vector(2 downto 0);      -- (2 downto 0)
    rowcol1_in, rowcol2_in: in std_logic_vector(5 downto 0);--x2,x1,x0,y2,y1,y0
    arb_out: out std_logic_vector(2 downto 0);              -- (2 downto 0)
    rowcol_out: out std_logic_vector(5 downto 0));
end arbiter;

architecture rtl of arbiter is

signal muxval,agtb: std_logic;

begin
--process for agtb
process(arb1_in,arb2_in)
begin
    if arb1_in>arb2_in then
        agtb<='1';
    else
        agtb<='0';
    end if;
end process;

--process for mux_val
process(arb1_in,arb2_in,invert_pri,agtb)
begin
    if invert_pri='1' and (arb1_in/="0000") and (arb2_in/="0000") then
        muxval<=not agtb;
    else
        muxval<=agtb;
    end if;
end process;

--process for arb_out and rowcol_out
process(arb1_in,arb2_in,rowcol1_in,rowcol2_in,muxval)
begin--optimize: try explicit values instead of mux
    if muxval='1' then
    --if arb1_in>arb2_in then
        arb_out<=arb1_in;
        rowcol_out<=rowcol1_in;
    else
        arb_out<=arb2_in;
        rowcol_out<=rowcol2_in;
    end if;
end process;

end rtl;

ソースの冒頭近くにあるMarcが書いたと思われるコメントを見ると、当時の開発環境(恐らくISEの古いバージョン)で合成した時、16LUTsを消費し14.42nsの遅延があったようだ。但し、この数字は昔のデバイスとは言え遅過ぎるので、多分入出力ピン-LUT間遅延も加算されているものと思われる。でなければ14.42ns×6(チェスの場合6レベルツリー接続なので)=86.52nsとなり、アービトレータだけでここまで遅延が大きいと、まともな速さでは走らない計算になってしまう。


さてこの回路は、駒コード3ビット×2つの入力を比較し、価値の高い方、あるいは逆に低い方を判定し、その駒位置を含めて駒コードを出力する、というものである。これをQuartusII 5.1で合成してRTL viewerで等価回路図を機械的に作らせたのが左下図だ。更にtechnology map viewerを使って作図させ、下中央がStratixIIの場合、右下がCycloneIIの場合の実装上の回路図になった。StratixIIとCycloneIIでtechnology mapが異なるのは、同一メーカでもFPGAのアーキテクチャが微妙に異なる為である(特にLUTの)。

RV-cmn051216 TVstr2501216 TVcyc2051216


1つのアービタのみに着目すれば、実装上のロジックレベルはStratixIIで2、CycloneIIで3となり、アーキテクチャの違いによる性能比が3:2になることが判るが、ここでは参考例として挙げてみる。回路の具体的な遅延時間は、プロセスは勿論デバイスのスピードグレイドに依存する。1ロジックレベルあたり0.5nsと仮定すると1つのアービタの遅延時間は単純計算でStratixIIで1.0ns、CycloneIIなら1.5ns。これをこのまま将棋用の指手生成器に使って強制的に7レベルツリーで接続してアービトレータを構成した場合のクリティカルパスは、StratixIIで7ns、CycloneIIで10.5nsとなる。が、元々64桝のチェスの為に作られたアービタを、81桝の将棋用として無理矢理用いるのは多少無駄がある。そこでこれを将棋用に最適化することを考えてみる。

-- 多分、次稿は来年頃に続く --

ホテルの予約 (1)

テーマ:

今回、ホテルの予約は各自が行い、運営側は関与しないことになった。前回、かなり問題があったのでそれ自体は解決したことになる。しかしだ、早速いつもの最寄のホテルに予約しようと試みたのだが、そのお値段が、なんと、


お一人様一泊¥21,000-の大ご奉仕


である。何かの間違いであろうか。私の調べ方が間違っていたのだろうか。2人部屋でも3人部屋でも同じである。前回までは¥15,000-くらいだったと思う。但し、それは選手権参加者特価だったのかもしれない。それとも某A元建築士が関わりあってないホテルだから値上げしたのだろうか。貧乏人は麦を食え、と言われたようで、なんだかショックである…。ここまで高いと、タクシー代がかかること考慮しても木更津駅近くのホテルに泊まった方がお得のような気がする。というわけで宿泊先をどうするか、現在保留中である。

新参戦予定者

テーマ:

最近、個人的に興味深いブログを見つけた。書き手が面白いキャラだと感じるので、ここで紹介しようと思う。


小宮日記


選手権に参戦されるようなので、一次予選では注目してみようと思っている。とか言ってあっちこっちの開発者にプレッシャ~を掛けてみる謎電の作者であった(笑)


全く話は逸れるが、そこでこみっくじぇねれーたー という楽しげなツールを見つけた。「コピペして、HPや掲示板、メールで使用できます」とあり、ブログでも使えるだろうと思ったのだが、本来、


となる筈なのだが、amebaブログで単にコピペして表示すると↓の様になってしまう。


…わけわからん
こんばんは
谷村新司です
ハゲって言うなー

原因は判っているが、巧い対処法が判らない。


(追加) ナンセンス系アバンギャルド式連載即打切型(よーするに読みきり)4コマ漫画





概ねこの時期になると、伝統的公式戦の募集が行われる。そう、「世界コンピュータ将棋選手権」のことである。これはいわば計算機将棋界の竜王戦。貴殿の挑戦を、俺は待ってるぜ。←ちょー偉そう(笑)


第16回世界コンピュータ将棋選手権 参加者募集のお知らせ


参加者数は増えるか否か判らないが、前回までと異なり次回は観戦客が凄いんじゃなかろうか、特に本戦は。(謎電には関係ないが)今から楽しみである。


ところで最近、世界最古の計算機将棋同士の対局棋譜が出てきた。何故今まで公開されなかったのだろうと思っていたが、恐らく積極的に公にする必要がある内容ではなかったから、ということなのではないかと思う。26年前と今の計算機将棋の棋譜に見る棋力差は全く桁違いで、その進歩を社会に知らせる意味はある。出来ればCSAのHPで堂々と棋譜を「展示」されては如何かと感じた次第である。

Junior考 (2)

テーマ:

僅かな時間を使いつつ、Juniorについて更に調べてみた。ちょっと気になる「DeepJuniorの謳い文句 」を見つけることができた(但し、内容はちょっと古い)。これを要約すると、次の様になる。


・マルチプロセッサマシン上で走る世界初の商用チェスプログラム

・デュアルプロセッサにおいては、約1.8倍速く探索する


DualProcessor と DualCore では少々意味が異なるが差はないものとして考えてみる(また、バージョンが異なることも考慮しない)。すると、並列探索効率は1.8/2=0.9となる。従って315/0.9=350で、2.4GHzのAMD64系シングルマシン上で走らせると350万局面/秒を読めると推定でき、1局面あたりのコストは700[clocks]を切ることになる。並列化の効率も非常に高いということも含めて、ますます発狂しそうな数字だ。また、先の記事ではFritz9についての記述もあり、これも少し引用すると、


>Fritz 9 running at 1.6 million positions per second on a 2 GHz Centrino notebook


このことから、2G/160万=1局面あたり1250[clocks]のコストで、これも相当なものである。Centrino[*1]とAMD64系プロセッサではIPC値が異なるが大差があるわけではないことを考えれば、Fritzも気合の入った最適化が行われていると想像できる。しかし、それでもJuniorの方が明らかにブッ跳んでいる。フォーミュラエンジンで喩えるなら、「Fritzは毎分2万回転まで廻るが、Juniorは毎分3万回転以上で廻る」というくらいビョーキ的で常識では考えられない。


余りに信じ難いのでAmirにメイルで訊ねてみようと思ったが、彼のアドレスを調べても判らないので一旦諦めた。もし私の解釈が誤りで「Multi-Dualで(即ちDualCoreのOpteronを複数用いて)毎秒630万局面」ということなら、ChessBaseに抗議のメイルを送りたいところである。日本語でもなく英語でもなく機械語で書いて、だ。しかし本当に事実なら、計算機将棋にも適用できる最適化技術が存在する筈だ、ということで研究を続けてみようと思っている。


全く余談だが、コンピュータチェスの世界で "Deep" の冠をプログラム名に付けている場合、それはマルチプロセッサマシン上で動くことを示す、という慣習があるようだ。


[*1] Centrinoの正体は、Banias(PentiumM)をベースとした3つのチップの組み合わせブランド名である。PenMは、条件分岐予測とL2キャッシュアクセスのレイテンシにおいてはAMD64より優位性がある。Pen4-Mと比べるなら遥かに「買い」であるし、実は本業の方でPenMノート(但し、1.86GHz)を私は使っている。惜しむらくは、動作周波数が低いということ。これが2.6GHzくらいで動いてくれて且つSMP化が可能ならAMD64が危なくなる話になるのだが、そうなったら完全にPen4の息の根が止まるので、Intel的にもそれが仮に可能でも商品化できないジレンマがあるような気がする。