CPU アーキテクチャ 基礎

働くのは 3 つだ。x86-64 なら 64 ビット枠 16 本のレジスタファイル(ARM64 は 31 本)、ALU、そしてプログラムカウンタ。

1 命令の add rax, rbx は順にその全部を訪ねる。再生を押して、命令が構造から構造へ移り、下で読まれるレジスタが灯るのを見てほしい：

レジスタファイルが 2 回触られること、そしてコアの外側には一切触れないことに注目。レジスタを読むのは命令の実行の一部であって、独自の遅延を持つ別の出来事ではない。

すべての命令が加算ではない。下の梯子は Skylake コアが種類ごとに払うサイクル数で、スライダはいま課金されている 1 本を歩く：

この幅こそがページ全体の話だ。レジスタ加算は 1 サイクル —— 3 GHz で 0.33 ns —— キャッシュを全部外すロードは 250、83 ns。 2 本の桟のあいだに 250 倍があり、クロックをいくら上げても埋まらない。

16 本は多くない。同時に生きていなければならない値を増やして、座る場所のない値が下の行へ落ちるのを見てほしい：

生きた値が 24 個になると 8 個が退避し、 1 つにつき毎反復ストア 1 回とロード 1 回がかかる —— ソースのどこにも書かれていない 16 回のメモリ操作だ。積極的なインライン化が効く本当の理由はここにある。

では、なぜレジスタをもっと積まないのか。レジスタ名は命令の中に書かねばならず、ARM64 では3 つのレジスタ欄に与える 1 ビットはオペコードから取り上げた 1 ビットになる：

ARM64 が選んだ 5 ビットでは、32 本のレジスタが 32 ビット中の 15 を食い、残り17 ビット —— 131,072 種の演算で十分すぎる。欄を 8 ビットに広げるとレジスタ 256 本と演算 256 種になり、それは命令セットではない。

日常会話まで生き残る数字は 1 つ、クロックだ。 3 GHz なら毎秒 30 億命令をリタイアさせると計算したくなる。DRAM まで行くロードを上げて、 2 本の棒が離れるのを見てほしい：

1000 命令あたり 8 ミスで CPI は 3.00、実スループットは毎秒 10 億命令 —— 箱の数字の 3 分の 1 だ。逆にも外れる。続く 3 セクションは、コアが 1 サイクルに1 命令を超えてリタイアさせる話だ。

ループを段に切る —— フェッチ、デコード、実行、メモリ、書き戻し —— 各段に専用のハードウェアを与える。1 命令ずつなら 1 サイクルに 1 段しか使わず、4 段が遊ぶ。

スライダは開始間隔だ。5 から 1 まで引いて、各命令が書き戻しまで依然 5 サイクルかかったまま合計がつぶれるのを見てほしい：

5 命令は 1 つずつなら 25 サイクル、重ねれば 9 サイクル —— 2.8 倍を、ハードもクロックも足さずに買っている。短くなったものはなく、機械が段を空けるのをやめただけだ。遅延は 5 のまま、動いたのはスループットだ。

1 サイクルずつ進めて対角線が埋まり、最初のリタイアが 5 サイクル目に来るのを見てほしい：

走行の値段は 5 サイクルの立ち上がりと、その後 1 命令 1 サイクル。だから n 命令は 5n ではなく n + 4 だ。これは平均ではなく償却の議論で、 1 命令が 5 サイクルより速くなることはないが、n が増えれば走行全体は毎サイクル1 リタイアに近づく。

成り立つのは各段が次に渡すものを持つあいだだけだ。下の 2 命令目は、 1 命令目がまだ書いていないレジスタを要る。フォワーディングを切って、現れる死んだサイクルを辿ってほしい：

なければ消費側は生産側の書き戻しを待つ —— 前半に書き後半に読むレジスタファイルを仮定して死んだ 2 サイクルだ。フォワーディングは ALU の出力を入力へ直結し、走行は 10 から 8 サイクルへ落ちる。

それでも消えないハザードが 1 つある。ロードの値はメモリ段の終わりまで分からず、真後ろの命令はストールする。消費側をロードから離して、バブルが消えるのを見てほしい：

1 スロット離れならバブル 1 つ、 2 スロットならゼロ。コンパイラがロードを前に出す理由はこれで、スケジューラはキャッシュに賢いのではなくスロットを買っている。独立な命令なら何でもよく、ループ展開が効くのも同じ理由だ。

5 段は 1990 年代の機械だ。現代のコアは 15〜20 段で走る。段が短いほど速く刻めるからだ。深さを引いて、クロックとフラッシュを見比べてほしい：

取引の中身はよく引用されるものと違う。5 段から 20 段でクロックはほぼ 3 倍、1.19 から 3.51 GHz、フラッシュは 4 から 19 サイクル —— だがサイクルは短く、時間では 3.36 ns から 5.42 ns だ。サイクルはフラッシュを測る単位として間違っている。

