古典的なRISCパイプライン

コンピュータ ハードウェアの歴史において、初期の縮小命令セット コンピュータ 中央処理装置(RISC CPU) のいくつかは、現在では古典的な RISC パイプラインと呼ばれる、非常によく似たアーキテクチャ ソリューションを使用していました。これらの CPU は、 MIPS、SPARC、 Motorola 88000、そして後に教育用に発明された概念上の CPU DLXでした。

これらの従来のスカラー RISC 設計はそれぞれ、サイクルごとに 1 つの命令をフェッチして実行しようとします。各設計の主な共通概念は、5 ステージの実行命令パイプラインです。動作中、各パイプライン ステージは一度に 1 つの命令を処理します。これらのステージはそれぞれ、状態を保持するフリップフロップのセットと、それらのフリップフロップの出力で動作する 組み合わせロジックで構成されています。

命令は、読み取りに 1 サイクルかかるメモリ内にあります。このメモリは、SRAM 専用にすることも、命令キャッシュとして使用することもできます。コンピュータ サイエンスでは、「レイテンシ」という用語がよく使用され、操作の開始から完了までの時間を意味します。したがって、命令フェッチには 1クロック サイクルのレイテンシがあります(シングル サイクル SRAM を使用している場合、または命令がキャッシュ内にある場合)。したがって、命令フェッチステージでは、32 ビット命令が命令メモリからフェッチされます。

プログラムカウンタ(PC) は、命令メモリに提示されるアドレスを保持するレジスタです。アドレスは、サイクルの開始時に命令メモリに提示されます。次に、サイクル中に命令が命令メモリから読み出され、同時に次の PC を決定するための計算が行われます。次の PC は、PC を 4 だけ増分し、それを次の PC とするか、分岐/ジャンプ計算の結果を次の PC とするかを選択することによって計算されます。従来の RISC では、すべての命令の長さが同じであることに注意してください (これが RISC と CISC ^[1]を区別する 1 つの点です)。元の RISC 設計では、命令のサイズは 4 バイトであるため、常に命令アドレスに 4 を追加しますが、実行される分岐、ジャンプ、または例外の場合は PC + 4 を使用しないでください (以下の遅延分岐を参照)。 (一部の最新のマシンでは、次の命令アドレスを推測するために、より複雑なアルゴリズム (分岐予測および分岐ターゲット予測) を使用していることに注意してください。)

最初のRISCマシンとそれ以前のCISCマシンを分けるもう1つの点は、RISCにはマイクロコードがないことです。^[2] CISCのマイクロコード化された命令の場合、命令キャッシュからフェッチされると、命令ビットはパイプラインに沿ってシフトされ、各パイプラインステージの単純な組み合わせロジックが命令ビットから直接データパスの制御信号を生成します。これらのCISC設計では、従来デコードステージと呼ばれていたステージでデコードはほとんど行われません。このデコードの欠如の結果として、命令の実行内容を指定するためにより多くの命令ビットを使用する必要があります。そのため、レジスタインデックスなどに使用できるビットが少なくなります。

すべての MIPS、SPARC、および DLX 命令には、最大 2 つのレジスタ入力があります。デコード ステージでは、これらの 2 つのレジスタのインデックスが命令内で識別され、インデックスがアドレスとしてレジスタ メモリに提示されます。したがって、指定された 2 つのレジスタはレジスタファイルから読み取られます。MIPS 設計では、レジスタ ファイルには 32 個のエントリがありました。

レジスタ ファイルが読み取られると同時に、このステージの命令発行ロジックは、パイプラインがこのステージの命令を実行する準備ができているかどうかを判断します。準備ができていない場合、発行ロジックは命令フェッチ ステージとデコード ステージの両方を停止させます。停止サイクルでは、入力フリップフロップは新しいビットを受け入れないため、そのサイクル中に新しい計算は行われません。

デコードされた命令が分岐またはジャンプの場合、レジスタ ファイルの読み取りと並行して、分岐またはジャンプのターゲット アドレスが計算されます。分岐条件は次のサイクル (レジスタ ファイルの読み取り後) で計算され、分岐が行われるか、命令がジャンプである場合は、計算された増分 PC ではなく、最初のステージの PC に分岐ターゲットが割り当てられます。一部のアーキテクチャでは、実行ステージで算術論理ユニット(ALU) が使用されていましたが、その代償として命令スループットがわずかに低下しました。

