キャッシュメモリの原理 ─ 連想方式・置換・一貫性

なぜ小さなキャッシュが効くのか

CPU コアの動作周期は 1ns 未満ですが、主記憶（DRAM）への往復は数十〜百 ns 以上かかります。この差をそのまま晒すと、CPU はメモリ待ちで遊んでしまいます。キャッシュは、よく使うデータを高速な SRAM に置いて待ち時間を隠す機構です。容量は主記憶のごく一部（L1 なら数十 KB）にすぎないのに広く効くのは、プログラムのアクセスに局所性があるからです。

• 時間的局所性: 一度参照したアドレスは近い将来また参照されやすい（ループ変数、ホットな関数）。
• 空間的局所性: あるアドレスを参照すると、その近傍も参照されやすい（配列の連続走査、命令の逐次実行）。

この経験則ゆえに、最近使った少量を保持するだけで多くのアクセスをキャッシュ内で完結できます。性能の指標はヒット率で、平均アクセス時間（AMAT）はおよそ次で表せます。

AMAT = ヒット時間 + ミス率 × ミスペナルティ

ヒット率が 95% でもミスペナルティが大きければ平均は跳ね上がるため、ミス率そのものとペナルティの両面を下げる設計が要ります。

アドレスの分解とブロック

キャッシュは1バイト単位ではなく、**ブロック（ライン）**単位で主記憶とやり取りします。典型は 64 バイトです。空間的局所性を狙い、ミス1回でブロック丸ごと引き込みます。物理（または仮想）アドレスは3つのフィールドに分解されます。

[ タグ | インデックス | ブロックオフセット ]
  上位      中位            下位

• ブロックオフセット: ブロック内の位置。64 バイトなら下位 6bit。
• インデックス: どのセット（行）に入れるかを選ぶ。セット数が 2^n なら n bit。
• タグ: 同じセットに入りうる多数のブロックを区別する識別子。エントリにタグを格納し、参照アドレスのタグと一致して初めてヒット。

ヒット判定は「インデックスでセットを選び、そのセット内のタグ群と照合し、有効ビットが立った一致があるか」を見ます。このどこに置けるかの自由度が、次の連想方式です。

連想方式：配置の自由度とコスト

ブロックをキャッシュ内のどこに置けるかで3方式に分かれます。

ダイレクトマップは「インデックス=置き場所」で一意に決まります。照合は1回で速く安価ですが、同じインデックスへ写る別アドレスが交互に来ると毎回追い出し合う競合ミスが起きやすい。

フルアソシアティブはどのエントリにも置けるので競合ミスは原理上ゼロですが、全エントリのタグを並列照合する**連想メモリ（CAM）**が要り、容量を増やすほど高コスト・高消費電力です。TLB のような小容量機構で使われます。

セットアソシアティブは両者の折衷で、2^n 個のセットを設け各セットに N 本のウェイ（置き場所候補）を持ちます。インデックスでセットを選び、そのセット内の N 本だけを並列照合します。L1 で 8 ウェイ前後、L2/L3 で 16 ウェイ程度が一般的で、競合ミスを実用上十分に抑えつつコストを現実的に保ちます。同じ容量でもウェイ数を上げると競合ミスは減りますが、照合回路とヒット時間が増えるため、青天井ではありません。

置換ポリシー：何を追い出すか

セット内が埋まった状態でミスが起きると、既存ブロックを1本選んで追い出します（ダイレクトマップは選択の余地なし）。理想は「最も遠い未来に使われるブロック」を追い出すこと（Bélády の最適置換）ですが未来は不可知なので、過去から近似します。

LRU（Least Recently Used）は時間的局所性に最も忠実ですが、N ウェイの厳密な参照順序を毎アクセス更新するのは高コストです。そこで実機はPseudo-LRU（二分木状のビットで「どちら側が新しいか」だけを保持し、近似的に古い側を選ぶ）を多用します。N=4 なら 3bit で表現でき、更新も軽量です。

ミスの3C分類

ミスは原因で3種に分類すると設計の手がかりになります。

• Compulsory（初期参照ミス）: そのブロックを初めて触ったときのミス。キャッシュをどれだけ大きくしても消えません。ブロックを大きくする、あるいはプリフェッチで先回りして緩和します。
• Capacity（容量ミス）: 作業集合（ワーキングセット）がキャッシュ容量を超え、まだ使うブロックが追い出されて起きるミス。容量を増やすしかありません。
• Conflict（競合ミス）: 容量に余裕があっても、同じセットへ写るブロックが集中して追い出し合うために起きるミス。連想度を上げる、置換を賢くすることで減らせます。フルアソシアティブなら原理上ゼロです。

書き込み方式と一貫性

読み出しと違い、書き込みは「いつ主記憶へ反映するか」の選択が要ります。

• ライトスルー: 書き込みをキャッシュと主記憶へ同時に反映。実装が単純で下位階層が常に最新だが、書き込みのたびにメモリ帯域を消費します。書き込みバッファで遅延を隠すのが定石です。
• ライトバック: 書き込みはキャッシュにだけ行い、各ブロックにダーティビットを立てておく。追い出される時にダーティならまとめて書き戻します。メモリ書き込みを大幅に削減でき、現代の L1〜L3 の主流です。

書き込みミス時の扱いも対になります。ライトバックは通常 write-allocate（先にブロックを読み込んでから書く）、ライトスルーは no-write-allocate（主記憶へ直接書きキャッシュに載せない）と組み合わせます。

階層間の関係には**包含（inclusive）と排他（exclusive）**があります。包含は「上位にあるものは必ず下位にもある」と保証する方式で、他コアのスヌープ照合を下位だけで済ませられる利点があり、その代わり容量が重複します。排他は重複を許さず実効容量を稼ぎますが、階層間の移動管理が複雑になります。

仮想アドレスとの関係

キャッシュをタグ付け・索引するアドレスが仮想か物理かで、設計上のトレードオフがあります。物理アドレスでタグ付けするにはアドレス変換（TLB）を待つ必要があり、ヒット経路に変換遅延が乗ります。そこで L1 では「インデックスは仮想アドレスの下位ビットで先に引き、タグ照合は TLB が返した物理タグで行う」**VIPT（Virtually Indexed, Physically Tagged）**が広く使われます。インデックスをページオフセット内（変換で不変なビット）に収めれば、TLB 引きとインデックス引きを並列化でき、エイリアス問題も避けられます。

まとめ

• キャッシュは局所性を前提に、アドレスをタグ・インデックス・オフセットへ分解してブロック単位で索引する。
• 連想方式はダイレクトマップ・セットアソシアティブ・フルアソシアティブの順に配置自由度（＝競合ミス耐性）とコストが上がる。
• ミスは3C（初期参照・容量・競合）に分かれ、連想度と**置換ポリシー（LRU/Pseudo-LRU）**が主に競合ミスを左右する。
• 書き込みはライトバック＋ダーティビットが主流で、マルチコアでは MESI による一貫性管理が正しさを支える。

CPU 側でミスをどう隠すかはアウトオブオーダー実行とパイプラインハザードが、SRAM セルを成り立たせる素子はMOSFET の動作原理が掘り下げます。