The Chess Monster Hydra

テーマ:

Hydra について再度調べなおしている最中に見つけた。Xcell journal online の "The Hydra Project" の大元だと思われる。こちらの方がやや正確な記述であるように感じる。


The Chess Monster Hydra


初代Hydraについてなので重視するほどではないのだが、念の為ここに置いておく。


これまでの最新情報を元にデータを修正すると、次の様になる。

・旧Hydraの探索コアは33[MHz]動作

 つまりはPCIバスクロックと同期している(おかしいと思っていた)。

・現Hydraの探索コアは55[MHz]動作

 PCIバスのクロックを3分の5逓倍しているのかもしれないが詳細は不明。

それ以外にも解決していない疑問が多々ある。大きな声では言えないが次のことがハッキリ判った。これを念頭に置いとかないと混乱する。


Chrillyは、十進数で1桁の精度しかない 大雑把な数字を語る男である。

AD

Move Generator 分析 (2)

テーマ:

AlteraのQuartusII 5.0 WebEdition(無償版[*1])を使って、各々のデバイスの現在最高のスピードグレイド品[*2]を使い、且つ最適化設定を速度優先[*3]にしてビルドを行い、クリティカルパスと消費したリソースについて調べてみると次の様になった(但し、フロアプランニングによる手動最適化は全く行っていない)。

--
a) StratixII(EP2S15F672C3) : 23.724[ns] 26[logic levels]
   10,047ALUTs, 407FFs, 11,200bits(Nett)  72,576bits(Gross:17%)
b) CycloneII(EP2C35F672C6) : 36.215[ns] 41[logic levels]
   12,025 LUTs, 407FFs, 11,200bits(Nett) 354,816bits(Gross:73%)
--

このMarcの指手生成回路に限って言えば、StratixIIはCycloneIIの1.5倍程度速く動作出来ることが判る。なお、Virtexと比べるとRAMのリソース消費が大きく異なるが、これはAlteraのFPGAとXilinxのFPGAのアーキテクチャの違いに因る。XilinxのFPGAの場合は、各LUTを(制限付きではあるが)非常に容量の小さなRAMとして使用できる機構を持っている[*4]。その為、AlteraのFPGAよりメモリ資源の消費量が少なく見えるのだが、リソースが足りず実装できないという深刻な状況ではないので、ここでは厳密な議論を省くことにする。


さて、指手生成回路だけで見れば、StratixII(a)の結果からは、1サイクルを(23.724[ns]の1/3の)約7.9[ns]にすることが出来るので、およそ126[MHz]動作が可能になり、フロアプランニングを巧く行えば更にその約20%増の150[MHz]程度で動作出来る可能性がある。単純に、Marcのベンチ結果の約4倍の速度で探索出来る潜在性能があるわけだ[*5]。また、廉価版CycloneII(b)の結果からは、1サイクルを約12.15[ns]にすることが出来るので、およそ82[MHz]動作となり、フロアプランニングによっては100[MHz]近くまで上げられる可能性があることになる。勿論、これは3サイクルを当てた場合の話で、サイクル数を減らしたい場合は、その分基準となる動作周波数を落とすことになるが、何れにせよクリティカルパスの時間が、その回路の性能を決める。


以上はあくまでチェスが前提の話で、しかも指手生成回路に限っての話だ。次項では、この手法を将棋へ適用し、且つ局面評価と探索制御についても考慮した場合を考えてみることにする。

-- 続く --


[*1] 機能が制限された無償版だけを用いた。これは、サードパーティの開発支援ツールを全く使ってないという意味で、相当辛い開発環境である。予算があれば強力な開発環境を構築出来る(性能を上げるための最適化ツールが色々あったりする)。
[*2] 但し無償版では、StratixIIならEP2S15*、CycloneIIなら EP2C35*しか選べないようになっている。

