当前的 cache 数据预取器大致可以分为如下几类:

  1. stride/stream prefetcher
  2. offset/delta prefetcher
  3. spatial prefetcher
  4. temporal prefetcher

但数据预取器处理需要关注自身的预取 accuracy, coverage 等之外，还需要考虑与其他子系统之间交互的影响：

  1. 是否应当进行跨页预取?
    • 跨页预取一般只有在 L1D 中国才需要考虑，因为只有 L1D 可以拿到完整的 VA/PA 信息，L2 只能看到 PA 信息。
    • 数据的访存规律一般由源程序决定，但源程序的访存规律又是建立在虚拟地址空间之上的，因此从 VA 的视角下往往才能看到真实的数据访存规律
    • L1D 本身会过滤一部分访存信息，因此 L2 本身看到的访存规律信息就是不完整的信息，因此其从 PA 的视角就更难看到真实的访存规律

  2. 不同 cache level 之间的互相影响
    - L2 cache 的 hit rate 提高可能导致 L1D cache hit rate 的提高：
    - L2 cache hit rate 提高之后，L1D cache MSHR 的响应 latency 降低，可能导致 L1D cache hit rate 上升

Paper

是否应该跨页

Title Year From URL
To Cross, or Not to Cross Pages for Prefetching? 2025 HPCA https://ieeexplore.ieee.org/abstract/document/10946723

一、Stride / Stream 预取器（经典基础方法）

Title Year From URL
Improving Direct-Mapped Cache Performance by the Addition of a Small Fully-Associative Cache and Prefetch Buffers 1990 ISCA https://doi.org/10.1145/325164.325162
An Effective On-Chip Preloading Scheme to Reduce Data Access Penalty 1995 SC https://doi.org/10.1145/224170.224222
Data Cache Prefetching Using a Global History Buffer 2004 HPCA https://doi.org/10.1109/HPCA.2004.10030

  1. Improving Direct-Mapped Cache Performance by the Addition of a Small Fully-Associative Cache and Prefetch Buffers (Jouppi, ISCA 1990)

    • 早期处理器 cache miss penalty 日益增长，需要在不增加大量硬件的前提下减少 miss 延迟
    • 核心 insight：利用简单的 stream buffer 在 cache miss 时预取后续连续 cache line，可以有效捕获顺序访问模式
    • 提出 stream buffer（流缓冲区）机制，在检测到 cache miss 后自动预取后续 N 个连续 cache line 到独立的 FIFO buffer 中
    • 这是硬件数据预取领域的奠基性工作之一，stream buffer 的思想被后续几乎所有商用处理器所采纳

  2. An Effective On-Chip Preloading Scheme to Reduce Data Access Penalty (Chen & Baer, SC 1995)

    • 单纯的顺序预取无法捕获非连续的规律性访存模式（如数组以固定步长遍历）
    • 核心 insight：通过 Reference Prediction Table (RPT) 记录每个 load 指令（以 PC 索引）的上次访问地址和计算出的 stride，可以预测下次访问地址
    • 提出 PC-indexed stride prefetcher，为每个 load 指令维护一个 (last_address, stride, state) 表项，当 stride 稳定时发出预取
    • 作为 stride 预取的经典方案，其核心思想被 Intel/AMD/ARM 等主流处理器广泛采用至今（如 Intel 的 IP-based stride prefetcher）

  3. Data Cache Prefetching Using a Global History Buffer (Nesbit & Smith, HPCA 2004)

    • 传统 stride 预取器以 PC 为索引，存储效率受限；不同 PC 可能共享相似的访存模式
    • 核心 insight：将全局 miss 地址历史记录在一个共享的环形缓冲区（GHB）中，通过不同的索引方式（PC-indexed 或 Address-indexed）支持多种预取策略
    • 提出 Global History Buffer（GHB）架构，将 miss 地址流存储在全局 FIFO 中，配合 Index Table 实现 PC/DC（PC-indexed delta correlation）、AC/DC（Address-Correlated delta correlation）等多种预取模式
    • 统一了 stride、delta correlation、Markov 等多种预取方法的存储框架，在 SPEC CPU 2000 上取得显著性能提升

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

