CPU パイプラインの可視化（2024 年）

配列パイプラインの可視化：命令デコード、ハザード検出、転送、HDU と FU、分岐

これは私の「分岐予測」シリーズの一部です。

CPU パイプラインを可視化する なぜ分岐予測は実際のデータが必要なのか LLDB をハッキングして分岐予測を評価する（近日公開予定）

CPU パイプラインについて私が学んだことを共有したいと思います。Dan Luu 氏による分岐予測に関する記述のおかげで、概念的な仕組みにはおおまかに気づいていたのですが、Rodrigo Copetti 氏の「PlayStation MIPS アーキテクチャ分析」を読む際には、分岐遅延スロット（branch delay slots）とその進化が分岐予測へと繋がるという内容に触れ、詳しく掘り下げたいとの思いが湧き上がりました。CPU パイプラインには数多く存在する繊細かつ魅力的な詳細事項に出会ったため、それらもぜひ共有したいと考えました。より詳細については、「Computer Organization and Design」の第 4 章を推奨します。本稿では、CPU の配列（または「アセンブリーライン型」）モデルについてはご存知かと思いますが、いくつかの下位レベルの詳細についてはまだあいまいである方を想定しています。また、5 セグメント MIPS パイプラインについて大まかな概要があることも役立つでしょう（これは簡潔な上位レイヤーのまとめです）。本稿で使用されるモデル CPU は 32 ビット MIPS です。

配列のパイプラインを可視化する

まずは、パイプラインを持たない基本的な CPU モデル（すなわちサイクル単一型 CPU デザイン）から見ていきましょう。

このアプローチのボトルネックは、CPU のどの構成要素も一度にしか活動せず、他のものはすべて不活性である点にあります。パイプライン化された CPU は、単一の命令が完全に終了するのを待つのではなく、複数の命令を順次各ステージに通すことでこれらの空き時間を埋め尽くします。

これは非常に直感的です：まるで複数の人が働くアセンブリーラインのようです。しかし、すでにいくつか繊細な問題が存在し、それらを解決する必要があります。

命令デコード

命令デコードは、他のステージが使用するフィール（フィールド）を供給することで、全体のパイプラインを統括します。簡略化された例で見ていきましょう。命令が

add $t1, $s2, $s3

と仮定してください。IF（フェッチ）ステージでは命令を Fetch し、それを ID（デコード）ステージのレジスタに格納します。これにより、ID レジスタには残りのすべてのステージが使用するフィールが格納されます。

• pc: 0x014b4820 -> フィールド op rs rt rd shamt funct バイナリ 000000 01010 01011 01001 00000 100000 # add $s2 $s3 $t1
• EX は、ALU 演算および入力に op、rs、rt を使用します。
• MEM（lw および sw の場合）は rt を使用します。
• WB はレジスタ rd に書き込みます。

パイプライン化された状態では問題が発生します。例えば、前述の可視化図のサイクル 3 では、

add

が EX ステージへ移動し、

sub

が ID ステージへ移動しています。しかし、WB ステージは

add

命令の rd フィールドを知る必要があります。かつてこのフィールは安全に ID レジスタに格納されていましたが、sub がそれを上書きしてしまったのです。解決策として、各パイプラインステージの間には、ID ステージ（および他のステージ）からフィールを運ぶレジスタを設置します。

こうすることで、add が WB に到達する時点では rd フィールドを持ち、正しいレジスタに書き込むことが可能になります。さらに、EX や MEM から得られる実際の値も MEM/WB レジスタに格納されます。

ハザード検出

ID ステージからのフィールメタデータは、各ステージで基本的な動作（例えば、レジスタへの書き戻し）を可能にするために必要ですが、同時にこのフィールはデータハザードの解決にも重要です。以下のような例から始めましょう：

sub

は

add

の出力に依存しています。これを「データハザード」と呼びます。構造的には CPU が進めることは可能でも、その結果は正しくありません。ID ステージにある命令の入力が、下流にあるどの命令の出力レジスタとも一致するかをチェックする手段が必要です。フィールメタデータが各ステージレジスタへ伝搬されているため、必要な情報はすべて入手できています！欠けているのはこれを計算するユニットです：

• ID/EXE.rs == EX/MEM.rd || ID/EXE.rt == EX/MEM.rd || ID/MEM.rs == MEM/WB.rd || ID/MEM.rt == MEM/WB.rd