デコード ステージには、かなりのハードウェアが必要になりました。MIPS では、2 つのレジスタが等しい場合に分岐する可能性があるため、レジスタ ファイルの読み取り後に 32 ビット幅の AND ツリーが連続して実行され、このステージを通過するクリティカル パスが非常に長くなります (つまり、1 秒あたりのサイクル数が少なくなります)。また、分岐先の計算には通常、16 ビットの加算と 14 ビットの増分が必要です。デコード ステージで分岐を解決することで、分岐予測ミスのペナルティを 1 サイクルのみに抑えることができました。分岐は頻繁に実行されるため (したがって予測ミスになる)、このペナルティを低く抑えることが非常に重要でした。

実行ステージでは、実際の計算が行われます。通常、このステージは ALU とビット シフターで構成されます。また、複数サイクルの乗算器と除算器が含まれる場合もあります。

ALU はブール演算 (and、or、not、nand、nor、xor、xnor) の実行と、整数の加算および減算の実行を担当します。結果の他に、ALU は通常、結果が 0 であったかどうか、オーバーフローが発生したかどうかなどのステータス ビットを提供します。

ビット シフタはシフトと回転を担当します。

これらの単純な RISC マシン上の命令は、操作の種類に応じて 3 つのレイテンシ クラスに分類できます。

• レジスタ間演算 (シングルサイクル レイテンシ): 加算、減算、比較、および論理演算。実行ステージでは、2 つの引数が単純な ALU に送られ、実行ステージの終了までに結果が生成されます。
• メモリ参照 (2 サイクルのレイテンシ)。すべてメモリからロードされます。実行ステージ中に、ALU は 2 つの引数 (レジスタと定数オフセット) を追加して、サイクルの終わりまでに仮想アドレスを生成します。
• マルチサイクル命令(多くのサイクル レイテンシ)。整数乗算と除算、およびすべての浮動小数点演算。実行ステージでは、これらの演算のオペランドがマルチサイクル乗算/除算ユニットに送られます。乗算/除算ユニットが動作している間、パイプラインの残りの部分は自由に実行を継続できます。ライトバック ステージと発行ロジックの複雑化を回避するために、マルチサイクル命令は結果を別のレジスタ セットに書き込みます。

データ メモリにアクセスする必要がある場合は、この段階で実行されます。

このステージでは、1 サイクル レイテンシの命令は、結果が次のステージに転送されるだけです。この転送により、1 サイクル命令と 2 サイクル命令の両方が常にパイプラインの同じステージで結果を書き込むため、レジスタ ファイルへの書き込みポートは 1 つだけ使用でき、常に使用可能になります。

多数のデータ キャッシュ構成の中で最も単純な直接マップおよび仮想タグ付きデータ キャッシュでは、2 つのSRAMが使用されます。1 つはデータを格納し、もう 1 つはタグを格納します。

このステージでは、シングル サイクル命令と 2 サイクル命令の両方が、その結果をレジスタ ファイルに書き込みます。2 つの異なるステージが同時にレジスタ ファイルにアクセスしていることに注意してください。デコード ステージは 2 つのソース レジスタを読み取り、同時にライトバック ステージは前の命令の宛先レジスタに書き込みます。実際のシリコンでは、これは危険となる可能性があります (危険の詳細については以下を参照)。これは、デコードで読み取られるソース レジスタの 1 つが、ライトバックで書き込まれる宛先レジスタと同じである可能性があるためです。その場合、レジスタ ファイル内の同じメモリ セルが同時に読み取りと書き込みの両方が行われます。シリコンでは、メモリ セルの多くの実装は、読み取りと書き込みが同時に行われると正しく動作しません。

ヘネシーとパターソンは、パイプライン内の命令が間違った答えを生成する状況を表すために 「ハザード」という用語を作り出した。

構造的ハザードは、2 つの命令が同時に同じリソースを使用しようとする場合に発生します。 従来の RISC パイプラインは、ハードウェアを複製することでこれらのハザードを回避しました。特に、分岐命令は ALU を使用して分岐のターゲット アドレスを計算できました。その目的でデコード ステージで ALU が使用された場合、分岐が続く ALU 命令では、両方の命令が同時に ALU を使用しようとします。この競合は、デコード ステージに専用の分岐ターゲット加算器を設計することで簡単に解決できます。

データ ハザードは、盲目的にスケジュールされた命令が、レジスタ ファイルでデータが使用可能になる前にデータを使用しようとすると発生します。

