キャッシュの基本動作：福田昭のデバイス通信 ARMが語る、最先端メモリに対する期待（7）（2/3 ページ）

今回は、キャッシュメモリの基本動作について解説する。基本動作は、大きく分けて2つある。メインメモリからデータをキャッシュラインにコピーする「アロケーション」と、特定のキャッシュラインからデータを追い出して“空き”を作る「エビクション」だ。

[福田昭，EE Times Japan]

キャッシュラインの空きを作成するアルゴリズム

　上記の説明から理解できるのは、キャッシュには大きく分けると2つの動作が存在することだ。1つは、主記憶（メインメモリ）からデータをキャッシュラインにコピーする動作（アロケーション）。もう1つは、特定のキャッシュラインからデータを追い出して空きのラインを作る動作（エビクション）である。

　それでは「いつ」あるいは「どのタイミング」でこれらの動作を実行するのだろうか。アロケーション動作では2つのタイミングが考えられる。1つは、CPUがデータを読み込むタイミングである。もう1つは、CPUがデータを書き込むタイミングだ。

　エビクション動作は、アロケーション動作に比べると単純ではない。セットアソシアティブ方式のキャッシュ構造だと、どのキャッシュラインからデータを追い出すのかを決める方法は、いくつも存在するからだ。最もシンプルな方法は、ランダムにキャッシュラインを決めるというもの。極めて簡単な回路を追加するだけで実行できる。しかしこの方式は、頻繁にアクセスするキャッシュラインの内容が消されてしまうというリスクが拭えない。

　もう1つの方法は、追い出すキャッシュラインを順番にずらしていくというもの。サイクリック方式あるいはラウンドロビン方式と呼ぶ。この方式もキャッシュラインへのアクセス頻度を考慮しないので、ランダム方式と同様に、ヒット率があまり高くない。

　有力な方式の1つは、最も古いデータを消すことである。古いデータは、使われる頻度が少ないデータだと考えられるからだ。この手法をLRU（Least Recently Used）方式と呼ぶ。2ウエイのセットアソシアティブ方式の場合は、ウエイ0とウエイ1の2つしかウエイがないので、どちらかが新しいウエイ、残りが古いウエイとなる。

2ウエイのセットアソシアティブ方式におけるキャッシュラインへのデータのコピー（アロケーション：Allocation）とキャッシュラインからのデータの追い出し（エビクション：Eviction） （クリックで拡大） 出典：ARM