キャッシュ置換ポリシー

コンピューティング において、キャッシュ置換ポリシー(キャッシュ置換アルゴリズムまたはキャッシュ アルゴリズムとも呼ばれる) は、コンピュータ プログラムまたはハードウェアで管理される構造が情報のキャッシュを管理するために使用できる最適化命令またはアルゴリズムです。キャッシュは、最近のデータ項目または頻繁に使用されるデータ項目を、通常のメモリ ストアよりも高速または計算コストのかからないメモリ位置に保持することで、パフォーマンスを向上させます。キャッシュがいっぱいになると、アルゴリズムは新しいデータのためのスペースを確保するためにどの項目を破棄するかを選択する必要があります。

平均記憶参照時間は^[1]

${\displaystyle T=m\times T_{m}+T_{h}+E}$

どこ

${\displaystyle m}$= ミス率 = 1 - (ヒット率)

${\displaystyle T_{m}}$= ミスがあった場合にメインメモリにアクセスする時間（または、マルチレベルキャッシュの場合は、次の下位のキャッシュの平均メモリ参照時間）

${\displaystyle T_{h}}$= レイテンシ: キャッシュを参照する時間 (ヒットとミスは同じである必要があります)

${\displaystyle E}$= マルチプロセッサシステムにおけるキューイング効果などの二次的影響

キャッシュには、レイテンシとヒット率という2つの主要な指標があります。また、キャッシュのパフォーマンスに影響を与える二次的な要因も数多くあります。^[1]

キャッシュのヒット率は、検索されたアイテムが見つかる頻度を表します。より効率的な置換ポリシーは、より多くの使用情報を追跡して、特定のキャッシュ サイズのヒット率を向上させます。キャッシュのレイテンシは、ヒットがあった場合に、目的のアイテムを要求してからキャッシュがそのアイテムを返すまでの時間を表します。より高速な置換戦略では、通常、より少ない使用情報 (または、直接マップされたキャッシュの場合は情報なし) を追跡して、情報の更新に必要な時間を短縮します。各置換戦略は、ヒット率とレイテンシの間の妥協点です。

ヒット率の測定は通常、ベンチマークアプリケーションで実行され、ヒット率はアプリケーションによって異なります。ビデオやオーディオのストリーミング アプリケーションでは、ヒット率がほぼ 0 になることがよくあります。これは、ストリーム内のデータの各ビットが 1 回読み取られ (強制ミス)、使用され、その後は再び読み取られたり書き込まれたりしないためです。多くのキャッシュ アルゴリズム (特にLRU ) では、ストリーミング データがキャッシュを埋め尽くし、すぐに再び使用される情報が押し出されます (キャッシュ汚染)。^[2]その他の要因としては、サイズ、取得にかかる時間、有効期限などが挙げられます。キャッシュ サイズによっては、アイテムを破棄するためのキャッシュ アルゴリズムがさらに必要ない場合もあります。複数のデータベース サーバーが共有データ ファイルを更新する場合など、同じデータに複数のキャッシュが使用される場合にも、アルゴリズムによってキャッシュの一貫性が維持されます。

最も効率的なキャッシュ アルゴリズムは、最も長い間必要とされない情報を破棄することです。これは、Béládyの最適アルゴリズム、最適置換ポリシー、または千里眼アルゴリズムとして知られています。一般に、情報が必要になる時期を予測することは不可能であるため、これは実際には実現不可能です。実用的な最小値は実験後に計算でき、選択したキャッシュ アルゴリズムの有効性を比較できます。

ページ フォールトが発生すると、一連のページがメモリ内にあります。例では、5、0、1 のシーケンスは、それぞれフレーム 1、フレーム 2、フレーム 3 によってアクセスされます。2 にアクセスすると、値 5 (フレーム 1 にあります) が置き換えられ、値 5 は近い将来にアクセスされないことが予測されます。汎用オペレーティング システムでは 5 がいつアクセスされるかを予測できないため、Bélády のアルゴリズムをそこに実装することはできません。

ランダム置換は、必要に応じてアイテムを選択し、それを破棄してスペースを確保します。このアルゴリズムでは、アクセス履歴を保持する必要がありません。このアルゴリズムはシンプルであるため、ARMプロセッサで使用されており、 ^{[3]効率的な}確率的シミュレーションを可能にします。^[4]

