メモリ階層とキャッシュ｜コンピュータ基礎

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：CPUと命令実行　|　関連：仮想記憶とページング・性能の評価とアムダールの法則

要点（BLUF）

速くて小さい記憶（レジスタ・キャッシュ）と、遅くて大きい記憶（主記憶・ディスク）を階層に積む。理由は「速い記憶は高価で小さい」という物理的トレードオフ。
階層が機能するのは 局所性のおかげ。「最近使ったものはまた使う（時間的）」「近くのものも使う（空間的）」というプログラムの性質。
効果は 平均メモリアクセス時間（AMAT）= ヒット時間 + ミス率 × ミスペナルティ で定量化できる。ヒット率99%なら、キャッシュ無しの約50倍速にもなる。

概念 ── なぜ「階層」なのか

記憶装置には残酷なトレードオフがあります。速いものは高価で小さく、安いものは遅くて大きい。レジスタは数百ピコ秒だがCPUに数十個、ディスクはテラバイト級だがミリ秒オーダ。1種類で全部をまかなうのは不可能です。

そこで全種類をピラミッド状に積み、「よく使うデータを上（速い層）に、滅多に使わないデータを下（大きい層）に」置きます。

flowchart TB
    R["レジスタ（1サイクル / 数百B）"] --> L1["L1キャッシュ（数サイクル / 数十KB）"]
    L1 --> L2["L2/L3キャッシュ（十数〜数十サイクル / 数MB）"]
    L2 --> M["主記憶（DRAM / 約100ns / 数GB）"]
    M --> D["ストレージ（SSD/HDD / マイクロ〜ミリ秒 / 数TB）"]

上ほど「速い・小さい・高い」、下ほど「遅い・大きい・安い」。各層は、下の層のよく使う一部のコピーを持ちます。

仕組み① ── 局所性がすべての前提

階層が効くかどうかは、プログラムが 局所性（locality） を持つかにかかっています。

時間的局所性：一度アクセスしたデータは、近いうちにまたアクセスされやすい（ループ変数、関数の頻繁な呼び出し）。
空間的局所性：あるアドレスを使ったら、その近くも使われやすい（配列の連続走査、命令の順次実行）。

CPUはこれを見越して、データをキャッシュライン（典型64バイト）という塊単位で運びます。1バイト要求しても周辺64バイトをまとめて持ってくる。だから配列を順に舐めると、最初の1回（ミス）以降はキャッシュに乗った隣接要素を高速に読めます。

要するにキャッシュは「次もこの辺を使うだろう」という賭けで、局所性の高いプログラムほどこの賭けが当たります。

仕組み② ── ヒット率とAMATの計算

キャッシュに目的のデータがあれば ヒット、なければミスで下の層へ取りに行きます（ミスペナルティ）。性能は次式で測れます。

\text{AMAT} = \text{ヒット時間} + \text{ミス率} \times \text{ミスペナルティ}

L1ヒットが1ns、ミスすると主記憶100nsかかる場合を計算します（[[#対応ラボ]] の 01-03_cache_amat.py）。

def amat(hit_time, miss_rate, miss_penalty):
    return hit_time + miss_rate * miss_penalty

for hit_rate in (0.90, 0.95, 0.99):
    print(f"ヒット率 {hit_rate*100:5.1f}% -> AMAT = {amat(1.0, 1-hit_rate, 100.0):6.2f} ns")

実行結果（実機）:

ヒット率  90.0% -> AMAT =  11.00 ns
ヒット率  95.0% -> AMAT =   6.00 ns
ヒット率  99.0% -> AMAT =   2.00 ns

注目すべきは、ヒット率が90%→99%に上がるとAMATが11ns→2nsへ激減する点。ミスは100倍遅いので、わずかなミス率の差が平均を支配します。「9割当たれば十分」ではなく、最後の数%が効くのです。

キャッシュ無し（毎回100ns）と比べると：

キャッシュ無し: 100.00 ns / ヒット率99%: 2.00 ns
速度比: 約 50.0 倍

実際は階層が多段（L1→L2→主記憶）で、ミス時に下の層の平均時間が効きます。ラボでは2階層を入れ子で計算し、全体AMAT ≈ 3.50ns を得ています。

具体例 ── ループの順序で速さが変わる

2次元配列を「行優先」で舐めるか「列優先」で舐めるかで、実行時間が数倍変わります。メモリ上で連続しているのは行方向なので、行優先なら空間的局所性が効いてキャッシュヒットが続き、列優先だと毎回飛んでミスを連発するためです。アルゴリズムの計算量（計算量とオーダー記法）が同じでも、メモリアクセスのパターンで実速度が変わる典型例です。

仕組みの直観 ── なぜこの設計か

階層にする理由：1種類で速さと容量を両立できない以上、「速い層に当たり続ける」設計が最善。当たれば速い層の速度、外れても下が支える。
ライン単位で運ぶ理由：空間的局所性を見越した先読み。1バイトずつ運ぶより、まとめて運ぶ方が割に合う。
透過的である理由：キャッシュはハードが自動管理し、プログラムからは「ただのメモリ」に見える。これがOSの仮想記憶（仮想記憶とページング）と同じ「下の遅い層を、上の速い層で見せかける」発想の原型。

⚠️ よくある誤解・落とし穴

「キャッシュはプログラマが明示的に置く」→ ハードが局所性に基づき自動管理（CPUキャッシュの場合）。プログラマは局所性の高いアクセスを書くことで間接的に効かせる。
「ヒット率が高ければ十分」→ ミスペナルティが大きいので、最後の数%のミスが平均を支配する。
「メモリは均一の速さ」→ 同じ「メモリ」でもL1と主記憶で100倍違う。データ構造の選択（基本データ構造）はこれに影響される。
「計算量が同じなら速さも同じ」→ アクセスパターン（局所性）で実速度は大きく変わる。

対応ラボ

cs-foundations-study/labs/01-03_cache_amat.py（実行して上記AMATを確認済み）。

確認できること：ヒット率とAMATの関係、ミスペナルティの支配性、多段階層の計算