現代CPUに使われるスーパースカラ構造とOut-of-Order (OoO) 実行について 見ていきましょう。

命令レベル並列性

ここまで見てきた内容では、CPUは命令を直列に実行してきました。パイプライン化に よって1サイクルで複数の命令を処理できるようにはなりましたが、同時に複数の 命令が一度に実行されるわけではありませんでした。1つずつ入力され、1つずつ 実行されていたのです。

これを改善するための方法が**命令レベル並列性(Instruction-Level Parallelism, ILP)**です。ILPとは、プログラムの中から同時に実行できる命令を見つけ出して 並列に処理することを指します。プログラマから見ると命令は1行ずつ実行されて いるように見えますが、CPU内部では互いに依存関係のない命令を同時に処理する ことで性能を高めています。

並列化にはILP以外の層もあります。複数のスレッドを同時に実行する スレッドレベル並列性(Thread-Level Parallelism, TLP) はマルチコアやSMTが 活用し、同じ演算を複数のデータに同時に適用する データレベル並列性(Data-Level Parallelism, DLP) はSIMDやGPUが代表的です。 TLPとDLPがプログラマによる明示的なコード記述を要求するのに対し、ILPは ハードウェアとコンパイラが自動で引き出すため、プログラマにはほぼ透過的で あるという点が特徴です。

Processing ElementとAverage ILP

ILPが実際にどれだけ可能なのかを話すためには、2つの概念が必要です。

まずProcessing Element(PE) とは、実際に演算を行う最小単位のハードウェア のことです。ILPの文脈では、ALUやFPUのようなfunctional unit1つだと考えれば よいでしょう。1サイクルに同時に処理できる命令数は、結局PEの数に縛られます。

次にAverage ILP は、リソースが無限であると仮定したときに、データ依存性 だけでプログラムをもっとも早く実行した場合、サイクルあたり平均何個の命令 が同時に実行されるかを示す値です。

$$ \text{Average ILP} = \frac{\text{全体の命令数}}{\text{critical pathの長さ(サイクル)}} $$

この値はリソース制約を考慮しない理想的な上限であり、プログラムが本質的 に持つ並列性を意味します。実機で測定されるIPCとは別の概念です。

簡単な例として、次の5つの命令を見てみましょう。

I1: r1 = a + b
I2: r2 = c + d
I3: r3 = r1 * r2     ; I1, I2に依存
I4: r4 = e + f
I5: r5 = r3 + r4     ; I3, I4に依存

データ依存性グラフに沿ってリソースが無限と仮定してスケジューリングすると、 次のようになります。

全体の命令数は5個で、critical pathはI1 → I3 → I5の3サイクルです。 したがってこのコード片のAverage ILPは $5 / 3 \approx 1.67$ になります。 つまり理想的にもサイクルあたり平均1.67個しか命令を引き出せないコードという ことです。

もしPEが1つしかない機械でこのコードを走らせれば5サイクルかかってILPを まったく活用できず、逆にPEが3つ以上あれば依存性が許す限界である3サイクル まで短縮されます。PEの数がILPをどれだけ引き出せるかの天井になるわけ です。

スーパースカラ

スーパースカラ(Superscalar) とは、1サイクルに複数の命令を同時に発行 (issue)して実行できるように作られたCPU構造です。前節で見たようにILPを 実際に引き出すにはPEが複数必要ですが、スーパースカラCPUはALU・FPU・ ロード/ストアユニットなどのfunctional unitを複数組備え、毎サイクルごとに 依存性のない複数の命令を選んで各PEに分配します。

このとき、1サイクルに発行できる命令の最大数をissue widthと呼び、 issue widthが$N$の機械を通常「$N$-wayスーパースカラ」と呼びます。たとえば 4-wayスーパースカラは毎サイクル最大4個の命令を同時に発行できます。

スーパーパイプラインとの比較

スループットを増やす別のアプローチとしてスーパーパイプライン (Superpipelined) 機械があります。スーパーパイプラインはパイプラインの 各ステージをさらに細かい単位に刻み、ステージ数を増やし、その分クロック 周波数を上げる方式です。1サイクルに発行する命令数は依然として1個なので Average ILP自体を引き上げることはできませんが、サイクルが短くなったおかげで 単位時間あたりにより多くの命令を処理できるようになります。

2つの方式の違いを整理すると次のようになります。

同じ8個の命令を3種類の機械で実行すると仮定してみましょう。命令同士に まったく依存性がないものとし、基本パイプラインは5ステージ(IF, ID, EX, MEM, WB)とします。

I1, I2, I3, I4, I5, I6, I7, I8   ; すべて独立

