キャッシュ置換ポリシーの深層 ─ LRUの近似からRRIPまで

置換は何を最小化したいのか

セットアソシアティブキャッシュでセットが埋まった状態でミスが起きると、そのセットの N 本のウェイから1本を選んで追い出します。理論上の最適は Bélády の MIN 置換、すなわち「最も遠い未来に再参照されるブロックを追い出す」ことです。未来は不可知なので、実機は過去のアクセス履歴から再参照の近さを推定します。置換ポリシーの良し悪しは、この推定がどれだけ MIN に近く、かつどれだけ安いハードで実現できるかで決まります。ヒット時間に乗る回路と、エントリあたりの状態ビットが実装コストの本体です。

キャッシュメモリの原理で触れた競合ミスの多くは、連想度だけでなく「どれを残すか」の判断で減らせます。ここではその判断アルゴリズムを掘り下げます。

真のLRUのコスト

LRU（Least Recently Used）は時間的局所性に最も忠実な近似で、「最も長く未参照のブロック」を追い出します。問題は厳密実装のコストです。N ウェイのセットで真の LRU を保つには、N 本の**全順序（最近使った順のランキング）**を保持しなければなりません。

• 状態ビット: N 本の順位を符号化するにはエントリあたり概ね N×log2(N) ビット要ります。N=16 なら 16×4=64 ビット/セット。これがセット数だけ要ります。
• 更新コスト: ヒットのたびに、参照したウェイを最上位へ繰り上げ、間にいたウェイの順位を1つずつ下げる「スタック更新」が必要です。これはヒットのクリティカルパスに乗ります。

このため真の LRU が現実的なのは N が小さいウェイ（4 程度まで）に限られ、16 ウェイ級の L2/L3 では採用されません。実機はほぼ例外なく近似します。

擬似LRU：ツリーとビット

実機の主流は LRU の近似です。代表が二種類あります。

Tree-PLRU は N 本のウェイを二分木の葉に並べ、各内部ノードに「最近アクセスされたのは左右どちらか」を示す1ビットを持ちます。N=4 なら 3 ビットで表せます。ヒット時はその葉までの経路上のビットを「反対側を指す」よう更新するだけ。追い出すときは根からビットの指す逆方向へ降りて葉を選びます。真の LRU と完全一致はしませんが、O(log N) の軽い更新で実用的な近似が得られ、L1/L2 で広く使われます。

Bit-PLRU（NRU; Not Recently Used） は各ウェイに1ビットの参照ビットを持ち、アクセス時に立てます。全ビットが立ったら（候補が尽きたら）一斉にクリアして再出発します。追い出しはビットが立っていないウェイから選びます。状態は N ビットと最小で、後述の RRIP はこの考え方を再参照予測へ一般化したものです。

なぜLRUはスキャンに弱いのか

LRU の致命的な弱点は、新規に挿入したブロックを暗黙に「最も最近使った＝最も長寿命」と仮定する点です。この仮定はアクセスパターンによって裏切られます。

どちらも根本は同じで、「新規ブロックを MRU（最長寿命）位置へ挿入する」既定の挿入規律が悪い、という点です。ここから挿入位置を変える改良が生まれます。

RRIP：再参照間隔を予測する

RRIP（Re-Reference Interval Prediction）は、各ブロックに M ビットの RRPV（Re-Reference Prediction Value） を持たせ、「このブロックが次に再参照されるまでの間隔」を予測します。値が大きいほど「遠い未来にしか使われない＝追い出してよい」を意味します。M=2 なら 0〜3 の4段階です。

挿入時:   RRPV ← 2（"long" 再参照間隔と予測。最大の3にはしない）
ヒット時: RRPV ← 0（"near-immediate"。再参照されたので残す）
追い出し: RRPV == 3 のウェイを左から探す
          無ければ全ウェイのRRPVを+1して再探索（飽和）