これがハザード検出ユニット（HDU）です。このユニットはハザードを検出すると同時に、ハザードが解消されるまで進捗を停止します。

このハザード検出ロジックは「R 型」命令（

add

や

and

などレジスタに書き込む命令）には適用されますが、すべての命令がレジスタに書き込むわけではありません（

sw

の場合など）。完全な実装のためには、特に

lw

および

sw

を関与するデータハザードに関するいくつかの追加条件をチェックする必要があります。

太い線は HDU への入力を示しており、ここでハザードを検出します。点線は制御シグナルであり、PC と IF を停止し、ID/EX レジスタに nop（無操作命令）を書き込むものです。この nop は各ステージを通り抜けていき、最終的にハザード比較ロジックを False にさせます。これにより PC および IF ステージへのストールが解除され、sub 命令の継続を許すシグナルも取り除かれます。

なぜストールを「バブル（泡）」とも呼ぶのか？ それは一度現れるとパイプラインを流れ、最終的に出口から外に出るからです。潜水員が水中で空気を放出すると同様に、バブルは表面へ上昇します。このたとえをさらに拡張すると、潜水員は状況に応じて複数のバブルを放出することもできます（HDU のように）。前述の例では 2 つのバブルが放出されました。

転送（Forwarding）

ハザード検出ロジックを用いて、レジスタメタデータを通じて特定の種類のハザードを解決する別の方法もあります。ストールではなく、「中間結果」を次の命令へ「転送（forward）」できます。

付記：データがパイプライン内を後方へ移動しているにもかかわらず「転送」と呼ばれるのは、マルチクロックのパイプライン図において、依存関係を時間的に前方に書き込むことができるからです。詳しくは「Computer Organization and Design 4th Ed.」の 364 ページをご参照ください。

add と sub の例を続けてみましょう。ステージ間のレジスタはメタデータだけでなく、前段の結果も保持しています。ハザードを検出すれば、命令がレジスタに書き戻し、パイプラインから退出するのを待つのではなく、その結果を即座に使用できます。

転送ユニット（FU）は同じ比較ロジックを使用します。ハザードを検出すると、制御サブユニットは入力レジスタデータ（本例では r3）代わりに EX の結果を使用することを確認します。この特定の場合においては、ハザードはゼロのストールで解決されます！（完全な図については「Computer Organization and Design 4th Ed.」の図 4.60 をご参照ください。これは少し簡略化されています）。

HDU と FU

FU の図では、HDU に使用していた ID/EX の入力レジスタと MEM/WB の出力レジスタとの比較を加えていません。その理由は、転送単独ではこの問題を解決できないからです。以下のような例を見てみましょう：

• lw r1, 0(r2)

• add r3, r1, r4

HDU はこの状況を問題なく処理します。実際には、以前に stall してレジスタ r1 に WB が書き込むのを待つ例と同じで、これにより 2 つのバブルが発生します。しかし、ここでは機会があります：r1 に書き戻される前に、中間結果は MEM/WB レジスタで利用可能です。したがって、add の EX ステージへの転送が可能になります。これを行うには、FU と HBU（ハザードブランチユニット）が連携して 1 つのバブルを節約する必要があります。

HDU と FU がどのように協力して動作するかすべての詳細に言及するつもりはありません。それはここに示したレイアウトとは少し異なるからです。また、この例でも触れましたが、lw および sw 命令に関連するニュアンスには注意が必要です。

分岐（Branching）

これまで築き上げてきたツール（レジスタメタデータ、転送、ストール）は、分岐（制御ハザード）に対処する助けになります。最もシンプルな手法から始めましょう。

分岐を「非実行」と予測する

「分岐を非実行と予測」のロジックと実装は、データハザードを解決するための転送と非常に類似しています。転送では、1 つの命令の結果（EX または MEM）が次の命令の EX ステージへの入力として使用されます。分岐予測では、EX ステージで分岐条件を計算し、その結果を EX/MEM レジスタに格納します。分岐が実行された場合、私たちはこの事実を前段すべてのステージへ「転送」します。この情報は入力として使用されるのではなく、命令を nop に変換し、パイプラインを通じてバブル化させます。さらに、分岐対象アドレスはステージ間レジスタに格納されており、PC の更新に使用されます（これは ID ステージの BTAC（分岐対象アドレス計算）ユニットにおいて、分岐オフセット指示語引数と分岐時の PC から計算されます）。以下の図にはこの流れが示されています。

