順不同実行

アウトオブオーダー実行を最初に採用したマシンは、おそらくスコアボードを使用して競合を解決したCDC 6600 (1964 年) でしょう。しかし、6600 はWAW 競合処理を欠いており、代わりに停止を選択しました。この状況は、ソーントンによって「第 1 次競合」と呼ばれました。^{[ 5 ]} RAW 競合解決 (「第 2 次競合」^{[ 6 ]}と呼ばれる) とWAR 競合解決 (「第 3 次競合」^{[ 7 ]}と呼ばれる) の 両方を備えており、完全なアウトオブオーダー実行が可能であると宣言するには十分でしたが、6600 には正確な例外処理がありませんでした。初期の限定的な分岐予測は可能でしたが、分岐先が「命令スタック」と呼ばれる場所であり、プログラムカウンタから 7 ワード以内の深さに制限されていました。^{[ 8 ]}

約2年後、IBM System/360 Model 91 (1966) では、トマスロのアルゴリズム^{[ 9 ]}によるレジスタリネーミングが導入され、偽の依存関係 (WAW および WAR) が解消され、完全なアウトオブオーダー実行が可能になりました。レジスタr _nへの書き込みをアドレス指定する命令は、レジスタr _{n を}使用する以前の命令が実行される前に、代替 (名前変更) レジスタalt-r n に実際に書き込むことで実行できます。alt-r _nは、 r n をアドレス指定する以前のすべての命令が実行された後にのみ通常のレジスタr _nに変換されますが、それまでは、 r _nをアドレス指定する以前の命令にはr _{n が}、後の命令にはalt-r _nが割り当てられます。

Model 91 では、レジスタのリネーミングは共通データバス(CDB)と呼ばれるバイパスとメモリソースオペランドバッファによって実装され、実行されていない命令によってアドレス指定されたレジスタの最も古い状態が CDB 上にあるため、物理アーキテクチャレジスタは多くのサイクルで使用されないままになります。Model 91 が 6600 よりも優れているもう 1 つの点は、6600 のようにユニット間だけでなく、同じ実行ユニット内で命令を順不同で実行できることです。これは、6600 の各実行ユニットのFIFO キューとは異なり、準備ができた命令がそこから実行ユニットに送られる予約ステーションによって実現されます。Model 91 は、ロードとストアを前のロードとストアの前に実行するように並べ替えることもできます^{[ 10 ]}。これは、ロードをロードの後ろに、ストアをストアの後ろに移動することはできますが、ロードをストアの後ろに、ストアをロードの後ろに移動することはできません。^{[ 11 ]}モデル91の浮動小数点レジスタのみが名前変更されているため、固定小数点計算を実行する際には、CDC 6600と同じWAWおよびWAR制限の対象となる。91と6600はどちらも不正確な例外にも悩まされており、アウトオブオーダー実行を一般的に適用してスーパーコンピュータ以外で実用化する前に、この問題を解決する必要があった。

正確な例外を実現するには、例外発生時にプログラムの実行の適切な順序状態が利用可能でなければなりません。1985 年までに、James E. Smithと Andrew R. Pleszkun によって説明されているように、さまざまなアプローチが開発されました。^{[ 12 ]} CDC Cyber​​ 205 はその先駆けであり、仮想メモリ割り込みが発生すると、プロセッサの全状態 (部分的に実行された命令に関する情報を含む) が目に見えない交換パッケージに保存され、同じ実行状態から再開できます。^{[ 13 ]}しかし、すべての例外を正確にするには、命令の効果をキャンセルする方法が必要です。CDC Cyber​​ 990 (1984) は、履歴バッファを使用して正確な割り込みを実装しています。履歴バッファには、例外によって命令を元に戻す必要がある場合に復元されるレジスタの古い (上書きされた) 値が格納されます。^{[ 12 ]}シミュレーションにより、スミスは、 Cray-1Sに再順序バッファ (または履歴バッファまたは同等のもの) を追加しても、最初の 14 個のリバモア ループ(非ベクトル化) の実行パフォーマンスは 3% しか低下しないことを確認した。^{[ 12 ]}この主題に関する重要な学術研究は、イェール パットがHPSmシミュレータを使用して主導した。^{[ 14 ]}