[*3] 速度優先以外には、エリア優先、それらをミクスチャしたバランス重視、それ以外にも様々な設定がある。一般に速度優先に設定すると、リソースの消費量がエリア優先と比べ数割増えるので注意が必要。
[*4] Xilinxでは、これを"DistributedRAM"と呼んでいる。AlteraのFPGAではそのようなことは出来ないのだが、その代わりに総容量としては大きなBlock型のRAMを用意している。特にStratix系では、そのブロックサイズが大・中・小3種類と豊富になっている。XilinxのFPGAではVirtex4でもBlock型は1種類しかないので、微小サイズのRAMに対しては、LUTをDistributedRAMに換えて用いる。

[*5] Marcが試したXilinxのXCV800-4は、初代Virtexで非常に古く、StratixIIが4倍の動作速度で動いても不思議ではないし、それくらいの性能が出せないと意味がない。

AD

Move Generator 分析 (1)

テーマ:

「Hydra考」を続けようと思っていたのだが、いくつかハッキリしない疑問が出て来たので現在Chrillyに問い合わせている最中である。返答を貰える保証はないが[*1]数日待ってみて改めて書こうと思う。


さて、先のMarcの指手生成回路を分析してみた。まず、この指手生成回路の論文に書かれてある諸元を要約すると次のようになる。

--
・33MHz動作。
・デバイスは Xilinx Virtex XCV800-4 を用いた。
・フロアプランニング[*2]を行うことで17%高速化した。
・回路のリソース消費状況は、
 1)の記述: 7,000LUTs,1000FFs, 2BlockRAMs。
 2)の記述:10,100LUTs, 800FFs, 350の32x1bit(Distributed)RAMs。
・非合法手を含めて、毎秒140万着手を生成。
・合法手に限れば、 毎秒 90万着手(テストプログラムを走らせて計測)を生成。
・αβ枝刈を行った上で、 毎秒28万局面を探索。
・FPGAを使わない版では、毎秒 5万局面を探索。
・それ自身は(通信オーバヘッド除)、非合法手を含んで毎秒約450万着手を生成。
--
ここで、最後の「毎秒約450万着手を生成」の示す意味について考えてみる。
この数字から逆算すると、1回の指手生成には約222[ns]が掛かっていることになる。手の生成はFindVictim, FindPivot, FindAggressor の3段階を踏む必要があるので、各々約74[ns]以内で処理を終らせる必要があることになる。つまりはこの時間がクリティカルパスの最大となる。各処理には3サイクルを当てているので、1サイクルは約24.7[ns]以上が必要だが、33Hz動作の1サイクル分は30[ns]なので問題はない。最大の遅延時間である約74[ns]は、2サイクル=60[ns]では駄目だ(処理が終らない)が、3サイクル=90[ns]なら無問題というわけだ。
注目すべきは、この「クリティカルパスが約74[ns]」という点にある。この時間を短くすることが出来れば、生成効率を上げることが出来る、つまりは探索速度を上げることに直結するからだ。
次項では、この指手生成回路をAlteraのデバイスへ移植した場合にどうなるかを分析してみることにする。

-- 続く --


[*1] というより、スパムと思われた可能性の方が高過ぎる気がする。
[*2] 回路の物理的な配置を(一般には大まかに)手動で指定すること。
AD

Marc Boulé Move Generator

テーマ:

Marc BouléのHPはここ 。ハードウエア指手生成に関する論文とHDLソースがある。

--
1) CICCpaper.pdf : An FPGA Based Move Generator for the Game of Chess
2) ICGApaper.pdf : An FPGA Move Generator for the Game of Chess
3) MBThesis.pdf  : An FPGA Move Generator for the Game of Chess
--

以上、論文。これらは基本的に全て同じだが、1)簡易版 2)詳細版 3)その改訂版という感じになっている。ハードウエア探索での模範的指手生成デザインが詳解されており、教科書とも言えるし非常に参考になる。逆に、ハードウエアだからこそ出来る、この過激な高速生成手法が理解できないと、先に進めない。


論文にある指手生成回路のソース:MoveGenVHDL.zip (125KB)


回路はVHDLで記述されている。基本的にはXilinxのISEでそのままビルド出来ると思われる。詳しくは、notes.docとreadme.txtを参照のこと。
因みに、自分で一部ソースを書けば[*1]、AlteraのQuartusII 5.0 WebEdition でもビルド出来ることを確認済み。TopLevelEntityはchess_chip[.vhd]。デバイスはStratixII、CycloneIIどちらでもビルド可。全ビルド時間は、最適化オプションがデフォルトのままならBarton/3000+で20分前後で終了する。また、ビルド時に約100MBの空メモリが必要[*2]


