Marcの3つの論文のうち、一番最初の CICCpaper.pdf の訳文を公開する。なお、テキストのみとしたので、図表については原論文を参照のこと。興味を持たれた方は、是非、MBThesis.pdf : An FPGA Move Generator for the Game of Chess も熟読されることをお奨めする。


CICCpaper.pdf : An FPGA Based Move Generator for the Game of Chess


概要
この論文は、チェス指手生成器のFPGAアーキテクチャを詳述します。その設計はDeepBlueの指手生成器を基にしています。ASICとFPGAの本質的な差は、頻繁な設計変更が出来るか否かにあります。FPGAの重要な特徴(ルックアップテーブルを基にしたロジックや配線資源、DistributedRAM[*1]やBlockRAM)を利用した改良を提案します。


1. はじめに
性能が上がり、より多くのゲート数を持つようになったFPGAは、ASICや専用ICからゆっくり置き換わろうとしています。新世代のFPGAは、チップ内のRAM、多くのI/O規格、マイクロプロセッサや高度なクロック制御回路といった資源を統合して持っています。この論文では、コンピュータチェスの中で使用されるαβ枝刈探索アルゴリズムの処理速度を上げることで、コンピュータチェスが巧くプレイ出来るよう改善するために、FPGAがどのように使用されるかをお見せします。FPGAアーキテクチャの特徴を利用することで、設計によってチェスの指手生成器がどのくらい改善するかをご覧に入れます。
1977年に、Belleチェスシステムは、そのプレイする強さを高めるために、最初に専用ディジタル回路を使用しました。チェスプログラムの中で、最も時間を消費する処理は指手生成です。他のチェスハードウエアを加えて、Belleはその探索速度を毎秒200局面から毎秒160,000局面に引き上げることが出来ました。ざっと1,700個のICがそのチェスマシンを構築するために使われました。Belleの中で使用された指手生成器は、より強力なチェスマシンの出発点として役立ちました。1997年にカスパロフを破ったDeepBlueは、480個のチェスチップを30台のIBM RS-6000 SPプロセッサに繋ぎました。このマシンは、Belleより計算上100万倍速い毎秒2億局面の速度を達成しました。
私たちは、チェスプログラムMBChessを改善するためのFPGA指手生成器の設計について記述します。指手生成器はゲーム中の探索の要です。BelleやDeepBlueの指手生成器の重要な詳細については第3章の中で示します。私たちのFPGA指手生成器の記述は第4章へ続きます。指手生成の鍵となるハードウエアアービタの設計によって、FPGAアーキテクチャがどのような影響を及ぼすかが判るでしょう。更に、柔軟なチップ内のRAM資源が、指手をマスクするための斬新な回路実装を可能にします。また、FPGAの実装結果は第5章で示します。
ASICの伝統的に大きな工数を不要にし、且つ開発コストを数分の1にすることを成功させ、FPGAチェス探索加速装置として使用できることを示します。再プログラムの容易さとチップ内のRAMがFPGAを成り立たせ、チェスアプリのための理想的なターゲットになります。


2. 指手生成器
チェスプログラムの中で使用される基本的なメカニズムは、最善手を求めるための深さ優先αβ探索です。この探索アルゴリズムで良い手の順に読むことは、探索量削減とより速い探索になることで報いられます。強いチェスマシンは、必ずと言ってよいほど最良から最悪の順に指手を生成しています。チェスの良い手の順位の例は次の通りです(最良が最初):
A1:王手、直接および発見された手
A2:もしあれば、成る手
A3:最も価値のある敵駒を、最も価値がない自駒で取る手で並び替えた順
A4:駒を取らない手
αβアルゴリズムの注目すべき振る舞いはβ枝刈です。β枝刈が生じる場合、現在のノードからすぐに引き返し、残っている枝を調べる必要はありません。効率的な探索のために、指手生成器は全体的に固定された指手順を決め、更に一回に一つの着手を生成することが出来なければなりません。これは、探索が戻ってきた時、未だ調べていない次の手を探索することが出来るように、既に生成した手をノードが忘れてはならないということです。


