再構成可能コンピューティング

再構成可能コンピューティングは、ソフトウェアの持つ柔軟性とFPGAなどの高度に柔軟な高速コンピューティング構造による高性能ハードウェア処理を組合わせたコンピュータ・アーキテクチャである。一般的なマイクロプロセッサを使った場合との根本的な違いは、制御フローに加えて実際のデータ経路を変更する能力があることである。一方、ASICなどの専用ハードウェアとの主な違いは、再構成可能な構造に動作中でも新たな回路構成を「ロード」することができる適応能力である。

1. 歴史と特性
--------

再構成可能コンピューティングの概念の発祥は1960年代ごろ、ジェラルド・エストリンの記念碑的論文で一般的なプロセッサに「再構成可能な」ハードウェアの配列を接続したコンピュータを提案したのが最初である。メインプロセッサは再構成可能ハードウェアのふるまいを制御する。再構成可能ハードウェアは画像処理やパターンマッチングなどの特定のタスクを実行するよう可及的速やかに仕立てられる。タスクが完了したら、そのハードウェアは別のタスク向けに構成し直される。これによってコンピュータはソフトウェアの汎用性とハードウェアの高速性を兼ね備えたものとなる。しかしこのアイデアは時期尚早であり、当時の電子回路技術では実現不可能だった。

1980年代から1990年代にかけて、この分野の研究は再び活気を帯びてきた。産業側でも学究側でも様々な再構成可能なアーキテクチャが開発された。たとえば、[1], Matrix, [2], Elixent, XPP, Silicon Hive, Montium, Pleiades, Morphosys, PiCoGA などである。これらのデザインが可能となったのは、半導体技術の進歩によって複雑なデザインをひとつのチップに実装できるようになったためである。世界初の再構成可能な商用コンピュータ Algotronix CHS2X4 は1991年に完成した。これは商業的には成功したとは言えないが、ザイリンクス社はこの技術と Algotronix の技術チームを買い取った。

2. パラダイムシフトとしての再構成可能コンピューティング
-----------------------------

計算機科学者ライナー・ハルテンシュタインは、再構成可能コンピューティングを「アンチマシン」と呼称している。ハルテンシュタインによれば、これは従来のフォン・ノイマン・マシンからの根本的パラダイムシフトを表したものだという。ソフトウェアからコンフィグウェアへの移行により、処理速度が劇的に向上すると同時に、消費電力も劇的に減らすことができる。しかし、FPGAの実装密度はムーアの法則で示されるものよりずっと低く、クロック周波数も最新のマイクロプロセッサに比べると大幅に低い。そのためハルテンシュタインはこれを「再構成可能コンピューティングのパラドックス」と呼んでいる。これは、パラダイムシフトであるがゆえのパラドックスであり、従来のパラダイムが持つフォン・ノイマン・ボトルネックが一因となっている。

ニック・トレデニックは、コンピューティングのパラダイムを分類することで、再構成可能コンピューティングの基本モデルの1つであるデータストリームベースのアンチマシンを従来からのパラダイムと対比させた。

再構成可能コンピュータの基礎モデルであるデータストリームベースのアンチマシンは、命令ストリームベースのフォン・ノイマン・マシンのパラダイムの対極にある。例えば、最も単純な再構成可能システムは、動作に際して命令をフェッチすることがない。通常動作以前に行う再構成は、ある意味で「スーパー命令フェッチ」ともいうべきものである。データストリームベースであるため、アンチマシンはプログラムカウンタを持たず、代わりにデータカウンタを持つ。「データストリーム」という用語はシストリックアレイから採用されたもので、シストリックアレイではセル間のデータの流れを意味する。

しかし元々のシストリックアレイは主に数学者が研究し、アンチマシンの半分だけ、すなわちデータの経路しか定義しなかった。データの順序を制御するという点は定義せず、シストリックアレイにどうデータを供給するか、シストリックアレイの出力をどう使うかは考慮されていない。アンチマシンのデータ順序制御面は分散メモリでモデル化される。これを Auto-Sequencing Memory  と呼ぶ。ASMブロックにはデータカウンタを含むシーケンサが備わっている。一例としてDMAを一般化した Generic Address Generator がある。

2.1. 計算のストリーミングモデルの例
--------------------

問題: 長さ256のchar型配列 A[] と B[] があり、配列 C[] を となるよう計算する。この問題は仮想的なものだが、実世界の問題にも似たような例はある。

ソフトウェアで解く場合、C言語では次のようなコードになる。 このプログラムの実行には 256*10*CPI サイクルかかる。ここでCPIとは、1命令あたりのサイクル数である。