従来の RISC パイプラインでは、データ ハザードは次の 2 つの方法のいずれかで回避されます。

バイパスはオペランド転送とも呼ばれます。

CPU が次のコードを実行しているとします。

SUB r3 , r4 -> r10 ; r3 - r4 を r10 に書き込みます。AND r10 , r3 -> r11 ; r10 と r3 を r11 に書き込みます。        
       

命令フェッチおよびデコード ステージでは、最初の命令の 1 サイクル後に 2 番目の命令が送信されます。これらは、次の図に示すようにパイプラインを流れていきます。

ハザードを考慮しない単純なパイプラインでは、データ ハザードは次のように進行します。

サイクル 3 では、SUB命令が の新しい値を計算しますr10。同じサイクルで、AND操作がデコードされ、 の値がr10レジスタ ファイルからフェッチされます。ただし、SUB命令はまだその結果を に書き込んでいませんr10。この の書き戻しは通常、サイクル 5 (緑のボックス) で発生します。したがって、レジスタ ファイルから読み取られ、ALU に渡される値 (操作の実行ステージAND、赤いボックス) は不正確です。

代わりに、計算されたデータを、通常の書き戻しの前に、操作SUBの実行ステージ (つまり、図の赤い円) に戻す必要があります。この問題の解決策は、バイパス マルチプレクサのペアです。これらのマルチプレクサはデコード ステージの最後に配置され、そのフロップ出力が ALU への入力になります。各マルチプレクサは、次の中から選択します。 AND

1. レジスタファイルの読み取りポート（つまり、単純なパイプラインの場合のデコードステージの出力）：赤い矢印
2. ALUの現在のレジスタパイプライン（1ステージバイパス）：青い矢印
3. アクセス ステージの現在のレジスタ パイプライン (ロードされた値または転送された ALU 結果のいずれかで、これにより 2 つのステージがバイパスされます):紫色の矢印。この場合、データを1 サイクルだけ時間的に逆方向に渡す必要があることに注意してください。これが発生する場合は、データが準備できるまで操作を停止するためにバブルを挿入する必要があります。AND

デコード ステージ ロジックは、パイプラインの実行ステージとアクセス ステージで命令によって書き込まれたレジスタと、デコード ステージで命令によって読み取られたレジスタを比較し、マルチプレクサが最新のデータを選択するようにします。これらのバイパス マルチプレクサにより、パイプラインは ALU、マルチプレクサ、およびフリップフロップのレイテンシのみで単純な命令を実行できるようになります。マルチプレクサがなければ、レジスタ ファイルの書き込みと読み取りのレイテンシをこれらの命令のレイテンシに含める必要があります。

データは時間的に前方にのみ渡されることに注意してください。データがまだ処理されていない場合は、データを前の段階にバイパスして戻すことはできません。上記のケースでは、データは前方に渡されます ( ANDALU のレジスタの準備ができるまでには、 によってSUB既に計算されています)。

ただし、以下の指示を考慮してください。

LD adr -> r10 AND r10 、r3 -> r11       
   

アドレスから読み取られたデータは、命令adrのメモリ アクセス ステージが終わるまでデータ キャッシュに存在しませんLD。この時点で、AND命令はすでに ALU を通過しています。これを解決するには、メモリからのデータを ALU への入力に逆方向に渡す必要がありますが、これは不可能です。解決策は、AND命令を 1 サイクル遅らせることです。データ ハザードはデコード ステージで検出され、フェッチ ステージとデコード ステージは停止します。つまり、入力がフロップしないようにし、1 サイクルの間同じ状態のままにします。下流の実行、アクセス、およびライトバック ステージでは、命令LDとAND命令の間に追加のノーオペレーション命令 (NOP) が挿入されます。

この NOP は、水道管内の気泡のようにパイプライン内で浮遊し、リソースを占有しながらも有用な結果を生成しないため、パイプラインバブルと呼ばれます。データ ハザードを検出し、ハザードが解消されるまでパイプラインを停止するハードウェアは、パイプライン インターロックと呼ばれます。

ただし、データ転送ではパイプライン インターロックを使用する必要はありません。 の最初の例と の 2 番目の例SUBは、ライトバックが達成され、レジスタ ファイル内のデータが正しいため、正しいレジスタ値が のデコード ステージによってフェッチされるまで、最初のステージを 3 サイクル停止することで解決できます。これにより、プロセッサが何も処理せずに多くの時間を費やすため、パフォーマンスがかなり低下しますが、待機する転送ロジックが少なくなるため、クロック速度を上げることができます。 ANDLDANDAND

