キャッシュアルゴリズム
キャッシュアルゴリズム(英: cache algorithm)は、コンピュータ上で情報を格納するキャッシュを管理するプログラムまたはハードウェア構造を最適化するアルゴリズム群。キャッシュが一杯になったとき、このアルゴリズムで新たな情報を格納するための場所を選択し確保する。置換アルゴリズムあるいは置換ポリシーとも。
キャッシュのヒット率(hit rate)とは、探しているデータがキャッシュ上で見つかる率(頻度)である。キャッシュサイズを増やさずにヒット率を向上させるには、キャッシュアルゴリズムはより多くの使用(usage)情報を必要とする。
キャッシュのレイテンシとは、あるデータを要求してからキャッシュがそれを返すまでにかかる時間である。より高速な置換戦略は一般に、より少ない使用情報を使用していて、情報の更新にかかる時間が少ない(ダイレクトマップ式なら全く情報を持たない)。
それぞれのキャッシュアルゴリズムは、ヒット率とレイテンシの兼ね合いを考慮している。