これを例えばFPGAなどハードウェアで実装した場合を示す。その場合、配列 'A' の各要素がマイクロプロセッサによって「ストリーム」化され、サイクル毎にFPGA上の回路に送り込まれる。配列 'B' はROM、例えばFPGAのBRAMに実装されるものとする。'B' とラベル付けされたROMに入っていく線はアドレス線であり、出てくる線はそのアドレスに格納されていた値を出力するものである。青い四角形は一時的な値を格納するレジスタである。見ての通り、これはパイプライン構造であり、8サイクルで C[i] の値を出力する。入力がストリーム化されていれば、出力もストリームとなる。

このハードウェア実装では、256+8 サイクルかかる。したがって、ソフトウェア実装に対して 10*CPI のぶんだけ高速化できると期待される。ただし、FPGAはクロック周波数が低いので、性能向上の度合いはそれよりも小さくなる。

3. 用語
-----

Reconfigurable DeviceFPGA、あるいは実行中に機能を変更できる何らかのデバイス。再構成可能なデバイスは粒度の細かいアーキテクチャかもしれないし、中程度の粒度のアーキテクチャかもしれない。プロセッシング要素の機能とそれらをつなぐ相互接続を全て再構成可能なら、そのハードウェアは再構成可能なデバイスと言うことができる。
BitstreamFPGAを構成するファイル。実行準備ができたら Bitstream が FPGA にロードされる。配置と経路のフェーズの最終結果として生成される。
Common Memory一種の共有メモリ。複数のFPGAを搭載したボード上のメモリを指し、FPGA間の直接通信やFPGA以外との通信に使われる。
Compile/Compilationこの用語はマイクロプロセッサ上で動作するコードに関して使うべきである。それにはプロセッサ上で動作するFPGAのシミュレーションやエミュレーションも含まれる。一方、この用語を再構成可能なデバイスの合成のプロセスと配置と経路の生成にも使っている例もある[3]。
Cocompilationソフトウェアのコードとコンフィグウェアのコードを生成するコンパイルを意味する。自動的なソフトウェア/コンフィグウェアの分割も含む[4]。
Configware構成のためのソースプログラム。構造的にコンフィグウェア[5]には対応するソフトウェアが存在する。
Configuration現にFPGA上にロードされている Bitstream を指す。もっと大まかに言えば、基板上の部品やチップを意味することもあるし、再構成可能マシン全体の構成を意味することもあるが、現在の文脈では関係ない。
Cycle accurate simulationFPGAのクロックレベルの動作を正確にシミュレーションするものであり、クロックパルスの上がり/下がりのタイミングに従ってデータの変化を記録する。
Emulation/Simulationシミュレーションあるいはモデリング。FPGAハードウェアのふるまいを通常のプロセッサを使って真似るプロセスである。
High Performance Computing 高性能組み込みコンピューティングあるいは並列コンピューティング。並列コンピューティングはマイクロプロセッサ群によるものか Reconfigurable HPC によるもの。Reconfigurable HPC とは FPGA群か rDPA 群を使ったもので、計算時間がかかり、並列化して実装できるアルゴリズムが特徴である。
Hybridこの文脈では Hybrid とは、ノイマン型コンピューティングと再構成可能コンピューティングの共生である[6]。
On-chip memoryBlock RAMやキャッシュ。この用語はひとつのチップ内に存在するメモリを指す。キャッシュという用語は通常のマイクロプロセッサについてのみ使用すべきである。
Aggregate On-chip memoryマルチFPGAシステムでのオンチップ・メモリの合計を指す。
Local MemoryDRAM, SRAM, QDR, DDR SRAM, ZBT RAM。この用語は FPGA や rDPA に直接接続される外部メモリに使用すべきものである。チップ内にある場合はオンチップ・メモリと呼ばれる。
Reconfigurable ComputingFPGA、rDPA、マイクロプロセッサを混成させてデータを処理するコンピューティングパラダイム。プログラム実行中やプログラム実行前に Bitstream を変更できる。
Reconfiguration構成、プログラミング、再プログラミング
System Memory/Host Memoryマイクロプロセッサのマザーボード上のメモリ。
Reconfigurable Computerマイクロプロセッサとそのメモリ、およびFPGAや rDPA とそのメモリから構成されるコンピュータ。
SynthesisHDL , HLL , GUI を使って記述されたロジックの netlist を作るプロセス。
Place and Route netlist をFPGAや rDPA の物理的構造に変換すること。これによって Bitstream が生成される。

4. 粒度
-----

再構成可能ロジックの粒度は最小機能ユニットのサイズで定義され、マッピングツールで扱う単位となる。粒度が細かいとアルゴリズムをハードウェアに実装する際の柔軟性が増す。しかし、細粒度では消費電力が増加し、経路変更に時間がかかるため、再構成による遅延が大きくなる。細粒度アーキテクチャはビット単位の操作が可能だが、大雑把な粒度ではより一般的なアプリケーション向きに最適化されている。粒度が大きいアーキテクチャの問題点は計算対象が小さいと使われない回路要素が出てくる点である。例えば、1ビットの加算を4ビット幅の機能ユニットで構成すると3ビット分無駄にすることになる。この問題は粒度の粗いものと粒度の細かいものを混合した構成にすることで解決できる。