3. 以前の設計
3.1. Belle
Belleでは、チェス盤はロジックブロックを組み合わせた8x8個の配列です。Belleの主なハードウエア構造は、チェスの桝間の通信です。各桝は、発信器、受信器および駒レジスタを持ち、現在の駒を表します。駒が置かれた桝は、ナイトの飛び越える利きを除いて、8つの隣接する桝に送信します。空桝は、駒の進む方向に沿って利きを伝えます。
チェスでは、移動元の駒は適切な送信線をアクティブにし、移動先の桝では入ってきた利きを受け取って(言わば立候補し)、アービトレイションを申し込みます。2つの主な通信ブロックは送信器と受信器です。各桝は各々1つ持っています。
チェスの指手は、移動元桝から移動先桝への(駒の)移動です。指手を構築するために、2つのサイクルが実行されます。最初の敵駒発見(find-victim)サイクルは移動先の桝を見つけます。次に自駒発見(find-aggressor)サイクルは移動元の駒を見つけます。敵駒発見(find-victim)過程中、動かせる自駒はすべてそれらの発信器をアクティブにします。対する敵駒および空桝の全ては、アービトレイション網へそれらの受信器の出力を送ります。2レベルの優先木はクイーンから空桝(キングは取ることができません)までに命じられ、取る敵駒(あるいは移動先の桝)を選択します。アービトレイションの第1レベルは4x4桝のブロック上で終っています。第2レベルは、これらのサブグループのうちの1つを選択します。一旦最も価値のある敵駒(MVV)が選択されていれば、自駒発見(find-aggressor)サイクルが実行されます。ここで、最初のサイクルで見つかった桝は全ての駒種の利きの結合を送信し、ポーンからキングまで命じられ、動ける駒の受信器が最も価値の低い自駒(LVA)を選ぶためにアービトレイションを行います。このようにしてMVV/LVA順で指手を生成しています。Belleの指手をマスクする能力は、64ビット(各桝1ビット)が、ある指定された桝へ動き終わった自駒をマスクするか、あるいは完全に探索された移動先をマスクするためにあります(桝は移動先(victim)か移動元(aggressor)のいずれかです)。深さ優先探索のために、64レベルのスタックが、これらのマスクビット記憶用に使われます。指手マスクがあることで、Belleは第2章のA3(駒を取る手)およびA4(駒を取らない手)の生成を行えます。


3.2. DeepBlue
Belleの受信器・発信器構造は、DeepBlueの指手生成器の出発点でした。DeepBlueでは、第1レベルのアービトレイションは桝の段(rows)の上で終っています。また、第2レベルは段(rows)の間を選択します。一旦桝がビットマスクにより無効になれば、以降(アービトレイションに)参加しません。また、同じ優先度を持った他の桝は選ばれるために申し込みを続けます。あらゆる指手が生成されるまでこの処理は継続します。
移動先と移動元をマスクする過程は、DeepBlueアーキテクチャでは完全に異っています。64レベル64ビットのスタックを使用する代わりに、マスクビットはそのノードで以前に生成された指手から算出されます。このマスキング法は、ロジックとデコーダを犠牲にしてメモリを必要としません。DeepBlueのVLSI設計では、このアプローチは有利でした。DeepBlueのアービトレイションと桝マスクをFPGA用に専用設計し、第4章の3および第4章の4の中で示します。
DeepBlueの指手生成器の最初の大改造は、王手の指手を最優先で生成する問題の解決から始まりました。指手生成順で、王手を高い優先度にすることは非常に重要で、MBChessの初期バージョンで気づきました。この特徴を実装するために、2個の発信器が入力数の倍を備えた受信機と同様に使用されます。王手発見(find-check)過程中、手番側の移動すべき駒は、それらの敵駒発見(find-victim)発信器をアクティブにします。また敵キングは、その自駒発見(find-aggressor)発信器をアクティブに(全駒種で結線)します。適切に(敵キングを)攻撃する桝は、王手することができる桝(と駒種)を示すでしょう。この論文では、これらを軸(pivot)桝と呼び、そのサイクルは軸桝発見(find-pivot)サイクルと呼ぶことにします。軸桝が超駒(super-piece)[*2]として放射し、王手を生成するのに必要な第2のサイクルは、通常の自駒発見(find-aggressor)サイクルです[*3]


