预取数据通常构成 cache 的很大一部分，所以与预取器的交互是设计 cache 替换策略时需要考虑的重要因素

设计预取感知 cache 替换策略有两个主要目标:

  1. 替换策略应避免 cache pollution，这种污染是由不准确的预取引起的
  2. 替换策略应优先淘汰那些可以被预取的 cacheline ，而不是那些难以预取的 cacheline

Belady 的 MIN 算法在无预取的情况下被证明是最优的，但在存在预取器的情况下是不完备的，因为它忽略了第二个设计目标：降低可预取 cacheline 的优先级

降低 Cache Pollution

此类解决方案可分为两大类:

  1. 第一类从预取器获取反馈，以识别可能不准确的预取请求
  • 此类策略通常需要与预取器进行明确的协同设计，或对现有预取器进行修改
  • 例 1，Ishii 等人利用 AMPM 预取器的内部状态来告知预取 cacheline 的插入优先级
  • 例 2，KPC 通过协同设计预取器来提供关于置信度和预计重用时间的反馈。这些信息随后被用于决定是将预取插入 L2 Cache 还是 L3 Cache，同时也用于确定插入 cacheline 的 RRPV 插入位置
  • Yasuo Ishii, Mary Inaba, and Kei Hiraki. Unified memory optimizing architecture: memory subsystem control with a unified predictor. In Proceedings of the 26th ACM International Conference on Supercomputing, pages 267–278, 2012.
  • KPC:
    Jinchun Kim, Elvira Teran, Paul V Gratz, Daniel A Jiménez, Seth H Pugsley, and Chris Wilkerson. Kill the program counter: Reconstructing program behavior in the processor cache hierarchy. In Proceedings of the Twenty-Second Int’Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 737–749, 2017.
  1. 第二类策略独立于预取器工作，通过监控 cache 行为来调整替换决策
  • 此类策略可与任何预取器配合使用，但可能缺乏精确的预取器特定信息
  • 例如，FDP 和 ICP 引入了动态估计预取准确性的方法，并将不准确的预取项插入到低优先级位置
  • FDP 通过统计一个时间周期内有用预取与总预取的比例，以粗粒度估计准确性
  • ICP 对 FDP 进行了增强，考虑了近期被踢出的预取 cacheline ——如果这些 cacheline 能在 cache 中多保留一段时间，本应被视为准确的
  • PACMan 则针对每个时间周期，为预取请求确定最佳的插入与提升策略
  • FDP:
    Santhosh Srinath, Onur Mutlu, Hyesoon Kim, and Yale N Patt. Feedback directed prefetching: Improving the performance and bandwidth-efficiency of hardware prefetchers. In Proceedings of the 13th International Symposium on High Performance Computer Architecture (HPCA), pages 63–74, 2007.
  • ICP:
    Vivek Seshadri, Samihan Yedkar, Hongyi Xin, Onur Mutlu, Phillip B Gibbons, Michael A Kozuch, and Todd C Mowry. Mitigating prefetcher-caused pollution using informed caching policies for prefetched blocks. ACM Transactions on Architecture and Code Optimization (TACO), 11(4):51, 2015.
  • PACMan:
    Carole-Jean Wu, Aamer Jaleel, Margaret Martonosi, Simon C. Steely, Jr., and Joel Emer. PACMan: prefetch-aware cache management for high performance caching. In 44th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 442–453, 2011b.

PACMan 定义了 RRIP 的三种变体:

  1. PACMan‑M: 侧重于通过将预取项插入到 LRU 位置来避免 cache pollution
  2. PACMan‑H: 通过不在 cache hit 时提升预取请求，来降低可预取 cacheline 的优先级
  3. PACMan‑HM
    并使用 set dueling 来寻找给定周期内的最佳插入策略
Baseline DRRIP PACMan-M on DRRIP PACMan-H on DRRIP PACMan-HM on DRRIP
Policy Metric All Demand Prefetch Demand Prefetch Demand Prefetch
SRRIP Insertion 2 2 3 2 2 2 3
Re-Reference 0 0 0 0 No Update 0 No Update
BRRIP Insertion Mostly 3 Mostly 3 Mostly 3 Mostly 3 Mostly 3 Mostly 3 Mostly 3
Re-Reference 0 0 0 0 No Update 0 No Update

降低可预取 Cacheline 的优先级

在存在预取的情况下，Belady 的 MIN 算法是不完备的，因为它没有区分可预取 cacheline 和难预取 cacheline
MIN 算法会同等倾向于缓存 prefetch request cacheline（可预取 cacheline ) ，以及 demand request cacheline（难预取 cacheline)，MIN 算法最小化了 cache misses 的总数（包括 prefetch cacheline），但它并未最小化 demand cacheline misses 的数量

Demand-MIN (2018)

Akanksha Jain and Calvin Lin. Rethinking belady’s algorithm to accommodate prefetching. In 2018 ACM/IEEE 45th Annual International Symposium on Computer Architecture (ISCA), pages 110–123. IEEE, 2018.

Demand‑MIN 能在存在预取的情况下最小化 demand misses

  • Belady MIN 踢出未来最远被重用的 cacheline
  • Demand‑MIN 踢出未来将被预取的最远的 cacheline，如果不存在这样的 cacheline ，则踢出未来将收到 demand 请求的最远的 cacheline，从而为那些无法被预取的 cacheline 提供了空间

Demand-MIN

代价：Demand‑MIN 带来的 demand hit rate 提升，是以增加大量 prefetch miss 为代价的，导致了额外的预取流量

MIN 和 Demand-MIN 定义了一个设计空间的两个极端点：MIN 在一个极端上最小化总流量，而 Demand‑MIN 则在另一个极端上最小化 demand miss

Flex MIN (2018)

Flex-MIN 选择了一个介于 MIN 和 Demand-MIN 之间的点，使得所选点在 demand hit rate 和 memory traffic 之间取得良好的权衡

Protected line: 会被 Demand-MIN 踢出但不会被 Flex-MIN 踢出的 cacheline，因为它会产生 memory traffic 却无法显著提升 hit rate

Flex‑MIN 策略定义为：踢出那个在未来最远时刻会被预取且非 protected line 。如果不存在这样的 cacheline ，则默认使用 MIN

Flex-MIN 通过使用一种简单的启发式方法来识别 protected line

与 MIN 和 Demand‑MIN 不同，Flex‑MIN 在任何理论意义上都不是最优的，因为它基于启发式方法构建

Harmony

Harmony 向 Flex-MIN 学习，探索了 MIN 和 Demand‑MIN 之间丰富的设计空间

Harmony 的整体结构与 Hawkeye 类似，主要区别在于 Harmony 用 FlexMINgen 替换了OPTgen，其中 FlexMINgen 模拟了 Flex‑MIN的解决方案

与 Hawkeye 类似，Harmony 的预测器也是基于 PC 的，只是 Harmony 有两个预测器，一个用于 demand request ，另一个用于 prefetch request

Harmony