このアルゴリズムでは、キャッシュはFIFO キューのように動作し、以前にアクセスされた頻度や回数に関係なく、追加された順序でブロックを削除します。

キャッシュはスタックのように動作し、FIFO キューとは異なります。キャッシュは、以前にアクセスされた頻度や回数に関係なく、最後に追加されたブロックを最初に削除します。

SIEVE は、キーバリューキャッシュやコンテンツ配信ネットワークなどの Web キャッシュ専用に設計されたシンプルな削除アルゴリズムです。これは、遅延昇格と迅速な降格という考え方を採用しています。^[5]そのため、SIEVE はキャッシュヒット時にグローバルデータ構造を更新せず、削除時まで更新を遅らせます。一方、キャッシュワークロードは一発屋比率が高く、新しいオブジェクトのほとんどはキャッシュに保持する価値がないため、新しく挿入されたオブジェクトはすぐに削除されます。SIEVE は単一の FIFO キューを使用し、移動する手を使用して削除するオブジェクトを選択します。キャッシュ内のオブジェクトには、オブジェクトがキャッシュに受け入れられた後に要求されたかどうかを示す 1 ビットのメタデータがあります。削除手は最初はキューの末尾を指し、時間の経過とともに先頭に向かって移動します。CLOCK 削除アルゴリズムと比較すると、SIEVE で保持されたオブジェクトは古い位置に留まります。したがって、新しいオブジェクトは常に先頭にあり、古いオブジェクトは常に末尾にあります。手が頭に向かって動くと、新しいオブジェクトはすぐに追い出されます（クイックデモーション）。これがSIEVEの追い出しアルゴリズムの高効率の鍵です。SIEVEはLRUよりもシンプルですが、最先端の追い出しアルゴリズムと同等のLRUよりも低いミス率を達成しています。さらに、定常の偏ったワークロードでは、SIEVEはLFUを含む既存の既知のアルゴリズムよりも優れています。^[6]

最も最近使用されていない項目を最初に破棄します。このアルゴリズムでは、何がいつ使用されたかを追跡する必要があり、面倒です。キャッシュ ラインの「経過時間ビット」が必要で、これらの経過時間ビットに基づいて最も最近使用されていないキャッシュ ラインを追跡します。キャッシュ ラインが使用されると、他のキャッシュ ラインの経過時間が変わります。LRU は、Theodore Johnson と Dennis Shasha による 2Q ^{[7]や、Pat O'Neil、Betty O'Neil、Gerhard Weikum による LRU/K [8]}を含むキャッシュ アルゴリズムのファミリです。この例のアクセス シーケンスは ABCDEDF です。

ABCD がシーケンス番号 (新しいアクセスごとに 1 ずつ増加) を持つブロックにインストールされ、E がアクセスされると、ミスとなり、ブロックにインストールする必要があります。LRU アルゴリズムでは、A のランクが最も低い (A(0)) ため、E が A を置き換えます。最後から 2 番目のステップでは、D にアクセスし、シーケンス番号が更新されます。次に、F にアクセスし、ランクが最も低い (B(1)) B を置き換えます。

時間を考慮した、最も最近使われていない (TLRU) ^{[9] は、}キャッシュの内容に有効な寿命がある場合に設計された LRU の変種です。このアルゴリズムは、情報中心ネットワーク(ICN)、コンテンツ配信ネットワーク(CDN)、一般的な分散ネットワークなどのネットワーク キャッシュ アプリケーションに適しています。TLRU では、TTU (time to use) という用語が導入されています。これは、コンテンツ (またはページ) のタイムスタンプであり、その場所とコンテンツ発行者に基づいて、コンテンツの使用時間を規定します。TTU により、ネットワーク ストレージを制御するローカル管理者に、より詳細な制御が提供されます。

TLRU の対象となるコンテンツが到着すると、キャッシュノードはコンテンツ パブリッシャーによって割り当てられた TTU に基づいてローカル TTU を計算します。ローカル TTU 値は、ローカルで定義された関数を使用して計算されます。ローカル TTU 値が計算されると、キャッシュ ノードの全コンテンツのサブセットに対してコンテンツの置き換えが実行されます。TLRU により、人気のないコンテンツや寿命の短いコンテンツが、到着したコンテンツに置き換えられます。