4. FPGA指手生成器
この章は、FPGAの重要なチェス指手アーキテクチャを含めた指手生成器を提案します。隣接する桝間の通信の基本は変わりませんが、駒の情報を伝える方法が異なります。


4.1 チェス盤表現
チェス盤は桝回路8x8個の配列として表現されます。チェス桝のブロックダイヤグラムは図1で示されます。発信器(TX)および受信器(RX)の中のL形の矢印は、2ビット(×8方向)のナイト用バスです。直線状の矢印は5ビット(×8方向)の隣接する桝とのバスです。各桝は、図の左上で示された信号を受け取ります。(図の中の)破線は、発信器と受信器の多くの関係のうちの2つを示します。更に32個の第1レベルアービタのうちの1つと16個の第2レベルアービタのうちの1つが見えます。6ビットの深さレジスタは、5ビットの書き込みバスを用いて更新され、駒を移動させることに使います。
全体的な情報は、駒利き伝搬の出力を除いて、すべての桝へ配線させます。これらの信号網によって要求されるファンアウト[*4]は、64個のチェス桝があることで信じ難いほど大きくなります。FPGA実装では、桝への値の送り込み(loading)および遅延を減らすために8つの桝をグループ化し、駆動するためにバッファ[*5]を付けます。バッファが論理合成によって削除されるのを防ぐために適切な制約を設けなければなりません。影響を受ける信号は指手データ、5ビットの書き込みバスとマスクおよび状態の情報です。
DeepBlueでは、マスクおよびアービトレイションバスも、駒レジスタ読み書きバスとして使用されます。この設計では、書き込みバスは異なる桝に駒値を書くために使用されます。書くべき駒値はすべての桝へ送られます。しかし、2つの桝選択線によって選択された桝だけが、その駒レジスタに駒値を書き込めます。また別の選択した桝(移動元)の駒レジスタをクリアするために使用されます。キャスリングを行う、あるいはアンパサンでポーンを取る手も、通常の指手生成と同じサイクルで行われます。指手生成器の重要な特徴は、移動しない駒の桝は駒レジスタを読む必要がないということです。このことは、必要となる配線量を減らし、設計の動作速度を上げます。


