明示的なデータグラフの実行

明示的データ グラフ実行( EDGE ) は、 Intel x86ラインなどの一般的なプロセッサと比較してコンピューティング パフォーマンスを向上させることを目的とした命令セット アーキテクチャ(ISA)の一種です。EDGE は、多数の個別の命令を「ハイパーブロック」と呼ばれる大きなグループに結合します。ハイパーブロックは、簡単に並列実行できるように設計されています。

現代のCPU設計の並列性は、一般的に約8つの内部ユニットと1から4つの「コア」で頭打ちになり始めますが、EDGE設計は数百の内部ユニットをサポートし、既存の設計よりも数百倍高速な処理速度を提供することを目指しています。EDGEコンセプトの主要な開発は、DARPAのポリモーフィズムコンピューティングアーキテクチャプログラムの下でテキサス大学オースティン校によって主導され、2012年までに1 TFLOPSのパフォーマンスを備えたシングルチップCPU設計を生み出すという目標が掲げられていましたが、2018年現在まだ実現されていません。^[1]

ほぼすべてのコンピュータ プログラムは、データをある形式から別の形式に変換する一連の命令で構成されています。ほとんどの命令では、操作を完了するために複数の内部ステップが必要です。時間の経過とともに、さまざまなステップの相対的なパフォーマンスとコストは劇的に変化し、ISA 設計にいくつかの大きな変化が生じました。

1960 年代のメモリは比較的高価で、CPU 設計者はこのリソースをより有効に活用するために、命令とデータを密にエンコードした命令セットを作成しました。たとえば、命令はadd A to B to produce Cさまざまな形式で提供され、A と B をメイン メモリ、インデックス、レジスタなどさまざまな場所から収集します。これらのさまざまな命令を提供することで、プログラマはメモリのスペースをできるだけ占有しない命令を選択でき、プログラムの必要性を減らし、データのためのスペースを増やすことができました。たとえば、MOS 6502には加算を実行するための8 つの命令 (オペコード) があり、オペランドを収集する場所だけが異なります。^[2]

これらの命令を実際に機能させるにはCPU内に回路が必要でしたが、これは初期の設計では大きな制約であり、設計者は本当に必要な命令だけを選択する必要がありました。1964年にIBMはSystem/360シリーズを発表しました。これはマイクロコードを使用し、必要に応じてハードウェアに命令を増減させることで、単一の拡張命令セットアーキテクチャ（ISA）をさまざまなマシンで実行できるようにしました。 ^[3]これにより360のISAは拡張可能になり、1960年代と70年代のコンピュータ設計の模範、いわゆる直交設計となりました。さまざまなモードを備えたこのメモリアクセススタイルは、何百もの異なる命令を持つ命令セットにつながり、今日ではCISC（複合命令セットコンピューティング）として知られています。

1975 年、IBM は当時最速だったコンピューターの約 3 倍の性能を必要とする電話交換機の開発プロジェクトを開始しました。この目標を達成するために、開発チームは IBM が過去 10 年間に収集した膨大な性能データの調査を開始しました。この調査により、複雑な ISA が実際に重大な問題であることが示されました。最も基本的な命令のみがハードウェアで実装されることが保証されていたため、コンパイラーは特定のマシンのハードウェアでのみ実行されるより複雑な命令を無視していました。その結果、プログラムの時間の大部分は 5 つの命令のみに費やされていました。さらに、プログラムがそれらの 5 つの命令の 1 つを呼び出す場合でも、マイクロコードはそれをデコードするのに有限の時間を必要としました。たとえそれが内部ハードウェアを呼び出すだけのことであったとしてもです。より高速なマシンでは、このオーバーヘッドはかなりのものでした。^[4]

当時IBM 801として知られていた彼らの研究は、最終的にRISC（縮小命令セットコンピューティング）コンセプトにつながりました。マイクロコードは削除され、特定の命令の最も基本的なバージョンのみがCPUに組み込まれました。より複雑なコードはコンパイラに任されました。たとえば、モトローラ68000のトランジスタの約1/3という大量の回路が削除されたため、CPUにさらに多くのレジスタを含めることができ、パフォーマンスに直接影響を及ぼしました。1980年代半ばまでに、これらの基本コンセプトをさらに発展させたバージョンは、あまり発達していない製造技術を使用しているにもかかわらず、最速のCISC設計の10倍もの性能を実現していました。^[4]