LRU とは異なり、MRU は最近使用されたアイテムを最初に破棄します。第 11 回VLDB カンファレンスで、Chou 氏と DeWitt 氏は「ファイルが [ループする順次] 参照パターンで繰り返しスキャンされている場合、MRU は最適な置換アルゴリズムです」と述べました。^[10]第 22 回 VLDB カンファレンスで発表した研究者は、ランダム アクセス パターンと大規模なデータセットの繰り返しスキャン(循環アクセス パターンとも呼ばれます) の場合、MRU キャッシュ アルゴリズムは古いデータを保持する傾向があるため、LRU よりもヒット数が多いことを指摘しました。^[11] MRU アルゴリズムは、アイテムが古いほどアクセスされる可能性が高い状況で最も役立ちます。この例のアクセス シーケンスは ABCDECDB です。

ABCD は、空きスペースがあるため、キャッシュ内に配置されます。5 回目のアクセス (E) では、D を保持していたブロックが E に置き換えられます。このブロックは最近使用されたためです。次のアクセス (D へ) では、D の直前にアクセスされたブロックであったため、C が置き換えられます。

SLRU キャッシュは、試用セグメントと保護セグメントの 2 つのセグメントに分かれています。各セグメントの行は、最近アクセスされたものから最近アクセスされなかったものの順に並べられています。ミスのデータは、試用セグメントの最近アクセスされた側のキャッシュに追加されます。ヒットは、その場所から削除され、保護セグメントの最近アクセスされた側のキャッシュに追加されます。保護セグメントの行は、少なくとも 2 回アクセスされています。保護セグメントは有限です。試用セグメントから保護セグメントに行を移行すると、保護セグメントの LRU 行が試用セグメントの最近使用された側のキャッシュに移行される可能性があり、この行は置き換えられる前にもう一度アクセスされる可能性があります。保護セグメントのサイズ制限は、I/Oワークロード パターンに応じて変化する SLRU パラメータです。キャッシュからデータを破棄する必要がある場合、試用セグメントの LRU 側のキャッシュから行が取得されます。^[12]

LRU は、連想度の高いキャッシュではコストが高くなる可能性があります。実際のハードウェアでは通常、より低いハードウェア コストで同様のパフォーマンスを実現するために近似値が使用されます。

大規模な連想性(一般に 4 ウェイ以上)を持つCPU キャッシュの場合、LRU の実装コストは法外なものになります。多くの CPU キャッシュでは、最も最近使用されていない項目の 1 つをほぼ常に破棄するアルゴリズムで十分です。多くの CPU 設計者は、キャッシュ項目ごとに 1 ビットのみで動作する PLRU アルゴリズムを選択します。通常、PLRU はミス率がわずかに悪く、レイテンシがわずかに短く、LRU よりも消費電力がわずかに少なく、オーバーヘッドがLRU よりも低くなります。

ビットは、最近あまり使用されていないサブツリーを指す 1 ビット ポインターのバイナリ ツリーとして機能します。リーフ ノードへのポインター チェーンをたどると、置換候補が識別されます。アクセスでは、アクセスされたウェイのリーフ ノードからルート ノードまでのチェーン内のすべてのポインターが、アクセスされたパスを含まないサブツリーを指すように設定されます。例のアクセス シーケンスは ABCDE です。

値 (A など) へのアクセスがあり、それがキャッシュ内にない場合は、メモリからロードされ、例で矢印が指しているブロックに配置されます。そのブロックが配置された後、矢印は反対方向を指すように反転されます。A、B、C、および D が配置されます。キャッシュがいっぱいになると、矢印が指していた場所が A であったため、E が A に置き換わり、A につながる矢印は反対方向 (次のキャッシュ ミスで置き換えられるブロック B) を指すように反転します。

LRUアルゴリズムは、オーバーヘッドが大きいため、オペレーティングシステムなどのコンピュータシステムのクリティカルパスには実装できません。代わりに、LRUの近似であるClockが一般的に使用されます。Clock-Proは、システムでの低コストの実装のためのLIRSの近似です。 ^[13] Clock-Proは基本的なClockフレームワークを持ち、3つの利点があります。3つの「時計の針」があり（Clockの1つの「針」とは異なり）、データアクセスの再利用距離を概算で測定できます。LIRSと同様に、1回限りのアクセスまたは低局所性のデータ項目をすばやく削除できます。Clock-ProはClockと同じくらい複雑ですが、低コストで簡単に実装できます。2017バージョンのLinuxのバッファキャッシュ置換実装は、LRUとClock-Proを組み合わせています。^{[14] [15]}