4.2. チェスの桝 - 曖昧な王手の解決
桝の発信器出力は図1で示されます。通常の指手生成中、これらの信号線は、以前に議論された敵駒発見(find-victim)および自駒発見(find-aggressor)の振る舞いに従います。
DeepBlueの中に潜在的な制限があることに気づきました。DeepBlueの設計で使用される発信器では、対角方向でヒットした時、軸桝はクイーンとビショップを区別することができません。軸桝に到着するクイーンは水平あるいは垂直にあるキングに王手するかもしれません。しかし、ビショップであれば王手になりません。そのような王手を考慮する場合、私たちの内部結線策は解決可能性を充分に実現します。軸桝発見(find-pivot)サイクル中、桝はどの種類の駒を移動させれば王手を正しく生成できるか判っています。
送信線は、付加的な意味を持っています。すべての駒種の利きの結合は、更に自駒発見(find-aggressor)サイクル中に送信されることができます。この目的(正しく王手を掛けること)を達成するために、6ビットの拡張駒ワードが、4ビットの駒レジスタからデコードされます。ビットフィールドは表1の中で示されます。例えば、111000は白クイーンを表わします。また、011111は、(全ての利きを)結合した駒を放射する桝を表わします。ナイトビットおよび色(敵・味方)判別ビットがナイトの到達可能な桝へ送られている一方、上位5ビットは8つの隣接する桝へ送られます。その結果、チェス桝回路は2個の発信器および二重入力の受信器を必要としません。それでも、内部結線の合計はDeepBlueと同じです。通常の敵駒発見(find-victim)および自駒発見(find-aggressor)サイクル中に、敵味方を判別することは不要です。しかしながら軸桝発見(find-pivot)サイクル中は、敵・味方を正しく判断することで王手を示すでしょう。この表現は、より一定の内部結線パタンにし情報分配の効率を最大にします。王手発見演算は、自駒発見(find-aggressor)サイクルが後に続く軸桝発見(find-pivot)サイクルになります。王手の指手は、それを命じるMVV/LVAによる指手順に従わず、暗黙のうちに指手生成器によって(優先的に)生成されている点がミソです。初めてノード(の探索に)に入る時、王手を見つけるループ(処理)が実行されるでしょう。マスクビットは、規則的ではないやり方(軸桝が使い尽くされた時に終了するように、それがマークされる)で生成された指手からマスクするでしょう。通常の指手生成ループに入る時にマスクビットがリセットされ、王手でない場合、古い軸桝は生成されないでしょう。この解決策は、2つの過程の間マスクビットをリセットし、それらが通常の過程中に生成される時、王手の指手は無視することです。


4.3. アービトレイションの2分木
ルックアップテーブル(LUT)を基にしたFPGAは、この設計中で多くの物理的な制約を課されたまま使用されます。DeepBlueの受信器の出力には大量の配線がありましたが、(本設計では)6つの優先レベル判断用の6*64の網が不要であることを表します。ASIC設計では、もしデコードや演算に必要となる論理ゲート数を更に減らせるならば、格子状に構成される大量の配線は有利になりえます。しかしながらFPGAでは、論理ファンクションは違った風に作用します。5入力のXORゲートは任意の5つの入力機能(2つのLUT)と同じエリアを占有します。受信器出力は、3ビットの値(比較するためにアービタが使用する)の中でエンコードされます。1つのアービタは2つの桝(のどちらか)を選択することができます。最終結果は、6レベルの2分木構造を通って出力されます。各アービタは、決定し選んだ桝の座標を切り替えて出力する6つのLUTのために、4つのLUT(任意の6入力)を使用します。この設計は、筋・段(row/column)に基いた幾何学的位置・距離(topology)より短い伝搬時間になります。


4.4. 指手マスク
Virtexデバイスでは、BlockRAMは4,096ビットの同期式メモリです。それは、1、2、4、8あるいは16ビット(4,096~256)の可変幅を備え、デュアルポートで使用することができます。私たち(が使っているFPGA)の場合、28個のRAMブロックが利用可能です。専用で用意されている配線は、これらのブロックへ信号を送ることを助けます。但し、それはチップの端に強制されます。対照的にDistributedRAMは、LUTをRAMとして使用することを可能にします。1つのLUTは、16x1(1ビット幅)の同期式または非同期式メモリを実装することができます。2つのLUTを組み合わせて、32x1、16x2あるいは16x1のデュアルポートメモリを作ることもできます。小さな多数の局所的なデータを保持する必要がある場合、この種類のメモリは有用です。BlockRAMはチップ全体に渡って用いる必要のない大量のデータを格納するために使用されます。
元々Belleの指手マスキング法は、このアーキテクチャで実装されています。各桝1ビットおよび64手分の深さの同期式メモリ(2つのRAM32x1Sを使用)は、マスクビット記憶用に使用されます。駒値を書くために使用されるバッファを介した信号線も、各桝の深さレジスタを更新するために併用されます。この設計ではフリップフロップを殆ど使わないので、各桝は配線を減らすために6ビットの深さレジスタを持っています。メモリベースのマスクビットスタックを使うことによって、DeepBlueでは指手をマスクするデコーダの意味を持っていた全てのロジックは不要です。
BlockRAMは、専用に用意された配線があっても、この場合マスクビットを格納するメモリとして最良の解決にはなりません。このメモリとの(データの)行き来によって4~8nsに及ぶ遅延が回路内で観察されました。局所的なメモリを使えば、前述した遅延は事実上除くことができます。しかしながらBlockRAMは、探索木中の各深さで生成された指手を格納する(メモリとして)理想的な候補です。2つのメモリが32ビットの指手を格納するために必要です。チェス盤を制御するステートマシンは、チップの(BlockRAMに接近している)傍近くに置かれます。これは、設計の中で適切なRAM資源の種類を選ぶことが重要だということです。


