キャッシュアルゴリズム
確率的にほぼ常に最近最もつかわれていないデータを捨てれば十分という場合、PLRUアルゴリズムを使う。この場合、キャッシュライン毎に1ビットの情報を保持するだけでよい。
以下は特にCPUのキャッシュメモリのキャッシュアルゴリズムに関する項目である。
2ウェイ・セットアソシアティブ: 高速なCPUキャッシュでは、Pseudo-LRU でも遅すぎる。2ウェイのキャッシュメモリではアドレスから対応するキャッシュラインが2つ選択され、その2つのキャッシュライン間でLRU方式で捨てるラインを選択する。このとき、どちらのラインがLRUかを示すことができればよいので、使用情報は1ビットで済む。
ダイレクトマップ: さらに高速なCPUキャッシュでは、2ウェイでも遅すぎる。ダイレクトマップでは、アドレスから対応するキャッシュラインを1つだけ選択し、そのキャッシュラインが使用済みならそのデータを捨てる。