1990 年代には、チップの設計と製造プロセスが進化し、あらゆる潜在的機能を組み込んだ汎用プロセッサを構築できるようになりました。以前は別々のチップ上に搭載されていた浮動小数点ユニットやメモリ管理ユニットなどのユニットを同じダイに統合し、オールインワン設計を実現できるようになりました。これにより、異なるタイプの命令を同時に実行できるようになり、システム全体のパフォーマンスが向上しました。1990 年代後半には、単一命令複数データ(SIMD) ユニットも追加され、最近ではAI アクセラレータも追加されました。

これらの追加により、システム全体のパフォーマンスは向上しますが、大多数のプログラムに当てはまる、主に基本ロジックと整数演算で動作するプログラムのパフォーマンスは向上しません (アムダールの法則の結果の 1 つ)。これらのタスクのパフォーマンスを向上させるために、CPU 設計では内部並列処理が追加され、「スーパースカラー」になりました。どのプログラムにも、関連のないデータで動作する命令があるため、機能ユニットを追加することで、これらの命令を同時に実行できます。CPU の新しい部分であるスケジューラは、これらの独立した命令を探してユニットに送り込み、その出力を取得して並べ替え、外部的には連続して実行されたように見えます。

スーパースカラー設計で抽出できる並列処理の量は、スケジューラが相互依存性を調べることができる命令の数によって制限されます。より多くの命令を調べると、並列実行できる命令を見つける可能性が高まりますが、スケジューラ自体の複雑さが増すという代償を払うことになります。多大な努力にもかかわらず、古典的なRISCまたはCISC ISAを使用したCPU設計は2000年代後半までに頭打ちになりました。2013年のIntelのHaswell設計には合計8つのディスパッチユニットがあり^[5]、さらに追加すると設計が大幅に複雑になり、電力需要が増加します。^[6]

システムからさらにパフォーマンスを引き出すには、命令を調べて異なるタイプのデータを操作する命令を見つけ、その種類のデータ専用のユニットを追加します。これにより、1980 年代と 90 年代にオンボード浮動小数点ユニットが導入され、最近では単一命令複数データ(SIMD) ユニットが導入されました。このアプローチの欠点は、CPU の汎用性が低下することです。たとえば、ほとんどすべての浮動小数点命令を使用するプログラムを CPU に入力すると、FPU が低速になり、他のユニットはアイドル状態になります。

最近の CPU 設計における問題は、レジスタとの通信の遅延です。一般的に、CPU ダイのサイズは時間の経過とともにほぼ一定のままですが、CPU 内のユニットのサイズは、ユニットが追加されるにつれて大幅に小さくなっています。つまり、 1 つの機能ユニットとグローバル レジスタ ファイル間の相対的な距離は時間の経過とともに大きくなっています。メイン メモリとの通信の遅延を回避するために導入されたグローバル レジスタ ファイル自体が、回避する価値のある遅延になっています。

メモリの価格が下落する一方でメモリとの通信に遅延が発生したことから、ISA (命令セットアーキテクチャ) が CISC から RISC に根本的に変更されたことが示唆されたのと同様に、設計者は、並列処理のスケーリングの問題とレジスタとの通信に遅延が増大する問題により、基本的な ISA の別の切り替えが必要になるかどうかを検討しています。

新しい ISA を導入する方法の 1 つに、 Itaniumに代表される非常に長い命令語(VLIW) アーキテクチャがあります。VLIW は、スケジューラ ロジックを CPU からコンパイラーに移動します。コンパイラーには、命令ストリームを検査するためのメモリがはるかに多く、タイムラインも長くなります。この静的配置、静的発行実行モデルは、すべての遅延がわかっている場合にはうまく機能しますが、キャッシュ レイテンシがある場合、命令語を埋めることはコンパイラーにとって困難な課題であることが判明しています。^[7]データがキャッシュ内にある場合に 5 サイクルかかる命令は、そうでない場合は数百サイクルかかる可能性がありますが、コンパイラーには、実行時にそのデータがキャッシュ内にあるかどうかを知る方法がありません。これは、全体的なシステム負荷や、コンパイルされるプログラムとは関係のないその他の要因によって決まります。

