キャッシュの仕組み

キャッシュメモリ

キャッシュメモリは、メインメモリとプロセサに近いローカルな高速メモリの間を、ハードウェアが自動的にデータ転送を行う方式である。

前述のように、キャッシュメモリが有効に働くためには、プログラムによるメモリアクセスパターンに局所性があることが必要条件であるが、この局所性をうまく引き出して利用するために色々な工夫が行われて来た。

キャッシュは、メインメモリのバラバラなアドレスからのデータを格納するが、その中にどのアドレスのデータが格納されているかがすぐに分かるようになっていないと高速のアクセスは出来ない。

従って、メインメモリのアドレスを受け取り、そのデータがキャッシュ内にあるかどうかを高速に判定する機構が必要である。また、頻繁に使用するデータは時とともに変わるので、使用頻度の落ちたデータを追い出さないとガラクタが詰まった箱になってしまい、役に立たなくなってしまう。

このため、どのアドレスのデータをキャッシュに保持し、どのアドレスのデータを追い出すかという判断を行う必要がある。

キャッシュタグ

キャッシュには、メインメモリのあちこちのアドレスのデータを持ってくるので、データとペアで、それがどこのアドレスから持って来られたかという情報を持っている必要がある。

このアドレス情報が無いと、プロセサからのアクセス要求に対して、そのデータがキャッシュに格納されているかどうかの判定ができない。

また、プロセサにより内容が書き換えられた時には、その内容をメインメモリに書き戻してやる必要があるが、どこに書き戻せば良いかも分からない。このデータとペアで格納するアドレスデータをタグ(Tag:海外旅行のスーツケースに付けるような荷札という意味))という。そして、データとタグのペアをキャッシュラインと呼ぶ。

また、タグには、そのキャッシュラインに有効なデータが入っているか(有効な情報でないことを示すInvalidビット)や、キャッシュの内容がメインメモリから読まれたままであるか書き換えられた(Modified)かを示すビットなどの制御情報が付け加えられている。

そして、タグを格納するメモリをタグアレイ、または、ディレクトリ(住所録や電話帳という意味)と呼び、データを格納するメモリをデータアレイと呼ぶ。

キャッシュラインサイズ

タグには、そのデータのメインメモリ上のアドレスを記憶するが、データの塊のサイズ以下の下位アドレスを記憶する必要はない。

例えば、データのサイズが32バイトであるとすると、アドレスの最下位の5ビットはタグに格納する必要はなく、32ビットアドレスの場合は、タグのアドレス部としては27ビットあれば良い。

しかし、InvalidやModifiedなどのような制御情報を格納する必要があるので、結果として、タグのビット数は、おおよそ、メモリアドレスのビット数と同程度必要である。つまり、32ビットアドレス空間の場合は32ビット程度、64ビット空間の場合は64ビット程度のビット数を必要とする。

図4.4に示すように、容量16KBのキャッシュをデータのサイズを32バイトで構成する場合は、合計512ラインとなり、512個のタグを格納する必要がある。タグが8バイト(64ビット)である場合、タグに必要なメモリは4KBとなり、全体の20%とオーバヘッドが馬鹿にならない。

一方、64バイトラインとした場合は、256ラインであり、半分の256個のタグで済む。どちらの場合もタグに必要なビット数はほぼ同じであるので、タグメモリは半分の2KBバイトで済む。

では、キャッシュラインのサイズ(一般にデータ部のサイズを言い、タグのサイズは含めない)を大きくすれば良いかというとそうとも言えない。極端な例であるが、ラインサイズを16KBにして1ラインとしてしまったとすると、

1. そのキャッシュラインの16KB以外のアドレスをアクセスすると、キャッシュミスになり、目的のデータがキャッシュにない事態が頻発する。
2. メモリとのデータバスが8バイト幅とすると、ラインの転送に2Kサイクルも掛かってしまう。
3. (1)とあいまって、せっかく読んだ16KBのほんの一部しか使わないうちに、別のアドレスのデータと入れ替える必要が出て、転送が無駄になる。

という問題が生じる。特に、(3)のようにキャッシュラインの一部のデータしか使われないということになると、データ部が16KBあっても、有効に利用される実効的なキャッシュラインサイズが小さくなってしまう。

このようにキャッシュラインサイズを大きくしすぎると、見かけのタグオーバヘッドは小さくても、この実効的なラインサイズに対するタグのオーバヘッドの比率が大きくなってしまい、本末転倒である。

さらに、データアレイやメモリバンド幅もほんの一部だけが有効に利用されているだけということになり効率も悪い。

また、最大の問題は、ミス率が大きくなってしまうことである。図4.4に見られるように、データ部のサイズを大きくすると、一定の容量のキャッシュに格納できるキャッシュラインの数はラインサイズに逆比例して減少してしまう。

一般に、プログラムにはジャンプや関数コールがあり、あちこちの命令を読んだり、データアクセスもあちこちのアドレスを参照する。

これらのあちこちのアドレスのうちの使用頻度の高いものの大部分はキャッシュに格納して置きたいのであるが、キャッシュラインの数が少ないと、使用頻度の高いデータでもキャッシュに格納しておくことができないという事態が発生し、データがキャッシュに入っていないというキャッシュミスの確率が増加する。

このような理由から、同じキャッシュ容量であれば、キャッシュラインサイズを小さくしてライン数を増やした方が、ミス率は減少する。

どの程度のサイズのキャッシュラインが適当かは、実行するプログラムの性質に依存するので、プログラムの実行状態でのキャッシュの振舞いをシミュレーションし、必要なデータがキャッシュに存在するキャッシュヒット確率と必要なハードウェア量のトレードオフを行って決めるという方法が採るのが一般的である。

その結果としての設計は、小容量のキャッシュでは16バイト(128ビット)から64バイト(512ビット)程度のキャッシュラインが一般的であり、大容量のキャッシュでは、256バイトや512バイトというものもあるという状況である。

また、最近のマイクロプロセサは、1次キャッシュ、2次キャッシュという2階層、あるいは3次キャッシュを加えた3階層のキャッシュを持っているが、階層によって異なるラインサイズを用いるという構造が一般的である。