(1) 通常のスカラパイプライン — 1サイクルに1命令だけ発行。最初の命令 が5サイクル後に終わり、その後は毎サイクル1個ずつ完了します。8個の命令 すべてを終えるのに $5 + (8 - 1) = 12$ サイクルかかります。IPCは $8/12 \approx 0.67$。

(2) スーパーパイプライン(10ステージ、クロック2倍) — ステージを2倍に 細かく刻んでクロックが2倍になります。1サイクルに1命令だけ発行しますが、 サイクル自体が短くなったわけです。最初の命令が10(短い)サイクル後に完了し、 その後は毎短サイクル1個ずつ完了して $10 + (8 - 1) = 17$ 短サイクルかかります。 元のサイクル基準に換算すると $17 / 2 = 8.5$ サイクルで、スカラパイプラインより 約1.4倍速いです。

(3) 2-wayスーパースカラ(5ステージ、PE 2組) — 1サイクルに命令を2個 同時に発行します。サイクル1にI1・I2がIFに入り、サイクル2にI3・I4が入る 形です。最初の2命令が5サイクル後に一緒に終わり、その後は毎サイクル2個 ずつ完了して合計 $5 + (8/2 - 1) = 8$ サイクルかかります。IPCは $8/8 = 1.0$ で、2-wayの理想的な限界である2.0には立ち上がりのせいで 届きませんが、十分に大きな命令ストリームでは2に近づいていきます。

ここから2つのことが観察できます。第一に、スーパーパイプラインはクロックを 引き上げて時間軸でスループットを増やすのに対し、スーパースカラはPEを 増やして空間軸でスループットを増やします。第二に、両方の方式は 互いに排他的ではなく、実際の現代CPUは深いパイプラインの上に広い スーパースカラ発行を組み合わせて、両者の利点を同時に享受しています。

In-Orderパイプラインの限界

ただし上の例は命令同士にまったく依存性がないという前提の話でした。実際の コードにはデータ依存性や分岐、メモリアクセス遅延が混ざっており、このとき 命令をプログラム順に発行するin-orderパイプラインは2つの大きな問題に ぶつかります。

1. 機械の並列性を上げるほど利用率が急激に落ちる

In-orderパイプラインは命令をプログラム順にしか発行できないため、前の命令が 止まるとその後ろの命令も依存性とは無関係に一緒に止まらなければなりません。 issue widthを上げるほど、この「1つの命令のstallが1サイクル全体を空ける」 損失はどんどん大きくなります。

次のコードを見てみましょう。

I1: r1 = load [r10]   ; キャッシュミス、データが4サイクル後に到着
I2: r2 = r1 + 1       ; I1に依存
I3: r3 = r5 + r6      ; 独立
I4: r4 = r7 + r8      ; 独立
I5: r5 = r9 + r11     ; 独立
I6: r6 = r12 + r13    ; 独立

このコードを2-way in-orderスーパースカラで実行すると、次のように進みます。

合計7サイクルで6個の命令、同時に処理できたスロットは $7 \times 2 = 14$ 個 あったのに、実際に埋まったのは6個です。利用率は約43%。サイクル2〜4 のstallの間、I3・I4・I5はすでに準備ができていたにもかかわらず、in-orderの 規則のせいで入れなかったわけです。

今度は同じコードを4-way in-orderスーパースカラに載せてみましょう。

合計6サイクル、スロットは $6 \times 4 = 24$ 個ですが埋まったのは6個で 利用率25%。issue widthを2倍にしたのに全体の時間は7 → 6サイクルと1サイクル しか縮まらず、大部分のスロットが空いてしまいました。機械の並列性を上げれば 上げるほどstallによる損失はwidthに比例して大きくなるので、一定の地点を 過ぎると追加されたPEがほとんど仕事をしないのがin-order構造の本質的な 限界です。

2. Forwardingではこの問題を解決できない

以前に見たパイプラインハザードはフォワーディング(forwarding) でかなりの 部分を解決できました。EX段階で計算された結果をWBまで待たずにそのまま次の 命令のEX入力へ流し込む方式ですね。しかしフォワーディングが効くのは 結果がすでに計算されている場合に限ります。

上の例のI1 → I2の依存を見ると、I1の結果はキャッシュミスのせいで4サイクル 後にメモリから届きます。フォワーディング経路がいくら整備されていても 存在しないデータを前倒しで流すことはできません。 つまりフォワーディング は「結果の生成 → 使用」の間のパイプライン遅延は減らしてくれますが、 「データがまだない」ことによる本質的な待ち時間自体は減らしてくれません。 キャッシュミス、浮動小数点の除算、長い乗算のような多サイクル演算の後ろに 依存命令が来ると、in-orderパイプラインはただ待つしかありません。

Out-of-Order Execution