従来の設計における主要なパフォーマンスのボトルネックは、データとそれを操作する命令が理論的にはメモリ上に分散していることです。メモリ パフォーマンスが全体的なパフォーマンスを左右し、従来の動的配置、動的発行設計はパフォーマンス能力の限界に達しているようです。VLIW は静的配置、静的発行モデルを使用しますが、プログラムの実行時の動作を予測して事前に適切にスケジュールすることが難しいため、習得が難しいことが証明されています。

EDGE アーキテクチャは、静的配置、動的発行設計に基づく新しいクラスの ISA です。EDGE システムは、ソース コードを、数百または数千の多数の個別の命令を含む静的に割り当てられたハイパーブロックで構成される形式にコンパイルします 。これらのハイパーブロックは、CPU によって動的にスケジュールされます。このように、EDGE は、コンパイル時に独立したデータを検索する VLIW コンセプトの利点と、データが利用可能になったときに命令を実行するスーパースカラー RISC コンセプトの利点を組み合わせています。

現実世界のプログラムの大多数では、データと命令のつながりは明白かつ明示的です。プログラムは、サブルーチン、プロシージャ、またはメソッドと呼ばれる小さなブロックに分割されます (時代と使用されているプログラミング言語によって異なります)。これらのブロックには、データが渡される入口と出口が明確に定義されています。この情報は、高級言語がプロセッサのはるかに単純な ISA に変換されると失われます。しかし、この情報は非常に便利なので、現代のコンパイラは、この概念を「基本ブロック」として一般化し、レジスタを介してメモリ アクセスを最適化しながら、プログラム内で基本ブロックを識別しようとしています。命令ブロックには制御文はありませんが、述語付き命令を含めることができます。データフロー グラフは、1 つの命令ブロックから別の命令ブロック、または何らかのストレージ領域へのデータ フローを指定することにより、これらのブロックを使用してエンコードされます。

EDGE の基本的な考え方は、ISA レベルでこれらのブロックを直接サポートし、操作することです。基本ブロックは明確に定義された方法でメモリにアクセスするため、プロセッサは関連するブロックをロードしてスケジュールし、1 つのブロックの出力がそのデータを使用するブロックに直接送られるようにすることができます。これにより、グローバル レジスタ ファイルが不要になり、プログラム全体によるレジスタへのアクセスをスケジュールするコンパイラのタスクが簡素化されます。代わりに、各基本ブロックに独自のローカル レジスタが割り当てられ、コンパイラがブロック内のアクセスを最適化します。これははるかに簡単なタスクです。

EDGE システムは、1960 年代から 1970 年代、そして 1990 年代のデータフロー言語と非常によく似ています。データフロー コンピュータは、命令はオペランドが使用可能になった後であればいつでも実行できるという「データフロー発火規則」に従ってプログラムを実行します。EDGE と同様に、データの分離により、データフロー言語は本質的に並列であり、一般的なコンピューティングの問題に対するソリューションとしての大規模な並列処理へのより一般的な関心に続いて、データフロー言語への関心が高まりました。当時の既存の CPU テクノロジに基づく研究では、データフロー マシンが CPU の近くに十分なデータを保持して広範囲に並列化することは困難であることが示されました。このボトルネックは、数百の CPU とそのメモリを単一のダイに配置することで、現代の製造技術で解決できます。

データフロー システムが普及しなかったもう 1 つの理由は、当時のコンパイラがC++などの一般的な命令型言語で動作することが困難だったことです。代わりに、ほとんどのデータフロー システムはPrographなどの専用言語を使用していたため、商業的な関心は限定的でした。10 年にわたるコンパイラの研究により、これらの問題の多くは解消され、データフローと EDGE アプローチの主な違いは、EDGE 設計が一般的に使用される言語で動作することを目的としていることです。

EDGE ベースの CPU は、独自のローカル レジスタを備えた 1 つ以上の小さなブロック エンジンで構成されます。実際の設計では、このようなユニットが数百個ある可能性があります。ユニットは、専用のブロック間通信リンクを使用して相互接続されます。コンパイラによってブロックにエンコードされた情報により、スケジューラはブロック全体を検査して入力が使用可能かどうかを確認し、エンジンに送信して実行できます。ブロック内の個々の命令を検査する必要はありません。