[*1] component RAM32X1Sとbufを自分で追加すればOK。

[*2] 激しく最適化を行う場合は時間も掛かるし、メモリも倍以上喰うので注意。

Hydra考 (2)

テーマ:

'05/05/26のChessBaseNews によれば、"Maximum moves per second: 200million" という記述[*1]があり、現Hydra(32/64プロセッサ版)は実効最大で毎秒2億局面読めるようである。非重複で局面をカウントした場合の値とは考え難い数字だが、「実効上の(平均ではなく)最大」と解釈することにした。

さて最近、DeepBlueで「チェスチップ」と称されていたチェス探索コアについてDeepBlueの論文とは別のHsuの話を見つけた。情報ソースはこれ [*2]なのだが、要約し箇条書きにすると次の様になる。 

--
・カスパロフに勝つには、13手(以上)の深さを読む必要があると考えた。
・人間はプログラムの弱点を学習するので、速度だけで十分ではない。
・局面評価コストは、一般的なCPUの約10,000命令[*3]と等価であると推測した。
・チェスチップは次の機能を含んでいる。
 - 指手生成
 - 指手スタック(後入先出処理)
 - 反復検出(千日手検出)
 - 評価機能(速い評価と遅い評価)
 - αβ枝刈探索制御
 - 19ビットの(指手データ用の)広いバス
・局面評価はチップエリアの約2/3、指手生成は残りの約3/4を使用している。
・静止探索の中で、王手と王手を逃れる手の生成(つまりは探索)ができる[*4]
・速い局面評価は1サイクルで行う。
・遅い局面評価は、1サイクルで1筋(カラム)分を走査し、8~11サイクルかかる。
・チップは0.6μmCMOSプロセスで、150万トランジスタ、1W、25MHz動作。
・チップあたり毎秒250万局面探索する(平均10サイクル)[*5]
・チップ1つは、強いGMレベル[*6]でプレイする。
・480個のチップで構成されたシステムは、毎秒約2億局面(全力の1/5未満)を探索する。
・数年で、1チップ(0.18μmプロセス)でも、DeepBlueと同じくらい速くなり得る[*7]
・成功の鍵は評価関数にある。
--

DeepBlueの局面評価には、速い(簡易の)評価と遅い(精密な)評価がある。Brutusの論文では「DeepBlueの局面評価は11サイクルを要する(が、Hydraのそれは3サイクル)」旨のことが書いてあるが、これは遅い(精密な)評価モード時の話だ。速い(簡易の)評価では1サイクルで済み、結局DeepBlueは平均的に1ノード探索あたりで10サイクルのコストとなり、Chrillyの探索コアのそれ(8~9サイクル)と大差があるわけではなさそうである。

因みにChrillyの探索コアの各機能の実行コストは、Brutusの論文では次のような内訳になっている。

--

・1手進めるか戻すことに(各)1サイクル

・2段階の指手生成で、2+2サイクル(つまりは4サイクル)

 - 最初の2サイクルで移動先の計算

 - 後の2サイクルで移動元

・局面評価で3サイクル

--

その他にも、王手が掛かっている時のテスト(詰め上がり判定の意味?)、局面更新待ち、探索(実行)制御、など細かな手続きが主処理と共に並列実行されているようだ。

-- 続く --


[*1] この記述は変で計算が合わない。原文通りの"moves"だと、倍の「毎秒4億手」になるので、恐らく "positions" あるいは "nodes" の誤りだと判断した。

[*2] DeepBlueの開発者の一人であるFeng-hsiung Hsuは、HotChips10に出席してたようである。なお、HotChips10 とは「Hot(高性能)なプロセッサに関する真夏の祭典の第10回目」のことで、1998年8月16~18日に例年通 りスタンフォード大学で開催されている。