1980年代、初期のRISCマイクロプロセッサの多くはレジスタへの書き込み順が逆であったため、例外が必ず不正確になるという問題がありました。Motorola 88100は、書き込み順が逆であったにもかかわらず、不正確例外が発生しなかった数少ない初期のマイクロプロセッサの1つでしたが、正確な浮動小数点例外と不正確な浮動小数点例外の両方を許容していました。^{[ 15 ]} 命令は順番に実行を開始しましたが、一部の命令（浮動小数点など）は実行を完了するのに多くのサイクルを要しました。しかし、最も基本的な命令のシングルサイクル実行により、CDC 6600と比較して問題の範囲が大幅に縮小されました。

スミスはまた、異なる実行ユニットが互いに、またメモリ、フロントエンド、および分岐からより独立して動作するようにする方法についても研究した。^{[ 16 ]}彼はこれらのアイデアをAstronautics ZS-1 (1988) に実装し、整数/ロード/ストアパイプラインを浮動小数点パイプラインから分離し、パイプライン間の再順序付けを可能にした。ZS-1 は、先行するストアの前にロードを実行することもできた。1984 年の論文で、彼は、整数/メモリ パイプラインにのみ正確な例外を適用すれば、仮想メモリも許可されるため、多くのユース ケースで十分であるはずだと意見を述べた。各パイプラインには、命令デコーダから分離してフロントエンドの停止を防ぐための命令バッファがあった。メモリ アクセスと実行をさらに分離するために、2 つのパイプラインのそれぞれに、実質的に限定的なレジスタ リネーミングを実行する2 つのアドレス指定可能なキューが関連付けられていた。 ^{[ 10 ]}同様の分離型アーキテクチャは、少し前にCuller 7で使用されていた。^{[ 17 ]} ZS-1のISAは、IBMの後のPOWERと同様に、分岐の早期実行を支援した。

IBMはPOWER1 （1990年）でアウトオブオーダー実行に回帰した。これは、レジスタリネーミング（ただし、やはり浮動小数点レジスタのみ）と厳密な例外処理を組み合わせた最初のプロセッサだった。リオーダーバッファの代わりに物理レジスタファイル（つまり、コミットされていない値とコミットされた値の両方を含む動的に再マッピングされたファイル）を使用するが、命令のキャンセル機能は分岐ユニットでのみ必要であり、分岐ユニットは履歴バッファ（ IBMではプログラムカウンタスタックと名付けられた）を実装して、カウントレジスタ、リンクレジスタ、および条件レジスタへの変更を取り消す。浮動小数点命令のリオーダー機能でさえ、依然として非常に限定的である。POWER1は浮動小数点演算命令のリオーダーができない（結果がインオーダーで利用可能になる）ため、それらの宛先レジスタはリネームされない。POWER1には、同じ実行ユニットをアウトオブオーダーで使用するために必要な予約ステーションもない。 ^{[ 18 ] [ 19 ]}翌年、IBMのES/9000モデル900では、汎用レジスタにレジスタリネーミングが追加されました。また、デュアル整数ユニット用に6エントリの予約ステーション（各サイクルで、6つの命令から最大2つを選択して実行できます）とFPU用に6エントリがあります。他のユニットには単純なFIFOキューがあります。再順序距離は最大32命令です。^{[ 20 ]} UnisysのAシリーズメインフレームのA19も1991年にリリースされ、アウトオブオーダー実行が謳われ、あるアナリストはA19の技術は競合製品より3～5年先を行っていると評しました。^{[ 21 ] [ 22 ]}