複雑さを少し増やすだけで、スケジューラは複数のブロックを調べて、あるブロックの出力が別のブロックの入力として取り込まれているかどうかを確認し、これらのブロックをユニット間の通信遅延を減らすユニットに配置することができます。現代の CPU が潜在的な並列性のために 1,000 個の命令を調べるのに対し、EDGE では同じ複雑さで、それぞれが数百個の命令で構成される 1,000 個のハイパーブロックを調べることができます。これにより、追加コストなしでスケジューラの範囲が大幅に広がります。この操作パターンがこの概念に名前の由来となっています。「グラフ」は、ブロック間を流れるデータによって接続された一連のブロックです。

EDGE コンセプトのもう 1 つの利点は、非常にスケーラブルであることです。ローエンドの設計は、プログラムによって呼び出されるとブロックを送信するだけのスタブ スケジューラを備えた単一のブロック エンジンで構成できます。デスクトップでの使用を目的とした EDGE プロセッサには、代わりに数百のブロック エンジンが含まれます。重要なのは、これらの設計間で変更されるのは、チップの物理レイアウトと、スケジューラのみが認識するプライベート情報だけであるということです。単一ユニット マシン用に作成されたプログラムは、デスクトップ バージョンで変更なしで実行できますが、速度は数千倍高速です。電力スケーリングも同様に大幅に改善され、簡素化されています。ブロック エンジンは、必要に応じてオンまたはオフにすることができ、電力消費に線形の影響を与えます。

おそらく、EDGE コンセプトの最大の利点は、あらゆる種類のデータ ロードの実行に適していることです。CPU のさまざまな部分がさまざまなデータ専用になっている現代の CPU 設計とは異なり、EDGE CPU は通常、1 種類のALUのようなユニットで構成されます。デスクトップ ユーザーが複数の異なるプログラムを同時に実行する場合、科学ユーザーが浮動小数点のみを使用して 1 つのプログラムを入力する場合と同程度の並列処理が得られます。どちらの場合も、スケジューラは、ユニットにロードできるすべてのブロックをロードするだけです。低レベルでは、個々のブロック エンジンのパフォーマンスは、たとえば専用の FPU のパフォーマンスには匹敵しませんが、大規模な並列処理によってそのような利点を圧倒しようとします。

テキサス大学オースティン校は、 TRIPSと呼ばれる EDGE ISA を開発していました。これを実行するために設計された CPU のマイクロアーキテクチャを簡素化するために、TRIPS ISA は各 TRIPS ハイパーブロックにいくつかの明確に定義された制約を課します。

• 最大128個の命令を持ち、
• 最大32回のロードおよび/またはストアを発行します。
• 最大32のレジスタバンクの読み取りおよび/または書き込みを発行します。
• ブロックの終了を示すために使用される 1 つの分岐決定があります。

TRIPS コンパイラは命令をハイパーブロックに静的にまとめますが、これらのブロックを特定の ALU で実行するように静的にコンパイルします。つまり、TRIPS プログラムは、コンパイル対象の正確な実装にある程度依存します。

2003 年に、彼らは 4 x 4 グリッドに 16 個のブロック エンジンと 1 メガバイトのローカル キャッシュおよび転送メモリを搭載した TRIPS のサンプル プロトタイプを作成しました。カナダのIBMが130 nm プロセスを使用して製造した TRIPS のシングル チップ バージョンには、このような「グリッド エンジン」が 2 つと、共有レベル 2 キャッシュおよびさまざまなサポート システムが含まれています。このようなチップ 4 つと 1 ギガバイトの RAM が、実験用のドーター カードに一緒に配置されています。

TRIPS チームは、2008 年に利用可能だったハイエンドの汎用 CPU (デュアル コア Xeon 5160 は約 17 GFLOPS を提供) の約 50 倍にあたる 1 TFLOPS の持続的なパフォーマンスで実行できるシングル チップ実装を作成するという最終目標を設定しました。

CMUのCASHは「Pegasus」と呼ばれる中間コードを生成するコンパイラです。 ^[8] CASHとTRIPSは概念的に非常に似ていますが、CASHは特定のアーキテクチャの出力を生成することを目的としていないため、ブロックレイアウトに厳しい制限はありません。

ワシントン大学のWaveScalarアーキテクチャはEDGE とほぼ同じですが、命令を「波」内に静的に配置することはありません。代わりに、特別な命令 ( phi、rho ) が波の境界をマークし、スケジュールを可能にします。^[9]

• テキサス大学オースティン校、「TRIPS 技術概要」
• A. Smith 他、「EDGE アーキテクチャ向けのコンパイル」、2006 年国際コード生成および最適化会議、2006 年 3 月