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

メインメモリのアドレスに対応して、どのキャッシュラインに格納するかを決めうちにする方式の一番基本的な方式はダイレクトマップ(Direct Map)方式のキャッシュである。ダイレクトマップ方式では、図4.6に示すように、アドレスを上位、中位、下位に三分する。

図4.6 ダイレクトマップのキャッシュのアドレス構造

下位アドレスはキャッシュラインのデータ部の中のアドレスであり、上位アドレスはタグに格納されるアドレスである。

例えば、キャッシュラインサイズを64バイトとすると、ライン内のアドレスとして6ビット、そして、キャッシュサイズが16KBとすると、64バイトのラインが256ライン存在することになる。ダイレクトマップキャシュでは、この256ラインを識別するのにアドレスの中位の8ビットを使用し、次の図4.7のように、中位アドレスのビット6～13をインデックスとして使用して、タグRAMとデータRAMをアクセスする。

図4.7 ダイレクトマップキャッシュのアクセス構造

この構造では図4.7のように、タグRAM、データRAMともにSRAMのメモリアレイを用いることができるので、フルアソシアティブ方式に較べると、同一容量のキャッシュをコンパクトに作ることができる。

このように、ダイレクトマップのキャッシュは構造が簡単で、フルアソシアティブ方式に比べるとハードウェア量が少ないというメリットがあるが、欠点もある。

ダイレクトマップ方式のキャッシュは、中位アドレスが同じ値となるメモリアドレスのデータ群に対して、1カ所のキャッシュラインしか割り当てられていない。このため、要求されたアドレスのデータがキャッシュに存在するかどうかの判定は容易になっているのであるが、これは、中位アドレスが同じになる複数のデータを同時にキャッシュに格納することができないという欠点でもある。

このようにキャッシュ内のデータ格納場所の自由度が低いので、同一キャッシュラインサイズ、ライン数のフルアソシアティブキャッシュと比較するとヒット率が低くなる。

最悪のケースとしては、

のように配列aとbを定義すると、各要素は8バイトであるので、aとbの先頭番地のアドレスの差は2048x8バイト=16Kバイトとなりa[i]とb[i]の中位と下位アドレスが一致してしまう。

そうなると、b[i]=a[i]の実行にあたり、a[0]～a[7]をキャッシュに読み込み、a[0]をレジスタにロードしてb[0]にライトしようとすると、b[0]はキャッシュに存在せずミスとなる。

そのため、今度はb[0]～b[7]をキャッシュに読み込んで、b[0]部分にロードしたデータを書き込む必要があるが、aとbの中位アドレスが同じであるので、a[0]～a[7]を追い出して、そのキャッシュラインにb[0]～b[7]を書き込むことになる。

そして、次にiを+1して、a[1]をロードしようとすると、キャッシュラインにはbが入っているので、これもミスになる。

というように、a、bのアクセスごとに、毎回、キャッシュミスが起こってしまう。こうなると、メインメモリへのアクセス回数を減らすというキャッシュの魔法はうまく働かず、本来、8バイトのリードと8バイトのライトで済む処理が、64バイトのキャッシュラインのリードが2回とライトが1回とメモリとのデータ転送量が24倍となり、キャッシュが無い場合よりも性能が低下してしまう。

この例のように互いに相手をキャシュから追い出してしまう状態はスラッシング(Thrashing)と呼ばれ、後述のより自由度の高い方式をとっている現在のマイクロプロセサでも発生することがある。

このような場合には、

のように配列aとbの間にキャッシュの1ライン分のdummyを入れてやると、b[i]の中位アドレスはa[i]の中位アドレスより1つ大きくなるので、両方のキャッシュラインを同時にキャッシュに入れることが可能になり、性能低下を避けることができる。

しかし、このようなケースの原因を見つけて、ダミー挿入のような対策を行うには経験と手間が必要である。