このデータ ハザードは、プログラムのマシン コードがコンパイラによって記述されている場合、非常に簡単に検出できます。スタンフォード MIPSマシンは、この場合、最初の 2 つのパイプライン ステージを検出して (より負荷の高い) ストールする回路を持つのではなく、コンパイラによって NOP 命令を追加することに頼っていました。そのため、MIPS (Microprocessor without Interlocked Pipeline Stages) という名前が付けられました。コンパイラによって追加された余分な NOP 命令によってプログラム バイナリが拡張され、命令キャッシュ ヒット率が低下することが判明しました。ストール ハードウェアは高価でしたが、命令キャッシュ ヒット率を向上させるために後の設計に再び取り入れられ、この時点で頭字語の意味はなくなりました。

制御ハザードは、条件付きおよび無条件分岐によって発生します。従来の RISC パイプラインは、デコード ステージで分岐を解決します。つまり、分岐解決の繰り返しは 2 サイクルになります。これには 3 つの影響があります。

• 分岐解決の繰り返しには、命令キャッシュの読み取り、レジスタ ファイルの読み取り、分岐条件の計算 (MIPS CPU では 32 ビットの比較が必要)、次の命令アドレス マルチプレクサなど、かなりの数の回路が介在します。
• 分岐およびジャンプ ターゲットはレジスタの読み取りと並行して計算されるため、RISC ISA には通常、レジスタ + オフセット アドレスに分岐する命令はありません。レジスタへのジャンプはサポートされています。
• 分岐が行われると、分岐の直後の命令が常に命令キャッシュからフェッチされます。この命令が無視されると、分岐が行われるたびに 1 サイクルのIPCペナルティが発生し、これは十分に大きくなります。

ブランチに関するこのパフォーマンスの問題を解決するには、次の 4 つの方法があります。

• 分岐しない予測: 分岐後の命令を常に命令キャッシュからフェッチしますが、分岐しない場合にのみ実行します。分岐しない場合は、パイプラインはいっぱいのままです。分岐する場合、命令はフラッシュされ (NOP であるかのようにマークされます)、命令を完了するための 1 サイクルの機会が失われます。
• 分岐可能性が高い: 分岐後の命令を常に命令キャッシュからフェッチしますが、分岐が行われた場合にのみ実行します。コンパイラは、このような分岐では常に分岐遅延スロットを埋めることができ、分岐が行われる頻度の方が行われない頻度よりも高いため、このような分岐の IPC ペナルティは以前の種類よりも小さくなります。
• 分岐遅延スロット: 遅延分岐の設計と分岐条件に応じて、分岐が行われた場合でも分岐命令の直後の命令を実行するかどうかが決定されます。分岐が行われた (おそらく 60%) または行われなかった (おそらく 40%) 分岐の一部に対して IPC ペナルティを課す代わりに、分岐遅延スロットは、コンパイラが分岐遅延スロットをスケジュールできなかった分岐に対して IPC ペナルティを課します。SPARC、MIPS、および MC88K の設計者は、ISA に分岐遅延スロットを設計しました。
• 分岐予測: 各命令のフェッチと並行して、命令が分岐またはジャンプであるかどうかを推測し、そうである場合はターゲットを推測します。分岐またはジャンプの後のサイクルで、推測したターゲットで命令をフェッチします。推測が間違っている場合は、間違ってフェッチされたターゲットをフラッシュします。

遅延分岐は、まずその意味が複雑であるという理由で議論を呼んでいます。遅延分岐は、次の命令の後に新しい場所へのジャンプが行われることを指定します。その次の命令は、分岐後に命令キャッシュによって必然的にロードされる命令です。

遅延分岐は、ISA 設計における短期的な選択としては不適切であると 批判されてきました^{(誰によって批判されたのでしょうか) 。}

• コンパイラは通常、分岐の後に配置する論理的に独立した命令を見つけるのが困難なため (分岐後の命令は遅延スロットと呼ばれます)、遅延スロットに NOP を挿入する必要があります。
• 1 サイクルごとに複数の命令をフェッチし、何らかの分岐予測が必要なスーパースカラープロセッサでは、遅延分岐のメリットはありません。Alpha ISAはスーパースカラー プロセッサ向けであるため、遅延分岐は省略されています。
• 遅延分岐の最も重大な欠点は、それに伴う制御の複雑さが増すことです。遅延スロット命令が例外を受け取った場合、プロセッサは次の命令ではなく、分岐で再起動する必要があります。例外には基本的に 2 つのアドレス (例外アドレスと再起動アドレス) があり、すべてのケースでこの 2 つを正しく生成して区別することが、後の設計でバグの原因となってきました。