結局、in-order構造でissue widthを増やすのは収穫逓減にすぐ突き当たり、 フォワーディングのような従来の技法では防げないという結論に至ります。 それならば、前の命令がstallしている間に、後ろの命令を先に実行すれば どうでしょうか?この発想から出発したものが、まさに非順序実行 (Out-of-Order Execution, OoO) です。

OoOは名前のとおり、命令をプログラムに書かれた順序どおりに実行するのでは なく、準備ができたものから先に実行する方式です。核心となる原則は次のよう にまとめられます。

• In-order fetch / decode: 命令を取ってきて解釈する段階は依然として プログラム順に従います。分岐予測や依存性追跡のためには、元の順序を 知っておく必要があるからです。
• Out-of-order execute: デコードされた命令は一種の待合室に積まれ、 自分が必要とする入力値(被演算子)がすべて準備できた命令から、利用可能な PEに発行されます。プログラム順は無視されます。
• In-order commit: 実行が終わっても結果をただちにアーキテクチャ状態 (レジスタファイル、メモリ)に反映させず、元のプログラム順に順番に コミットします。こうすることで分岐予測ミスや例外(exception)が発生した ときに、まるでin-orderで実行したかのようにきれいに巻き戻せます。

この「in-orderで取り込み、OoOで実行し、再びin-orderで終える」構造のおかげで、 プログラマは依然として命令が1行ずつ順番に実行されているように見えながら、 CPU内部ではILPを最大限に引き出すことができるのです。

このようなOoOを実際に実装するには、解決すべき問題がいくつかあります。

1. 同じレジスタ名を再利用することで生じる偽の依存性が命令順を縛って いるが、これをどのように解くのか? → Register Renaming
2. ある命令の被演算子が準備できたかを追跡し、準備できた命令を適切なPE に分配するメカニズムをどう作るのか? → Reservation Station / Issue Queue
3. 順序がバラバラに実行された結果を、元のプログラム順に並べ直して コミットするには何が必要か? → Reorder Buffer (ROB)

それでは、この3つを順に見ていきましょう。

Register Renaming

命令の順序を変えようとすると、データ依存性が足を引っ張ります。依存性には 3種類あります。

• RAW (Read After Write, true dependency): パイプライン化でも見た 依存性です。前の命令が書いた値を後ろの命令が読む。これは本物のデータ フローに由来する依存性なので、どんな方法でも取り除くことはできません。
• WAR (Write After Read, anti-dependency): 前の命令が読むレジスタを 後ろの命令が上書きする。順序が入れ替わると前の命令が誤った値を読むこと になります。
• WAW (Write After Write, output dependency): 2つの命令が同じレジスタ に順番に書き込む。順序が入れ替わると最終値が変わってしまいます。

WARとWAWは実は同じ名前のレジスタを再利用することで生じる偽の依存性です。 実際にデータが流れているわけではなく、ただコンパイラが使える アーキテクチャレジスタ(x86のRAX、RISC-Vのx1〜x31など)の数が限られている ために同じ名前を使い回した結果にすぎません。もし名前だけでも別にできれば、 この偽の依存性は消えてなくなります。

Register Renamingはまさにこの仕事をします。CPU内部にアーキテクチャ レジスタよりもずっと多い物理レジスタ(physical register) を持ち、命令が あるアーキテクチャレジスタに書き込むたびに、空いている物理レジスタを1つ 新しく割り当てます。そしてその後の命令が同じアーキテクチャレジスタを読むと、 もっとも最近にマッピングされた物理レジスタから値を読み取ります。結果として 同じ名前を使う命令同士が別々の物理レジスタを見るようになり、WAR・WAWは 消えてRAWだけが残ります。

次のコードを見てみましょう。

I1: r1 = r2 + r3
I2: r4 = r1 * 2       ; I1にRAW依存
I3: r1 = r5 + r6      ; I1とWAW、I2とWAR
I4: r7 = r1 - r8      ; I3にRAW依存

I3はI1・I2とデータフロー上まったく関係がありません。たまたまr1という 名前を再利用しているだけです。しかしin-orderで見ると、I3はI1・I2が終わる まで待たなければなりません。I1がキャッシュミスなどでstallすればI3・I4まで 一緒に縛られて止まります。

それでは物理レジスタp10, p11, p12, ...を割り当てながらリネーミングを 適用してみましょう。初期マッピングをr1→p1, r2→p2, ..., r8→p8とすると:

リネーミング後の依存性グラフをもう一度描いてみましょう。

• I1(p10) ← I2(p11がp10を読む): RAW
• I3(p12) ← I4(p13がp12を読む): RAW
• I1とI3はもう同じレジスタに書き込まない → WAWが消失
• I2とI3の間の偽のWARも消失

