【再録】コンピュータアーキテクチャの話(8) キャッシュの構造(基礎編) - セットアソシアティブキャッシュとLRU

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

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

このような欠点を緩和する方式がフルアソシアティブとダイレクトマップの中間であるセットアソシアティブ(Set Associative)方式である。

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

図4は2wayセットアソシアティブキャッシュの構造を示している。図2のダイレクトマップ方式との大きな違いは、メモリブロックの横方向のグループを格納することが出来るキャッシュのマスが2個に増加している点である。従って、命令が0ブロック、データがnブロックという前述の例でも、対応するキャッシュラインが2つあるので同時に格納でき、スラッシングは発生しない。勿論、3つ以上のアドレスがぶつかる場合はダメであり、スラッシングの発生確率を下げるにはメモリブロックの横方向のグループを格納するキャッシュライン数を増やす必要がある。この横方向のキャッシュライン数をwayと呼び，図4の例では2wayであるが、4way、8way、場合によっては2のベキでないような6とか10wayのキャッシュも作られている。

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

2wayセットアソシアティブキャッシュは図5に示すような構造になっており、データアレイ、タグアレイともに2組もうけられている。プロセサからの要求アドレスのインデックスにより両方のタグアレイをアクセスし、二つのデータアレイのタグを読出して要求アドレスのタグと比較する。たった二組では連想という感じはしないが、横に並んだ2個のキャッシュデータの集合の中では連想的にサーチするので、セットアソシアティブ方式と名づけられている。

両方のタグのどちらか一方が一致すればヒットであり、ヒット信号は両方の比較結果をORして生成される。また、データアレイは選択回路によりヒットに対応した側のデータ出力を読み出す。

タグが一致せずミスとなった場合は、データアレイの読出しは無駄となり、無駄な電力を消費することになる。先ず、タグアレイを読み出して比較し、一致した場合だけデータアレイを読み出すという方式とすれば無駄な電力消費を抑えられるが、タグのアクセスとデータのアクセスが順次行われるので、データが得られるまでの時間が長くなるという問題がある。このため、1次キャッシュのように容量が小さく、高速アクセスの要求が強いキャッシュではタグアレイとデータアレイを並列にアクセスする方式が用いられる。一方、大容量の2次、3次キャッシュでは消費電力が問題であり、アクセスタイムの増加はある程度我慢できるので、タグのヒットを確認してから、ヒットしたwayだけのデータアレイをアクセスする方式が用いられるようになってきている。

どのデータをキャッシュから追い出すか?

しかし、ここで新たな問題がある。それは、どちらのタグとも一致せず、メモリから新たなデータを持ってくる場合に、どのデータを追い出して格納場所を作るかという問題である。キャッシュのアイデアは、頻繁に使われるものをプロセサコアに近い高速小容量メモリに格納するというものであるが、横方向に並んだセットのうち、どちらが頻繁にアクセスされるデータであるか、次にアクセスされるのはどちらのwayのデータであるかはプロセサやキャッシュのハードウェアには判らない。

ここで、一般的に用いられる仮定は、最も最近にアクセスされたものは、また使われる確率が高く、一番長く使われていないものは再利用される確率が低いというものである。この方式をLRU(Least Recently Used)と言う。2wayのセットアソシアティブキャッシュの場合は、ヒットした側が最近にアクセスした方であり、反対側が一番長く使われていないものであるから、キャッシュの各インデックスに対して、どちらが最近かを示すHotビットを設けてやればよい。そして、キャッシュミスして新たなデータをメモリから持ってくる場合にはHotでない側を追い出して、そこに格納することになる。

しかし、これが4wayになると話はかなり複雑になる。0から3までのwayがアクセスされた順番を数え上げると4×3×2＝24通り存在する。従って、5ビットで各ケースを表現しておき、今回のアクセスでヒットしたwayを最新アクセスとし、その他のwayは順序を保存して繰り下げるという状態遷移マシンを作る(論理合成を使えば簡単にできるが)ことになる。しかし、8wayになると40320通りになり、まじめに状態遷移マシンを作るのは物量の点で大変である。また、LRU自体があまり厳密性の無い仮定であり、8個のwayのアクセスされた順序を完全に正確に記憶する必要も無いことから、細部をサボった状態遷移マシン(Quasi LRUなどと呼ばれる)を作るのが一般的である。この、どの順序で各wayがアクセスされ、新しい情報の格納するためにどのwayを次に追い出すべきかを示す情報を格納するアレイをLRUアレイと呼ぶ。

インデックスでタグアレイをアクセスして全てのwayで一致するタグが無い場合はミスであり、Readアクセスの場合は、下位のキャッシュあるいはメモリに対して要求するアドレスを送り、データの読出しを開始する。また、どれかのWayの内容を追い出して読み出されるメモリブロックのデータを入れる場所を作る必要がある。

このため、図6に示すように、インデックスでタグアレイと同時にLRUアレイも読出し、その情報をデコードしてアクセスが最も古い(＝LRU)wayを知る。追い出すキャッシュラインがメモリから読み出された状態のまま、変更が無い場合は書き戻しの必要は無く、アクセスされたメモリブロックのデータが到着すれば、上書きすれば良い。

一方、このキャッシュラインに書き換えられた部分がある場合は、メモリに書き戻しを行う必要がある。タグアレイやLRUアレイと同時に全部のwayのデータアレイを読み出している場合は、追い出すべきwayのデータを選択して書き戻しバッファへ書き込み、メモリへの書き戻しを開始する。