わけあってHigh Performance Cache Replacement Using Re-Reference Interval Prediction (RRIP) という論文を読んでいる。
キャッシュの割り当て方式(というか、どのキャッシュブロックをEvictionするか)には、LRUという方式が一般的に知られている。
LRU(Least Recently Used)は、「最も最近使用されていないものをキャッシュから追い出す」という考え方に基づいている。 もっとも純粋なLRUを実現するためには、各キャッシュブロックに時間のタイムスタンプをつけておき、アクセスされるたびに当該ブロックのタイムスタンプを更新する。
これは考え方によっては最近アクセスされたキャッシュブロック順に並べてチェインを作る、と考えることができ、この時のチェインをRRIPチェインとみなしている。 LRUの基本的な考え方は、最近アクセスしたキャッシュラインをチェインの先頭になる。 そして、RRIPチェインの末尾の要素をキャッシュから追い出すことになる。 \footnote{ちなみに、最もタイムスタンプが小さいもの(つまり最も古いもの)を追い出す、ということになるのだが、純粋にこのようなLRUを実装するとなると各エントリに対するアップデートが必要になり実装が複雑になる。}
つまり、最も最近アクセスされた(MRU : Most Recently Used)なキャッシュブロックはもう一度再参照させる可能性が高い、という予測に基づいている。
一方、そうでないプログラムのアクセスパタンというものもある。 例えばストリーミングアクセスのような処理は、一度キャッシュにロードして処理するものの二度と再利用されることなくキャッシュから抜け出していく。実際にはこのようなキャッシュラインは早めに吐き出すか、そもそもL1キャッシュにロードしなくても良いのだが、このような時にLRUは不利な方法に働く。
そこで、提案手法のRRIPベースの置き換えアルゴリズムだ。 大きく2つの提案がなされており、SRRIP(Static RRIP)とDRRIP(Dynamic RRIP)だ。まずはSRRIPの方を読んだので、そっちをまとめていく。
SRRIPでは、各キャッシュブロックに2ビットの情報が付けられる。この情報が3になると置き換え対象となる。 まず、キャッシュにロードされたブロックは、SRRIPビットが3から2になる。なぜ2なのか、というのは、3の1つ下、くらいの認識で良い。
次に、実際にキャッシュヒットでアクセスがあったものは、SRRIPビットが0になる。これは最も最近アクセスされたということを示している。 キャッシュミスが発生すると、空きキャッシュブロックが無い場合すべてのSRRIPビットを1つインクリメントする。 その中でSRRIPビットが3のものを選んで吐き出すということだ。
つまり、一度キャッシュにロードされただけではSRRIPビットは2に設定され、まだ十分に再参照されていないということを意味する(再参照されると、0に更新される)。 従って、キャッシュの空き容量が無くキャッシュミスが発生すると、SRRIPビットは2から3に戻り、置き換え対象になってしまう。 つまり、再参照がなされていないキャッシュ・ブロックを優先的に吐き出すという仕組みになっているということが分かる。