LFU アルゴリズムは、アイテムが必要とされる頻度をカウントします。あまり使用されないアイテムは最初に破棄されます。これは LRU に似ていますが、ブロックが最近アクセスされた回数ではなく、アクセスされた回数が保存される点が異なります。アクセス シーケンスの実行中、最も使用回数の少ないブロックがキャッシュから削除されます。

最も使用頻度の低い最近のデータ（LFRU）^[16]アルゴリズムは、LFUとLRUの利点を組み合わせたものです。LFRUは、ICN、CDN、分散ネットワークなどのネットワークキャッシュアプ​​リケーションに適しています。LFRUでは、キャッシュは特権パーティションと非特権パーティションの2つのパーティションに分割されます。特権パーティションは保護されており、コンテンツが人気がある場合は特権パーティションにプッシュされます。特権パーティションを置き換える際、LFRUは非特権パーティションからコンテンツを追い出し、特権パーティションから非特権パーティションにコンテンツをプッシュし、特権パーティションに新しいコンテンツを挿入します。特権パーティションにはLRUが使用され、非特権パーティションには近似LFU（ALFU）アルゴリズムが使用されます。

バリアントである動的エージング付き LFU (LFUDA) は、動的エージングを使用して、人気のあるオブジェクトのセット内のシフトに対応します。新しいオブジェクトがキャッシュに追加されたとき、または既存のオブジェクトが再参照されたときに、参照カウントにキャッシュ経過時間係数を追加します。LFUDA は、ブロックを削除するときに、削除されたオブジェクトのキー値に設定してキャッシュ経過時間を増分します。キャッシュ経過時間は常に、キャッシュ内の最小キー値以下になります。^[17]オブジェクトが過去に頻繁にアクセスされ、人気がなくなった場合、そのオブジェクトはキャッシュに長期間残ります (新しいオブジェクトや人気のないオブジェクトがそのオブジェクトを置き換えるのを防ぎます)。動的エージングにより、そのようなオブジェクトの数が減り、置き換え可能になります。また、LFUDA は、キャッシュが小さいときに LFU によって引き起こされる キャッシュ汚染を軽減します。

これは 2023 年に設計された新しい削除アルゴリズムです。主に LRU (最近最も使用されていない) に基づいて構築されている既存のアルゴリズムと比較して、S3-FIFO は 3 つの FIFO キューのみを使用します。キャッシュ スペースの 10% を占める小さなキュー、キャッシュ スペースの 90% を使用するメイン キュー、およびオブジェクトのメタデータのみを格納するゴースト キューです。小さなキューは、一発屋 (短時間で 1 回しかアクセスされないオブジェクト) を除外するために使用されます。メイン キューは、人気のあるオブジェクトを格納するために使用され、再挿入を使用してキャッシュに保持します。ゴースト キューは、小さなキューから削除された、人気のある可能性のあるオブジェクトをキャッチするために使用されます。オブジェクトは最初に小さなキューに挿入されます (ゴースト キューで見つからない場合は、メイン キューに挿入されます)。小さなキューから削除されると、オブジェクトが要求されている場合はメイン キューに再挿入され、そうでない場合は削除され、メタデータはゴースト キューで追跡されます。^[18]

S3-FIFOは、FIFOキューが効率的でスケーラブルなエビクションアルゴリズムを設計するのに十分であることを示しています。LRUおよびLRUベースのアルゴリズムと比較して、S3-FIFOは6倍のスループットを達成できます。さらに、Webキャッシュワークロードでは、S3-FIFOは著者が比較した11の最先端のアルゴリズムの中で最も低いミス率を達成しました。^[19]

RRIPスタイルのポリシーは、Hawkeyeを含む他のキャッシュ置換ポリシーの基礎となっています。^[20]

RRIP ^[21]はIntelが提案した柔軟なポリシーで、再利用されていない古いキャッシュラインの削除を許可しながら、優れたスキャン耐性を提供しようとします。すべてのキャッシュラインには、ラインが再利用されると予想される時期と相関する予測値、RRPV（再参照予測値）があります。RRPVは通常、挿入時に高くなります。ラインがすぐに再利用されない場合は、スキャン（一度だけ使用される大量のデータ）によってキャッシュがいっぱいになるのを防ぐために、そのラインは削除されます。キャッシュラインが再利用されると、RRPVはゼロに設定され、そのラインが一度再利用され、再び再利用される可能性が高いことを示します。