4.5. 例外手
チェスの例外的な指手にどのように対処するのか、チェスハードウエア探索の論文中滅多に言及されません。5ビットの全方向出力は、ポーンとキングが2つの桝の距離を伝搬することを可能にします。第4・第5段が2桝分ポーンが進めることができるように、第3・第6段の桝はポーンビットを広めます。更に、目的(移動先)桝をキャスリングする手を示せるように、桝f1、f8、d1およびd8にはキングビットを広めます。
水平のポーン出力は、取って移動するアンパサン用に使われ、またこのポーンの例外的な指手は、良い指手(優先手)として扱われます。ポーンが成ることがMVV/LVA順と単純な関係を持たないので、これらの手は、最上段へのポーンが進む手だけを生成する特殊な敵駒発見(find-victim)-成サイクルで扱われます。無駄を省くために、通常の指手生成はこれらのポーンを進める手を生成しません。これは無秩序に成る手のためにマスクビットを回復しなければならないからです。敵駒あるいは移動先桝(victims)は、マスクされてオフになる前に完全に探索されます。これは、最初の成生成と非互換で、通常の指手生成と共に継続しています。


5. 実装および結果
FPGA設計はVHDLで行いました。また、チェスプログラムはCでコード化しました。デバイスドライバは、チェスソフトウエアとPCIカード上に置かれたFPGAを接ぎます。64個のチェス桝の実体と63のアービタの実体を内部結線させるVHDLファイルを生成するために、Cプログラムを作成しました[*6]。使用したチップはXCV800-4です。また実装ツールはXilinx製です。フロアプランナは、チェス盤が8x8配列であることを配置配線ツールに知らせるために使用しました。
これは実行時間を縮め、より高い性能を備えた設計が行えます。この場合、17%の速度増加が得られました。図2は、チェス盤とアービタのために使用された間取り図です。アービタは、配線遅延を最小限にするために入力として使用されるブロック間に置かれます。全設計は、およそ7,000のLUT、1,000のFF、2つのBlockRAMを使用し、33MHzで走ります。
チェス指手生成器は、MBChessを実行するコンピュータに接続するPCIインタフェースを含んでいます。様々な異なるコマンドがあることで通信オーバヘッドを減らしています。例えば、カードからの単一の読み取りでは、指手生成器は、現在格納されている指手を取消し、次の指手を生成し、それを返し、ハードウエアチェス盤上の指手を実行するように命じることができます。アドレスの一部が、メモリ位置ではなくコマンドを渡すために使用される時、この読み書きの両立は可能です。
表2は、33MHzのPCIバス速度で得られた結果を示します。Hsuの論文と同じ計測法で数えた時、およそ毎秒800万手を生成することができます。著者のプログラム(MBChess)のプレイする強さへのハードウエア指手生成器の影響は、チェストーナメントによって評価されるでしょう。期待される改善は、チェスのレイティングで数百点の範囲内にあります。


