Explicit Data Graph Execution

Explicit Data Graph Execution あるいは EDGE とは、命令セットアーキテクチャ (ISA) であり、個々の命令を結合して「ハイパーブロック」と呼ばれる容易に並列実行可能なグループにまとめ、膨大な数の実行ユニットで実行させることで、 一般的なプロセッサ（x86など）に対して演算性能を大きく向上させることを目指している。 現代的なCPU設計における並列実行は、8個程度の実行ユニットと1～4個程度のコアで頭打ちになっているが、EDGE の設計では数百個のユニットを内部的に持てるようにし、これまでの設計に対して数百倍の高速化を実現しようとしている。EDGE の概念は2012年までに1チップで1TFLOPSを実現させることを目指した米国国防高等研究計画局の Polymorphous Computing Architectures プログラムの下、テキサス大学オースティン校が牽引している^[1]。

ほぼ全てのコンピュータプログラムは、データをある形態から別の形態へと変換する命令列から成り立っている。CPUの目的は、データの変換を可能な限り高速に行って性能を向上させることであり、CPUがサポートする命令セットは変換が高速になるような意図で設計されている。コンピュータの発展に伴って、コンピュータ内部の様々な要素の相対的なコストが大きく変化し、それによって命令セットの設計に大きな転換期が何度か訪れた。

1960年代にはメモリが相対的に高価であり、CPU設計者は貴重なメモリ資源を有効に活用できるよう、内部に命令とデータを密に詰め込んだ命令セットを開発した。たとえば、 A と B を加算し、C に出力 という命令は A と B を主記憶、インデックス、レジスタなど様々な場所から取り出すために異なる種類のものが提供されていた。異なる命令が提供されることで、プログラマは最もメモリ消費量が抑えられる命令を選択することができた。全ての命令に任意のデータアクセス方法を選択できるようにした命令セット(たとえばMotorola 68000)は「直交的」と呼ばれ、設計の模範とされた。こうした命令セットは様々なアクセス方法を提供するため複雑化し、今日ではCISC(複雑な命令セットを備えたコンピュータ)と呼ばれている。

1970年代の後半までにメモリは安価になったが、相対的に性能が低くなり、CPUはメモリの数倍の速度で動作できるようになった。その結果、直交性によりCPUはわずかなメモリ上のスペースを節約できるものの、性能の向上には寄与せず、もはや直交性は重要ではなくなった。 この時期にはRISCの設計思想が繁栄し、直交的な命令はほとんどなくなってデータを操作する命令はレジスタとのみやり取りするようになった。命令を減らしたことで命令デコーダが簡潔なものになり、CPUには大きな空きスペースが生まれた。このスペースはレジスタを大きく増やすために用いられた。データをレジスタ内に保持することでアクセスが高速になり、1990年代まで、RISC設計のCPUはCISC設計のものの性能を上回った。この差は圧倒的なもので、その後x86などの現代的なCISC設計のCPUは、実質的にRISCのエンジンとなり、内部で CISC 命令を RISC 的な形式に変換して動作するようになった。

1990年代にはチップの設計技術、製造プロセスが進歩し、安価なプロセッサにすら実現可能な全ての機能を盛り込むことができる段階に達した。さらなる性能向上のため、CPUの設計は内部的に並列性を獲得するようになった。これは "スーパースケーラ" と呼ばれる。どんなプログラムでも、互いに関連のないデータを処理する命令があり、演算ユニットを追加すれば、これらは同時に実行することができる。CPUに追加された新たな要素「スケジューラ」が、関連のないデータを探して演算ユニットに投入し、出力結果を並べ替える。外部には通常に実行したかのように見える。

スーパースケーラの設計で獲得できる並列性の度合いは、スケジューラが命令同士の依存関係を調べることのできる数に依存する。多数の命令を調べることができれば並列に実行可能な命令を見つける可能性が高まるが、これにはスケジューラー自体を複雑にする以外にない。膨大な労力が費やされたが、これまでのRISC / CISC命令セットでは演算ユニットの数は3〜4で飽和している。

他には、特定の種類のデータを処理する命令を見つけて専用の処理ユニットを追加することで、システムの性能を向上させることができる。浮動小数点演算ユニットや、最近ではSIMDユニットの追加はこうした方法である。この方法の問題はCPUが汎用的ではなくなることで、たとえば全てが浮動小数点演算であるようなプログラムを実行すると、FPUは全力で動作し続けるが他のユニットは遊んでしまう。