[*3] ここでの数字は、あくまで「局面評価のみのコスト」だろう。DeepBlueの論文では「1ノード分の探索は、40,000の一般的な命令に相当する」となっており、これはChrillyも同様のことを言っている(Chrillyは、単にHsuの数字を借りただけかもしれないが)。

[*4] 静止探索の中で(チェスでいう"mate"ではなく)、将棋でいう「詰」を読んでいるようだ。ある程度で打ち切るのだろうが、これは相当終盤に強くなると思われる。

[*5] DeepBlueの論文では、「チップあたり毎秒200万~250万局面」と記述されている。

[*6] GMとはグランドマスタのこと。イロレイティングでいえば、概ねR2500以上でGM。強いGMとはR2600程度を指すものと思われる。因みに世界チャンプはR2850前後である。

[*7] これはかなり大ゲサな話に感じる。現在の90nm(0.09μm)プロセス技術を用いたフルカスタムASICなら、80倍の2GHzで動作させて1チップ(しかもシングルコア)で毎秒2億局面を探索させることは可能。しかしながらチェスの場合そこまでしなくても、当時と比べ現在では探索技術が相当進んでいるので、専用プロセッサを使わず(PCのみで)DeepBlueと互角に戦えるかも知れない。

別冊MultiCore (号外)

テーマ:

皆さんこんにちは。別冊MultiCore(号外)です。

さて、Athlon64 X2ですが、ナンバと周波数、フィーチャの関係は次の様になっていました。

--
4800+:2.4GHz L2:1MB*2=2MB
4600+:2.4GHz L2:512KB*2=1MB
4400+:2.2GHz L2:1MB*2=2MB
4200+:2.2GHz L2:512KB*2=1MB
--
現在4800+と4400+はアキバ市場で見かけない(即日売り切れ、予約しないと買えない)ようです。それ以外の実勢価格は、4600+が\99k前後、4200+が66k前後。結局L2:1MB*2品は、(ロードマップを見ても)Athlon64FXのDualCore版という位置付けになるものと思われます。

Hydra考 (1)

テーマ:
先の"The Hydra Project"[*1] とBrutusに関する記述について考察してみる。資料の中にChrillyがプログラミングしたチェス探索コアのリソース消費等のデータがあるので、これを簡単に表形式でまとめてみると次の様になる。

Brutus Hydra
BlockRAMs 66 67
Slices 9,019 9,879
TBUFs 5,302 5,308
Flip-flops 534 534
LUTs 17,022 18,403
FSM states 54[states] 56[states]
Critical path 53[logic levels] 51[logic levels]
Device