6. 結論と将来の作業
このプロジェクトは、コンピュータチェスでのFPGAの活用を提案しています。ASICとFPGAの資源の基本的な違いが、FPGAによく適している解決策を生みました。現行のFPGAで見られる、予め埋め込まれたRAMが重要な役割を果たすことを示しました。フロアプランナは、更に設計の動作速度を上げることに貢献しました。より単純な内部結線策によって、チェスの例外手、および王手する駒を区別する問題を解決しました。FPGAの中にプロセッサが標準で入ることが近い将来起きると共に、集積回路とプログラムコードの統合は、FPGAを完成させ更に強力なソリューションとなるでしょう。
これを書いている今、次の人対計算機のチェスの大試合は、2002年の第1四半期に予定されています。それは現在の世界チャンプであるVladimir KramnikとDeepFritzの対局になるでしょう。そのチェスハードウエアは、専用ハードを付けないマルチプロセッサ型スパコンでしょう。その完成システムは、毎秒400万手以上を読むことが出来ます。DeepFritzは(DeepBlueと比べ)処理速度を欠いていても、チェスの棋理と最適化されたプログラミングで武装しています。私たちは、そのコストの僅か数分の1で同様のことを行うために、FPGA指手生成器が使われると信じています[*7]


[*1] :XilinxのFPGAのみにある小規模RAMのことで、LUTを代替して用いる。
[*2] super-pieceとは巧い表現だが、ここではポーンからクイーンまでの利きを合わせ持つ仮想的な駒のことを意味している。

[*3] この項は、何が書いてあるのか非常に判り難い。要は「王手を掛ける手を見つけ出すハードウエア的アルゴリズム」がテキストで説明されているだけで無理がある。このあたりは、MBThesis.pdf の記述の方が図を加えて説明されていて判り易い。

[*4] ファンアウトとは、あるゲートの出力が、他のゲートの入力へ同時に幾つ分岐しているかを言う。

[*5] ファンアウトが極端に大きい(一般に10以上の)場合、バッファと呼ばれる回路を介して充分な電流を流せるようにし、他のゲートを正しく駆動する必要がある。但し、最近の論理合成では、このあたり自動的に判断してバッファを入れてくれるので、あまり深く考えなくても構わない。

[*6] Cプログラムを用いて、VHDLの文法で記述されたソースファイルを作っている。具体的には、以前紹介したMarcのソース MoveGenVHDL.zip の中の、 chess_board_auto_genフォルダの中にある、cb_gen.cpp のことを言っている。なお、このソースの拡張子はC++だが中身はCである。何故そんなことをやったのかといえば、多数の部品間配線について人間がVHDLコードを手で書くと、手間がかかる上に間違いが極めて多くなるからで、それを回避したかったのだと思われる。

[*7] と、取りあえず日本語(になってない気がする言語)に訳したが、一度原文の方も読まれることを強くお奨めする。どのようなことが書いてあるのか大筋を知った上で原文を読まれた方が、より正確に理解し易いと思われる。

AD

Chrilly said (2004/10/17)

テーマ:
Sun Oct 17 13:28:39 PDT 2004 [computer-go] Computer Go hardware

>あなたのシステムは、それ自体、"nothing short of"スパコンだ[*1]


"nothing short of"(私の辞書にはこの句がない)とはどういう意味でしょうか。もし、スパコンですらない、という意味なら同意はしません。私は現在、(Hydraの)32/64プロセッサ()版を作っています。そのマシンは、ピークで毎秒3億局面を探索するようになるでしょう。1つの局面は(Cで書いたものとして)40,000命令になるので、私の計算が正しいなら120テラIPS[*2]になります。

32/64は恐らく合理的に使用することができるプロセッサ数です。並列化による高速化は、プロセッサ数が多くなると共に急激に減少します。日本の地震マシン[*3]は、次のHydraのFPGA群編成(クラスタ)ほど効率的でなく、間違いなく(Hydraより)遅いでしょう[*4]。囲碁の場合、使えるプロセッサの数は、恐らく多くなります。しかし、1024個以上のプロセッサマシンにおいては、主にプロセッサ間の通信で忙しくなり、それ以上増やしても変わりません。

