メモリ階層間でやり取りされるデータの最小単位をブロックと呼んでいますが、キャッシュ内にこのブロックを取る上でいくつかの配置方式が存在しています。
それぞれの方式を用いることで、キャッシュのミス率やヒット時間に影響を与えます。
それぞれの方式の解説と簡単な例題を組み合わせて解説していきます。
ダイレクト・マップ
ダイレクト・マップでは、メモリ内の任意のブロックとその上位の階層における位置( メモリ・アドレスと呼ぶ )が対応する方式です。(これは二つの位置が一対一で定まるということではなく、あくまで上の階層での位置が定まればそこから一意にブロックの位置を得られるということです。)
以下の式で配置先が決定されるようです。
配置されるブロックの位置 = メモリ・アドレス % キャッシュ内のブロック数
下二つの方式と異なりメモリ・アドレスが定まれば、一発でどのブロックに配置されるか知ることができます。
フル・アソシアティブ
フル・アソシアティブでは、任意の位置のブロックに対してメモリ・ブロック(格納するブロック単位のデータ)を配置する方式です。ダイレクト・マップのように配置にきまりはなく、空いているところに置かれる方式です。
一方、メモリ・アドレスからブロックの位置を特定できないのでデータを得る場合にはその都度探索を行う必要があります。一般にブロック数の少ないキャッシュに使用されることが多いようです。
セット・アソシアティブ
上二つの間をとったような方式がこのセット・アソシアティブです。この方式では、セットと呼ばれるいくつかのブロックが含まれたものにキャッシュを分割されます。例えば一つのセットにn個のブロックが含まれているならば、n-ウェイ・セット・アソシアティブなどというふうに呼ばれるようです。
（ここでセットに含まれる一つのブロックをウェイ、nの値を連想度と呼んでいます。）
メモリ・アドレスに応じてどのセットに配置するかまでは一意に定めれるが、セット内でどのブロックに配置されるかは決まっていないのが特徴です。フル・アソシアティブと比べて探索範囲は小さくなります。
配置されるセットの位置 = メモリ・アドレス % キャッシュ内のセット数
以下は、ダイレクト・マップとセット・アソシアティブの二つの方式を表した例です。
メモリ・アドレスが10だった場合、ダイレクト・マップではブロックの数8で10を割った余りのアドレスの2に配置されます。
セット・アソシアティブではセットの数4で10を割った余りのアドレス2のセットがまず割り当てられ、その中の任意のブロックに配置される。
例を用いた比較
さて、上の説明だけではダイレクト・マップ方式の方が良いように感じるでしょう。しかし、アソシアティブ方式では、アドレスの干渉を避け、キャッシュのヒットミス率を小さくすることができます。
以下の簡単な例を用いてアソシアティブ方式の利点を確認していこうと思います。
ブロック・アドレスが０、３、4、0、4の順でアクセスするとする。
- ダイレクト・マップの場合
| ブロック・アドレス | キャッシュ・ブロック |
| 0 | 0 |
| 3 | 3 |
| ４ | ０ |
| 参照したアドレス | ヒット/ミス | ブロック0 | ブロック1 | ブロック2 | ブロック3 |
| 0 | ミス | 0 | |||
| 3 | ミス | 0 | 3 | ||
| 4 | ミス | 4 | 3 | ||
| 0 | ミス | 0 | 3 | ||
| 4 | ミス | 4 | 3 |
ダイレクト・マップ方式では、メモリ・アドレスの値によってはブロックの位置が重複してしまい、読み込みの都度上位のメモリに取りに行く必要があります。
結果としてキャッシュミス率が大きくなってしまいます。
- 2-ウェイ・セット・アソシアティブの場合
| ブロック・アドレス | キャッシュ・ブロック |
| 0 | 0 |
| 3 | 1 |
| ４ | ０ |
| 参照したアドレス | ヒット/ミス | セット0 | セット0 | セット1 | セット1 |
| 0 | ミス | 0 | |||
| 3 | ミス | 0 | 3 | ||
| 4 | ミス | 0 | 4 | 3 | |
| 0 | ヒット | 0 | 4 | 3 | |
| 4 | ヒット | 0 | 4 | 3 |
一方、アソシアティブ方式ではアドレスの重複に対して、ある程度マージンが存在しています。結果として参照が進むほどヒット率が向上していきます。
参考文献
コメント