セットアソシアティブキャッシュ

以上のように、フルアソシアティブキャッシュとダイレクトマップキャッシュは帯に短し襷に長しの感があり、両者の長所を併せ持つ解として考案されたのが、セットアソシアソシアティブ(Set Associative)キャッシュである。

ダイレクトマップキャッシュでは同一の中位アドレスをもつデータ群は1つのキャッシュラインにしか格納できなかったが、セットアソシアティブキャッシュでは、これを2つ以上のキャッシュラインから選択して格納できるように改善している。この1つの中位アドレスに対応する複数のキャッシュラインデータ部をセットと言う。

図4.8 セットアソシアティブキャッシュの構造

セットアソシアソシアティブキャッシュとメインメモリアドレスとの対応を模式的に示すと、図4.8に示すようになる。図4.8は1つのセットに含まれるタグ、データ部のペアの数は2であるが、4あるいはそれ以上のメンバーを持つセットアソシアティブキャッシュも一般的である。また、このセットの中のメンバー数をWay数と呼び、図4.8は2wayのセットアソシアソシアティブキャッシュを示している。

そして、図4.9にその詳細を示すように、2wayセットアソシアティブキャッシュは、タグ、データ部を2組持ち、それらを並列にアクセスするハードウェア構造となっている。

図4.9 2way Set Associative Cacheの構造

そして、タグアレイから読み出された2つのタグと上位アドレスを比較し、一致した方のデータアレイの出力をANDとORゲートを経由して読み出す。つまりセットのそれぞれのメンバーのアクセスはダイレクトマップ方式であるが、セットの中では並列に一致を検索するフルアソシアティブ構造になっている。

そして、Way数を大きくする場合には、それぞれのインデックスに対応するタグアレイ、データアレイの要素をWay数分持ち、タグの比較回路やデータを選択する選択回路もWay数にあわせて拡張すれば良い。

このセットアソシアティブキャッシュは、フルアソシアティブ方式とダイレクトマップ方式の良いところを兼ね備えており、最近のマイクロプロセサの1～3次キャッシュは、ほとんどがこのセットアソシアティブキャッシュ方式を使用している。

キャッシュの管理

プログラム制御のローカルメモリの場合は、何を入れておくのかはソフトウェアが指示するので、ハードウェアは言われた通りにデータを出し入れしていれば良いが、キャッシュの場合は、ハードウェアが判断して、将来使われる頻度の高いデータを格納しておく必要がある。しかし、ハードウェアは、将来、プログラムがどのアドレスをアクセスするかは分からないので、経験的に、将来使用される可能性が高いデータを残すために色々な工夫が行われている。

キャッシュの処理フロー

以前述べたように、プログラムからメモリアクセス要求を受けると、キャッシュは、まず、そのアドレスのデータを保持しているかどうかをタグアレイをアクセスして検索するが、ここでそのデータがキャッシュ内に存在しない場合は、メインメモリから持ってくる必要がある。

しかし、プログラムの実行に伴いアクセスされるアドレスを含む転送単位を、次々とキャッシュに格納していくと、程なくキャッシュは一杯になってしまう。

そして、次に新しいアドレスのアクセスが要求されると、どこかのキャッシュラインのデータをメインメモリに追い出し、そして、空いたキャッシュラインに新たなアクセス要求に対応するデータを格納することが必要になる。

次の図4.10に、メモリのリードアクセスの場合の処理のフローを示す。

図4.10 キャッシュメモリの読出しアクセスの処理フロー(グリーンの部分がキャッシュの実行すべき機能)

まず、プロセサからのリード要求に対して、タグを検索して、そのアドレスのデータがキャッシュにすでに格納されている(ヒット)のか否(ミス)かを判定する。

そして、ヒットの場合には、そのデータをデータアレイから読み出してプロセサに送り返せばよい。しかし、キャッシュミスの場合には、メインメモリにリード要求を出して、メインメモリを読み、そのデータをプロセサに送ると同時に、次の使用に備えてキャッシュに格納する。

この場合に、キャッシュの使用可能なキャッシュラインに空きがあればよいのであるが、空きが無い場合には、不要なデータをメインメモリに書き出して空きを作り、空いたキャッシュラインに書き込みを行うという操作が必要となる。

一方、プロセサからのライト要求に対しては、次の図4.11のフローチャートにような動作を行う。

図4.11 キャッシュメモリの書込みアクセスの処理フロー(グリーンの部分がキャッシュの実行すべき機能)

このシリーズの命令アーキテクチャのところで述べたように、データタイプという概念があり、メモリのアクセスは8ビットのバイト単位であったり、16ビット、32ビットの整数や、32ビット、64ビットの浮動小数点数など、さまざまな単位でアクセスされる。

キャッシュヒットの場合は、そのキャッシュライン内の対応する8ビット、16ビットや32ビットの部分にデータを書き込めばよいが、ミスの場合は、そうは行かない。

空のキャッシュラインがあったとしても、そのキャッシュライン、例えば32バイトの内の、書き込むデータのサイズの部分だけに書き込んだ状態にすると、次に同じキャッシュラインの隣のアドレスをリードする要求が来た場合には、そのデータはキャッシュに入っていないし、メモリからキャッシュライン全体を読んで格納すれば、先に書き込んだデータが上書きされて消えてしまうという困った事態となる。

このため、キャッシュにデータが格納されていない場合は、メインメモリから書き込みを行うアドレスを含むキャッシュラインを読み込み、それに書き込みデータをマージ(Merge:合併する)して、キャシュライン上に書き込む部分だけを変更したデータを作り、キャッシュに書き込むという動作をする必要がある。

そして、この場合も使用できる空きキャッシュラインが無い場合は、古いキャッシュラインのデータをメインメモリに追い出して空きを作ってやる必要がある。