現代的なCPU設計で、より近年問題になっているのはレジスタとのやり取りに伴う遅延である。CPUのダイサイズは過去数十年間概して変わっていないが、各機能ユニットは様々な機能ユニットが追加されにつれどんどん小さくなっている。すなわち、機能ユニットとレジスタとの相対的な距離はどんどん長くなっている。かつてメインメモリとの通信による遅延を抑えるために生まれたレジスタが避けるべき遅延となってきている。

かつてメモリが安価になり通信による遅延が問題になったことがCISCからRISCへの急激な変化を引き起こしたように、 CPUの設計者は、並列化による性能向上の問題とレジスタの遅延の問題が、基本的に命令セットを切り替えることになるかどうかについて検討している。

新しい命令セットを導入しようという試みの一つがItaniumに代表されるVery Long Instruction Word (VLIW) アーキテクチャである。VLIWはスケジューラのロジックをCPUから移動し、命令列を検査するのに十分な時間とメモリを使用することが可能なコンパイラで実行する。この「静的配置、静的発行」という実行モデルは遅延が全て事前に既知である場合にはうまく動作するが、実際にはコンパイラが命令語を命令で満たすことは困難な挑戦であることがわかってきた^[2]。たとえば、キャッシュにデータがあれば5サイクルかかる命令も、なければ数百サイクルかかる可能性があるが、コンパイラには実行中にどのデータがキャッシュに入っているかを知る術はない。こうした遅延は、コンパイルするプログラムとは何の関係もないシステムの全体的な負荷やその他の要素によって定まるものである。

既存のCPU設計における性能上のボトルネックは、データとそれを処理する命令が、メモリ上に分散していることである。メモリ性能は全体の性能を規定し、過去の「動的配置、動的発行」は、性能の限界に達しているようである。VLIWは「静的配置、静的発行」モデルを用いたが、プログラムの実行時の振る舞いを予測し、あらかじめ適切にスケジュールしておくことが困難であるため、実現困難なことがわかってきている。

EDGEアーキテクチャは「静的配置、動的発行」設計に基づく新しい種類のISAである。EDGEシステムはソースコードを静的に割り当てられた数百〜数千の命令からなる「ハイパーブロック」を形成するようにコンパイルし、ハイパーブロックが CPU により動的にスケジュールされる。EDGEは、VLIWのコンパイル時にデータの依存関係を見つけるという概念と、データが利用可能になったときに命令を実行すると言うスーパースケーラのRISCの概念の、それぞれの利点を組み合わせて用いる。

現実世界の大半のプログラムは、データと命令の関連は明示的である。プログラムは（時代によって異なるが）サブルーチン、手続き、メソッドと呼ばれる開始点、終了点が明確に定義されたデータの入出力を行うブロックに分割される。この情報は高級言語がより単純なプロセッサの命令セットに変換される際に失われる。しかし、この情報は非常に役立つもので、現代的なコンパイラはこれを "基本ブロック (basic block)" として一般化し、レジスタを介したメモリアクセスを最適化する際に基本ブロックの特定を行う。命令のブロックは制御命令を含んでおらず、述語命令を含むことができる。命令ブロック間や記憶領域とのデータの流れを示すことで、これらのブロックを用いてデータフローグラフが生成される。

EDGEの基本的な考え方は、こうしたブロックの操作を命令セットレベルでサポートすることである。基本ブロックはメモリへのアクセスを詳細に定義された方法で行うので、プロセッサは関連したブロックをロードし、スケジュールし、あるブロックの出力をそれを用いるブロックに直接与えることができる。これによって汎用の大域的なレジスタファイルが必要なくなり、コンパイラがレジスタへのアクセスをスケジュールする作業が全体として簡略化される。その代わり、各基本ブロックは専用のローカルレジスタを持ち、コンパイラはより単純なブロック内部での最適化を行う。

EDGEシステムは、1960 / 70年代、また1990年代のデータフロー言語によく似ている。データフローコンピュータはプログラムを、ある命令がその処理対象が利用可能になると実行可能になることを規定する「データフロー着火規則」に基づいて実行する。EDGE のようにデータを分離するため、データフロー言語は本質的に並列的であり、データフローへの関心は一般的なコンピュータの問題に対する大規模な並列化方法への関心につながった。当時存在したCPU技術を用いた研究結果では、データフローマシンが、CPUが十分並列的に動作できるほど近くにデータを保持することが難しいとされたが、それはまさに現在の製造技術を用いて数百個のCPUとメモリを一つのダイに配置れば解決できるボトルネックである。

データフローシステムが全く受け入れられなかったもう一つの理由は、当時のコンパイラがC++のような必須の言語に対応していなかったことである。代わりに、ほとんどのデータフローシステムはPrographのような専用の言語を用いており、商業的な関心を失わせた。この10年のコンパイラの研究によりこうした問題の多くは解決しており、またデータフローとEDGEの大きな違いとして、EDGEの設計は一般的に用いられている言語に対応することを意図している。