分岐遅延スロット

このスキームに対する単純な改良は、より少ないハードウェアを使用します。ID、IF、EX を nop に変換する代わりに、分岐の直後に実行される命令は無条件に実行されると仮定します。分岐直後の位置を「分岐遅延スロット」と呼び、コンパイラまたはプログラマがこれを埋める責任があります。利点は、3 つのバbubble ではなく、2 つしか発生しないことです。最後の例において分岐の直前に命令を追加すると仮定しましょう。コンパイラは

add

が分岐の遅延スロットにあるように命令を再編成する可能性があります。

assembly         add t0, t1, t2 \   beq r1, r2, br         beq r1, r2, br  /   add t0, t1, t2         add r7, r1, r4      add r7, r1, r4         lw  r8, 0(t6)       lw  r8, 0(t6)     

これでパイプラインは依然として「分岐非実行」と予測できますが、

add t0

は引き続き有効な作業を行います。残念ながら、コンパイラが分岐遅延スロットを埋める命令を見つけられない場合があり、nop を挿入せざるを得ない場合があります。以下のような例を考えてみてください（配列を超循環してゼロを見つけるまで反復しています）。

assembly         loop:             lw   t0, 0(s0)             beq  t0, 0, done             nop             add  s0, s0, 4             j    loop         done:     

add

を遅延スロットに入れられないのは、もし分岐が実行された場合、s0 を誤って修正することになるためです。その場合、s0 は配列における最初のゼロのポインタを指さしなくなしまいます。また、lw をスロットに下方移動することもできません。なぜなら、分岐は t0 の値に依存しており、lw が最初に実行される必要があるからです。おそらく十分に賢いコンパイラは解決策を模索できるかもしれませんが（例えば、遅延スロットに add を入れても大丈夫で、後で 4 を引いてゼロのポインタを取得すればよい）、コンパイラが考慮しなければならない状況です。

動的な分岐予測

この節では、動的な分岐予測の解決について簡潔に触れたいだけです。Dan Luu 氏の記述には予測自体の詳細が多く含まれているため（特に 2 ビット飽和カウンターセクションを推奨します）。彼らの説明は私に多くのことを明確にさせました。幸運にも、動的な分岐の解決ロジックは、分岐非実行と予測する際の解決ロジックとほとんど同じです。単純な分岐予測の場合、EX ステージの分岐結果と「分岐は実行されなかった」という仮定を比較します。動的な分岐予測では、EX/MEM レジスタ内の実際の分岐結果と、予測値を比較する必要があります。つまり、IF ステージで分岐予測を取得する際、その予測は IF/ID レジスタに格納され、下流のステージ間レジスタへ伝搬される必要があります。ここではインタラクティブな可視化を含めることはせず、最後の例と同じです。しかし、分岐予測と解決の概略的なフローを示す大まかな図を用意しました：

BRU（分岐解決ユニット）

• 実際の分岐結果と予測を比較します。
• 予測が誤った場合、パイプラインをフラッシュします。
• BPU（分岐予測ユニット）に予測を更新するシグナルを送ります（予測スキームにより、予測が正しいか間違っているかを BPU に通知します）。
• ミスプレディクションが発生した場合は、PC を次のアドレス（分岐の直後）または BTAC で計算された分岐対象アドレスに設定します（分岐が実行されたかどうかによる）。

BTAC（分岐対象アドレス計算）

• 分岐の PC とオフセットから分岐対象アドレスを計算します。
• 「分岐非実行と予測」した場合に使用するよう、予測誤りがあった場合でも分岐対象アドレスを ID/EX レジスタに格納します。

BPU（分岐予測ユニット、または Branch Target Buffer (BTB)）

• 分岐の PC の最後のビットに基づいて分岐予測を検索します。
• IF/ID レジスタに予測を書き込みます。
• 最後に分岐が実行されたかどうかを記録します。

結論

CPU パイプラインへの興味は、Dan Luu 氏の分岐予測に関する記述や Rodrigo Copetti 氏の PlayStation アーキテクチャ分析といった高レベルな記事を通じて始まりました。概念的にはアイデアが魅力的であり、それがすべてがどのように機能するかを詳しく知りたいという欲求を生みました。最も印象的だったのは、レジスタメタデータ、ストール、転送といった単純なコアメカニズムが、いかにして組み合わされ、再構成されて、ますます複雑化する問題を解決しているかです。