CPUパイプラインと分岐予測 — 1クロックの中の工場

1命令が1クロックで終わるように見えるのは、工場のラインと同じ流れ作業だから。5段パイプラインの組み立てから、流れを止める3種のハザード、分岐予測と投機実行、そして投機の副産物が情報漏洩になったSpectreまでを、前提知識ゼロから追いかけます。

Spectre Attacks: Exploiting Speculative Execution

1クロックで1命令、という言い方の正体

仕様には「3.5 GHz」と書いてあります。1秒に35億回の拍。命令はおおむね1拍で1個ずつ片づく——そう聞くと、1命令が0.3ナノ秒で終わっているように思えます。実際は違います。1命令が入口から出口まで通るには何拍もかかる。それでも1拍に1個ずつ出てくるのは、何個もの命令が別々の工程で同時に作業されているからです。

コインランドリーで考えると早い。洗濯30分、乾燥30分、たたむ30分。1人分は必ず90分で、4人を律儀に1人ずつ通せば360分です。けれど乾燥機へ移した瞬間に次の人が洗濯機を回し始めれば、最初の1人が終わるのは90分後のままなのに、その後は30分おきに1人ずつ終わる。全体では180分になります。

混ぜてはいけない量が2つあります。1人分が終わるまでがレイテンシ（90分）、単位時間に何人分片づくかがスループット（30分に1人）。パイプラインはレイテンシを縮めず、工程の境目の手間でむしろわずかに伸ばします。それでもスループットが3倍になるから採用されている、というのが骨格です。

5段の工場ライン

古典的な構成が5段パイプラインです。1命令の仕事を5工程に割ります。

工程の境目にはパイプラインレジスタという小さな棚があり、途中の結果をそこに置いてから次へ渡します。おかげで各工程は、前後の事情を知らずに自分の棚だけ見て働けます。$N$ 個の命令を $k$ 段に流したときの所要時間は、1段ぶんの時間を $t$ として次のとおりです。

要するに「最初の1個が出るまで $k$ 段ぶん待ち、あとは1段ぶんの時間ごとに1個ずつ出てくる」。$N$ が大きければ $k-1$ は誤差で、1命令あたりは $t$ に近づきます。パイプライン無しなら $kt$ ですから、理屈のうえでは $k$ 倍です。ただし段を細かく割るほど1段は短くなる一方、棚に置く時間は割っても縮まないので、増やせる段数には限りがあります。

流れが止まる3つの理由

きれいに流れれば1拍1命令。それを妨げるものをハザードと呼び、原因は3種類しかありません。

構造ハザード — 同じ設備を2人が同時に使いたい。乾燥機が1台なら片方が待たされます。命令もデータも同じメモリから取ると起きるので、現代のCPUは命令キャッシュとデータキャッシュを分けて避けています。

データハザード — 前の命令の結果が次の命令の材料になっている。前の人がたたみ終えた服を次の人が着ようとしている状態で、並べただけではまだ乾いていません。

制御ハザード — 次にどの命令を取ればいいかが決まっていない。分岐の判定が出るまで入口が止まる問題で、この記事の後半はほとんどこれとの戦いです。

データハザードは配線で回避する

a = b + c の次に d = a - e があるとします。1本目が計算を終えるのはEX段、書き戻されるのはWB段なので、素直に作ると2本目はID段で古い値を掴みます。解決は直接的で、EXの出力をEXの入力へ配線で戻すだけ。これをフォワーディング（バイパス）と呼びます。乾燥機から直接手渡しするようなものです。

配線で消せない組み合わせが1つだけあります。ロード-ユース ハザードです。メモリから読んだ値が出るのはMEM段の終わりで、次の命令のEX段には間に合わない。時間をさかのぼる配線は引けないので1拍待つ（ストール）しかありません。だからコンパイラはロードの直後に「その値を使わない命令」を置こうとします。最適化ビルドで命令の順序が原型をとどめないのは、この埋め合わせの結果です。

制御ハザード — 分岐は「行き先が分からない」

分岐の厄介さは、判定と取得の時間差です。IF段は毎拍「次の命令」を取りにいくのに、if (x > 0) の判定が出るのはEX段のあたり。その数拍、入口は何を流すか分かりません。しかもコードのおおむね5〜10命令に1本は分岐です。ループの底、関数呼び出し、switch、仮想関数——プログラムは実質、分岐でできています。

そこでCPUは待たずに賭けることにしました。予測してその先を流し始め、当たれば損失ゼロ、外れたら流した分を捨てて取り直す。損得を式にすると、1命令あたりの平均サイクル数（CPI）はこうなります。