最初のスーパースカラ・シングルチップ・プロセッサ（ 1989年のIntel i960CA）は、25年前にCDC 6600が採用していたような単純なスコアボード方式のスケジューリングを採用していた。1992年から1996年にかけて、トランジスタ数の増加によって可能になった技術の急速な進歩により、パーソナルコンピュータにまで普及した。Motorola 88110（1992年）は、履歴バッファを使用して命令を元に戻した。^{[ 23 ]}ロードは、先行するストアよりも先に実行できた。ストアとブランチが実行開始を待っている間、他のタイプの後続命令は、ライトバックを含むすべてのパイプラインステージを流れ続けることができた。履歴バッファの12エントリの容量は、再順序距離に制限を設けた。^{[ 24 ] [ 25 ] [ 26 ]} PowerPC 601（1993年）は、 RISCシングルチップの進化形であり、RISCシングルチップ自体はPOWER1の簡略化である。 601 では、分岐命令と浮動小数点命令が、フェッチされた命令キューに既にある整数命令を追い越すことが許可されており、その下位 4 つのエントリがディスパッチ可能かどうかスキャンされました。キャッシュ ミスの場合、ロードとストアは再順序付けされる可能性があります。リンク レジスタとカウント レジスタのみが名前変更可能でした。^{[ 27 ] [ 28 ] [ 29 ] [ 30 ] [ 31 ]} 1994 年秋、NexGenとIBM は Motorola とともに、汎用レジスタの名前変更をシングル チップ CPU に導入しました。NexGen の Nx586 は、アウト オブ オーダー実行が可能な最初のx86プロセッサであり、最大 14マイクロ オペレーションの再順序付け距離が特徴でした。 ^{[ 32 ]} PowerPC 603では、汎用レジスタと FP レジスタの両方の名前が変更されました。4つの非分岐実行ユニットのそれぞれは、他のユニットへの命令の流れをブロックすることなく、1 つの命令をその前に待機させることができます。 5エントリのリオーダーバッファでは、未実行の命令を追い越せる命令は最大4つまでです。ストアバッファのおかげで、ロードは先行するストアよりも先にキャッシュにアクセスできます。^{[ 33 ] [ 34 ]}

PowerPC 604 (1995) は、実行ユニットレベルの再順序付け機能を備えた最初のシングルチッププロセッサでした。6 つのユニットのうち 3 つのユニットにはそれぞれ 2 エントリの予約ステーションがあり、新しいエントリが古いエントリより先に実行されるようになっていました。再順序付けバッファの容量は 16 命令です。4 エントリのロード キューと 6 エントリのストア キューは、キャッシュ ミス時のロードとストアの再順序付けを追跡します。^{[ 35 ]} HAL SPARC64 (1995) は、整数、浮動小数点、アドレス生成ユニット用に 3 つの 8 エントリの予約ステーションと、ロード/ストア用に 12 エントリの予約ステーションを備え、 ES/9000モデル 900 の再順序付け容量を超え、以前のプロセッサよりもキャッシュ/メモリ アクセスの再順序付けがさらに可能になりました。一度に最大 64 命令を再順序付け状態にすることができます。^{[ 36 ] [ 37 ]} Pentium Pro (1995) は統合予約ステーションを導入し、20 マイクロ OP の容量で非常に柔軟な再注文を可能にし、40 エントリの再注文バッファによってバックアップされています。ロードは、ロードとストアの両方の前に再注文できます。^{[ 38 ]}

1996年にSGI / MIPS（R10000）とHP PA-RISC（PA-8000 ）が完全なアウトオブオーダー実行をさらに採用したことで、実際に達成可能なサイクルあたりの実行速度はさらに向上した。同年、Cyrix 6x86とAMD K5は高度な再順序付け技術を主流のパーソナルコンピュータにもたらした。 1998年にDEC Alphaがアウトオブオーダー実行を獲得して以来（Alpha 21264）、最高性能のアウトオブオーダープロセッサコアは、HP / Intel Itanium 2とIBM POWER6以外のインオーダーコアには及ばなかったが、後者はアウトオブオーダー浮動小数点ユニットを持っていた。^{[ 39 ]}他のハイエンドのインオーダープロセッサは大きく遅れをとっており、SunのUltraSPARC III / IVや、アウトオブオーダー実行機能を2度失い、 z10世代までインオーダーのままだったIBMのメインフレームなどが挙げられる。その後、大型のインオーダープロセッサはマルチスレッド性能に重点を置いていましたが、最終的にSPARC TシリーズとXeon Phiはそれぞれ2011年と2016年にアウトオブオーダー実行へと移行しました。

