わけあってHigh Performance Cache Replacement Using Re-Reference Interval Prediction (RRIP) という論文を読んでいる。
キャッシュアクセスの分類について。
- recency-friendlyアクセス・パターン : [tex: $(a_1, a_2, …, a_{k_1}, a_k, a_{k-1}, …, a_2, a_1)N$]
- 図1aは、 $N$ 回繰り返す典型的なスタック・アクセス・パターンを示している。一般に、再利用しやすいアクセス・パターンは、ほぼ即時の再参照間隔を持つ。kがどのような値であっても、このアクセスパターンはLRU置換の恩恵を受ける。LRU以外の置換ポリシーは、これらのアクセスパターンのパフォーマ ンスを低下させる可能性がある。
- スラッシング・アクセス・パターン：$(a_1, a_2, …, a_k)N$
- 図1bは、N回繰り返す長さkの周期的アクセスパターンを示している。$k$がキャッシュ内のブロック数以下の場合、作業セットはキャッシュに収まる。しかし、$k$がキャッシュ・ブロック数より大きい場合、LRUはキャッシュ・スラッシングによりゼロ・キャッシュ・ヒットを受け取る。このようなパターンの場合、LRUは、アクセス・パターンのすべての$k$エントリを保持するためにキャッシュ・サイズを大きくしない限り、キャッシュ・ヒットを提供しない。利用可能なキャッシュが$k$エントリ未満の場合、最適な置換ポリシーはキャッシュ内の作業セットの一部を保存する。残念ながら、LRUにはそれができない。
- ストリーミング・アクセス・パターン：$(a_1, a_2, a_3, a_4, … a_k)$
- 図1cは、ストリーミング・アクセス・パターンを示している。k = ∞のとき、このアクセスパターンは参照に局所性を持たない。ストリーミングアクセスパターンは、無限の再参照間隔を持つ作業負荷として特徴付けることができる。その結果、ストリーミング・アクセス・パターンは、どのような置換ポリシーにおいてもキャッシュ・ヒットを受けない。その結果、ストリーミング・アクセス・パターンが存在する場合、置き換えの決定は無関係であるため、LRUは適切である。
- 混合アクセスパターン：
- 混合アクセスパターンは、ある参照はほぼ即時の再参照間隔を持ち、他の参照は遠い再参照間隔を持つ作業負荷として特徴付けることができる。図1dは、スキャンを持つ2つのアクセスパターン例（図中、グレーのボックスで強調表示）を用いてこれを示している。どちらの例も、長さkのアクセスパターンがA回繰り返され、その後に長さmのシーケンスが確率εで参照される。最初の参照パターンは、m個のエントリーを持つリンクリストに対して操作を実行するアプリケーションを代表する。最初のスタック参照パターンは、リンクリストの先頭に時間的な局所性を持つ操作を示す。スキャンは、リスト全体を走査する必要がある検索または更新操作を示す。番目の例は、kエントリーのデータ構造を操作した後、mエントリーの別のデータ 構造を更新するアプリケーションを表している。どちらのアクセスパターンでも、m + kが利用可能なキャッシュより小さい場合、作業セット全体がキャッシュに収まり、LRUはうまく機能する。しかし、m + kが利用可能なキャッシュより大きい場合、LRUは頻繁に参照される作業セットをキャッシュから破棄する。その結果、頻繁に参照される作業セットへのアクセスは、スキャン後に常にミスする。スキャンがない場合、混合アクセスパターンはLRUを好む。 しかし、スキャンがある場合、最適なポリシーはスキャン完了後にキャッシュ内のアクティブな作業セットを保持する。 残念ながら、LRUはアクティブな作業セットを保持できない。
4.3. ダイナミックRRIP（DRRIP）
SRRIPは、全ブロックの再参照間隔が利用可能なキャッシュより大きい場合、キャッシュを非効率的に利用する。このようなシナリオでは、SRRIPはキャッシュスラッシングを引き起こし、キャッシュヒットが発生しない。キャッシュスラッシングを回避するために、再参照間隔が遠い（すなわち、RRPVが2M-1）と予測されるキャッシュブロックの大部分を挿入し、再参照間隔が長い（すなわち、RRPVが2M-2）と予測される新しいキャッシュブロックを（低確率で）まれに挿入するバイモーダルRRIP（BRRIP）を提案する。BRRIPはDIPのBIP（Bimodal Insertion Policy）[25]コンポーネントに類似しており、キャッシュ内の作業セットの一部を保持するのに役立つ。
非スラッシング・アクセス・パターンの場合、常にBRRIPを使用すると、キャッ シュ・パフォーマンスが著しく低下する可能性がある。すべてのキャッシュ・アクセス・パターンに対応するために、アプリケーションに最適なSRRIPとBRRIPを動的に決定することを提案する。我々は、セットデュエリング[25]を使用して、アプリケーションに最適な置換ポリシーを特定する動的再参照間隔予測(DRRIP)を提案する。DRRIPは、2つのセット・デュエル・モニター（SDM）[11]を使用することで、スキャン耐性SRRIPとスラッシュ耐性BRRIPを動的に選択する。SDMは、キャッシュの数セット5を恒久的にそのポリシーに従うようにすることで、任意のポリシーのミスを推定する。セット決闘は、単一のポリシー選択（PSEL）カウンタを使用して、勝利ポリシーを決定する。DRRIPは、キャッシュの残りのセットに対して、2つのSDMのうち勝利したポリシーを使用する。
