Paper

Delta / Offset 预取器（基于地址差分的方法）

Title Year From URL
Efficiently Prefetching Complex Address Patterns (VLDP) 2015 MICRO https://doi.org/10.1145/2830772.2830793
Multi-Lookahead Offset Prefetcher (MLOP) 2019 DPC-3 https://dpc3.compas.cs.stonybrook.edu/pdfs/MLOP.pdf
Signature Path Prefetcher (SPP) 2016 MICRO https://doi.org/10.1109/MICRO.2016.7783743
Perceptron-Based Prefetch Filtering (SPP+PPF) 2020 ISCA <>

  1. Efficiently Prefetching Complex Address Patterns — Variable Length Delta Prefetcher (VLDP) (Shevgoor et al., MICRO 2015)

    • 很多应用的访存模式包含多个交替出现的 delta 值，简单的固定 stride 预取器无法捕获
    • 核心 insight：利用可变长度的 delta 历史序列来预测下一个 delta，类似于文本压缩中的可变长度匹配
    • VLDP 维护多张不同长度的 delta 预测表（1-delta, 2-delta, 3-delta…），通过最长匹配优先的策略选择最佳预测
    • 在复杂的多 delta 模式工作负载上显著优于传统 stride 预取器，在 SPEC CPU 2006 上 IPC 提升约 8%

  2. Multi-Lookahead Offset Prefetcher (MLOP) (Shakerinava & Bakhshalipour, DPC-3 2019)

    • BOP 只选择单一最优 offset，在同时存在多种有效 offset 的场景下预取覆盖率受限
    • 核心 insight：允许多个 offset 同时参与预取，并通过多步前瞻来发出更多预取请求
    • MLOP 维护多个候选 offset 的评分表，根据评分动态选择多个 offset 同时预取，并支持多步 lookahead
    • 在 DPC-3 竞赛中(面向 L1D)取得优秀成绩，特别是在同时存在多种访存 stride 的工作负载上

  3. Signature Path Prefetcher (SPP) (Kim et al., MICRO 2016)

    • 传统 stride/delta 预取器只关注最近一个或几个 delta，无法利用更长的历史 delta 模式
    • 核心 insight：将连续的 page 内 delta 序列压缩（哈希）为一个固定位宽的 signature，利用 signature 查表预测后续 delta 路径，支持多步递归前瞻
    • SPP 使用 Signature Table (ST) 记录每个 page 的当前 signature，使用 Pattern Table (PT) 存储从每个 signature 出发的候选 delta 及其置信度，支持 lookahead path 的递归预取
    • 在 SPEC CPU 2006 上相比 stride 预取器 IPC 提升约 7%，在复杂非规则 delta 模式上表现尤为突出

  4. Perceptron-Based Prefetch Filtering (SPP+PPF) (Bhatia et al., ISCA 2020 / DPC-3)

    • SPP 在多步递归前瞻中会产生大量低置信度的预取候选，这些无用预取会污染缓存并浪费带宽
    • 核心 insight：使用 perceptron 模型综合多种特征（PC signature、page address、delta、置信度等）来判断每个候选预取是否值得发出
    • 在 SPP 框架基础上增加了基于感知机的过滤层，训练权重表以在线学习哪些预取特征组合对应有用预取
    • 相比原始 SPP，准确率大幅提升，整体 IPC 显著改善；在 DPC-3 竞赛中取得了顶尖成绩

Spatial 预取器（空间区域预取方法）

Title Year From URL
Spatial Memory Streaming (SMS) 2006 ISCA https://doi.org/10.1109/ISCA.2006.38
Bingo: Elastic Data Prefetching for Hardware-Efficient Spatial Data Prefetching 2019 HPCA https://doi.org/10.1109/HPCA.2019.00045
DSPatch: Dual Spatial Pattern Prefetcher 2019 MICRO https://dl.acm.org/doi/epdf/10.1145/3352460.3358325
Merging Similar Patterns for Hardware Prefetching (PMP) 2022 MICRO https://dl.acm.org/doi/10.1109/MICRO56248.2022.00071

AMPM 原文实验面向 L2