(# of slices)

Xilinx Virtex (E)

XCV1000E

(12,288)

 Xilinx Virtex IIPro
XC2VP70-5[*2]
(33,088)
Max. freq. 30[MHz] 50[MHz]
Search rate(Peak) 3.2M[nodes/s] 5M?[nodes/s]
Search rate(E.max) 2.5M[nodes/s] (about80%) 4M?[nodes/s]
Total rate(E.max)

15M?[nodes/s]

(8processors)

200M?[nodes/s]
(32/64processors version)

ロジックリソースで特に注目すべき点はXilinxのFPGAの場合Slice数である。このSliceという単位は、AlteraのCyclone系FPGAでいうLE(LogicElement)[*3]2個分に相当し、StratixIIに限れば、ALM(AdaptiveLogicModule)1個分にほぼ等しい[*4]

余談だが、以前Chrillyが、「リソースの70%を使用している」旨の発言をしていた。これはV1000Eが12,288個のSliceを持ち、そのうち9,019個を使用していたので「約70%」になるわけだ。Slice数は、Chrillyがプログラミングしたチェス探索コアがどのくらいの回路規模であるかを正確に知るための重要な基準になる。


なお、AlteraのFPGAであるStratixIIのALM1個は、Cyclone系のLE2.5個分に相当するとAlteraは言っており、それを基準にデバイスの型番が決められている。例えばStratixII EP2S15は、6,240個のALMで構成されるが、LE15k個に相当するので、EP2S15となっている。因みにXilinxのVirtexII~4では、LogicCell数を基準として型番が付けられる。LogicCell数はLUT(FF)数+CarryLogic数を意味し概ねSlice数×2.25倍なのだが、Alteraの基準とは異なるので注意が必要。例えばXC2VP70は、Slice数33,088×2.25=74k個のLogicCell数だが、1桁を四捨五入してXC2VP70となるわけだ。このことを頭に入れておかないと、AlteraのFPGAを用いる(置き換える)時のデバイスの選択を誤ることになる。

-- 続く --


[*1] 「現在のHydraは毎秒3600万局面読める」となっているので、初代Hydraに関するデータだと思われる。

[*2] 型番の"-5"というのはデバイスのスピードグレイドを指しており、この場合の-5は、VirtexIIProの中では最も低い(遅い)グレイドであることを意味する。

[*3] AlteraのいうLEは、1個のLUT(LookUp Table)と1個のFF(Flip-flop)から成り、FPGAの基本的な回路要素単位を指す。

[*4] XilinxのFPGAのLUTとFFの単体を見れば、Cyclone系のそれとはほぼ同じだが、特にStratixIIのLUTは仕様が微妙に高度で、ユーザロジックが多少複雑になってもリソースの消費が増えたり動作速度が落ちたりしにくい(クリティカルパスが延びにくい)アーキテクチャになっている。なお、Alteraの主張 では、「StratixIIの1個のALMは、Virtex4のSlice1.3個分に匹敵する」と堂々と公言している。

HDL入門書

テーマ:

お奨めのHDL入門書、その関連本を、以下に紹介する。



左から順に、右に向かって内容が高度になって行くが、出来れば読んでおきたい本だ。

1.VHDLによるハードウェア設計入門

2.HDLによる高性能ディジタル回路設計

3.実用HDLサンプル記述集

4.HDLによるVLSI設計(第2版)


左の本は、上の4冊と別扱いになるが、トラ技別冊で最新刊のトラ技スペシャル No.90「ディジタル回路の設計入門 」。

本書は、昔出版された「ディジタルIC回路の設計」をイマドキ風に大幅に加筆改訂したもので、HDL入門書というより、全くハードウエアというものを知らない人の為の、つまりは純粋なソフト屋必読の入門書である。



更に左に示す「CPUの創りかた 」は、HDLと直接は関係がなく原始的なのだが、HDLのありがたみを実体験して頂くには最適の本である。

つまりは、ユニバーサル基板と標準ロジックICを買ってきて、自分で半田ゴテとテスタを握ってCPUを作ってみる、というものだ。この路を一度は通ることによって、FPGAを含めてHDLの真の意味や価値が体で判る。例えるなら、ハンドアセンブルの経験があればこそコンパイラの意義が身にしみて判る、ようなものである。


なお、出版社は 毎コミ である。


ハード屋やファーム屋がよく読む雑誌も以下に紹介しておく。殆どCQ出版。

DesignWave:http://www.cqpub.co.jp/dwm/

Interface:http://www.cqpub.co.jp/interface/default.htm

トランジスタ技術:http://www.cqpub.co.jp/toragi/

CQ出版:http://www.cqpub.co.jp/


同じく、よく利用するアキバのパーツショップ。通常は略称を使うのだが、念の為フルネームで書く。

東京ラジオデパート:http://www.toradi.com/

秋月電子通商:http://akizukidenshi.com/

若松通商:http://www.wakamatsu.co.jp/

別冊MultiCore ('05/06号)

テーマ:

皆さんこんにちは。『別冊MultiCore』の時間がやってまいりました。


AMD Athlon™ 64 X2 デュアルコア・プロセッサ発売記念イベントスケジュール


どうやら今週の土曜には、Athlon64 X2が秋葉原でお目見えするようです。
さて、DualCoreの現実勢価格ですが、昨日は次のようになっていました。

--
・PXE840(3.2GHz)     :\115k前後
・PentiumD840(3.2GHz): \62k前後
・Opteron275(2.2GHz) :\155k前後
--

まだまだ高いという印象があります。とりあえず、Athlon64 X2のリリースを待とうと思います。今度の土曜はアキバへゴー。だけど、買うのは選手権直前(笑)