永遠にではない。Pentium 4 の Prescott は 31 段・3.8 GHz で、段ごとのラッチ遅延が利益をかなり返した。25 を過ぎるとクロック曲線は寝るのに、フラッシュは登り続ける。

だから待たない。フロントエンドは当てずっぽうで取り続ける。分岐の確定を深い段へ押しやり、その後ろで取られたものを数えてほしい：

誤った経路のものはすべて削除され、本当の飛び先がフェッチからやり直す。確定が遅いほど捨てる量は増える —— §02 の取引を反対側から見た姿だ。実機の再充填は 17 サイクル。

だいたい 5 命令に 1 つは分岐なので、この計算は容赦がない。外れて返る割合を上げて、コアのどれだけがあなたのプログラムのものでなくなるか見てほしい：

実コードが達成する 2% では CPI 1.07、サイクルの 6.4% が捨てられる。コイン投げの 50% では同じコアが CPI 2.70 で走り、サイクルの 63% をすぐ捨てる仕事に使う。精度は 2 台の別の機械を分ける線だ。

仕組みは分岐ごとのカウンタだ。1 ビットは「前回どおり」と言い、 2 ビットは 2 回外すまで意見を変えない。結果を辿って、それぞれの下の外れを見てほしい：

8 回まわるループでは 1 ビットが 32 回中 8 回、2 ビットが 6 回外す。増えた 1 ビットが、ループを忘れずに 1 回だけの脱出を吸収している。交互パターンでは 2 ビットが 16 回外す —— 真ん中で振動し、成立をただの一度も予測しない。読めないデータでは 32 中 21 で、1 ビットよりわずかに悪い。

最後のこれが有名な話だ。閾値を越える値を後ろへ並べていって、外れた予測が消えるのを見てほしい：

シャッフル時は 32 反復で 15 回外し 383 サイクル、整列後は 2 回で 162 サイクル。同じデータ・同じコードで 2.4 倍 —— ホットなフィルタの前の std::sort が元を取る理由だ。

次は第 2 段の問い。どれだけ並べ替えが要るのか。16 を過ぎると棒はまだ並び替わるのに予測ミスの数は動かない。 16 は 128 未満がすべて 128 以上の前に来た地点で、予測器に見えるのは結果列だけだ。分割で足り、それは O(n) だ。

方向は半分にすぎない。間接呼び出しが要るのは飛び先で、それを覚えるバッファは前回の 1 つしか持たない。呼び出し地点に飛び先を足して、的中率が落ちるのを見てほしい：

飛び先1 つならタダだ。学べない順で現れる 4 つは 4 回に 1 回しか当たらず、毎回 12.8 サイクル余計にかかる —— 小さな仮想メソッドの本体より高い。これが単態・多態・巨大多態の差で、ホットなディスパッチが特殊化される理由だ。

本物の予測器は直近の分岐結果でもカウンタを索引する。繰り返しパターンを選び、棒がゼロに落ちるまでグローバル履歴のビットを足してほしい：

周期 6 のパターンは 4 ビットでは見えない —— 60 回中 10 回外れ —— 5 ビットで完全に読める。閾値は長さでなくパターン自体に依存するので、TAGE は複数の履歴長を同時に持つ。 Spectre が訓練するのもこの仕組みだ。

前半はハードウェアを増やす話だ。実行ポートを複数持ち、養えるだけ広いフロントエンドを置く。後半は、互いに依存しない命令を見つけることだ。

発行幅を広げて、独立な仕事が早く終わる一方で数珠つなぎの版が動かないのを見てほしい：

独立な 12 演算は 15 サイクルから 4 幅の 6 サイクルまで縮み、そこで止まる。実行ポートが 4 つで、5 番目のスロットに送り先がないからだ。連鎖はどの幅でも 48 サイクル。長さ 1 の待ち行列を幅は救えない。

がっかりする最適化のほとんどはこの形だ。1 つのアキュムレータへのリダクションは 100 万連の鎖になる。アキュムレータを足して、スループットの床が止めるまでそれぞれの鎖が短くなるのを見てほしい：

1 つなら 400 万サイクル、3 GHz で 1.33 ms。4 つなら 100 万サイクル、 0.33 ms —— ちょうど 4 倍で命令数は同じだ。8 を超えると各鎖は毎サイクル 2 発行の上限より短くなり床が効く。9 個目も 12 個目も稼がない。

依存のもう 1 種類は本物ではない。ともに rax に書く 2 命令がぶつかっているのは名前であって値ではない。リネームを入れて、そもそも不要だった待ちが消えるのを見てほしい：

なければ mov rax, 7 は 20 サイクル目まで発行できない —— すぐ上書きする除算の結果を待っている —— 依存側の完了は 23 だ。リネームは新しい物理レジスタを与えるので 0 サイクル目に発行され、依存側は 3 サイクル目に終わる。

当然の不安が湧くが、答えはこの機械の中心的な約束だ。第 N 命令がリタイアした後のアーキテクチャ状態は、1 命令ずつ実行する機械が作るものとまったく同じである。実行が順不同に終わりコミットは順のままなのを見てほしい：