EDGE設計に基づく CPUは、一つ以上（現実的には数百）の小さなブロック実行エンジンと、専用のローカルレジスタを持つ。各ユニットは専用のブロック間コミュニケーションリンクで接続されている。コンパイラによってブロックに付加される情報により、スケジューラはブロック全体を検査して、入力データが利用可能であれば実行エンジンに送る。ブロック内の個別の命令を検査する必要はない。

複雑さをわずかに増やすだけで、スケジューラは複数のブロックを検査してあるブロックの出力が他のブロックの入力となることを判断し、これらのブロックをユニット間の通信による遅延を減らすよう配置することができる。現代的な並列性を抽出するために CPU が数千の命令を検査することができるなら、EDGEでは同等の複雑さで、それぞれ数百の命令からなる数千のハイパーブロックを検査することができる。この操作がEDGEの名前の一部「グラフ」の元になっており、グラフとはブロック間のデータの流れを元にブロック同士を接続したものである。

EDGEの概念におけるもう一つの利点は、大規模に拡大可能な点である。ローエンドの設計では、ブロック実行のエンジンを一つしか持たず、スケジューラもプログラムから呼び出すとおりにブロックをエンジンに送出するだけ、といった構成にすることができる。デスクトップ向けのEDGEプロセッサの設計では、数百個のブロック実行エンジンを備えるだろう。決定的な点は、二つの設計の違いは、チップの物理的な配置と、スケジューラのみが知っている情報だけであり、実行ユニットが一つのマシン用に記述されたプログラムは、デスクトップ用のものでも全く同じように（ただし数千倍高速に）動作するという点である。また消費電力も劇的に改善され、その管理も簡潔なものになる。消費電力上の必要に応じて各ブロックの実行エンジンを有効無効にすることができ、それが電力消費に正比例する。

EDGEの概念で最も優れている点は、いかなる種類のデータ処理にも適合するという点である。CPUの異なる部分が異なる種類のデータ専用になっている現代のCPU設計とは異なり、EDGE CPUは通常ひとつの種類の ALU的な演算ユニットからなる。様々なプログラムを同時に実行するデスクトップのユーザーは、浮動小数点の演算のみ用いる一つのプログラムを実行する科学技術演算のユーザーと同じ恩恵を受ける。いずれのケースでも、スケジューラは各ブロックを実行ユニットにロードするだけである。個別のブロック実行エンジンの性能は専用のFPUには到底及ばないが、これを膨大な並列化によって圧倒しようとするものである。

テキサス大学オースティン校は、TRIPS と呼ばれるEDGE命令セットアーキテクチャを開発している。EDGEを動作させるCPUのマイクロアーキテクチャを簡略化するため、TRIPSのハイパーブロックに制約を設けている。

• 最大128命令
• 最大32のロード/ストア
• 32のレジスタバンクに対する読み書き
• ブロックの終端を示す分岐を一つ持つ

TRIPSコンパイラは静的に命令をハイパーブロックにまとめるが、ブロックを特定のALUで動作するようにする。TRIPSのプログラムは実行するアーキテクチャの実装に若干の依存が生じる。

2003年、TRIPSのプロトタイプが作成された。これは4x4のグリッドに配置された16個の実行エンジンと、1MBのローカルキャッシュ、転送メモリを備えていた。シングルチップの TRIPS は、カナダでIBMが130 nmプロセスで製造し、上記のグリッドエンジンを二つ、共有のL2キャッシュと様々なサポートシステムを備えていた。このチップ4つと1GバイトのRAMが実験用のドータカードに乗せられていた。

TRIPSチームは最終的な目標をシングルチップで1TFLOPSの性能を持続的に出すことに設定している。これは、2008年におけるハイエンドのCPU性能の約 50 倍に当たる（デュアルコア Xeon 5160は17G FLOPSの性能）。

CMUのCASHは "Pegasus" と呼ばれる中間コードを生成するコンパイラである。CASHとTRIPSはよく似た考え方であるが、CASHは特定のアーキテクチャを対象としたコードを生成するのではないため、ブロックのレイアウトに制約はない。

ワシントン大学 のWaveScalarアーキテクチャは、実質的にEDGEと似ているが、命令を "wave" に静的に配置しない。替わりに特殊な命令 (phi、rho) を用いてwaveの境界をマークし、wave単位のスケジューリングを可能にする^[3]。

• University of Texas at Austin, "TRIPS Technical Overview"
• A. Smith et al., "Compiling for EDGE Architectures", 2006 International Conference on Code Generation and Optimization, March, 2006