つまり命令の流れが2つの独立した鎖 (I1 → I2) と (I3 → I4) にきれいに 分かれます。I1がstallに陥ってもI3・I4は自由に先に実行でき、2-way スーパースカラならば2つの鎖を同時に進めてI1の遅延を隠すこともできます。

リネーミング前後のcritical pathの長さを比べると効果は明らかです。元の コードはI1 → I2 → I3 → I4に縛られて4サイクルが必要ですが(偽の依存性 のせい)、リネーミング後はI1 → I2とI3 → I4が並列なので2サイクルで 十分です。Average ILPが4/4 = 1.0から4/2 = 2.0へと2倍になったわけです。 偽の依存性を取り除くことで、プログラムの中に隠れていたILPが露わになった のです。

Reservation Station (Issue Queue)

リネーミングで偽の依存性は取り除きましたが、RAW依存性はまだ残っています。 ある命令は自分の入力値がまだ計算されていないのですぐには実行できず、ある 命令はすぐに実行できます。毎サイクル**「今誰が実行可能か」** を追跡し、 可能な命令を空いているPEへ送ってくれるメカニズムが必要です。この役割を 担う構造がReservation Station (RS)、あるいはIssue Queueです。

リネーミングを経た命令はすぐにはPEに行かず、まずRSの1つの枠(エントリ)に 入って待機します。各エントリはおよそ次のような情報を持ちます。

リネーミング直後、すでにレジスタファイルに値のある被演算子はready=1で 埋められ、まだ誰かが計算中の被演算子はready=0のまま入ってきます。そして 毎サイクル、RSは2つの動作を同時に行います。

1. Wakeup: あるPEが結果の計算を終えると、その結果はCDB(Common Data Bus) という共用バスを通じてRSのすべてのエントリに同時にブロード キャストされます。自分が待っていた物理レジスタ番号と一致する エントリは、その被演算子を受け取ってreadyを1に変えます。
2. Select: 2つの被演算子が両方とも準備できた(ready1 = ready2 = 1) エントリの中から、利用可能なPEの数だけ選んで発行します。選ばれた エントリはRSから抜けます。

この2つの動作が毎サイクル繰り返されることで、命令たちはプログラム順と 関係なく、準備ができたものから順に実行されていきます。

Reorder Buffer (ROB)

RSのおかげで命令たちがバラバラの順序で実行できるようになりました。 ところがこのまま結果をそのままレジスタファイルやメモリに書き込んで しまうと、大きな問題が生じます。

• 分岐予測ミス: 分岐予測が外れると、その後ろに投機的に実行された 命令の結果をすべて取り消さなければならないのですが、すでにレジスタ ファイルに書き込んでしまっていれば戻せません。
• 例外(Exception): ある命令がページフォルトや0除算などの例外を 起こしたときには、プログラマから見た時点でその命令より前のすべての 命令は反映されており、それ以降のすべての命令は反映されていない状態 でなければなりません。前の記事で説明したとおり、これをprecise exceptionと呼びます。

この2つの要件を満たすためには、たとえ実行はOoOで行ったとしても、結果を アーキテクチャ状態に反映させる段階だけは再びプログラム順に行う必要が あります。この役割を担う構造がReorder Buffer (ROB) です。

ROBは名前のとおり循環キュー(circular queue)型のバッファで、dispatch段階で 命令がプログラム順に1つずつ席を取っていきます。各エントリはおよそ次の ようなものを収めます。

命令の一生は次のように進みます。

1. Dispatch (in-order): デコード後、ROBの尾に席を取り、同時にRSにも エントリを作ります。
2. Execute (out-of-order): RSが準備できた命令をPEに送って実行します。
3. Writeback: 実行が終わると結果を物理レジスタに書き、対応するROB エントリのdoneを1にマークします。
4. Commit / Retire (in-order): ROBの先頭(head) にあるエントリが done = 1になると、その命令を「公式に完了」させます。つまり論理 レジスタのマッピングを更新して外部からもその結果が見えるようにし、 storeであればメモリに実際に値を書き込みます。そしてROBの先頭が次の 枠へ進みます。

もし4番目の段階でエントリに例外マークが付いていたら、ROBはその エントリから後ろのすべてのエントリをまとめて破棄し、RSも空にします。 分岐予測ミスも同じ方法で処理されます。まだcommitされていない命令は アーキテクチャ状態に何の影響も与えていないので、このように捨てても 安全です。

OoOでメモリ遅延を隠す

ここまで見てきたOoOの効果は主にALU命令間の短いstallを隠すことに焦点が ありましたが、実際にOoOが実機で得る最大の利益はメモリアクセス遅延を 隠すことです。

現代CPUのクロックは速いのにDRAMはそれほど速くなっておらず、1回のキャッシュ ミスのコストは凄まじく大きいです。

