memory-hierarchy-and-caches

メモリ階層とキャッシュ

目的

CPU のメモリ階層について解説します。キャッシュレベル、連想度、ラインサイズ、コヒーレンスプロトコル、フォルスシェアリング、プリフェッチの動作を扱い、skills/low-level-programming/cpu-cache-opt の最適化実践をアーキテクチャ面から補完します。

使用する場面

• パディングによってスケーラビリティが改善する理由を説明する
• マルチコア向けの構造体レイアウトを選ぶ
• キャッシュミスカウンターを解釈する
• 組み込み SoC における DMA と CPU キャッシュの違いを理解する

ワークフロー

1. 階層（一般的なデスクトップ／サーバー）

Registers
├── L1d / L1i (per core, ~32 KiB, ~4 cycles)
├── L2 (per core, ~256 KiB – 1 MiB)
├── L3 (shared last-level, MiB – tens of MiB)
├── DRAM (hundreds of cycles)
└── Storage / NUMA remote (much slower)

組み込み MCU では、密結合メモリしかない場合もあります（L2／L3 はありません）。

2. キャッシュラインと連想度

• ラインサイズ：x86／ARM64 では通常 64 バイトです（getconf LEVEL1_DCACHE_LINESIZE で確認してください）
• セットアソシアティブ方式：ラインは 1 つのセットに割り当てられ、そのセット内のウェイ間で競合します
• コンフリクトミス：同じセットに多数のエイリアスが割り当てられます

3. フォルスシェアリング

/* Bad — two atomics on same cache line */
struct {
    atomic_int counter_a;
    atomic_int counter_b;
} stats;

/* Good — pad to cache line */
struct alignas(64) {
    atomic_int counter_a;
    char pad[64 - sizeof(atomic_int)];
    atomic_int counter_b;
} stats;

4. コヒーレンス（マルチコア）

MESI 状態は Modified、Exclusive、Shared、Invalid です。書き込みによって他のコアにある同じラインのコピーが無効化されます。これが、アトミック操作やロックによってキャッシュラインがコア間で行き来する理由です。

5. プリフェッチ

#ifdef __builtin_prefetch
for (int i = 0; i < n; i++) {
    __builtin_prefetch(&data[i + 8], 0, 3);
    process(data[i]);
}
#endif

ハードウェアのストライドプリフェッチャーは逐次アクセスを検出しますが、ランダムアクセスではミスが発生します。

6. 測定

perf stat -e cache-references,cache-misses,L1-dcache-load-misses ./app

7. エージェントの使用

/memory-hierarchy-and-caches Diagnose false sharing in this per-thread stats array

よくある問題

症状	原因	対処法
スケーリングが崩れる	フォルスシェアリング	スレッドごとのデータをライン境界にアラインする
LLC ミスが多い	ワーキングセットがキャッシュを超えている	アルゴリズムをブロック化する。NUMA を固定する
DMA のコヒーレンスが取れない	CPU キャッシュとデバイスの不整合	MCU ではフラッシュ／無効化する。Linux では dma_sync を使用する
プリフェッチで性能が低下する	不規則なアクセス	手動プリフェッチを削除する
巨大な構造体のコピーが発生する	AoS によるキャッシュラインの低利用	SoA レイアウトを使用します。cpu-cache-opt を参照してください

関連スキル

• skills/low-level-programming/cpu-cache-opt — 実践的な最適化
• skills/computer-architecture/cpu-pipelines-and-hazards — ロード使用ストール
• skills/computer-architecture/virtual-memory-paging-and-tlb — TLB ミス
• skills/allocators/numa-programming — リモートメモリのレイテンシ
• skills/profilers/hardware-counters — perf カウンターイベント