肝は挿入時に最大値(3)ではなく long(2)を入れること（SRRIP; Static RRIP）。こうすると、一度も再参照されないスキャンブロックは追い出し探索でまず +1 されて 3 に達し、すぐ追い出し候補になります。再参照されたブロックだけが RRPV=0 に下がって生き残るため、スキャンがホットなブロックを一掃する事態を防げます。NRU を「2ビットの寿命カウンタ」に一般化したものと見ると分かりやすいです。実装コストはエントリあたり M ビット（典型 2 ビット）と軽量です。

DRRIP：set duelingによる適応

SRRIP はスキャン耐性に優れますが、ワーキングセットがキャッシュより大きい純粋な容量ミス支配の状況では、もっと積極的に追い出す方が良いことがあります。そこで BRRIP（Bimodal RRIP） は、大多数のブロックを distant(3) で挿入し、ごく一部（例 1/32）だけ long(2) で挿入して「ほぼ即追い出し」気味に振る舞います。

問題はワークロードごとに SRRIP と BRRIP のどちらが勝つか事前に分からないこと。DRRIP はこれを実行時に決めます。

set dueling は方針選択を「ごく一部のセットでの実測勝負」に委ねる汎用テクニックで、後の多くの適応的置換・挿入の土台になりました。フォロワーが多数決の勝者に追従するため、ワークロードがスキャン的なら SRRIP、容量支配的なら BRRIP へと自動で寄ります。

SHiP：署名で再参照を学習する

DRRIP の挿入はセット全体で一律です。SHiP（Signature-based Hit Predictor） はもう一段細かく、「ブロックを持ち込んだ文脈」ごとに再参照されやすさを学習します。文脈の署名には、ミスを起こしたメモリアクセス命令の PC（命令アドレス）の一部や、メモリ領域、あるいはアクセス系列のハッシュを使います。

構造: 署名 → SHCT（Signature Hit Counter Table、飽和カウンタの配列）
挿入時: その署名のSHCT値が高い → 再参照されやすい → RRPV=0近くで挿入
        SHCT値が低い        → 再参照されにくい → distant(3)で挿入
学習:   ブロックが一度でもヒット → 署名のSHCTを+1
        一度も使われず追い出し   → 署名のSHCTを−1

ある PC のロードが持ち込むブロックが「いつも一回使ったきり」なら、その署名は低カウンタになり、以後その PC のブロックは最初から追い出し寄りに挿入されます。逆に再利用が多い PC のブロックは長寿命位置に置かれます。命令単位の振る舞いの違いを置換に反映できるため、SRRIP/DRRIP より高いヒット率を出すことが多く、各ブロックに署名を覚えておく数ビットと SHCT のテーブルが追加コストです。

コストとヒット率の見取り図

実機の選択は階層で変わります。ヒット時間が最優先の L1 では更新の軽い Tree-PLRU が好まれ、容量ミスとスキャンの両方に晒される大容量の LLC（L3）では RRIP 系や DRRIP/SHiP のような再参照予測が効きます。置換はプリフェッチ機構と相互作用する点も重要で、プリフェッチで持ち込んだ未確定のブロックを長寿命位置に入れると、的中しなかったとき有用なブロックを追い出してしまうため、プリフェッチブロックは控えめな RRPV で挿入する設計が一般的です。

まとめ

• 置換は MIN への近似精度と実装コストの綱引き。真の LRU は全順序保持のため N が大きいと非現実的で、実機は Tree-PLRU や NRU で近似する。
• LRU は新規ブロックを暗黙に長寿命と仮定するため、容量＋1の周期走査とスキャンに脆い。本質は挿入規律にある。
• RRIP は RRPV による再参照間隔予測で、挿入を long(2) にしてスキャン耐性を獲得する。DRRIP は set dueling で SRRIP/BRRIP を実測選択し、SHiP は命令署名で再参照されやすさを学習して挿入位置を最適化する。

置換は単独でなく、連想度・プリフェッチ・コヒーレンシと噛み合って初めてヒット率に効きます。設計では「どのウェイを追い出すか」と同じ重みで「新規ブロックをどの寿命位置に入れるか」を考えるのが現代的な勘所です。