キャッシュの内部構造

この章でわかること:

• キャッシュが「データをどこに置くか」を決める仕組み(セットと結合性)
• 2のべき乗ストライドのアクセスが桁違いに遅くなる理由(実測92倍)と対策
• ミスの3分類(初回・容量性・競合性)という診断の語彙
• キャッシュブロッキング — 走査の形を変えてキャッシュに収める技法(実測2倍)
• なぜ体系に必須か — 2章は「キャッシュは 自動で効く」で止めました。内部の配置規則を知らないと、 「特定のサイズやストライドのときだけ異常に遅い」という 実務で頻出の現象を説明も回避もできません

キャッシュはどこに置くかをどう決めるか

2章では、キャッシュを「最近使ったラインの置き場」とだけ説明しました。 では、あるアドレスのラインはキャッシュ内のどこに置かれるのでしょうか。

理想は「空いている場所ならどこでも」(フルアソシアティブ)ですが、 ラインを探すたびに全エントリと比較する回路が必要になり、 大容量では現実的ではありません。逆の極端は「アドレスごとに 置き場所を1か所に固定」(ダイレクトマップ)で、回路は簡単ですが、 同じ場所を取り合う事故が起きます。

現実のキャッシュはその中間、セットアソシアティブ (set-associative)方式です。キャッシュをセット(set)という グループに分け、各セットに数個〜十数個の枠(ウェイ、way)を 持たせます。あるアドレスのラインは、アドレスから決まる 1つのセットの中の、どのウェイにでも置けます。

どのセットに入るかは、次の図のとおり、アドレスのビットを そのまま切り出して決めます。

アドレスの下位ビットがそのまま置き場所(セット)を決める

具体例で確かめます。よくあるL1構成「32KB、8ウェイ、ライン64B」なら、 セット数は 32KB ÷ 64B ÷ 8 = 64セット。アドレスのビット6〜11の 6ビットがセット番号です。

同じセットの取り合い — 2のべき乗ストライドの罠

この配置規則から、恐ろしい帰結が1つ導けます。 4096バイト(=2^12)おきのアドレスは、セット番号のビットが 全部同じ——つまり全員が同じセットに入ろうとします。 8ウェイのセットに9個目を入れれば誰かが追い出されます。 それを何度も巡回すれば、毎回追い出し合いになります。

実験します。読むのは64か所×8バイト = たった512バイトです。 ストライドを4096にした場合と、64バイトだけずらして4160にした場合を 比べます。

512バイトしか触らないのに——

use std::time::Instant;

fn main() {
    // 64か所を何度も巡回して読む。触るデータ量は 64 × 8バイトだけ
    let slots = 64;
    let rounds = 2_000_000;

    for (name, stride) in [("4096バイトおき(2のべき乗)", 4096usize), ("4160バイトおき(+64ずらし)", 4160)] {
        let buf = vec![1u8; slots * stride + 8];
        let start = Instant::now();
        let mut sum = 0u64;
        for _ in 0..rounds {
            for i in 0..slots {
                let p = i * stride;
                let v = u64::from_ne_bytes(buf[p..p + 8].try_into().unwrap());
                sum = sum.wrapping_add(v);
            }
        }
        println!("{name}: {:>9.3?} (sum={sum})", start.elapsed());
    }
}