キャッシュ ミスが発生すると、RRPV が最大 RRPV に等しい行が削除されます。3 ビット値の場合、RRPV が 2 ³ - 1 = 7 の行が削除されます。この値を持つ行がない場合、セット内のすべての RRPV が 1 ずつ増加され、いずれかがこの値に達するまで続きます。タイ ブレーカーが必要で、通常は左側の最初の行です。増加は、古い行が適切に古くなり、再利用されない場合は削除されるようにするために必要です。

SRRIP は、RRPV 値が maxRRPV の行を挿入します。挿入されたばかりの行は、キャッシュ ミスで削除される可能性が最も高くなります。

SRRIP は通常はうまく機能しますが、ワーキング セットがキャッシュ サイズよりはるかに大きい場合はパフォーマンスが低下し、キャッシュ スラッシングが発生します。この問題は、ほとんどの場合に RRPV 値が maxRRPV の行を挿入し、低い確率で RRPV 値が maxRRPV - 1 の行をランダムに挿入することで解決します。これにより、一部の行がキャッシュに「固定」され、スラッシングを防止できます。ただし、BRRIP はスラッシングのないアクセスではパフォーマンスが低下します。SRRIP はワーキング セットがキャッシュより小さい場合に最もパフォーマンスが高く、BRRIP はワーキング セットがキャッシュより大きい場合に最もパフォーマンスが高くなっています。

DRRIP ^[21]はセットデュエル^[22]を使用してSRRIPとBRRIPのどちらを使用するかを選択します。DRRIPでは、いくつかのセット（通常32）をSRRIP専用にし、別のいくつかのセットをBRRIP専用にし、セットのパフォーマンスを監視するポリシーカウンタを使用して、残りのキャッシュでどのポリシーを使用するかを決定します。

Béládyのアルゴリズムは最適なキャッシュ置換ポリシーですが、将来最も再利用される行を削除するには将来の知識が必要です。過去のアクセスパターンから将来の再利用距離を予測し、^[23]最適な置換ポリシーに近似する置換ポリシーが数多く提案されています。最も優れたパフォーマンスを発揮するキャッシュ置換ポリシーの中には、Béládyのアルゴリズムを模倣しようとするものがあります。

Hawkeye ^[20]は、PC による過去のアクセスを使用して、生成されるアクセスがキャッシュ フレンドリー (後で使用される) アクセスを生成するか、キャッシュ アバース アクセス (後で使用されることがない) を生成するかを予測することで、Bélády のアルゴリズムをエミュレートしようとします。これは、非整列キャッシュ セットの数をサンプリングし、長さの履歴を使用して、これらのアクセスに対して Bélády のアルゴリズムをエミュレートします。これにより、ポリシーは、どの行をキャッシュする必要があり、どの行をキャッシュしない必要があるかを決定し、命令がキャッシュ フレンドリーかキャッシュ アバースかを予測できます。このデータは、次に RRIP に送られます。キャッシュ フレンドリー命令からのアクセスは RRPV 値が低く (後で削除される可能性が高い)、キャッシュ アバース命令からのアクセスは RRPV 値が高くなります (より早く削除される可能性が高い)。RRIP バックエンドが削除の決定を行います。サンプリングされたキャッシュとOPTジェネレーターは、挿入されたキャッシュ ラインの初期 RRPV 値を設定します。 Hawkeyeは2017年にCRC2キャッシュチャンピオンシップを獲得しました^[24]。Harmony ^[25]はHawkeyeの拡張版であり、プリフェッチ性能を向上させます。 ${\displaystyle 8\times {\text{キャッシュサイズ}}}$

Mockingjay ^[26]は、いくつかの点でHawkeyeの改良を試みた。バイナリ予測を廃止し、どのキャッシュラインを削除するかをより細かく決定できるようにし、どのキャッシュラインを削除するかの決定は、より多くの情報が利用可能になったときに行うようにした。

Mockingjay は、一意のアクセス、それを生成した PC、およびそれらのタイムスタンプのサンプル キャッシュを保持します。サンプル キャッシュ内の行が再度アクセスされると、その時間差が再利用距離予測器に送信されます。RDP は時間差学習^[27]を使用し、外れ値を補正するために新しい RDP 値が小さな数値だけ増減します。この数値は次のように計算されます。値が初期化されていない場合は、観測された再利用距離が直接挿入されます。サンプル キャッシュがいっぱいで行を破棄する必要がある場合、RDP は、最後にアクセスした PC がストリーミング アクセスを生成するように指示されます。 ${\displaystyle w=\min \left(1,{\frac {\text{タイムスタンプ差}}{16}}\right)}$

