メモリ階層の包含/排他/非包含設計

階層をどう「重ねる」かという設計問題

L1・L2・L3 という複数階層のキャッシュを積むとき、上位（コアに近い小容量）に載っているラインを下位（大容量）がどう扱うかには自由度があります。同じ L1+L2+L3 のトータル SRAM 量でも、その重なり方の規約次第で、利用できる実効容量も、マルチコアのスヌープにかかる負荷も大きく変わります。この規約が**包含ポリシー（inclusion policy）**で、inclusive・exclusive・non-inclusive non-exclusive (NINE) の3種に分かれます。

ここでの「上位/下位」は包含関係を語る向きで、コアに近い L1 を上位、共有 L3 を下位（最終段、LLC）と呼びます。議論は主に「LLC が上位の私有キャッシュ群をどう内包するか」に集約されます。

3ポリシーの定義

包含は「上位（L1/L2）に存在するブロックは必ず下位（L3）にも存在する」を不変条件として保つ方式です。L3 がコア群の全保持内容のスーパーセットになります。排他は逆に重複を禁じ、あるラインはどの一瞬も L2 か L3 のどちらか一方にだけ置きます。NINE はどちらも強制しません。上位にあるラインが下位に「あってもなくてもよい」状態を許し、たまたま重複することもあれば、しないこともあります。Intel の多くの世代の LLC は包含、近年のサーバー向けでは非包含/排他寄りへ、というように世代と用途で選択が分かれてきました。

包含の利点：スヌープフィルタ効果

包含が長く好まれた最大の理由は、コヒーレンスのスヌープ照合を下位タグだけで完結できる点にあります。あるコアからの読み書きで他コアがそのラインを持つか調べたいとき、包含なら「L3 にそのラインのタグが無ければ、どのコアの L1/L2 にも存在しない」と即断できます。L3 が全コアの保持集合のスーパーセットだからです。

包含時の他コアスヌープ:
  L3 を引く
    タグ無し  → どのコアも未保持と確定（上位への問い合わせ不要）
    タグ有り  → 該当コアにだけスヌープを送る

これにより、関係ないコアの L1/L2 を一々叩かずに済み、オンチップネットワークのスヌープトラフィックと電力を抑えられます。L3 タグが事実上のスヌープフィルタとして無料で手に入る、という構図です。コヒーレンスの追跡方式そのものはディレクトリベースのキャッシュコヒーレンスが扱いますが、包含の下位タグはそのディレクトリ的な役割を兼ねられます。

包含のコスト：容量重複とバックインバリデーション

利点の裏返しとして、包含には2つの代償があります。

第一に容量の重複です。L1/L2 にあるものは L3 にも必ず複製されるため、L3 の一部は上位のコピーで埋まり、実効容量はトータルの SRAM 量より小さくなります。LLC が私有キャッシュ合計に対して十分大きくないと、包含の維持コストが顕在化します。経験則として「L3 容量が L1+L2 合計の数倍以上」でないと包含は割に合いにくいとされます。

第二に**バックインバリデーション（back-invalidation）**です。包含の不変条件「上位 ⊆ 下位」を保つには、下位があるラインを追い出すとき、上位に残るそのコピーも同時に無効化しなければなりません。さもないと「上位にあるのに下位に無い」という違反状態が生じます。

排他の利点：実効容量を稼ぐ

排他はラインを1階層にしか置かないため、重複が無く、実効容量が概ね各階層容量の単純和まで伸びます。L2 が 1MB、L3 が 8MB なら、排他では実効的に約 9MB ぶんの異なるラインを保持できますが、包含では L3 の 8MB の中に L2 の 1MB が複製されるため、異なるラインは最大 8MB ぶんに留まります。小さめの LLC で容量効率を最大化したい構成（AMD が伝統的に好んだ方式）で有利です。

挙動上の特徴は、ヒットしたラインの移動です。排他では、上位がミスして下位でヒットすると、そのラインは下位から消され上位へ移されます（fill）。上位から追い出されたラインは下位へ書き戻されます（victim を受ける）。つまり下位 LLC はビクティムキャッシュ的に振る舞い、上位から溢れたものを引き受けます。

排他時の L2 ミス → L3 ヒット:
  L3 から該当ラインを読み出す
  L3 側の当該コピーを無効化（重複禁止）
  L2 へ充填
  L2 から押し出されたビクティムを L3 へ移す

排他・NINE のコスト：フィルタを失う

排他と NINE の弱点は、下位タグだけでは上位の存在を保証できないことです。あるラインが上位に居ても下位には無いことがあるため、「L3 にタグが無い」では他コアの未保持を断定できません。結果として包含のような無料のスヌープフィルタが成立せず、コヒーレンスのために別建ての追跡機構が必要になります。

NINE はさらに、上位ラインを下位が必ずしも持たないため、下位の追い出し時にバックインバリデーションが「不要」になる利点があります（包含の不変条件が無いので、下位が捨てても上位は健在で構わない）。容量効率と実装の単純さのバランスが良く、明示的なライン移動を要する排他より管理が軽い局面で選ばれます。

コヒーレンスとの相互作用

包含ポリシーはコヒーレンスプロトコル（MESI など）と密に絡みます。包含の不変条件を保つには、追い出しと無効化の伝播経路を正しく設計しなければなりません。たとえば下位の追い出しに伴うバックインバリデーションで、上位にダーティ（Modified）コピーがあれば、ただ無効化するのではなく先に書き戻してから無効化する必要があります。さもないと最新値を失います。

複数ソケットにまたがる構成では、この所在情報の管理はソケット間コヒーレントインターコネクトのレイヤへ拡張されます。また、包含の有無はフォルスシェアリングとキャッシュ競合の挙動にも影響し、バックインバリデーションが余計な再ミスを誘発する経路を生みます。

トレードオフの整理

要点は「包含はスヌープを簡単にする代わりに容量を捨て、排他は容量を稼ぐ代わりにスヌープと移動を複雑にする」という対称的なトレードオフです。NINE はその中間で、近年は独立スヌープフィルタの普及によって、容量効率と実装簡素さを両取りしやすくなりました。容量比（下位÷上位）が大きいほど包含の不利は薄れ、小さいほど排他/NINE の容量メリットが効く、という軸で選択を捉えると見通しが良くなります。

まとめ

• 包含・排他・NINE は、上位キャッシュのラインを下位がどう内包するかの規約で、実効容量とコヒーレンス負荷を左右する。
• 包含は下位タグが無料のスヌープフィルタになる一方、容量が重複し、下位の追い出しが上位へバックインバリデーションを波及させる。
• 排他は実効容量を各階層容量の和近くまで稼ぐが、フィルタ効果を失い、ヒット時のライン移動・交換が増える。
• NINE は中庸で、独立スヌープフィルタと組み合わせることで容量効率とスヌープ絞り込みを両立しやすい。
• いずれもコヒーレンスと密結合で、特に包含維持の追い出しでは「書き戻し→無効化」の順序保証が正しさの鍵になる。