私は、多並列のZugzwang[*5]チェスプログラムのコードを得ました。そしてプログラムの問題が判りました。それは大きな通信ループと、通信の空き時間の中でのみ僅かなステップのチェス計算(探索)しか行われていないかった、ということです。これはそのようなシステムを走らせておく唯一の方法で、ZugzwangではCPU当たりの探索ノード数が極端に低かったのです。

:32個の物理ノードを持ち、各FPGAには2つのチェスコアが入っているので、32/64プロセッサマシンと私は呼んでいます。


>コンピュータ囲碁が、組織された学者によって優位に立たれた段階まで成熟していないので、私たちの多くは嬉しく思う。しかしそれは、まもなく起きるだろう。


私は組織の中の学者では全くありません。ChessBaseからの僅かな予算でBrutusFPGAマシンを開発した、フリーの専門チェスプログラマです。今年から始まったプロジェクトは Hydraと呼ばれます。Hydraは、アラブ首長国連邦のPal-Computingに資金援助されています。コンピュータチェスは、確かにあまりにもプロ的で厳しくなりました。そして更に著しい開発競争を引き起こしました。私はこの空気が好きではありません。Graz 2003の中に、チェス世界選手権より遥かに愉快なコンピュータ囲碁大会を見つけました。


[*1] Chrillyも解釈に困っているようだが、私も書き手の意図が正しくは判らない。「あなたのシステムは、スパコンに届かない、それ自体が無(意味なもの)だ」と取れるので、単に嫌味を言われているだけなのかもしれない。('05/06/10) "nothing short of" は「他ならない」という意味だそうである(コメント参照)。exactlyと等価なようで、「あなたのシステムは、それ自体スパコンに他ならない」の意となる。ニュアンスを厳密に訳すると「スパコンであって、それ以外の何者でもない」というところだろうか。

[*2] 「テラ」は1012倍を意味する。原文では、"120 Tera-MIPS" と記されているが、"120 Tera-IPS" の誤りである。それはともかく、この数字の妥当性を検証してみよう。40,000命令を仮に10[clocks]で実行したとすればIPC値は4,000となり、64個のコアの稼働率が100%の時、総IPC値は単純に64倍の256kとなる。そのコアがユーザクロック50MHzで動くものと仮定すれば、128TIPSとなるので試算上は、ほぼ間違っていない。また、50MHzで動くということは、1局面あたり10[clocks]で毎秒500万局面となるので、500万×64=3.2億となり、Chrillyの「ピークで毎秒3億局面」という発言と符号は一致する。

[*3] 原文では、"The Japanese earthquake-machine"となっている。ここでいう「日本の地震マシン」とは「地球シミュレータ ('02年3月11日運転開始) NEC SX6」のことを指しているものと思われる。当時('04/11まで)、この世界最速のウルトラコンピュータは、ベクトルプロセッサ総数5,120個、主記憶容量10TB、ピーク性能40.96TFLOPS、実測稼動率87.55%で35.86TFLOPS、と公表されている。

[*4] 計算機資源を、ある程度自在に分割して複数のプログラムが同時多目的で使えるので、Hydraと同じ次元で語られても日電社員が怒るだけである。また、ベクトルマシンは日本のお家芸であるから、VPPシリーズを手掛けた富士通社員も怒って可。仮に現Hydraの持つ全FPGAで浮動小数点乗算が出来るようにプログラミングしても、1TFLOPSどころかせいぜい数十GFLOPSの性能しか出せない。短距離選手がマラソン選手相手に、その瞬発力や最高速を自慢しても意味がないのと同じだ。付け加えて、Hydraで使用されている光ネットワークは、結局市販品レベルで速いとは言えない。

[*5] Zugzwang(ツークツワンク)とは、本来「自分の手番であっても、状況が不利なる手しか残っていない局面のこと」なのだが、ここではZUGZWANGという名前のチェスプログラム を指している。

AD

Chrilly said (2003/12/05)

テーマ:

Fri Dec 5 09:31:47 PST 2003 [computer-go] FPGA


FPGAで実行可能な速度は、設計の論理的な複雑さに依存します。Brutusでは、私は多少時代遅れだったXilinx Virtex-IのV1000Eを使用しました。Brutusは30MHzで走ります。それほど速くありませんが、局面を8-9サイクルで評価できます。私が考えている碁の設計なら(より速いチップを使えば)、約100MHzで走る筈です。従って、局面を評価するのに100サイクルを必要としても、100万局面/秒になります(私の目標は10-15サイクルです)。


ゲート数は言い難いですね。一応、Virtex-Iの1000Eは100万ゲート品です。しかしこれは市場で手に入るゲート数で、はるかに大きく(かつより速い)利用可能なFPGAは他にもあります。思うに、ゲート数はもはや重大な制限ではないでしょう。特に、Brutusの評価はかなり複雑で、Virtex-1000の70%を使用しています。Virtexの回路構成設定には、Alpha-Data社のADM-XRCボードの場合で約1秒かかります。理屈の上では、ゲーム中にプログラムを切り替えることができたことになります(例えば、特殊な終盤モジュールを使うことで切り替えて)。


他の現実問題として:

a) FPGAの価格は実に高い。FPGAは、それだけがあれば十分というのではなくボード/カードも必要とします。Xilinxは今非常に面白いチップ、Spartan-3を作ろうとしてます。それは90nmプロセス技術を用い、また非常に安くなる(100万ゲートあたり12ドル)と発表されています。しかしそれは現在、発表だけの話です(FPGAビジネスは、発表を第一とする商売です)。