粗い粒度のアーキテクチャでは、ワード幅のデータパスを必要とするアルゴリズムを実装することを想定している。このため、細かい粒度の機能ユニットで同等機能を実現した場合に比べて消費電力も性能も有利である。中には一般的な特定のアルゴリズムを実装済みで、それに限定された修正を加えるための機能ユニットが付属したタイプのデバイスも存在する。

5. 再構成の頻度
---------

再構成は実行中あるいは実行と実行の間に行われ、それを deployment timeと呼ぶ。deployment timeの間に bitstream を使ってデバイスを再構成する。細粒度のシステムは前述した通り経路接続が多くなるために再構成に時間がかかり、消費電力も増える。また、再構成の頻度が少なければ、消費電力的にも遅延時間の面からも有利となる。部分的に再構成を行いつつ、同時に再構成していない部分で計算を続けるということもあり、その場合は消費電力もあまり増えないし遅延も最小に抑えられる。bitstream を圧縮することも原理的には可能であるが、データを伸長する際の計算にかかる時間と電力を考慮すると効果はそれほど大きくは無い。

6. ホストとの接続
----------

再構成可能デバイスはホストとなるプロセッサに接続してアクセラレータとして使われる。どのような構成が最適かを考えるには、データ転送の種類、遅延時間、電力、性能向上の度合いを考慮する必要がある。最も直感的なデザインとしては、コプロセッサを接続するようなバスで再構成可能デバイスを接続する方法がある。しかし、中にはホストプロセッサのレジスタに再構成可能デバイスが直接アクセスできるような密な接続をした例もある。ホストプロセッサは再構成可能デバイスの機能を呼び出したり、再構成を行ったり、外部とのインターフェイスを受け持つ。

7. ルーティング/相互接続
--------------

再構成可能デバイスの柔軟性は、主にその相互接続のルーティングによるものである。FPGAのベンダーであるザイリンクスやアルテラの相互接続のスタイルは、アイランド型のレイアウトであり、二次元の配列状に機能ユニットが並んでいる。不適切なルーティングをすると、柔軟性が損なわれ、資源が無駄となり、性能が制限される。相互接続を余分に行ってしまうと、必要以上にトランジスタを使ってしまい、シリコン上の領域を消費し、経路が伸びて電力消費が多くなる。

8. ツールフロー
---------

一般に再構成可能コンピューティングのツールはふたつに分類される。再構成可能デバイスのEDAツールとCPUのコンパイルツールである。フロントエンドのコンパイラはこれらを統合したツールであり、構造化されたハードウェア表現形式を生成してハードウェア設計フローへの入力とする。ハードウェア設計フローは、テクノロジーマッピング、配置アルゴリズム、経路設定アルゴリズムの三段階に分けられる。

データフロー型プロセッサには再構成可能コンピューティングを使って実装されたものもある。

9. 参考文献
-------

S. Hauck and A. DeHon, //Reconfigurable Computing: The Theory and Practice of FPGA-Based Computing//, Morgan Kaufmann, 2008.
J. Henkel, S. Parameswaran : Designing Embedded Processors. A Low Power Perspective; Springer Verlag, March 2007
J. Teich  et al.: Reconfigurable Computing Systems. Special Topic Issue of Journal //it — Information Technology//, Oldenbourg Verlag, Munich. [7]
T.J. Todman, G.A. Constantinides, S.J.E. Wilton, O. Mencer, W. Luk and P.Y.K. Cheung, "Reconfigurable Computing: Architectures and Design Methods", IEE Proceedings: Computer & Digital Techniques, Vol. 152, No. 2, March 2005, pp.   193–208.
A. Zomaya : Handbook of Nature-Inspired and Innovative Computing: Integrating Classical Models with Emerging Technologies; Springer Verlag, 2006
J. M. Arnold and D. A. Buell, "VHDL programming on Splash 2," in More FPGAs, Will Moore and Wayne Luk, editors, Abingdon EE & CS Books, Oxford, England, 1994, pp.   182–191. 
J. M. Arnold, D. A. Buell, D. Hoang, D. V. Pryor, N. Shirazi, M. R. Thistle, "Splash 2 and its applications, "Proceedings, International Conference on Computer Design, Cambridge, 1993, pp. 482–486.
D. A. Buell and Kenneth L. Pocek, "Custom computing machines: An introduction," The Journal of Supercomputing, v. 9, 1995, pp.   219–230.

10. 脚注
------

11. 関連項目
--------

プログラマブルロジックデバイス  - FPGA は PLD の一種。
ハードウェア記述言語 
動的再構成
1チップMSX

12. 外部リンク
---------

[8] 南カリフォルニア大学
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]
[30]
[31]