OoOはこの時間をそのまま無駄にはしません。loadがメモリ応答を待っている 間に、ROBとRSに入ってきている後ろの命令のうち、そのloadに依存しないもの を先に実行してしまいます。 loadの結果が届く頃には、独立な命令はすでに かなりの部分が処理済みになっているわけです。

Load-Store Queue (LSQ)

メモリアクセス命令(load, store) を実行するには、1つ厄介な点があります。 レジスタはリネーミングで偽の依存性を消せましたが、メモリアドレスは リネーミングできません。 同じアドレスに書き込む2つのstore、同じアドレス を読むloadとstoreの間には本物のデータ依存性が存在し、しかもそのアドレスは 命令がEX段階でベースレジスタ・オフセットを加算するまで分からないのです。

この問題を扱うための専用構造がLoad-Store Queue (LSQ) です。通常は2つの 部分に分かれます。

• Store Queue (SQ): dispatch時点でstore命令が席を取ります。アドレスと 書く値が計算されるとそのエントリに埋められますが、実際のメモリには ROBがcommitしてくれるまで書き込みません。 分岐予測ミスや例外でsquash されたらSQから抜いてしまえばよいので、安全です。
• Load Queue (LQ): load命令がdispatchされるときに席を取ります。loadは 通常、メモリ遅延を隠すために早めにOoOで実行する必要があるため、ROBの commitを待たずにデータを取ってきます。

LSQが解くべき核心的な問題は2つあります。

1. Store-to-load forwarding — loadがメモリからデータを取ってくる前に、 自分より前(older)のstoreのうち、同じアドレスに書き込んだものがSQに残って いないかをまず確認しなければなりません。もしあれば、そのstoreがまだ メモリに反映されていなくても、SQから直接値を受け取ります。これが store-to-load forwardingです。これがなければloadはキャッシュにある 古い値を読んでしまうでしょう。

I1: store [r10], r1     ; r10のアドレスにr1を書き込む
I2: load  r2, [r10]     ; 同じアドレスから読む

I1がまだcommitされておらずメモリに反映されていなくても、I2はSQからI1の値を 直接受け取ってr2に入れることができます。

2. Memory disambiguation — loadは自分より前のstoreのアドレスをすべて 知るまでは、原則として実行できません。どのstoreが自分と同じアドレスに 書き込むか分からないからです。しかしそれほど保守的に振る舞うとOoOの利点 がほとんどなくなってしまいます。そこで現代CPUはloadも投機的に実行 します。「前のstoreたちは自分と違うアドレスのはずだ」と仮定して、早めに メモリから値を取ってくるわけです。

後でその前のstoreが実際にアドレスを知ったとき、すでに早めに実行された loadがLQに残っていないかを検査します。もし同じアドレスを先に読んで しまったloadがあれば、そのloadは誤った値を取ってきたことになるので、その loadとそれより後ろのすべての命令をROB squashと同じ方法で破棄して、再び 実行します。これをmemory ordering violationと呼びます。

OoOの制御投機

ここまでの説明には1つ大きな仮定が隠れていました。ROBとRSに後ろの命令が 十分に入ってきているということです。ALU命令がずらっと並んだ直線的な コードならばあまり問題にはなりませんが、実際のコードには5〜6命令に1回 ずつ分岐(branch) が挟まっています。分岐にぶつかると、次にどの命令を 取ってくるべきかが決まって初めてfetchを続けられるのですが、その決定は 通常、分岐命令がEX段階で実際に実行されるまで分かりません。

もしCPUが正直に「分岐が解決するまで待とう」と言ったらどうなるでしょう? 大きなROBも広いissue widthもすべて無用の長物となります。分岐が解決するまで の数十サイクルの間、ROBはがら空きになり、前節で見たメモリ遅延隠しの効果も 消えてしまいます。したがってOoOが意味のある動作をするためには、分岐を 待たずに乗り越える必要があります。

このために導入されるのが制御投機(Control Speculation) です。分岐の 結果を予測して、その予測が正しいと仮定してとりあえず次の命令たちを fetchし続け、ROBに入れて実行してしまうのです。予測が当たればその命令たちは 正常にcommitされ、外れればすべて破棄して正しい経路から再び始めます。

分岐予測そのものは前の記事で扱った ので、ここでは「予測器が何らかの方法でtaken/not-takenと目的地アドレスを 教えてくれる」程度にしておきます。重要なのは予測が外れたときにどう きれいに巻き戻すか、そして1サイクルに複数の命令をfetchするとき分岐を どう扱うかです。

スーパースカラfetchと分岐

