キャッシュアルゴリズム
CPUのキャッシュメモリとして使用した場合、以下の特徴がある。
Least Recently Used: このアルゴリズムでは、どのデータがどの時点で使われたかという情報を保持する必要があり、本当に最近最も使われていないデータを常に捨てるようにしようとすると、かなり手間がかかる。一般的実装では、キャッシュライン毎に世代ビット群(age bits)を持たせ、どのラインが最近最も使われていないかを世代ビット群で判断する。その場合、あるキャッシュラインを使うときには、常に全キャッシュラインの世代ビット群を更新する必要がある。
Most Recently Used: アクセスに局所性を想定できず、LRUの実装が複雑すぎる場合に使われる。MRUの使用例としてはデータベースのメモリキャッシュがある。
Pseudo-LRU (PLRU): 例えば、キャッシュメモリの連想度が大きい場合(4ウェイ以上)、LRUの実装コストは無視できなくなる。