b) 複雑な設計であれば論理合成(コンパイルに相当する)が終わるまで、実に時間が掛かります。私のやや速いPCでも全合成に2時間かかります。

c) CPU-FPGA間通信は、PCIバスを介します。これは厳しいボトルネックです。 直接メモリへマップさせるいくつかの設計法がありまが、それはやや脆弱な考えです。そうなると特定のマザーボードでしか動かないことになってしまいます。


このボトルネックの影響によって、極めて高度なFPGAプログラム(探索を含んで)を書かなければならなくなります。局面評価あるいは指手生成を単独で実行することができません。バスを介してこれらの機能を呼び出すことは、PC上で行う[*1]より遅くなります(少なくともチェスでは)。(但し将来)新しいPCI Expressによって、この状況は改善するでしょう。


最後になりましたが:

ハードウエアとソフトウエアとでは設計が全く異なります。それは非常に険しい学習曲線をとります。私は、その(ハードウエア設計の)概念を習得するまで約1年を必要としました。ソフトウエアではタイミング[*2]についての概念はありませんが、ハードウエアではタイミング[*2]は極端に重要です。全ての演算は正確なサイクルで行わなければなりません[*3]。その命令の順序は重要ではありません[*4]

ソフトウエアプログラマなら、最初に命令Aそして次にBと書けば、AはBの前に実行されると思うでしょう。その想像は、ハードウエアプログラミングでは全く誤っています[*5]


[*1] 勿論、通信に時間を喰われるので、CPUで実行するのと比べて、という意味。

[*2] 原文では "time" となっているが、「回路内で同期を取る時期・時刻」という意味。

[*3] 厳密に言うなら、「均等な時間間隔の中で行わなければならない」となる。つまりは、回路内での各演算の入力から出力までの最大遅延時間を、そのサイクル時間内に収めなければならないということ。

[*4] ハードウエアというのは、結局回路全体が一斉同時に動くものなので。

[*5] 直訳すると、奇怪な翻訳になるので、全体的に意訳した。

AD