キャッシュメモリの仕組みと性能

キャッシュメモリは、CPUと主記憶の間に置かれる小容量で高速な記憶装置であり、主記憶の一部のデータを複製して保持することで平均的なアクセス時間を短縮する。その性能は、要求されたデータがキャッシュに存在する割合であるヒット率、主記憶との書込み方式、ブロックの置換アルゴリズムの三つによって決まる。

キャッシュの原理と書込み方式

CPUが必要とするデータがキャッシュにあることをヒットといい、なければミスという。ヒット時はキャッシュだけにアクセスすればよいため、主記憶へアクセスする場合より短時間で処理できる。

キャッシュへの書込み方式には、ライトスルー方式とライトバック方式がある。ライトスルー方式は、データをキャッシュメモリと主記憶の両方に同時に書き込むため、主記憶の内容が常にキャッシュと一致する。 主記憶の内容が常に最新に保たれる点は、ほかの方式と区別する重要な特徴である。

ライトバック方式は、書込み時にはキャッシュだけを更新し、主記憶への反映を後回しにする方式である。主記憶への書込み回数を減らせるため、書込み性能の面で有利になりやすい。 更新済みで主記憶と異なる状態になったブロックはダーティと呼ばれ、そのブロックが追い出される際には主記憶へ書き戻す必要がある。

置換アルゴリズムの判断基準

キャッシュが満杯のとき新しいブロックを読み込むには、既存のブロックのうちどれを追い出すかを決める必要がある。その判断に用いられる代表的な方式が、FIFO、LFU、LIFO、LRUである。

FIFOは、キャッシュへの読込み時刻が最も古いブロックを追い出す。LFUは、参照回数が最も少ないブロックを追い出す。 LIFOは、読込み時刻が最も新しいブロックを追い出す。LRUは、最後に参照された時刻が最も古いブロックを追い出す方式であり、最も長く使われていないブロックを対象とする。

LRUは、最近使われていないブロックは当面使われにくいという局所性の考え方に基づいており、ブロックごとの参照時刻の管理によって判断する。どの基準で選ぶかを、時刻、回数、後入れといった観点で切り分けて理解することが重要である。