スーパースカラCPUは毎サイクル1個ではなく、複数の命令を一度にfetch します。4-wayなら1サイクルに4命令、8-wayなら8命令が同時に入ってきます。 ところがこのfetchグループの中に分岐が挟まっていたら、次のサイクルのnextPC (nPC)はどう決めればいいのでしょうか?

2-way fetchを例に3つの場合を見てみましょう。

Case 1: 2つの命令が両方分岐でないか、両方not-takenと予測される

もっとも平凡な場合です。そのまま次の2命令へ続けばよいので

$$ nPC = PC + 8 $$

となります(1命令4バイトを仮定)。命令fetchは途切れることなく進みます。

Case 2: 2つのうち1つがtakenと予測された分岐

この場合、nPCはその分岐の予測された目的地アドレスになります。

$$ nPC = \text{predicted target} $$

もしtaken分岐がfetchグループの2番目の位置にあれば、最初の命令は通常 どおりパイプラインに流し、次のサイクルからtargetでfetchを続ければ大丈夫 です。

Case 3: 2つの命令が両方分岐

これがもっとも厄介です。まず最初の分岐の予測結果を見なければなりません。

• 最初の分岐がnot-takenと予測されれば、2つ目の分岐までそのまま生かし、 2つ目の分岐の予測に従ってnPCを決めます。
• 最初の分岐がtakenと予測されれば、2つ目の分岐はすでに同じサイクル にfetchされてしまった状態です。しかし最初の分岐がtakenならば2つ目の 分岐は実際には実行されてはならない命令なので、fetchはされたが パイプラインから流し出さなければなりません。nPCは最初の分岐の予測 targetになります。

この最後のシナリオはスーパースカラfetchの本質的な非効率を示しています。 issue widthが大きいほど1つのfetchグループの中に分岐が2つ以上入る確率が 高くなり、その分fetchスロットが捨てられることが多くなります。この損失 を減らすために、現代CPUは1サイクルに分岐予測を複数同時に実行できる マルチポートBTBや予測器を置いたりもしますが、本質的に「1サイクルに複数の 分岐を扱うこと」はfetch段階の複雑さを大きく上げる部分です。

予測ミスからの復旧 (Recovery)

分岐予測が外れたという事実は、その分岐命令がEXで実際に実行されて初めて 分かります。ところがその時点ではすでにROB・RSに分岐より後ろの命令が たくさん入っており、一部は実行が終わって物理レジスタに結果まで書き込んで いるかもしれません。この全てをまるで最初からなかったかのように巻き 戻さなければなりません。

幸い、先ほど見たROBのin-order commit原則のおかげで、誤った予測経路の命令 はまだcommitされていません。つまりアーキテクチャレジスタファイルや メモリには影響を与えていない状態です。したがって復旧は次の手順で行われ ます。

1. Squash: ROBから誤って予測した分岐より後ろのすべてのエントリを 破棄します。RS内の該当する命令も一緒に空けます。破棄された命令が 占有していた物理レジスタはfree listに返却されます。
2. RATの復元: Register Renamingは「どのアーキテクチャレジスタが今 どの物理レジスタにマッピングされているか」をRegister Alias Table (RAT) で追跡します。分岐予測時点のRATの状態をあらかじめスナップ ショットとして保存しておき、予測が外れたときにそのスナップショット へ戻します。こうすることで「あたかもこの分岐の直後から実行するかの ように」リネーミングを再開できます。
3. Fetch再開: PCを分岐の正しい目的地に変え、そこから新たにfetchを 始めます。

この全作業は普通、1〜2サイクルの内に終わるようにハードウェアが設計されて います。しかしその後ROBが再び埋まり、新しい命令たちがEX段階まで到達して 再びバックエンドが全開になるまでには追加で数十サイクルがかかります。 この全体のコストをbranch misprediction penaltyと呼び、深いパイプライン の現代CPUでは通常15〜20サイクル程度です。これゆえ分岐予測精度がわずか1% 落ちるだけでも性能に大きな影響を与えるわけです。

次のコードを見てみましょう。

I1: cmp r1, 0
I2: beq L1            ; 分岐、taken予測
I3: r2 = r3 + r4      ; (予測された経路の命令)
I4: r5 = r2 * r6
I5: store [r7], r5
L1: ...

OoO + 分岐予測機械で:

• Cycle 1: I1, I2がdispatch。予測器が「I2はtaken」と教えてくれるので fetchはL1側へジャンプし、この時点のRATをスナップショットとして保存 します。
• Cycle 2〜: L1以降の命令が続々とdispatchされてROBに入り、一部はRS で実行を始めます。
• Cycle 5: I2がEXで実際に実行されてみると、実はnot-takenだった ことが明らかになります。予測が外れました。
• Cycle 6: ROBからI2以降のすべてのエントリ(L1以降の命令)をsquash します。RSも空にします。RATはCycle 1で保存したスナップショットから 復元されます。
• Cycle 7〜: PCをI3に戻してfetchを再開します。I3, I4, I5が新たに dispatchされ始めます。

