PLRUについてだいぶ分かってきた。
このアルゴリズムはTree PLRUというものに基づいている。各ツリーにおける状態を保持するためにstateという変数が各ノードで定義されている。
このstate変数により、どのWayに最新でアクセスされたのかを記録するようになっている。
例えば、Way=8の場合は以下のように3階層でstateビットが組まれている。
例えば、直近のアクセスでWay=5にアクセスした場合、それぞれのstateは以下のように設定される。つまり、stateを上から順にたどっていくとWay=5につながるようにチェイン作られる、というイメージだ。
この図だと、Way=5までにつながるstateのビット位置以外のstateにも値が格納されている。
次に、Way=3がアクセスされるとどうなるだろうか。Way=3までにつながるstateのビットが設定される。stateは以下のように更新される。
ここで注目すべきなのは、Way=3により茶員が更新されたことにより、それより前にWay=5にアクセスされた正確な情報は失われる。
しかし、少なくともも、左半分のツリーに着目すれば、Way=5にアクセスした記録というのはなんとなく残っている、というのがポイントだ。
左半分のツリーを構成するstate[1][1]およびstate[2][3:2]を見ると、少なくともWay=5につながる道をチェインしていることが分かる。
この情報を利用して「最もアクセスされていないっぽい」Way番号を特定する。つまり、現在のチェインをひたすら逆向きにたどっていく。*1
上記の例だと、stateが指し示す方向と逆向きにたどってみる。
すると、Way=6にたどり着いた。つまり、この場合はEvictionの候補としてWay=6が選ばれる、ということになる。
*1:全然イメージは違うだろうが、トーナメント表を逆にたどる、ということを考えた人は少なくともいると思う。 例えば、ABCDの4チームでAとBの対決でAが勝利、CとDの対決でDが勝利し、決勝戦でAとDが対決してAが優勝した場合を考える。 そうすると、1回戦で負けたBとCの強弱は直接比較はできないのだけれども、なんとなく「DはAに負けたんだからCはBよりも弱いんじゃないの？つまりCは最弱」という最弱決定戦をするのと、考え方は似ていると思う。
