缓存替换策略

发布于 2023-08-20  737 次阅读


概述

在这里记录了部分看到的简单的缓存替换策略。
并未实践,可能有不严谨或者错误之处。

遍历情况指连续访问大量互不相同的元素。
缓存阻塞指多个元素争抢同一个缓存位置导致大量 miss 的情况。

Belady 算法

理论内最有效的缓存替换策略,但是无法用于实践。

未命中时从缓存中逐出未来最晚使用的元素。

随机算法

未命中时从缓存中随机逐出元素。

基于时间的算法

最后访问时间指元素在该生命周期中最后一次被访问的时间刻。

最早使用(LRU)

未命中时从缓存中逐出最后访问时间最早的元素。

无法有效处理遍历情况。

最晚使用(MRU)

未命中时从缓存中逐出最后访问时间最晚的元素。

为处理遍历情况最优的算法,但无法处理新增工作集的情况,一般不独立使用。

预驱逐 LRU(EELRU)

当工作集小于缓存大小时使用 LRU,当检测到工作集大于缓存大小时提前逐出部分空间以避免缓存阻塞。

双态插入(BIP)

以一定概率随机插入 LRU 或 MRU,以缓解 MRU 无法处理新工作集的情况。

分段 LRU(SLRU)

核心思路是保护那些出现至少两次的元素。

将缓存划分为两部分,保护段和试用段。两个段内均独立使用 LRU 算法。
未命中元素首先加入试用段,若再次 hit 则加入保护段。保护段逐出元素时将元素加入使用段并更新该元素访问时间。

重用间隔预测(RRIP)

对于每个元素记录一个 RRPV 值(Re-Reference Prediction Value,重用预测值)。在元素被新插入时 RRPV 值较高,当一个元素 hit 时 RRPV 被设为 $0$。驱逐时逐出 RRPV 为 $maxRRPV$(RRPV 最大值)的元素,若不存在则增加所有元素的 RRPV 值并重复上述操作直至逐出一个元素。

静态 RRIP(SRRIP)

SRRIP 算法在插入新元素时将他的 RRPV 值设置为 $maxRRPV$。

这对于遍历情况是相当有效的。

双态 RRIP(BRRIP)

SRRIP 算法有可能产生缓存阻塞情况,BRRIP 通过在插入新新元素时以一定概率将 RRPV 值设为 $maxRRPV - 1$ 在一定程度上解决此类问题,但略微降低了在一般情况下的性能。

基于频率的算法

访问频率指元素在生命周期内一共的访问频率。

最少频率(LFU)

未命中时从缓存中逐出访问频率最低的元素。

仅在缓存内保留了高频元素,不适用于一般情况。

基于频率算法(FBR)

根据访问时间将元素划分为 new/middle/old 三个区域,new 区域不对频率进行计数,其他两个区域对频率进行计数。逐出时从 old 区域内逐出 LFU。

混合算法

动态插入算法(DIP)

在 LRU 算法和 BIP 算法中动态切换。
在缓存中划分出两个小区域,一个区域使用 LRU 另一个使用 BIP,通过观察两个区域的命中率决定剩余区域使用哪个算法。

动态 RRIP(DRRIP)

当工作集小于缓存大小时 SRRIP 性能最佳,工作集大于缓存大小时 BRRIP 性能最佳。

在 SRRIP 和 BRRIP 间动态切换,用与 DIP 相同的方法决定使用哪种算法。

预测算法

Hawkeye

对缓存操作进行采样,使用采样点过去的操作和 PC 计数器的情况训练预测器,使其对新插入的元素进行预测,若元素为缓存友好则赋予较低的 RRPV 值,若缓存不友好则赋予较高的 RRPV 值,然后使用 RRIP 算法处理缓存内的元素。

参考


我缓慢吐出一串啊吧啊吧并不再想说话