引き続き今回もキャッシュの話である。前回はキャッシュにデータを取り込み、それをタグで検索するところまでを解説したが、今回はその先のことを考える。
新しいデータでキャッシュを入れ替える
「リフィル」の方式
プログラムや利用するデータが非常に小さくて、(OSまで含めて)全部オンキャッシュで動くなんて場合は問題ない。例えばMS-DOSであれば、OSそのものは100KB前後で動くし、簡単なプログラムであればライブラリやデータまで含めても100KB未満、なんてことも少なくない。
こうした小さなプログラムなら、2次/3次キャッシュまで含めれば、数MBのキャッシュ容量を持つ昨今のプロセッサーなら、最初だけメモリーアクセスしたあとは、全部オンキャッシュでも動作する。しかし、昨今のOSは流石にこんなものでは済まないし、アプリケーションだって数10MBを軽く超えるものが普通だから、当然キャッシュには入りきらない。
例えば図1のように、すでにキャッシュが満杯になっている状態で、プログラムが新たな領域(赤線内の一番下のメモリー領域)をアクセスしようとした場合に、どうなるか?
「キャッシュが満杯になったら、それ以上取り込まない」という選択肢はない。通常、プログラムはまず初期化ルーチンが動き、それに続いてメインのルーチンがループしながら動くという形になるから、むしろ積極的に取り込む形にしないと全然意味がない。そこでキャッシュの入れ替え(Refill、リフィルと呼ぶ)をすることになる。
リフィルの方式にはいくつかあるが、比較的多く利用されるのが「LRU」(Least Recently Used)という方式である。これは「頻繁にアクセスするキャッシュラインは保存し、アクセスされないラインからリフィルの対象とする」という方法である。実装にはいくつか方法があるが、簡単なものでは図2のように、タグに「LRU bit」と呼ばれるフラグを1bit付加する方法がある。
CPUは一定期間ごとに、全部のLRU bitを「1」にする(図2)。次に、CPUからアクセスのあったキャッシュラインは、アクセスのあったタイミングでLRU bitを「0」に変更する(図3)。
そのうちに新しいリフィルの要求が来た場合、キャッシュコントローラーはタグを先頭からチェックして、最初にLRU bitが「1」のラインを見つけたら、そこをクリアして、新しいタグアドレスとキャッシュデータを入れる動作をする(図4)。この際、頻繁に同じキャッシュラインのみが書き変わらないように、LRU bitは「0」に変更してリフィルするのが一般的だ。
この仕組みの場合、どの程度の頻度でLRU bitの書き換えるかが、キャッシュの効率にかなり影響してくる。書き換え期間が長すぎるとリフィルの際に不要なキャッシュラインを正しく判別できず、頻繁にアクセスするラインを排除してしまう可能性がある。逆に短すぎると、かなり頻繁にアクセスするキャッシュライン以外、全部排除されてしまう危険性がある。適度な値はシミュレーションなどでいろいろトライしながら、決定してゆくことになる。
ちなみに、アーキテクチャーによってはLRU bitを複数bit化することで、アクセス頻度の重み付けまでするものとか、ほかに属性bitを用意して、そちらと併用する方法などを採用する製品もある。ただ、こうした機構はリフィルの際の手間が余分に掛かるので、余り凝ったことはしない方が一般的である。
逆にもっと簡単な方式として、そのキャッシュラインが過去にどの程度の頻度で使われたかを一切考慮せず、先頭から順にリフィルの対象としてゆく「ラウンドロビン」方式や、リフィルの対象となるキャッシュラインを乱数で決定する「ランダム」といった方式もある。
もっとも、これらはリフィル対象の決定は簡単かつ高速であるけれど、キャッシュのヒット率そのものが落ちやすいという欠点もある。そのため、1980~1990年代の、利用できるトランジスター数がとにかく少なかった時代はともかく、昨今のトランジスターが有り余っている時代では、あまり利用されない。
この連載の記事
-
第772回
PC
スーパーコンピューターの系譜 本格稼働で大きく性能を伸ばしたAuroraだが世界一には届かなかった -
第771回
PC
277もの特許を使用して標準化した高速シリアルバスIEEE 1394 消え去ったI/F史 -
第770回
PC
キーボードとマウスをつなぐDINおよびPS/2コネクター 消え去ったI/F史 -
第769回
PC
HDDのコントローラーとI/Fを一体化して爆発的に普及したIDE 消え去ったI/F史 -
第768回
PC
AIアクセラレーター「Gaudi 3」の性能は前世代の2~4倍 インテル CPUロードマップ -
第767回
PC
Lunar LakeはWindows 12の要件である40TOPSを超えるNPU性能 インテル CPUロードマップ -
第766回
デジタル
Instinct MI300のI/OダイはXCDとCCDのどちらにも搭載できる驚きの構造 AMD GPUロードマップ -
第765回
PC
GB200 Grace Blackwell SuperchipのTDPは1200W NVIDIA GPUロードマップ -
第764回
PC
B100は1ダイあたりの性能がH100を下回るがAI性能はH100の5倍 NVIDIA GPUロードマップ -
第763回
PC
FDD/HDDをつなぐため急速に普及したSASI 消え去ったI/F史 -
第762回
PC
測定器やFDDなどどんな機器も接続できたGPIB 消え去ったI/F史 - この連載の一覧へ