キャッシュラインの追い出し

このように、新たにメインメモリから読んでくるデータを入れる空きキャッシュラインが無い場合は、現在、データを格納しているどれかのキャッシュラインを追い出して空きを作る必要がある。

ダイレクトマップの場合は、使えるキャッシュラインが中位アドレスで1つに決まってしまうので、そこにあるデータを追い出すことになるが、セットアソシアティブの場合はWay数だけ選択肢があり、どれを追い出すかを決めなければならない。どれを追い出してもプログラムの処理結果が誤るということはないが、性能の点からは、将来、使われる可能性が低いキャッシュラインを追い出すのが望ましい。

しかし、ハードウェアには、将来、どのアドレスのメモリがアクセスされるかは分からない。このため、ハードウェアで実現できる程度の比較的簡単なルールで、将来、使われる可能性の小さいものを選び出すことが必要になる。

どれを追い出すべきかに関しては、多くの研究が行われているが、セットの中で、最後に使われてからの時間がもっとも長いものが、将来、使われる可能性が一番低いと判定するいうルールが妥当とされている。

我々の実生活でも、長らく使わないで、だんだんと引き出しの奥の方にに仕舞いこまれてしまったものが必要になる場合は少なく、最近使って、取り出しやすいところに入れてあるものが、また、必要になるというケースが多い。

この追い出しラインの選択法を、LRU(Least Recently Used)と言う。LRUでキャッシュラインの追い出しを行うためには、セットの中のどのキャッシュラインが一番古いかが分かるようにしなければならない。

セットが2wayの場合は話が簡単で、最近way-0を使ったらway-1が古い方であり、way-1を使った時点でway-0が古くなる。したがって、キャッシュがアクセスされた時点で、使用したwayがどちらであるかを記憶しておき、その反対のwayを追い出せばLRUとなる。

Way数が2より大きいのキャッシュの場合は、話は複雑になり、各wayが使用された順番を記憶しておく必要がある。例えば、4wayの場合は、新しい順に、0-1-2-3、0-1-3-2、0-2-1-3、…のように4の階乗の24通りの順序が有りうる。そして、0-1-2-3の状態で、次に、way-2が使われたとすると、そのwayを先頭に持ってきて、順序を2-0-1-3に変更する。このようにして各wayが使用された履歴を管理すれば、どれが一番古いwayであるかが分かる。

4wayの場合は、4!で24通りの順序があるので、5ビットでそれぞれの順序を表現することができ、次の図4.12のような回路でwayの使用履歴を管理できる。

図4.12 Wayの使用履歴の管理回路

LRUアレイは、前述のwayの使用履歴をコーディングして記憶するメモリであり、独立のRAMで作れらる場合が多いが、論理的にはセットに付属したタグ情報の一部と考えることもできる。そして、Next LRUロジックは、LRUアレイから読んだ現在までのway使用順序から、今回使用するwayを先頭に持ってくるように使用順序を変更したデータを作成する組み合わせ論理回路である。また、LRU wayロジックはコード化された使用履歴をデコードして、一番古いway番号を取り出す組み合わせ論理回路である。

4wayの場合は、5ビットで24通りの順序をコーディングすることになるが、このやり方には色々な方法が考えられる。例えば、Bit1:0の2ビットで一番古いway番号を表し、次のBit3:2でその次に古いway番号を表し、残りの1ビットのBit4で残る最近使われた2つのwayの使用順序がway番号順であるか、逆転しているかを表すという方法が考えられる。

少し長くなるが、このコーディングの場合の状態遷移表を次に示す。表4.1はBit4=0で最近の2つのwayが番号順のケースであり、次のアクセスされるwayに対応してNext LRUロジックの出力を示している。そして、その次の表4.2はBit4=1で最近の2wayが番号と逆順の場合の状態遷移表である。この表に基づいて、論理合成を行うなり、人手でカルノーマップを書いてロジックを組めば、Next LRUの論理回路が得られる。なお、グレーの部分は存在しない状態であり、この部分はDon't Careとして論理を組んでよい。

表4.1 Bit4=0の場合の状態遷移表

表4.2 Bit4=1の場合の状態遷移表

そして、一番古いway番号はBit1:0に書かれているので、LRU wayロジックは単純にBot1:0を取り出せばよい。

4wayの場合はwayの使用順序は24通りであるが、階乗であるのでway数が増えると使用順序の数は急激に増加する。8wayの場合は4万320通り、商用プロセサでは12wayというものもあり、この場合は、何と4億7,900万1,600通りになる。この順序をコード化するには8wayの場合は16ビット、12wayの場合は29ビットを必要とし、また、Next LRUやLRU wayロジックもビット数の増加に伴って急激に複雑化する。

しかし、もともとLRU自体が古いものは再使用の可能性が低いという程度の経験則であり、最近のway使用履歴は重要であるが、12wayの11番目であるか、12番目であるかはそれほど重要ではない。また、way数が大きい場合は、同一中間アドレスを持つデータのキャッシュへの格納の自由度が高く、追い出すway番号をランダムに選んでも、ヒット率の低下は比較的小さいという研究結果も報告されており、厳密なwayの使用順序に固執する必要はない。

したがって、8wayとか12wayのようにway数が大きいセットアソシアティブキャッシュでは、厳密なLRUではなく、新しい方からある程度の順番は正しく記憶するが、その他は、1まとめにして表現してLRUアレイのビット数を節約する擬似LRUという方式を用いるのが一般的である。