• Cache Replacement Policies - Coarse-Grained Frequency

FREQUENCY-BASED POLICIES

  • 基于频率的策略不依赖于最近的访问频率,而是使用访问频率来识别受害者,因此访问频率较高的行优先缓存在访问频率较低的行之上。这种方法不太容易受到扫描的干扰,并且在较长一段时间内考虑重用行为,而不仅仅是最后一次使用。
  • 最简单的基于频率的策略是最少频繁使用(LFU)策略[Coffman and Denning, 1973],它将频率计数器与每条缓存行关联起来。当该行插入缓存时,频率计数器初始化为 0,每次访问该行时,频率计数器都增加。在缓存丢失时,频率最低的候选对象将被逐出。表 3.9 总结了这些操作。
    20210820170200
  • 不幸的是,基于频率的策略不能很好地适应应用程序阶段中的更改,因为即使不再访问前一阶段中具有高频率计数的行,它们仍然会缓存到新的阶段中。为了解决这个问题,有几个解决方案[Lee等人,2001年,O Neil等人,1993年,Robinson和Devarakonda, 1990年,Shasha和Johnson, 1994] 用最近的信息增加频率信息,让旧的行优雅地老化。这里我们讨论两种这样的解决方案。

Frequency-Based Replacement (FBR)

  • FBR [Robinson和Devarakonda, 1990] 指出,基于频率的方法容易受到短时局域性突发的高计数器值的误导。因此,FBR 通过选择性地增加频率计数器从频率计数中剔除局部性。特别是,FBR 不增加 LRU 堆栈的顶部部分的频率计数器,这被称为新部分。因此,时间局部性的短突发不会影响频率计数器。图 3.8 说明了这个策略。
    20210820170345
  • 不幸的是,这种策略有一个缺点,即一旦新部分的行老化,即使是经常使用的行也会很快被淘汰,因为它们没有足够的时间来建立频率计数。因此,FBR 进一步限制替换在一个旧的部分中使用最少的行,其中包括最近没有被访问的行(LRU堆栈的底部)。堆栈的其余部分称为中间部分,它为经常使用的行提供了足够的时间来建立它们的频率值。
  • 表 3.10 总结了 FBR 的操作策略。
    20210820222332

Least Recently/FrequentlyUsed (LRFU)

  • LRFU 策略 [Lee等人,2001] 建立在这样的观察之上:LRU 和 LFU 策略代表了结合了最近和频率信息的一系列政策的极端点(见图3.9)。LRFU 使用一种名为联合近期和频率(Combined Recency and Frequency, CRF)的新指标,通过允许近期和频率之间的灵活权衡来探索这个频谱。
    20210820222453
  • 与基于频率的策略一样,LRFU 将每个过去对块的引用计算进去,但与基于频率的策略不同的是,LRFU 通过一个权重函数来衡量每个引用的相对贡献。特别地,LRFU 为每个区块计算 CRF 值,CRF 值是权重函数 F(x) 对每个过去的参考的总和,其中 x 是过去的引用距离当前时间的距离。因此,对于纯粹基于频率的策略仿真,权重函数可以对所有过去的引用给予同等的优先级,而对于基于最近的策略仿真,权重函数可以对最后的引用给予较高的优先级。
  • LRFU采用式3.1中的权重函数,其中 λ\lambda 是经验选择的参数。权重函数为老的缓存行提供指数级的低优先级,这使得 LRFU 保留了 FBR 的好处,同时支持优雅的老化。$$F(x) = (\frac{1}{p})^{{\lambda}x}$$
  • 表 3.11 总结了块 b 在不同决策点上的 LFRU 策略操作。
    20210820225822
  • LRFU 的性能很大程度上依赖于此,因此随后开发的 ALRFU 策略动态调整了λ\lambda 的值 [Lee et al., 1999]。