もしsquashがなかったらL1側の命令がそのままcommitされ、誤った結果が プログラマに見えてしまうでしょう。ROBのin-order commit原則とRAT スナップショットのおかげで、誤った予測が表に出ずに静かに吸収される のです。

P6スタイル vs R10Kスタイル

ここまで説明してきたOoO構造は抽象的なモデルでしたが、実機のCPUは大きく 2つの流れに分かれます。重要な違いは**「命令の結果値をどこに保存するか」** です。

P6スタイル (Pentium Pro, AMD K8/Opteronコア)

1995年のIntel Pentium Proで初めて登場した方式です。名前が「P6 マイクロアーキテクチャ」なのでP6スタイルと呼ばれます。AMDのK8(Opteron, Athlon 64)コアも同じ系列に属します。

この方式の核心はROBが2つの仕事を同時にこなすことです。

1. 本来のROBの役割: 命令をin-orderに並べてcommit順を保証する
2. 追加の役割: まだcommitされていない命令の結果値を直接持っている

つまりP6スタイルでは、命令が実行を終えると結果値が自分のROBエントリの 1つのフィールドに記録されます。別途の物理レジスタファイルはありません。 そしてcommitの時点になると、ROBエントリに入っていた値が 別途存在するアーキテクチャレジスタファイル(ARF) へコピーされ、ROB エントリは空けられます。

ROBエントリはだいたい次のような形をしています。

この設計では、RSの命令が被演算子を読もうとすると2箇所を見なければ なりません。すでにcommitされた値ならARFから、まだcommitされていない in-flightの値ならROBエントリから取ってきます。RATは「このアーキテクチャ レジスタの最新値がARFにあるか、それともどのROBエントリにあるか」を指し示す ポインタの役割を果たします。

長所:

• 構造が直感的で、RATの復元も比較的単純です。分岐予測ミス時には、squash されたROBエントリをそのまま捨てればよく、ARFには手を触れる必要が ないからです。
• Precise exceptionの保証がきれいです。ARFに入っている値は定義上commit されたものだけなので、ARF自体がそのまま「アーキテクチャ状態」です。

短所:

• 同じ値がROBとARFに2回存在しうるので、保存スペースが無駄になります。
• Commitのたびに ROB → ARF へ値を物理的にコピーしなければなりません。 issue widthが広くなるとcommitポートも一緒に増やさなければならず、コスト が大きいです。
• ROBエントリに値まで入るためエントリのサイズが大きくなり、大きなROBを 作るのが難しくなります。

AMD Opteron(K8)コアもこの系列です。K8は整数ROBと浮動小数点ROBを分離する など変形を加えましたが、「結果値がROBの中に住む」という本質は同じです。 K8の場合、整数コアは統合reservation stationの代わりに命令の種類別に小さな RSを置くdistributed schedulerを採用しており、整数RSはdispatch時点で 被演算子の値を直接コピーして持つ形になっています。

R10Kスタイル (MIPS R10000)

1996年のMIPS R10000で確立された方式で、Alpha 21264, IBM Power、そして Intelも Sandy Bridge(2011)以降はこのスタイルへ移りました。今日ほとんど すべての高性能OoO CPUはR10Kスタイルです。

核となるアイデアは別途のARFを無くし、すべてのレジスタ値を単一の物理 レジスタファイル(PRF)にまとめることです。PRFはアーキテクチャレジスタの 数よりずっと多くのエントリを持ち(たとえばMIPS R10000は32個のアーキテクチャ 整数レジスタに対して64個の物理整数レジスタ)、in-flightな値もcommitされた 値もすべてこの1箇所に一緒に住むことになります。

ここでROBは値を持ちません。代わりに「この命令はどの物理レジスタへ 書き込むことになっているか」というマッピング情報だけを保管します。

命令がdispatchされるときにfree listから空の物理レジスタを1つもらって dst (物理)に入れ、その直前まで同じ論理レジスタを指していた物理 レジスタ番号をprev dstに記録しておきます。この情報がsquash・commit時 のfree list管理の核心になります。

命令がEXで実行を終えると結果値をそのままPRFのdst (物理)スロットに書き 込みます。これで終わりです。 もうcommit時点でデータを動かす必要は ありません。RSの他の命令たちも最初からPRFだけを見ているので、この値が 書き込まれた瞬間からそのままforwardingが可能です。

それではcommitは何をするのでしょうか? 大したことをするわけではなく、 2つのことです。