Title Year From URL
Best-Offset Hardware Prefetching 2016 HPCA https://doi.org/10.1109/HPCA.2016.7446087
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 for SPP (SPP+PPF) 2020 ISCA https://doi.org/10.1109/ISCA45697.2020.00024

  1. Best-Offset Hardware Prefetching (BOP) (Michaud, HPCA 2016)

    • 传统 stride 预取器需要较长的训练时间才能锁定 stride，且只能跟踪单一 PC 的 stride
    • 核心 insight：在一个 page 内，通过”回溯验证”（retrospective verification）的方式评估多个候选 offset 的有效性——对于每个 demand access 地址 A，检查 A-offset 是否曾出现在最近的 demand 访问中
    • BOP 维护一个候选 offset 的评分表，周期性地评估每个 offset 的得分（即该 offset 成功预测的次数），选出得分最高的 best offset 作为全局预取 offset
    • 以极低的硬件开销（约 2KB）获得了 DPC-2 竞赛冠军，在 SPEC CPU 2006 上相比无预取 IPC 提升约 10%

  2. 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%

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

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

  4. 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 模式上表现尤为突出

  5. Perceptron-Based Prefetch Filtering for SPP (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://doi.org/10.1145/3352460.3358325
Access Map Pattern Matching (AMPM) Prefetch 2011 ICS https://doi.org/10.1145/1995896.1995947
Merging Similar Patterns for Hardware Prefetching (PMP) 2022 MICRO https://dl.acm.org/doi/10.1109/MICRO56248.2022.00071

  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. Access Map Pattern Matching (AMPM) Prefetch (Ishii et al., ICS 2011)

    • 传统预取器难以同时处理多种混合访存模式（如同一 page 内既有 stride 又有不规则访问）
    • 核心 insight：为每个 memory page 维护一个 access map（位图），记录哪些 cache line 已被访问，然后通过模式匹配在 map 中发现 stride 和复杂模式
    • AMPM 对每个 hot page 维护一个 access/prefetch 状态位图，扫描 map 中的访问模式来生成预取地址
    • 获得了 DPC-1 竞赛冠军；能够同时捕获多种不同 stride 的混合访问模式

四、Temporal 预取器（时间关联预取方法）

Title Year From URL
Prefetching Using Markov Predictors 1997 ISCA https://doi.org/10.1145/264107.264207
Practical Off-Chip Meta-Data for Temporal Memory Streaming (STeMS) 2009 HPCA https://doi.org/10.1109/HPCA.2009.4798239
Linearizing Irregular Accesses for Temporal Prefetching (ISB) 2013 MICRO https://doi.org/10.1145/2540708.2540730
Domino: Temporal Data Prefetching Using Irregular Patterns of Correlated Misses 2018 MICRO https://doi.org/10.1109/MICRO.2018.00057
Profile-guided temporal prefetching (Prophet) 2025 ISCA https://dl.acm.org/doi/epdf/10.1145/3695053.3731070

  1. Prefetching Using Markov Predictors (Joseph & Grunwald, ISCA 1997)

    • 规则的 stride/stream 预取器无法处理指针追踪等不规则访存模式
    • 核心 insight：可以将 miss 地址序列建模为 Markov 链——miss 地址 A 之后最可能出现的 miss 地址 B 是可以通过历史统计学习的
    • 提出使用关联表（correlation table）记录 miss 地址之间的转移概率，在当前 miss 发生时查表预取最可能的后续 miss 地址
    • 这是时间关联预取（temporal prefetching）的开创性工作，为后续 GHB、STMS、ISB、Domino 等一系列时间预取器奠定了理论基础

  2. Practical Off-Chip Meta-Data for Temporal Memory Streaming (STeMS) (Wenisch et al., HPCA 2009)

    • 时间预取器需要存储大量的 miss 地址序列历史，片上存储远远不够
    • 核心 insight：将完整的 temporal stream 元数据存储在片外 DRAM 中，通过索引结构只在片上缓存当前活跃的少量 stream
    • STeMS 通过 Sampled Temporal Memory Streaming 方法，在片上只维护少量的 stream 头指针和一小段活跃序列，大部分元数据存储在专用的片外 DRAM 区域
    • 在 OLTP、Web 服务器等 irregular 访存密集型工作负载上取得了显著的 miss 覆盖率

  3. Linearizing Irregular Accesses for Temporal Prefetching — Irregular Stream Buffer (ISB) (Jain & Lin, MICRO 2013)

    • 时间预取器存储完整 miss 地址序列的存储开销过大，且序列重放需要精确匹配
    • 核心 insight：将不规则的 physical address 序列映射到一个线性化的”structural address”空间，使得时间关联的地址在结构空间中变为连续的，从而可以用简单的 stream buffer 进行预取
    • ISB 通过训练单元和预测单元，利用 PC-localized correlation 将 physical address pair 映射为结构地址，之后用常规 stream buffer 机制预取
    • 大幅减少了时间预取的存储开销，在 irregular workload 上性能接近理想的全 miss stream 回放方案

  4. Domino: Temporal Data Prefetching Using Irregular Patterns of Correlated Misses (Bakhshalipour et al., MICRO 2018)

    • 完整时间序列的存储和匹配开销过大（如 STMS），限制了时间预取的可扩展性
    • 核心 insight：将完整的 miss 序列分解为成对（pair-wise）的关联关系，每对只需记录 (trigger, target) 即可
    • Domino 将 miss stream 分解为相邻 miss 对的关联表，通过链式查找进行多步预取
    • 以约 SMS 十分之一的存储开销达到了接近完整 temporal stream 回放的覆盖率

五、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 信息的关键工作

六、基于机器学习的预取方法

Title Year From URL
Pythia: A Customizable Hardware Prefetching Framework Using Online Reinforcement Learning 2021 MICRO https://doi.org/10.1145/3466752.3480114
Learning Memory Access Patterns (Voyager) 2020 ICML https://proceedings.mlr.press/v119/hashemi20a.html
A Hierarchical Neural Model of Data Prefetching 2021 ASPLOS https://doi.org/10.1145/3445814.3446752
TransFetch: A Transformer-Based Hardware Prefetcher 2022 ICS https://doi.org/10.1145/3524059.3532372

  1. Pythia: A Customizable Hardware Prefetching Framework Using Online Reinforcement Learning (Bera et al., MICRO 2021)

    • 传统预取器依赖固定的手工规则，难以泛化到多样化的访存行为
    • 核心 insight：将预取决策建模为在线强化学习问题——agent 观察程序上下文状态（PC, delta, page offset 等），选择预取 action（target delta），并根据预取是否被使用获得 reward
    • Pythia 使用在线 RL agent 和基于 CMAC 函数逼近的 Q-learning，动态学习最优预取策略；硬件开销仅约 1% 面积
    • 在 SPEC CPU 和 GAP 基准上相比最佳固定规则预取器 IPC 提升 5-10%，且在不同工作负载间鲁棒性更好

  2. Learning Memory Access Patterns — Voyager (Hashemi et al., ICML 2020)

    • 复杂应用（如图遍历、指针追踪）的访存模式存在长距离依赖，传统预取器无法捕获
    • 核心 insight：基于 Attention 机制的序列模型能有效捕获 miss 地址序列中的长距离时间依赖关系
    • Voyager 使用 Attention-based 神经网络对 miss 地址序列建模，预测下一个 miss 的 page + offset
    • 在指针追踪等复杂不规则模式上大幅优于传统预取器；但推理延迟和模型规模是硬件化的主要挑战

  3. A Hierarchical Neural Model of Data Prefetching (Zeng & Guo, ASPLOS 2021)

    • 访存模式同时包含 page-level 和 offset-level 两个层级的规律，单层模型难以同时建模
    • 核心 insight：使用层级化的神经网络架构，分别建模 page-level 的粗粒度模式和 offset-level 的细粒度模式
    • 提出双层 LSTM/Attention 模型：上层预测目标 page，下层预测目标 offset
    • 在不规则访存场景上覆盖率大幅提升；硬件实现需要定制的神经网络加速单元

  4. TransFetch: A Transformer-Based Hardware Prefetcher (Wu et al., ICS 2022)

    • 基于 LSTM 的预取模型参数量大、推理延迟高，不满足硬件预取的实时性约束
    • 核心 insight：轻量化的 Transformer 编码器可以在保持预测精度的同时降低推理延迟
    • 使用简化的 Transformer encoder 进行访存地址预测，通过模型压缩和量化降低硬件开销
    • 相比 Voyager 推理延迟降低约 3-5 倍，在部分工作负载上精度有提升

七、预取管理与反馈控制

Title Year From URL
Feedback Directed Prefetching: Improving the Performance and Bandwidth-Efficiency of Hardware Prefetchers 2007 HPCA https://doi.org/10.1109/HPCA.2007.346185
Triage: Characterizing and Balancing Accuracy and Timeliness of Prefetching 2019 IEEE CAL https://doi.org/10.1109/LCA.2019.2916520
Perceptron-Based Prefetch Filtering 2012 ISCA https://doi.org/10.1109/ISCA.2012.6237009

  1. Feedback Directed Prefetching (FDP) (Srinath et al., HPCA 2007)

    • 静态配置的预取器激进程度无法适应程序行为的动态变化
    • 核心 insight：通过运行时监测三个关键指标——准确率（accuracy）、延迟性（lateness）和缓存污染（pollution）——动态调节预取行为
    • FDP 实时统计上述三个指标，据此动态调整预取 degree 和 distance，在极端情况下关闭预取
    • 预取管理领域的奠基工作，在 SPEC CPU 上平均性能提升约 30%，被后续几乎所有预取管理工作引用

  2. Triage: Characterizing and Balancing Accuracy and Timeliness of Prefetching (Jimenez, IEEE CAL 2019)

    • 准确率和及时性之间存在根本矛盾——提高 prefetch distance 可以改善及时性但降低准确率
    • 核心 insight：需要同时量化和平衡这两个指标，而非只优化其中一个
    • 提出了同时评价和平衡预取准确率与及时性的方法论和指标
    • 为预取器设计和管理提供了重要的评价框架

  3. Perceptron-Based Prefetch Filtering (Jimenez, ISCA 2012)

    • 预取器发出的大量无用预取浪费带宽并污染缓存
    • 核心 insight：类似分支预测中的 perceptron，使用感知机模型根据多种程序上下文特征对预取请求分类（useful vs useless）
    • 提出 perceptron-based filter，综合 PC、address、delta 等特征在线训练分类器，过滤无用预取
    • 开创了将 ML 技术引入预取过滤的先河，为 SPP+PPF 等后续工作奠定基础

八、综述与基准平台

Title Year From URL
A Survey of Recent Hardware Prefetching Techniques 2023 ACM Computing Surveys https://doi.org/10.1145/3593428
A Survey of Hardware Prefetching Techniques for On-Chip Caches 2016 ACM Computing Surveys https://doi.org/10.1145/2907071
ChampSim: A Trace-Based Simulator for Microarchitectural Studies 2023 IEEE CAL https://doi.org/10.1109/LCA.2023.3311530

  1. A Survey of Recent Hardware Prefetching Techniques (Liao et al., ACM Computing Surveys 2023)

    • 按 stride-based、delta/offset-based、spatial、temporal、RL/ML-based 等维度全面综述了近年主要预取器设计
    • 覆盖了 2010-2023 年间几乎所有重要的硬件预取器论文，并对预取管理策略进行了专门讨论

  2. A Survey of Hardware Prefetching Techniques for On-Chip Caches (Mittal, ACM Computing Surveys 2016)

    • 较早期的全面综述，覆盖了 2000-2015 年间的主要硬件预取技术
    • 按预取器类型、预取层级、评估方法等维度进行分类，对 stride、stream、correlation、spatial 等经典方法有详细分析

  3. ChampSim: A Trace-Based Simulator for Microarchitectural Studies (Gober et al., IEEE CAL 2023)

    • 预取器研究需要标准化的模拟器和基准
    • ChampSim 是 DPC 系列竞赛的官方模拟器，已成为预取器研究的事实标准
    • 详细规范了 ChampSim 的架构和使用方法，为预取器研究的可复现性提供基础