替换策略的主要目标：提高 hit rate
策略分类：（基于 cacheline 插入的粒度）
- 粗粒度策略：当 cacheline 插入 cache 时平等地对待所有 cachelines ，仅仅根据 cacheline 在 cache 中的行为来区别这些 cachelines
- 细粒度策略：当 cacheline 插入 cache 时区别对待不同的 cacheline ，除此之外还会观察 cacheline 在 cache 中的行为（需要 cache 访问模式的历史信息）
在 cacheline 生命周期中替换策略的作用点：
- Insertion Policy: 新的 cacheline 被插入 cache 时如何初始化该 cacheline 的状态
- Promotion Policy: 某个 cacheline hit 时如何更新其状态
- Aging Policy: 当一个竞争性的 cacheline 插入 cache 或在 cache 中 hit 时如何更新其他 cachelines 的状态
- Eviction Policy: 给定固定数量的 cachelines 选择，踢出哪一条 cacheline
设计约束:
- Granularity: 插入 cacheline 时区分不同 cachelines 的粒度
- History: 替换策略做出决定时需要多少历史信息
- Access Pattern: 替换策略是否仅适用于特定的访问模式，不同的访问模式策略是否会发生变化
Coarse-Grained Policy
当 cacheline 插入 cache 时平等地对待所有 cachelines ，仅仅根据 cacheline 在 cache 中的行为来区别这些 cachelines
基于具体策略在区分 cacheline 时使用的指标，将粗粒度策略可以分为三类:
Recency-Based Policies
- 基于每个 cacheline 的生命周期中前一次被访问的时间排序 cachelines
- 有一个概念上的 recency stack 提供各个 cacheline 被访问的相对顺序
基于生命周期的定义的不同， Recency-Based Policies 又可以分为两类：
- fixed lifetime: 当 cacheline 被踢出 cache 时其生命周期结束
- extended lifetime: 当 cache 被踢出后通过维护一个临时的结构保存 cacheline, 使其有可能再次 cache hit (适应更长的 reuse distance)
Frequency-Based Policies
维护一个 frequency counter 来基于访问频率排序 cachelines
不同策略实现使用不同的方式更新和解释 frequency counter
Hybrid Policies
动态选择一个预定义好的粗粒度策略
在一个评估周期中，观察各个候选策略的 hit rate 并选出最优的策略进行未来的访问
可以很好克服各种单独的粗粒度策略的缺点
Coarse-Grained 粗粒度策略的一个主要任务是：识别三种常见的 cache 访问模式：
- recency-friendly access: 应用程序的访存范围足够小以至于可以完全放入 cache
- thrashing access: 应用程序的访存范围超出了 cache 的容量
- scans: 永不重复的流式访存请求
绝大多数粗粒度策略主要针对这几种访存模式或者结合体
Fine-Grained Policy
当 cacheline 插入 cache 时区别对待不同的 cacheline ，除此之外还会观察 cacheline 在 cache 中的行为
需要 cache 访问模式的历史信息(cacheline 上一个生命周期的信息), 但记录所有 cacheline 的历史信息代价高昂，可以将cachelines 分组然后记录历史信息来减少开销。
基于 cacheline 插入时采用的分组的策略，细粒度策略分为两类：
- Classification-based-policies: 每个组的 cachelines 有两个预测结果：cache-friendly or cache-averse
- Reuse Distance-Based Policies: 每个组的 cachelines 需要预测更细节的 reuse distance (多个预测结果)
Classification-Based Policies
第一级排序: 将 cachelines 分为两类: cache-friendly or cache-averse, 主要的策略是:
- 尽可能踢出 cache-averse lines ，为 cache-friendly lines 留下空间
- cache-friendly lines 的插入优先级比 cache-averse 更高
第二级排序: 基于 recency 对所有的 cache-friendly lines 再进行排序
优势：
- 可以挖掘比较长的历史信息做出更智能的决策
- 可以考虑很多 cache 访问模式
Reuse Distance-Based Policies
reuse distance 超出设定阈值的则可以被踢出 cache