use std::time::Instant; fn main() { // 64か所を何度も巡回して読む。触るデータ量は 64 × 8バイトだけ let slots = 64; let rounds = 2_000_000; for (name, stride) in [("4096バイトおき(2のべき乗)", 4096usize), ("4160バイトおき(+64ずらし)", 4160)] { let buf = vec![1u8; slots * stride + 8]; let start = Instant::now(); let mut sum = 0u64; for _ in 0..rounds { for i in 0..slots { let p = i * stride; let v = u64::from_ne_bytes(buf[p..p + 8].try_into().unwrap()); sum = sum.wrapping_add(v); } } println!("{name}: {:>9.3?} (sum={sum})", start.elapsed()); } }

▶ 実行編集stable / releasePlaygroundで開く ↗

筆者の実測(Playground)では、4096バイトおきが約680ミリ秒、 4160バイトおきが約7ミリ秒。92倍の差です。 読んでいるデータはL1容量のわずか1.6%(キャッシュライン単位で 数えても64ライン=4KB、12.5%)にすぎないのに、2のべき乗ストライドの 側は全アクセスが同じL1セットに集中し、8ウェイからあふれた分が 毎回下の階層まで取りに行く状態になっています(1回あたり約5ナノ秒 という実測値は、L2以遠のレイテンシに相当します。L2はセット数が 多いため同じようには集中しませんが、それでもL1にほぼ載らない 時点で数倍〜数十倍の代償です)。

ここでキャッシュミスの診断語彙を整理しておきます。ミスは3種類です。

• 初回ミス(cold miss) — 一度も読んでいないから当然ミス
• 容量性ミス(capacity miss) — 作業データがキャッシュ容量を超えている
• 競合性ミス(conflict miss) — 容量は余っているのに、 特定セットの取り合いでミスする。今回の実験がこれです

2章の実験はすべて初回・容量性の話でした。競合性ミスは 「容量計算では説明できない遅さ」として現れるのが特徴です。

実世界でこの罠を踏む典型は次の場面です。

• 2のべき乗の行列・画像の幅 — 幅1024のf32行列の「列方向の走査」は ストライド4096です。転置や縦方向フィルタが刺さります。 古典的な対策は、幅を1列分だけ余らせて確保する(n+パディング)ことです
• 複数の大きな配列を並行して走査する — アロケータは大きな確保を ページ境界(4KBの倍数)に揃えがちなので、複数の配列の同じ添字が 同じセットに当たることがあります

ブロッキング — 走査の形をキャッシュに合わせる

セットの話を踏まえて、キャッシュ最適化の代表技法 キャッシュブロッキング(cache blocking、タイリングとも)を 導入します。題材は行列の転置です。

転置は「行方向に読んで列方向に書く」操作なので、素朴に書くと 読みか書きのどちらかが必ずストライドアクセスになります。 2048×2048でストライドは8KB——先ほどの罠(2のべき乗)まで踏んでいます。

そこで、行列全体を32×32の小さなブロックに分け、 ブロック単位で転置します。32×32のf32ブロックは4KB。 読み側と書き側のブロックを合わせても8KBで、容量としては L1に収まります(この行列は行ストライドが2のべき乗のため セット競合は残り、完全なヒットまでは保証されません—— それでも局所性は大幅に改善します。さらに詰めるなら パディングで競合も外せます)。

素朴な転置 vs ブロック転置

use std::time::Instant;

fn main() {
    let n = 2048;
    let src: Vec<f32> = (0..n * n).map(|i| i as f32).collect();
    let mut dst = vec![0.0f32; n * n];

    // (1) 素朴な転置: dst の書き込みが列方向(ストライドn)になる
    let start = Instant::now();
    for i in 0..n {
        for j in 0..n {
            dst[j * n + i] = src[i * n + j];
        }
    }
    println!("素朴な転置        : {:>9.3?} (check={})", start.elapsed(), dst[123 * n + 45]);

    // (2) 32×32のブロック単位で転置: 読み書きともキャッシュ内で完結
    let mut dst2 = vec![0.0f32; n * n];
    let b = 32;
    let start = Instant::now();
    for bi in (0..n).step_by(b) {
        for bj in (0..n).step_by(b) {
            for i in bi..bi + b {
                for j in bj..bj + b {
                    dst2[j * n + i] = src[i * n + j];
                }
            }
        }
    }
    println!("ブロック転置(32×32): {:>9.3?} (check={})", start.elapsed(), dst2[123 * n + 45]);
    assert!(dst == dst2);
}

use std::time::Instant; fn main() { let n = 2048; let src: Vec<f32> = (0..n * n).map(|i| i as f32).collect(); let mut dst = vec![0.0f32; n * n]; // (1) 素朴な転置: dst の書き込みが列方向(ストライドn)になる let start = Instant::now(); for i in 0..n { for j in 0..n { dst[j * n + i] = src[i * n + j]; } } println!("素朴な転置 : {:>9.3?} (check={})", start.elapsed(), dst[123 * n + 45]); // (2) 32×32のブロック単位で転置: 読み書きともキャッシュ内で完結 let mut dst2 = vec![0.0f32; n * n]; let b = 32; let start = Instant::now(); for bi in (0..n).step_by(b) { for bj in (0..n).step_by(b) { for i in bi..bi + b { for j in bj..bj + b { dst2[j * n + i] = src[i * n + j]; } } } } println!("ブロック転置(32×32): {:>9.3?} (check={})", start.elapsed(), dst2[123 * n + 45]); assert!(dst == dst2); }

▶ 実行編集stable / releasePlaygroundで開く ↗

筆者の実測(Playground)では約36ミリ秒→約18ミリ秒、2倍です。 計算量は完全に同一で、変えたのは走査の順序だけ—— 12章のループ順入れ替え(ikj)と同じ思想の、 より一般的な形です。

このブロッキングは行列積にも適用できます(12章のikj版は大きなnで bの行がキャッシュから溢れ始めるため、ブロック化でさらに 伸びしろがあります)。そして重要なのは、 12章で書いたGPUの共有メモリタイル化 (matmul_tiled)が、まったく同じ技法のGPU版だったということです。 CPUでは自動のキャッシュに「収まるような走査順」を書き、GPUでは 手動の共有メモリに「載せる」——道具は違えど、原理は1つです (23章では同じ共有メモリを 別の形で使います)。

サイズを知らずに全階層に効かせる — cache-oblivious

ブロックサイズはキャッシュ容量に合わせて選びました。では L1/L2/L3のどれに合わせるべきか? 一つの答えが cache-obliviousアルゴリズムです。問題を再帰的に半分に 割り続けると、どこかの深さで必ず各キャッシュ階層に収まるため、 容量を知らずに全階層へ同時に適応します。転置や行列積、 ソート(funnelsort)に既知の構成があります。本書では思想の 紹介にとどめますが、「再帰分割は階層をまたいで局所性を作る」 という視点は覚えておく価値があります。

まとめ

• キャッシュはセットアソシアティブ方式で、アドレスの下位ビットが 置き場所(セット)を決めます
• 2のべき乗ストライドはアクセスを同一セットに集中させ、 512バイトのデータで92倍の遅さを生みました(競合性ミス)。 パディングでストライドをずらすのが対策です
• ミスは初回・容量性・競合性の3分類で診断します
• キャッシュブロッキングは走査をキャッシュに収まる単位に割る技法で、 転置で2倍。GPUの共有メモリタイル化と同じ原理です

次章はデータ側から命令側へ視点を移します。3章で扱ったのは 命令の「実行」の話でした。その手前——命令を供給する側 (フロントエンド)——にも律速があり、それを見分ける体系的な方法 (top-down分析)があります。