Paper

一、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 (BOP) 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 (SPP+PPF) 2020 ISCA <>

  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 竞赛中(面向 L1D)取得优秀成绩，特别是在同时存在多种访存 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 (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
Bingo: Elastic Data Prefetching for Hardware-Efficient Spatial Data Prefetching 2019 HPCA https://doi.org/10.1109/HPCA.2019.00045
(AMPM) Access map pattern matching for data cache prefetch 2011 ICS https://dl.acm.org/doi/epdf/10.1145/1542275.1542349
RICH Prefetcher: Storing Rich Information in Memory to Trade Capacity and Bandwidth for Latency Hiding 2025 MICRO https://dl.acm.org/doi/epdf/10.1145/3725843.3756081

由于 SMS (没有评估面积), DSPatch 需要针对 PC 进行索引，所以都面向 L1；但 Bingo 同样也是类似的索引方式，但却面向 LLC (猜测：面积太大，分给 L1 不现实)

  1. 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 相当的性能，是空间预取器设计中硬件效率最高的方案之一

  2. 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 的混合访问模式
    • 面向 L2 Cache

  3. RICH (2025 MICRO)

    • 占用面积还是很大，只是把元数据搬到了片外

四、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
Elevating Temporal Prefetching Through Instruction Correlation (Karios) 2025 MICRO https://dl.acm.org/doi/epdf/10.1145/3725843.3756133
Streamlined On-Chip Temporal Prefetching (Streamline) 2026 HPCA

  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 回放的覆盖率

  5. Elevating Temporal Prefetching Through Instruction Correlation (Karios) (NUDT 国防科大, MICRO 2025)

    • 现有 on-chip temporal prefetcher（STMS, Domino, Triage, Triangel）在片上元数据存储容量受限时，利用率普遍不足 —— 要么无差别缓存导致污染，要么像 Triangel 预采样过程本身损失 prefetch 机会。
    • 核心 Insight：少量指令（top 10 IP）贡献绝大多数 cache miss（>90%），且这些 miss 的地址绝大多数会被重用，因此应以”指令”为粒度筛选 metadata，而不是以”地址序列”为粒度统计重复性。
    • Kairos 三阶段设计：Key IP Detection（miss 贡献 >12.5% 即判为 critical）→ Prefetch Evaluation（用 useful prefetch coverage 把指令分为 positive/negative/neutral 三类以控制 metadata 保留策略）→ Dynamic Partition（PID 控制器动态调整 LLC 中 metadata 区大小）。
    • 相比 Triangel 在 SPEC irregular 上 15.1% 的加速，Kairos 达到 25.2%（即 +10.1%），而且总固定硬件开销仅 251 B，约为 Triangel 17.6 KiB 的 1.4%（两个数量级降低）。

  6. Streamlined On-Chip Temporal Prefetching (Streamline) (UT Austin, HPCA 2026)

    • 当前 SOTA 片上时序预取器 Triangel 采用 pairwise 元数据（一条表项存一对 trigger→target），存在 冗余（每个中间地址作为 target 和 trigger 被存两次）、动态分区代价高（重新分区要搬动最多 1MB 元数据）、替换策略不考虑 prefetch utility 三大问题。
    • Streamline 把元数据改为 stream 形式（一条表项 = 1 个 trigger + 4 个连续 target），一举解决：消除冗余（容量多 33% correlations），消除 misplaced metadata，enable 更利于整体 correlation 命中的替换策略。
    • 围绕 stream 引入的三个新问题（missed trigger、stream misalignment、conflict miss），分别用 stream length=4、stream alignment + per-PC metadata buffer、tagged set-partitioning + filtered indexing 解决。
    • 进一步将 prefetch utility 引入管理：提出 TP-MIN（temporal-prefetching Belady’s MIN，驱逐未来最远被使用的 correlation 而非 trigger），以及 utility-aware dynamic partitioning（基于 prefetch accuracy 打分而非 trigger hit rate）。

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

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 等后续工作奠定基础