[パタヘネ:読書メモ]第5章　容量と速度の両立：記憶階層の利用

まず基本原則として、コスト的な制約により記憶域には”少量の高速な記憶域”か”大量の低速な記憶域”のどちらかしかない。これは、たとえ十分な資金を用意できたとしても、”より大量”の情報をアーカイブしておく保存領域が欲しくなるので、結局上記の状況になる。

一方、プログラム側としては、大量の記憶域へ高速へアクセスしたいという要望が出てくる。
その結果として、データのキャッシュを行う必要があるけど、キャッシュがなぜ有効かというと、それは以下の原則によっている。

局所性の法則

なので、複数の速度･容量を持つメモリを記憶階層を組み合わせて情報を管理する事になり、この階層を記憶階層と呼ぶ。

階層はCPUに近い方を上位レベルと呼び、遠い側を買いレベルと呼ぶ。
また、各階層間で受け渡すデータの最小単位をブロック(もしくはライン)と呼ぶ。

5.2　キャッシュの基礎

まずはデータ要求サイズとデータサイズ共に1ワードである、シンプルなキャッシュシステムを考える。

キャッシュ構造を作るためには、実際のキャッシュデータ格納領域に加えて、以下の2つの情報が必要となる。



前者は純粋な有効フラグで、CPUの起動時は全て無効化されており、キャッシュが進むにつれて有効となっていく。

後者の検索方法には複数の戦略があるが、最もシンプルなのはダイレクトマップ方式になる。

— ダイレクトマップ方式 —
あるデータのキャッシュが存在する場所(アドレス)が一意とする実装方式。
当然の前提条件として、元データの場所のサイズよりはキャッシュ領域のサイズの方が小さいので、あるデータをキャッシュする場合には、キャッシュ場所を求めるための計算式が必要となる。
これは、元データの場所がある場所の下位Nビットを、キャッシュの保存場所のキーとすることが多い。

ダイレクトマップ方式でデータの検索方法を決めたとして、次はデータがキャッシュされているか否かを判定出来る必要がある。
これには、キャッシュアドレスの数分、付加情報を持たせればよい。
付加情報には、以下の情報が含まれる。




前者は1bit有れば事が足りる。後者に関しては前述した”下位Nビットを、キャッシュの保存場所のキー”としている場合だったら、N+1ビット目以上のデータを管理すればよくなる。
このN+1ビット目以上のデータのことを、タグと呼ぶ。

一般的にキャッシュサイズというのはキャッシュデータのサイズ分だけを指し、有効フラグやタグ情報の格納領域のことはカウントに入れない。



キャッシュに関しては、WriteよりReadについてから考えるほうが用意となる。
これはWriteがキャッシュデータと実データの一貫性についてを検討する必要があるのに対して、Readは単に読むこと(とキャッシュミスの検討)だけだから。

というわけで、まず読み込みを考えるが、CPUがLOADしたかったデータがキャッシュに存在するかの判定は以下のロジックになる。




というわけで、このロジックは値の同値比較とビット演算(AND)のみで実装できるので、論理回路として実装するのは比較的容易になる。

ここまでの説明でざっくりと説明したけど、MIPSの場合は32bit単位でデータのアクセスを行うので、アクセスするアドレスのうち下位2bitは検索キーとして使用する必要が無く、これによって記憶領域の節約が出来る。

ここまで、1度のLOADで1ワードだけキャッシュすることを考えたけど、周辺の複数ワード分のデータをキャッシュできれば(＝ブロックサイズを大きくすれば)キャッシュのヒット率は向上する。
これは、最初に考えたデータの空間的局所性に起因する性質となる。

それではブロックサイズを際限なく大きくすればよいか？という質問になるけど、大きくしすぎると関係ないところのデータまでキャッシュされ、本来必要だったデータがキャッシュから追い出される頻度が上がってくるので却ってヒット率が下がる事もありうる。
また、ブロックサイズが大きすぎると、キャッシュミスが起きたときに、キャッシュへロードする量が増えるのでキャッシュミスペナルティが大きくなる。


複数ブロックをまとめてキャッシュする場合、全データをロードしてから処理を継続させると、転送処理を待つ必要が出るので処理が遅くなる。
これを避けるために、必要データが手に入ったタイミングで処理を続行し、キャッシュデータのロードを非同期で続けるという考え方も有る。この方法を早期実行再開(early restart)と呼ぶ。

さらに、必要データを一番最初にロードしてしまえば、早く処理を継続できる。これを要求データ先送り(requested word first)と呼ぶ。




キャッシュへの書き込みには、前述したようにデータの一貫性の管理についての問題が発生する。
キャッシュへ書くと同時に、下のレイヤの記憶装置にもデータを書けば(ライトスルー)、一貫性は保たれるが、処理が遅くなる。
キャッシュだけにデータを記録すれば(ライトバック）、処理が早くなるが、実データとキャッシュの間でデータの不整合が発生する。
ライトバック方式の場合、データが書き込まれるのは該当のキャッシュが追い出されるタイミングになる。

読み込みと同様、書き込みにもキャッシュミスが発生しうる。
書き込みのキャッシュミスが有った場合、下位の階層への書き込みには時間が掛かるので、ライトバッファを設けて非同期処理を行う場合もある。