キャッシュの内部構造

この章でわかること:

• キャッシュがデータの置き場所を決める仕組み(セットと結合性)
• 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にした場合を 比べます。

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());
    }
}

筆者の実測(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つです。

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

ブロッキング: 走査の順序をキャッシュに合わせる

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

転置は行方向に読んで列方向に書く操作なので、単純に書くと 読みか書きのどちらかが必ずストライドアクセスになります。 2048×2048ではストライドが8KBで、前節の2のべき乗ストライドの条件にも 該当します。

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

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);
}

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

このブロッキングは行列積にも適用できます(12章のikj版は大きなnで bの行がキャッシュ容量を超えるため、ブロック化でさらに 改善できます)。また、12章で書いたGPUの 共有メモリタイル化(matmul_tiled)は、まったく同じ技法のGPU版です。 CPUでは自動で動くキャッシュに収まる走査順を書き、GPUでは 手動で共有メモリに配置します。手段は違いますが、原理は同じです (23章では同じ共有メモリを 別の形で使います)。

まとめ

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

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