電話やその他のローエンド アプリケーション向けのプロセッサは、2010年頃までほぼすべてインオーダーのままでした。まず、QualcommのScorpion (再順序距離 32) がSnapdragonに搭載されて出荷され、^{[ 40 ]}少し後にArmのA9 がA8 の後継となりました。ローエンドのx86パーソナル コンピュータでは、初期のIntel AtomプロセッサのインオーダーBonnell マイクロアーキテクチャが、最初にAMDのBobcat マイクロアーキテクチャに挑戦され、2013 年にアウトオブオーダーSilvermont マイクロアーキテクチャに取って代わられました。^{[ 41 ]}アウトオブオーダー実行の複雑さにより、最小の消費電力、コスト、サイズを実現できないため、インオーダー実行はマイクロコントローラや組み込みシステム、およびbig.LITTLE構成のArm のA55やA510などの電話クラスのコアで依然として主流です。

アウトオブオーダー実行は、インオーダー実行のベースラインに比べてより高度な処理です。パイプライン方式のインオーダー実行プロセッサでは、命令の実行はパイプライン方式でオーバーラップし、それぞれが完了するまでに複数のクロックサイクルを要します。その結果、前の命令の結果が次の命令で必要となるタイミングよりも遅れることになります。インオーダー実行でもこれらの依存関係を追跡する必要がありますが、そのアプローチは非常に単純で、毎回ストールするだけです。アウトオブオーダー実行では、後述するように、はるかに高度なデータ追跡技術が用いられます。

初期のプロセッサでは、命令の処理は通常、以下のステップからなる命令サイクルで行われていました。

1. 命令の取得。
2. 入力オペランドが利用可能な場合（例えばプロセッサレジスタにある場合）、命令は適切な機能ユニットにディスパッチされます。現在のクロックサイクル中に1つ以上のオペランドが利用できない場合（通常はメモリからフェッチする必要があるため）、プロセッサはオペランドが利用可能になるまで停止します。
3. 命令は適切な機能ユニットによって実行される。
4. 機能ユニットは結果をレジスタファイルに書き戻します。

多くの場合、インオーダープロセッサは、パイプラインによってレジスタに書き込まれるビットベクタを記録します。 ^{[ 42 ]}入力オペランドのいずれかにこのベクタ内の対応するビットが設定されている場合、命令は停止します。基本的に、ベクタはレジスタハザードから保護するという非常に簡略化された役割を果たします。したがって、アウトオブオーダー実行では 2 次元マトリックスを使用するのに対し、インオーダー実行ではハザード回避のために 1 次元ベクタを使用します。

この新しいパラダイムでは、命令の処理を次のステップに分割します。^{[ 43 ]}

1. 命令の取得。
2. 命令のデコード。
3. 命令名の変更。
4. 命令キュー（命令バッファまたは予約ステーションとも呼ばれる）への命令のディスパッチ。
5. 命令は、入力オペランドが利用可能になるまでキューで待機します。命令は、古い命令よりも先にキューから出る場合があります。
6. 指示は適切な機能部門に発行され、その部門によって実行される。
7. 結果はキューに格納されています。
8. すべての古い命令の結果がレジスタファイルに書き込まれた後にのみ、この結果がレジスタファイルに書き込まれます。これは卒業段階または引退段階と呼ばれます。

アウトオブオーダー処理の重要な概念は、演算に必要なデータが利用できない場合に発生する一種の停止をプロセ​​ッサが回避できるようにすることです。上記の概略図では、プロセッサは、データ不足のために命令が完全に処理準備できていない場合に、インオーダー処理のステップ2で発生する停止を回避します。

アウトオブオーダープロセッサは、準備のできた他の命令でこれらのスロットを時間通りに埋め、最後に結果を並べ替えて命令が通常どおり処理されたように見せるか、元のプログラム順序を記録して適用するか、または順序がデータ破損を引き起こさない中断不可能なバッチでコミットします。元のコンピュータコードにおける命令の順序はプログラム順序として知られていますが、プロセッサではデータ順序、つまりプロセッサのレジスタでデータが利用可能になる順序で処理されます。一方の順序から他方の順序に変換し、出力の論理的な順序を維持するには、かなり複雑な回路が必要です。

命令パイプラインが深くなり、メインメモリ（またはキャッシュメモリ）とプロセッサの速度差が大きくなるにつれて、アウトオブオーダー処理の利点は増大します。最新のコンピュータでは、プロセッサはメモリよりもはるかに高速に動作するため、インオーダー処理のプロセッサがデータ到着を待っている間に、理論的には大量の命令を処理できる可能性があります。