コミットが順なので、何も早く見えたりはしない。最後の 3 本は 3 サイクル目に終わっていながら除算の後、 22・23・24 でリタイアする。それがリオーダバッファの買うもので、例外をちょうどその命令で届けられる理由でもある。

その大きさが、独立な仕事を探してどこまで先を見られるかを決める。先を見ることがキャッシュミスを重ねるやり方だ。8 命令に 1 回 DRAM を外すループで窓を広げ、同時に抱えるミスが増えるのを見てほしい：

8 エントリなら一度に1 ミスだけで丸ごと 250 サイクル。80 なら 10 ミスで 1 つ 25 サイクル。そこで頭打ちだ —— フィルバッファは 10 本なので、窓がいくら大きくても11 番目のミスは待つ。Skylake の ROB は 224、 Golden Cove は 512 だが、どちらも律速ではない。

これが「なぜポインタ追跡は遅いのか」への答えだ。連結リストは構造上一度に 1 ミスしか渡さないので、512 エントリの機械でもスライダの左端、1 ノード 250 サイクルに座る。

メモリにはもう 1 つ、ソースから見えない罠がある。ロードがストアバッファから答えてもらえるのは、ストアがロードを完全に含むときだけだ。ロードをストアの上で滑らせて、フォワードが失敗する位置を見つけてほしい：

ストアの内側ならロードは 5 サイクル、境界をまたぐとハードウェアはあきらめて L1 まで流し再実行する —— 同じ C の文で 18 サイクル、しかも静かに失敗する。

設計どおり動いていてもタダではない。分岐をフェッチしてから確定するまで、 4 幅のフロントエンドは推測だけを頼りに命令を注ぎ込み続ける。影の 17 サイクルを辿り、その推測の上に積まれた仕事が捨てられる仕事に変わるのを見てほしい：

4 幅で 68 µop、6 幅なら 102 —— すべてデコード・リネーム・スケジュールされ、多くは実行までされて削除される。広げるほど予測ミスは高くつく。幅と予測器の精度が一緒に設計される理由だ。

アーキテクチャ的にこの削除は完全だ。レジスタもメモリ位置もフラグも生き残らない。「投機は安全」という議論はまるごとこれで、穴もここにある —— キャッシュは初めからアーキテクチャ状態ではなかった。

下は Spectre v1 のガジェットだ。境界チェックは成立と訓練済みで、投機実行は配列の末尾を越えて読み、本来見えてはならないバイトを添字に使う。そのバイトを選び、最後の段まで進めてほしい：

最後の段に注目。レジスタはすべて復元され、そのロードは公式には起きなかったことになり、プログラムはチェックが失敗した場合と同じに振る舞う —— しかしプローブ配列の 1 ラインはキャッシュに残る。どのラインかは秘密で決まる。キャッシュのためのロールバックは誰も書かなかった。

それを読み出す作業は計時であり、負荷のある計時にはノイズが乗る。攻撃者が指すラインが投機が触れたラインでなくなるまでノイズを上げ、それから再び当たるまで平均回数を増やしてほしい：

ノイズ 0.80 では 1 回の測定はライン 9を指し、攻撃はただ外れる。16 回平均するとノイズは 4 分の 1 になり、ライン 11 がきれいに戻る。概念実証が何千回もループする理由であり、ブラウザが最初に出した緩和が高分解能タイマの精度制限だった理由でもある。

本物の緩和は構造的で、そして高い。カーネルページテーブル分離はユーザモードにカーネル写像のないページテーブルを与えるので、システムコールのたびにアドレス空間を切り替えることになる。システムコールの頻度を上げて、その切り替えの値段を見てほしい：

毎秒 20 万システムコールは PCID ありでコアの 6.0% を食う。タグつき TLB が切り替えを生き延びるからだ。PCID がなければ20.0% —— 切り替えのたびに TLB が流れる。

retpoline や IBRS も請求書を持ち、新しい側チャネルは届き続けている。共有ハードウェアで信頼できないコードを走らせる者へ ——あなたが引いた境界はアーキテクチャ上のもので、その下の機械はそうではない。

double s = 0;                  // 4.00 M
for (i = 0; i < n; i++) s += a[i];

double s0=0, s1=0, s2=0, s3=0; // 1.00 M
for (i = 0; i + 3 < n; i += 4) {
  s0 += a[i];    s1 += a[i+1];
  s2 += a[i+2];  s3 += a[i+3];
}
s = (s0 + s1) + (s2 + s3);

• ホットループの巨大多態な呼び出し。1 回 12.8 サイクル。
• 未整列入力へのデータ依存分岐。上流で 1 回分割する。
• リダクションでアキュムレータ 1 本。4 倍の遅延、静かに失敗。
• ホットパスの連結構造。配列なら 10 のミスを 1 つしか抱えない。
• 直前のストアと重なるロード。5 サイクルが 18 に。