1. RAT (architectural map) の更新: 「この論理レジスタの公式マッピングは これから新しい物理レジスタだ」と記録。この表はsquash時のRAT復元に 使われます。
2. prev dstに記された古い物理レジスタをfree listへ返却。以前の マッピングはもう誰も見ないからです。

逆にsquashの時は: 破棄されるROBエントリのdst (物理)をfree listへ返し、 RATを分岐予測時点のスナップショットから復元します。

長所:

• Commitが非常に軽いです。データコピーがなくポインタ更新だけだからです。
• 結果値がPRFの1箇所にだけ存在するので保存スペースが無駄になりません。
• ROBエントリが小さくなるので、同じ面積でより大きなROBを作れます — これが結局、前節で見たメモリ遅延隠しのウィンドウの大きさを広げて くれます。
• PRFのポート数をうまく設計すればwakeup・forwarding回路が単純に なります。

短所:

• Free list, RAT, ROBがより複雑な形で噛み合う必要があります。squash時に free listの復元が厄介で、別途のhistory bufferやwalkメカニズムが必要に なります。
• PRF自体が非常に大きなマルチポートSRAMとなり、面積・電力の負担が大きい です。4-wayの機械ならissue段階だけで8つのreadポートが必要になることも あります。

MIPS R10000とAMD Opteronコアの比較

2つのCPUはほぼ同じ時代(1996年頃)に登場しましたが、正反対の設計哲学を 見せてくれます。

R10000は学術的・理論的に最もきれいなOoO設計として評価されています。統合 PRF、明確なRAT/free list管理、命令種類別のRS分離 — ほとんどすべての後続 OoO CPUの青写真となりました。ただし物理レジスタ64個とROB 32個とウィンドウ が狭く、今日の基準ではメモリ遅延を隠す能力は限定的でした。

Opteron K8はx86という複雑なISAをOoOで動かすためにP6スタイルを選びました。 x86命令を内部のマクロopにデコードしたあと、各マクロopがROB・RS・LSQを 経て実行される形です。P6スタイルのおかげでIntel/AMDがすでに持っていた Pentium Pro系列のノウハウをそのまま活用でき、K8はそれをもとに大きな ROB(72)と広いLSQ(44)を備え、当時のPentium 4を凌ぐメモリ性能を見せました。

興味深いことにIntel自身もPentium 4まではP6スタイルを維持していましたが、 Sandy Bridge(2011) からはR10Kスタイルの統合PRFへ切り替えました。 理由は単純です — ROBをさらに大きくしようとすると結局R10Kスタイルが必要 だったからです。今日のApple Mシリーズ、ARM Cortex-Xシリーズ、AMD Zen、 Intel Golden CoveはすべてR10Kスタイルであり、ROBの大きさは 200〜600エントリに達します。メモリ壁の時代を耐えるための巨大な命令 ウィンドウは、R10Kスタイルの上でようやく可能になったわけです。

チップマルチプロセッサ

ここまでは1つのコアの中でILPを最大限に引き出す話をしてきましたが、 2000年代半ばからこの方向性には明確な限界が見えはじめました。issue widthをさらに広げ、ROBをさらに大きくしても追加されるトランジスタに 対する性能向上がどんどん小さくなり、何よりもクロックをこれ以上上げ られない電力・熱問題(power wall) が決定打でした。Pentium 4が4GHzの 壁にぶつかった出来事が象徴的です。

このとき登場した代替案がチップマルチプロセッサ(Chip-Multiprocessor, CMP)、よくマルチコアと呼ばれる構造です。1つのコアをもっと大きく 速く作る代わりに、適度な大きさのコアを複数1つのダイ(die)に載せると いう発想です。2005年のAMD Athlon 64 X2とIntel Pentium Dを皮切りに、 それ以降のすべての主流CPUはマルチコアになりました。

CMPはトランジスタ予算をILPではなくTLP(Thread-Level Parallelism)に 投資します。それぞれのコアが別々のスレッドを独立に実行するので、ILPを 絞り出すときのように依存性・分岐・キャッシュミスに悩まされることなく、 ほぼコア数に比例してスループットを上げることができます。記事の冒頭で 見たILP/TLP/DLPの分類に戻ると、スーパースカラ・OoOがILPのための ハードウェアだとすれば、CMPはTLPのためのハードウェアだということに なります。

もちろん、ただではありません。複数のコアが同じメモリを共有するので キャッシュコヒーレンス(cache coherence) プロトコルが必要で、 プログラマの側では明示的なマルチスレッドプログラミングをして初めて マルチコアの利点を享受できます。シングルスレッドだけで動くプログラムは コアがいくら多くても1つのコアの上でしか動きません。このためCMPの登場は 「ハードウェアが勝手に速くなる時代」が終わり、「ソフトウェアが並列性を 明示的に扱わなければならない時代」へ移る分岐点となりました。