一种缓存替换策略:Dynamic Re-Reference Interval Prediction (RRIP)

LRU 替换策略

Least Recently Used (LRU)替换策略是广泛应用的cache(缓存)替换策略。LRU中有两个位置,一个是LRU,一个是MRU,前者表示最近最久使用到的,后者表示最最近使用到的。

一种对LRU新的理解的方法将LRU看成是对将来可能的访存序列的预测称之为Re-Reference Interval Prediction,那么MRU对应对头,LRU对应队尾。

一种称之为Dynamic insertion policy的策略是对LRU方法的改进,该方法可以应对”最近的访存是对即将被置换出去的LRU位置的访问”的问题,通过动态得改变LRU队列中的位置,使得并不总是LRU位置的块被替换出去。

但是该方法的局限是:对那些数据局部性比较好的程序,会造成性能损失。因为它可能将最近就要使用的块置换出去。

NRU 替换策略

NRU(Not Recent Used) 是LRU的一个近似策略,被广泛应用于现代高性能处理器中。应用NRU策略的cache,需要在每个cache block中增加一位标记,该标记(NRU bit)“0”表示最近可能被访问到的,“1”表示最近不能访问到的。

每当一个cache hit,该cache block的NRU bit被设置为“0”表示在最近的将来,该cache block很有可能再被访问到;每当一个cache miss,替换算法会从左至右扫描NRU bit为“1”的block,如果找到则替换出该cache block,并将新插入的cache block 的NRU bit置为“0”,如果没有找到,那么将所有cache block的NRU bit置为“1”,重新从左至右扫描。

Static RRIP

该替换策略是对NRU的扩展,其将NRU bit扩展成M位,当M=1时,该算法蜕化成NRU。而扩展成M位的原因是为了更细粒度的区分cache block,而不是只有两个状态(最近将要访问和最近最远将要访问)。

该算法的描述和NRU相同,每当一个cache hit,该cache block的NRU bit被设置为“0”表示在最近的将来,该cache block很有可能再被访问到;每当一个cache miss,替换算法会从左至右扫描NRU bit为“2^M -1”的block,如果找到则替换出该cache block,并将新插入的cache block 的NRU bit置为“2^M -2”,如果没有找到,那么将所有cache block的NRU bit增加1,重新从左至右扫描。

上面将新插入的cache block设置为“2^M -2”,主要是为了防止那些很久才能被再次使用到的cache block长期占用cache空间。说到这里,你也许会说,这样岂不是影响那些空间局部性很好的程序的性能,确实是这样。

Dynamic RRIP

对Static RRIP来讲,如果程序的工作集大于cache容量,那么将会频繁的换进换出,造成抖动。为此,Bimodal RRIP提出,对于新插入的cache block,以较大概率设置NRU bits为“2^M -1",同时以较小概率设置为”2^M -2",一次来避免抖动。

那么对于混合的访存序列,应该使用SRRIP还是BRRIP的问题,一种称之为“set Dueling”的技术将两种技术应用到不同的两个cache set上,然后统计两个set上的运行情况(主要是命中率),然后来决断到底使用两种技术中的哪一个,然后将该算法策略部署到其余各个set上。