32 ビット RISC が 2 つの大きな数値を加算する ADD 命令を処理し、その結果が 32 ビットに収まらないとします。

ほとんどのアーキテクチャで提供されている最も簡単なソリューションは、ラップ演算です。エンコード可能な最大値より大きい数値は、収まるまで最上位ビットが切り落とされます。通常の整数システムでは、3000000000+3000000000=60000000000 です。符号なし 32 ビット ラップ演算では、3000000000+3000000000=1705032704 (6000000000 mod 2^32) です。これはあまり便利ではないように思えるかもしれません。ラップ演算の最大の利点は、すべての演算で結果が明確に定義されることです。

しかし、プログラマーは、特に大きな整数をサポートする言語( LispやScheme など) でプログラミングする場合、算術演算のラップを望まないことがあります。一部のアーキテクチャー (MIPS など) では、結果をラップするのではなく、オーバーフロー時に特別な場所に分岐する特別な加算演算が定義されています。ターゲットの場所にあるソフトウェアは、問題を修正する責任があります。この特別な分岐は例外と呼ばれます。例外は、ターゲット アドレスが命令自体によって指定されず、分岐の決定が命令の結果に依存するという点で、通常の分岐とは異なります。

従来の RISC マシンにおけるソフトウェアから認識できる最も一般的な例外は、TLB ミスです。

例外は分岐やジャンプとは異なります。これらの他の制御フローの変更はデコード ステージで解決されるからです。例外はライトバック ステージで解決されます。例外が検出されると、後続の命令 (パイプラインの前のほう) は無効としてマークされ、パイプの末尾に流れるときにその結果は破棄されます。プログラム カウンターは特別な例外ハンドラーのアドレスに設定され、特別なレジスタに例外の場所と原因が書き込まれます。

ソフトウェアが簡単に (そして速く) 問題を修正してプログラムを再起動できるようにするには、CPU は正確な例外を取得する必要があります。正確な例外とは、例外命令までのすべての命令が実行され、例外命令とそれ以降のすべての命令が実行されていないことを意味します。

正確な例外を処理するには、CPU はソフトウェアで見える状態への変更をプログラム順にコミットする必要があります。この順序どおりのコミットは、従来の RISC パイプラインでは非常に自然に行われます。ほとんどの命令は、ライトバック ステージで結果をレジスタ ファイルに書き込むため、これらの書き込みは自動的にプログラム順に行われます。ただし、ストア命令は、アクセス ステージで結果をストア データ キューに書き込みます。ストア命令が例外を処理すると、ストア データ キューのエントリは無効になり、後でキャッシュ データ SRAM に書き込まれなくなります。

場合によっては、データ キャッシュまたは命令キャッシュに必要なデータまたは命令が含まれていないことがあります。このような場合、CPU はキャッシュに必要なデータが入るまで操作を一時停止し、その後実行を再開する必要があります。キャッシュに必要なデータを入れる (および削除されたキャッシュ ラインをメモリに書き戻す) という問題は、パイプライン構成に固有のものではないため、ここでは説明しません。

サスペンド/再開の問題に対処するには 2 つの戦略があります。1 つ目は、グローバル ストール信号です。この信号がアクティブになると、通常は各ステージの開始時にフリップフロップへのクロックをゲートオフすることで、命令がパイプラインを進むのを防ぎます。この戦略の欠点は、フリップフロップの数が多いため、グローバル ストール信号の伝播に時間がかかることです。マシンは通常、ストールを必要とする条件を識別するのと同じサイクルでストールする必要があるため、ストール信号は速度を制限するクリティカル パスになります。

サスペンド/レジュームを処理するもう 1 つの戦略は、例外ロジックを再利用することです。マシンは問題のある命令に対して例外を取得し、それ以降のすべての命令は無効になります。キャッシュに必要なデータが満たされると、キャッシュ ミスの原因となった命令が再開されます。データ キャッシュ ミスの処理を迅速化するために、データ キャッシュが満たされてから 1 サイクル後にそのアクセス サイクルが発生するように命令を再開できます。

• プロセッサパフォーマンスの鉄則