キャッシュの構造(基礎編) - フルアソシアティブ方式とダイレクトマップ方式

本連載はHisa Ando氏による連載「コンピュータアーキテクチャ」の初掲載(2005年9月20日掲載)から第72回(2007年3月31日掲載)までの原稿を再掲載したものとなります。第73回以降、最新のものにつきましては、コチラにて、ご確認ください。

フルアソシアティブ方式のキャッシュ

使用できるメモリ容量から、キャッシュラインサイズとライン数を決定すると、次はこれらのラインにどのように情報を格納するかを考えることになる。理想的なのは、メモリのどの番地の内容でも、どのキャッシュラインにでも格納できる形態である。しかし、これは管理やデータの転送が難しいので、通常はラインサイズが128バイトであれば、各ラインに格納するデータの先頭番地は128バイトの整数倍の番地と制約が付けられる。つまり、各ラインはプロセサが要求するデータの番地を含む128バイト単位のブロックをメモリから持ってきて格納することになる。

このとき、128バイト単位のメモリのどのブロックでも、どのキャッシュラインにも格納できるというのが利用効率の点からは理想的である。しかしこの方式は、どこのフォルダに何を入れるという規則がないファイルシステムのようなもので、プロセサがデータを要求した場合には、全部の格納場所に何が入っているかを片っ端から調べる必要がある。このため、各キャッシュラインに対応してそれぞれメモリブロック単位の番地データを保持するアレイを持ち(このデータを保持する構造をディレクトリとかタグと呼ぶ)、要求されたデータの番地と全部のタグを比較する必要がある。全部のタグを連想的に検索するという方式であるので、この方式はフルアソシアティブ(Full Associative)方式と呼ばれる。タグの比較を順次行うのでは時間が遅くなってしまうので、連想メモリ(Associative Memory、あるいはContent Addressable Memory CAMと呼ぶ)が用いられるが、比較に必要な回路の物量が大きく面積を喰うのに加えて、要求されるアクセス速度にもよるが128～512ライン程度が実用的な上限である。

ダイレクトマップキャッシュ

このフルアソシアティブ方式の対極にあるのが、次に述べるダイレクトマップ(Direct Map)方式である。図2に示すように、ダイレクトマップ方式ではメモリのブロック番号(128バイトラインの例では、メモリ番地の下7ビットを除いた上位ビット)が直接、ライン番号を決定する。

• 

  図2 ダイレクトマップ方式のキャッシュ構造

図2(a)に示した一つのマスがラインサイズのブロックで、マスの中に示したように順番付けられている。当然、メモリの方がキャッシュより大きいので、横一列のマスの組が一つのキャッシュラインに対応付けられることになる。メモリのアドレスが決まれば、どのキャッシュラインに格納されるかが一意に決定されるので、この方式はダイレクトマップと呼ばれる。このキャッシュラインのアドレスは通常、インデックスと呼ばれ、図2(b)に示すように、メモリアドレスの最下位のラインサイズ分のビットを除いた中間のインデックスと書かれた部分が直接キャッシュラインを選択するために用いられる。

ダイレクトマップのキャッシュでは、インデックスだけでは、横一列のメモリブロックのどれが現在キャッシュに格納されているかは判らない。この情報を持つのが最上位のタグと呼ばれるビット列である。図3にダイレクトマップキャッシュのヒット判定回路を示す。キャッシュはデータを格納するデータアレイと管理情報を格納するタグアレイ(ディレクトリとも呼ばれる)からなっており、プロセサからのアクセス要求のインデックスを用いてタグとデータ両方のアレイを読み出す。タグアレイに格納されたアドレスの上位ビット(タグ)とプロセサからの要求アドレスのタグが一致すれば全アドレスが一致しておりヒットである。しかし、タグが一致しない場合は、横一列のグループの別のブロックが格納されており、目的のデータではないのでミスである。また、ここでは図示していないが、タグアレイには、キャッシュラインのデータが有効か無効かを示すバリッドビットや、キャッシュラインの内容がメモリから読まれたままであるか、書き換えられた部分があるかなどの、後述のコヒーレンシ制御のための各種のキャッシュラインの状態を示す情報が格納されている。

• 

  図3 ダイレクトマップ キャッシュのヒット判定

このダイレクトマップ方式は、連想メモリなどを必要とせず、タグのビット数も少なく、構成が簡単であるが、次のような欠点がある。例えば、実行するプログラムの命令が0ブロックにあり、そのプログラムがnブロックにあるデータを使うケースでは、命令をインデックス0のキャッシュラインに入れて実行を開始すると、今度はnブロックのデータの読み込みを要求するので、nブロックのメモリデータがインデックス0のキャッシュラインに入れられ、命令は上書きされてしまう。0ブロックにある次の命令を読もうとすると、既に0ブロックの内容は無くなっており、また、メモリから読んで来る必要がある。というように、頻繁にキャッシュラインの入れ替えが発生し、キャッシュが無い場合に比べても性能が低下してしまう。このような現象はスラッシング(Thrashing)と呼ばれる。この例では命令とデータのぶつかりで説明したが、丁度、キャッシュ容量の整数倍離れたアドレスにある二つの配列を扱うようなプログラムでもスラッシングは発生する。また、マルチコアになって複数のコアが共有するキャッシュでは、より頻繁にぶつかりが発生することになる。