Bingo 也是针对 PC 进行索引，所以理应面向 L1，但却面向 LLC (猜测：面积太大，分给 L1 不现实)

  1. Spatial Memory Streaming (SMS) (Somogyi et al., ISCA 2006)

    • 许多应用对一个 spatial region（如 4KB page 或 2KB region）内的多个 cache line 有不规则但可重复的访问 footprint
    • 核心 insight：记录 PC 触发的 spatial region 的完整访问 footprint（bitmap），当相同 PC 再次触发新 region 时，回放（replay）之前记录的 footprint
    • SMS 使用 Active Generation Table (AGT) 追踪当前活跃 region 的 footprint，Generation Complete 后存入 Pattern History Table (PHT)，以 PC+offset 为索引
    • 在 SPEC CPU 2000/2006 上覆盖率极高，尤其对 OLTP、图数据库等空间访问密集型工作负载效果显著；但存储开销较大

  2. Bingo: Elastic Data Prefetching for Hardware-Efficient Spatial Data Prefetching (Bakhshalipour et al., HPCA 2019)

    • SMS 需要大量存储记录每个 spatial region 的 footprint，在硬件上不够实际
    • 核心 insight：相同 PC 触发的不同 region 的访问 footprint 高度相似，可以用 PC + trigger offset 作为索引来大幅压缩 footprint 的存储
    • Bingo 通过 Event Table 和 Footprint Table 的两级结构，在仅约 10KB 的硬件开销下实现接近理想 SMS 的预取覆盖率
    • 以远低于 SMS 的硬件开销取得了与 SMS 相当的性能，是空间预取器设计中硬件效率最高的方案之一

  3. DSPatch: Dual Spatial Pattern Prefetcher (Bera et al., MICRO 2019)

    • 单一的空间 footprint 记录方式在不同程序阶段的 footprint 发生变化时适应性不足
    • 核心 insight：维护两种互补的 spatial pattern 记录方式——基于 PC 和基于 page offset——并动态选择更准确的一种
    • DSPatch 同时维护 PC-based 和 offset-based 两组 spatial pattern，通过 anchor 机制和准确率反馈在两者之间切换
    • 在 SPEC CPU 2017 和 GAP 基准上综合表现优于 SMS 和 BOP，尤其在程序行为动态变化的场景中

  4. Merging Similar Patterns for Hardware Prefetching (PMP) (MICRO 2022)

PC-Classifier / Hybrid 预取器（基于 PC 分类的混合方法）

由于需要基于 PC 来分类，此类方法一般是针对 L1DCache 进行预取的

Title Year From URL
Bouquet of Instruction Pointers: Instruction Pointer Classifier-based Spatial Hardware Prefetching (IPCP) 2020 ISCA (DPC-3) https://doi.org/10.1109/ISCA45697.2020.00023
Berti: An Accurate Local-Delta Data Prefetcher 2022 HPCA https://doi.org/10.1109/HPCA53966.2022.00072
Kill the Program Counter: Reconstructing Program Behavior in the Processor Cache Hierarchy 2020 ASPLOS https://doi.org/10.1145/3373376.3378456

  1. Bouquet of Instruction Pointers — IPCP (Pakalapati & Panda, ISCA 2020 / DPC-3)

    • 不同的 load 指令（PC）展现出截然不同的访存模式类型（常量 stride、复杂 stride、全局 stream 等），用单一预取策略无法最优覆盖所有类型
    • 核心 insight：对每个 PC 的历史行为进行分类（constant stride / complex stride / global stream），然后为每个类别分配最合适的预取策略
    • IPCP 使用 IP Table 记录每个 PC 的分类和相关历史信息，constant stride 用 stride 预取，complex stride 用 delta signature 预取，global stream 用 stream 预取
    • 赢得 DPC-3 预取竞赛第一名；在综合得分上超过所有其他参赛方案，证明了 PC 分类方法的有效性

  2. Berti: An Accurate Local-Delta Data Prefetcher (Navarro-Torres et al., HPCA 2022)

    • 现有 delta 预取器在选择使用哪个 delta 进行预取时缺乏对预取及时性（timeliness）的考量
    • 核心 insight：对于同一个 PC，不同的 delta 对应不同的预取距离（time distance）；应选择在预取到达时间与 demand 到达时间匹配最好的 delta
    • Berti 为每个 PC 维护 delta history 和 time stamp history，通过比较 delta 对应的预取延迟与历史延迟来选择最优 delta
    • 以极低的硬件开销取得了 DPC-3 竞赛的顶级覆盖率和准确率，核心创新在于将 timeliness 纳入 delta 选择标准

  3. Kill the Program Counter: Reconstructing Program Behavior in the Processor Cache Hierarchy (Pakalapati & Panda, ASPLOS 2020)

    • 在 L2/LLC 层级中，PC 信息通常不可用（因为 L1 已经过滤），限制了 PC-based 预取策略
    • 核心 insight：可以利用 L2 miss 的地址模式信息来重构等效的 PC 分类信息，无需实际传递 PC 值
    • 提出利用 cache 层级中可获取的地址 pattern 来推断程序行为分类，使 L2/LLC 预取器也能利用 PC-like 信息
    • 使得高层级缓存预取器也能享受类似 L1 级别 PC-based 预取的精确性，是解决 L2 预取器缺少 PC 信息的关键工作