アクセスまたは挿入時に、この行の推定再利用時間 (ETR) は、予測された再利用距離を反映するように更新されます。キャッシュ ミスが発生すると、ETR 値が最も高い行が削除されます。Mockingjay の結果は、最適な Bélády アルゴリズムに近いものになります。

多くのポリシーでは、パーセプトロン、マルコフ連鎖、またはその他の種類の機械学習を使用して、どの行を削除するかを予測しようと試みてきました。^{[28] [29]キャッシュの置き換えのための} 学習拡張アルゴリズムも存在します。 ^{[30] [31]}

LIRSは、LRUやその他の新しい置換アルゴリズムよりも優れたパフォーマンスを備えたページ置換アルゴリズムです。再利用距離は、アクセスされたページを動的にランク付けして置換を決定するための指標です。^[32] LIRSは、最新性を使用して相互参照最新性（IRR）を評価し、置換を決定することで、LRUの限界に対処します。

図の X は、特定の時間にブロックがアクセスされることを示します。ブロック A1 が時間 1 にアクセスされた場合、その最新性は 0 になります。これは最初にアクセスされたブロックであり、時間 3 に A1 が再度アクセスされると予測されるため、IRR は 1 になります。時間 2 では、A4 がアクセスされるため、A4 の最新性は 0 になり、A1 の最新性は 1 になります。A4 は最後にアクセスされたオブジェクトであり、IRR は 4 になります。時間 10 では、LIRS アルゴリズムには 2 つのセットがあります。LIR セット = {A1、A2} と HIR セット = {A3、A4、A5} です。時間 10 で A4 へのアクセスがあるとミスが発生します。LIRS は、最新性が高い A5 を A2 ではなく排除します。

適応型置換キャッシュ（ARC）は、LRUとLFUのバランスを常に保って、組み合わせた結果を改善します。^[33]最近削除されたキャッシュ項目に関する情報を使用して、保護されたセグメントと試用セグメントのサイズを調整し、利用可能なキャッシュスペースを最大限に活用することで、SLRUを改善します。^[34]

適応型置換機能付きクロック(CAR) は、ARC とクロックの利点を組み合わせたものです。CAR のパフォーマンスは ARC と同等で、LRU やクロックよりも優れています。ARC と同様に、CAR は自己調整型であり、ユーザー指定のパラメータは必要ありません。

マルチキュー置換（MQ）アルゴリズムは、サーババッファキャッシュなどの第2レベルバッファキャッシュのパフォーマンスを向上させるために開発され、Zhou、Philbin、Liの論文で紹介されました。^[35] MQキャッシュには、 m個のLRUキュー（Q ₀、Q ₁、...、Q _{m -1 ）が含まれています}。mの値は、そのキュー内のすべてのブロックの存続期間に基づく階層を表します。^[36]

Pannier ^[37]はコンテナベースのフラッシュキャッシュ機構であり、ブロックのアクセスパターンが可変のコンテナを識別する。Pannierは優先度キューベースの生存キュー構造を持ち、コンテナ内のライブデータに比例する生存時間に基づいてコンテナをランク付けする。

静的解析では、どのアクセスがキャッシュヒットかミスかを判断し、プログラムの最悪実行時間を示します。 ^[38] LRUキャッシュの特性を解析するアプローチとして、キャッシュ内の各ブロックに「年齢」（最近使用した場合は0）を与え、考えられる年齢の間隔を計算する方法があります。^[39]この解析は、ミスまたはヒットにつながるパスから同じプログラムポイントにアクセスできるケースを区別するように改良できます。^{[40]キャッシュ状態のセットを、コンパクトな}二分決定図で表されるアンチチェーンで抽象化することで、効率的な解析が得られます。^[41]

LRU静的解析は疑似LRUポリシーには適用されない。計算複雑性理論によれば、疑似LRUとFIFOによってもたらされる静的解析問題は、LRUの場合よりも高い複雑性クラスに属する。 ^{[42] [43]}

• キャッシュ無視アルゴリズム
• 分散キャッシュ

• さまざまなキャッシュアルゴリズムの定義
• フラッシュ/SSDのキャッシュアルゴリズム