ロードマップでわかる！当世プロセッサー事情 第75回

トランジスター数と性能を秤にかけるキャッシュ

　引き続き今回もキャッシュの話である。前回はキャッシュにデータを取り込み、それをタグで検索するところまでを解説したが、今回はその先のことを考える。

新しいデータでキャッシュを入れ替える
「リフィル」の方式

　プログラムや利用するデータが非常に小さくて、(OSまで含めて)全部オンキャッシュで動くなんて場合は問題ない。例えばMS-DOSであれば、OSそのものは100KB前後で動くし、簡単なプログラムであればライブラリやデータまで含めても100KB未満、なんてことも少なくない。

　こうした小さなプログラムなら、2次/3次キャッシュまで含めれば、数MBのキャッシュ容量を持つ昨今のプロセッサーなら、最初だけメモリーアクセスしたあとは、全部オンキャッシュでも動作する。しかし、昨今のOSは流石にこんなものでは済まないし、アプリケーションだって数10MBを軽く超えるものが普通だから、当然キャッシュには入りきらない。

　例えば図1のように、すでにキャッシュが満杯になっている状態で、プログラムが新たな領域(赤線内の一番下のメモリー領域)をアクセスしようとした場合に、どうなるか？

図1 キャッシュが満杯の状態で、新たなメモリーにアクセスしようとした場合

　「キャッシュが満杯になったら、それ以上取り込まない」という選択肢はない。通常、プログラムはまず初期化ルーチンが動き、それに続いてメインのルーチンがループしながら動くという形になるから、むしろ積極的に取り込む形にしないと全然意味がない。そこでキャッシュの入れ替え(Refill、リフィルと呼ぶ)をすることになる。

　リフィルの方式にはいくつかあるが、比較的多く利用されるのが「LRU」(Least Recently Used)という方式である。これは「頻繁にアクセスするキャッシュラインは保存し、アクセスされないラインからリフィルの対象とする」という方法である。実装にはいくつか方法があるが、簡単なものでは図2のように、タグに「LRU bit」と呼ばれるフラグを1bit付加する方法がある。

図2 LRU bitを使ったキャッシュの管理

　CPUは一定期間ごとに、全部のLRU bitを「1」にする(図2)。次に、CPUからアクセスのあったキャッシュラインは、アクセスのあったタイミングでLRU bitを「0」に変更する(図3)。

図3 アクセス要求のあったタグのLRU bitを「0」に

　そのうちに新しいリフィルの要求が来た場合、キャッシュコントローラーはタグを先頭からチェックして、最初にLRU bitが「1」のラインを見つけたら、そこをクリアして、新しいタグアドレスとキャッシュデータを入れる動作をする(図4)。この際、頻繁に同じキャッシュラインのみが書き変わらないように、LRU bitは「0」に変更してリフィルするのが一般的だ。

図4 LRU bitが「1」のタグとキャッシュラインを新しいデータでリフィル

　この仕組みの場合、どの程度の頻度でLRU bitの書き換えるかが、キャッシュの効率にかなり影響してくる。書き換え期間が長すぎるとリフィルの際に不要なキャッシュラインを正しく判別できず、頻繁にアクセスするラインを排除してしまう可能性がある。逆に短すぎると、かなり頻繁にアクセスするキャッシュライン以外、全部排除されてしまう危険性がある。適度な値はシミュレーションなどでいろいろトライしながら、決定してゆくことになる。

　ちなみに、アーキテクチャーによってはLRU bitを複数bit化することで、アクセス頻度の重み付けまでするものとか、ほかに属性bitを用意して、そちらと併用する方法などを採用する製品もある。ただ、こうした機構はリフィルの際の手間が余分に掛かるので、余り凝ったことはしない方が一般的である。

　逆にもっと簡単な方式として、そのキャッシュラインが過去にどの程度の頻度で使われたかを一切考慮せず、先頭から順にリフィルの対象としてゆく「ラウンドロビン」方式や、リフィルの対象となるキャッシュラインを乱数で決定する「ランダム」といった方式もある。

　もっとも、これらはリフィル対象の決定は簡単かつ高速であるけれど、キャッシュのヒット率そのものが落ちやすいという欠点もある。そのため、1980～1990年代の、利用できるトランジスター数がとにかく少なかった時代はともかく、昨今のトランジスターが有り余っている時代では、あまり利用されない。