基于频率的策略不依赖于最近使用，而是利用访问频率来识别 victim cacheline，因此访问更频繁的缓存行会比访问较少的 cacheline 优先被保留

优势：

  1. 不易受到扫描的干扰
  2. 能考量更长时期内的 reuse 行为，而不仅仅是最后一次使用

Least Frequently Used Policy (LFU, 1973)

  • 为每个 cacheline 关联一个频率计数器
  • 当 cacheline 被插入时，频率计数器初始化为 0
  • 每次 cacheline 被访问时频率计数器递增
  • 发生 cache miss 时，频率最低的 cacheline 将被踢出
Insertion Promotion Aging Victim Selection
Freq = 0 Increment Freq no Least Frequency

缺点：难以适应应用程序 phase 的变化
来自前一 phase 、具有高使用频率计数的 cacheline ，即使在新 phase 不再被访问，仍会保留在 cache 中

Frequency-Based Replacement (FBR, 1990)

通过有选择地递增频率计数器，将局部性因素从频率计数中剥离

FBR 不会为 LRU Stack 的顶部部分（称为 new section）递增频率计数器
因此短时间的突发时间局部性就不会影响频率计数器

FBR

Insertion Promotion Aging Victim Selection
MRU position, Freq = 0 MRU position, Freq++ if not in new section Increment by 1 LFU Line in old section

缺点：一旦 cacheline 从 new section 老化退出，即使是频繁使用的行也会被快速踢出，因为它们没有足够的时间来累积其使用频率计数

FBR 进一步限制替换操作仅针对 old section 中的 LFU 项，该区域由 LRU 项组成

栈的其余部分称为 middle section，它为 MFU cacheline 提供了足够的时间来累积其频率值

Least Recently/Frequently Used (LRFU, 2001)

LRU 和 LFU 策略代表了综合 recency 与 frequency 信息的策略中的两个极端点

  • 与 FBR 的相同点：LRFU 会考虑对 cacheline 的每一次引用
  • 与 FBR 的不同点：LRFU 通过一个权重函数来衡量每次引用的相对贡献

LRFU 使用一种新的指标： Combined Recency and Frequency (CRF)
通过允许在 recency 与 frequency 之间进行灵活权衡，来探索最优策略

计算 CRF: 权重函数

LRFU 为每个 cacheline 计算一个 CRF 值，该值是每次曾经引用的权重函数 $F(x)$ 之和，其中 x 是曾经的引用距离当前时间的时间间隔

  • 为模拟 FBR ，权重函数可以赋予所有曾经引用相同的优先级
  • 为模拟 recency-based policy，权重函数可以赋予最后一次引用的 cacheline 较高的优先级

LRFU 的权重函数：$F(x) = (\frac{1}{p})^{\lambda x}$，其中 $\lambda$ 是一个根据经验选择的参数(很大程度上决定 LRFU 的性能)

  • 该权重函数赋予较早的 cacheline 呈指数级降低的优先级
  • 使 LRFU 既能保留 frequency-based replacement 的优势，又能支持合适的 aging
Insertion Promotion Aging Victim Selection
$CRF(b) = F(0)$, $LAST(b) = t_c$ $CRF(b) = F(0) + F(t_c - LAST(b)) \times CRF_{last}(b)$, $LAST(b) = t_c$ $t_c += 1$ Line with min CRF value