这篇论文提出的是 Sandbox Prefetching (SBP)：

TLDR：

  1. 现有预取器面临 accuracy vs. coverage 的两难：confirmation-based 预取器（如 stream prefetcher）准确但慢，immediate 预取器（如 next-line）快但不准
  2. SBP 提出用 Bloom filter 作为”沙箱”，模拟评估多个候选 offset prefetcher 的准确率，而不实际发出预取请求，从而避免污染 cache 和浪费带宽
  3. 准确率达标的候选 prefetcher 才被激活，发出真实预取；
  4. 尽管原文只面向多个 offset prefetcher 之间的管理，但其核心思想是模拟评估各个子预取器的准确率，以模拟的准确率作为子预取器管理的指标
    1. 模拟的 score (和 accuracy 相关)越高，该预取器允许的 prefetch 请求数越多
    2. 总的 prefetch degree 的调节通过带宽反馈

背景和动机

硬件预取器按确认方式分为两大类：

  • Confirmation-based prefetcher（如 stream prefetcher）：需要观察到连续多个地址（如 A, A+1, A+2）才确认存在 stream，然后才开始预取。优点是准确，缺点是前几个访问必然 miss（确认延迟），且无法预取非 stream 模式（如链表遍历每次跳两个 cache line）。
  • Immediate prefetcher（如 next-line prefetcher）：每次访问立即预取，无需确认。优点是能覆盖 confirmation-based 无法发现的模式，缺点是准确率低，可能浪费带宽和污染 cache。

核心矛盾：要提高 coverage 就需要更激进的 immediate prefetcher，但激进意味着更多无用预取。如何在不实际浪费资源的前提下，评估哪些激进预取模式是有效的？

相关工作

  • Feedback Directed Prefetching (FDP), Srinath et al., HPCA 2007 — 根据 accuracy、timeliness 和 cache pollution 动态调整 stream prefetcher 的激进度
  • Access Map Pattern Matching (AMPM), Ishii et al., JILP 2011 — 用 address map 追踪 16KB 区域内每条 cache line 的访问状态，穷举匹配 stride 模式进行预取；DPC-1 冠军，但硬件开销大（4KB/core）且关键逻辑在性能路径上

Insight

能否把 immediate prefetcher 的”预取动作”放到一个虚拟环境中执行——只记录地址、不实际搬数据——然后通过后续真实访问来验证其准确性？

如果准确率足够高，再把它部署到真实内存层次中。

这就是”沙箱”的思想：用 Bloom filter 低成本地模拟预取，用全局访问模式做确认，兼得 immediate 的速度和 confirmation 的安全性

核心设计

SBP 结合了 global confirmation 和 immediate prefetch action 两个思想：

  1. Sandbox 评估：用 Bloom filter 沙箱模拟候选 offset prefetcher，不实际发出预取
  2. 轮转评估 + 淘汰：16 个候选 prefetcher 轮流评估，每轮淘汰最差的 4 个，引入新 offset
  3. Strided stream 检测：评估时顺带检测 strided access stream，允许沿流多步预取
  4. 带宽感知预取：根据可用带宽动态控制预取数量

4.1 Sandbox 结构

Sandbox 用一个 2048-bit Bloom filter（256 bytes）实现。每个候选 prefetcher 被评估时：

  • 每次 L2 访问，根据当前地址和候选 offset 计算模拟预取地址，插入 Bloom filter
  • 同时查询当前 L2 访问地址是否在 Bloom filter 中（即之前的模拟预取是否”命中”了）
  • 命中则递增该候选 prefetcher 的 accuracy score

关键优势：Bloom filter 只需 256 bytes，查询时间 O(1)，且 256 次插入下 false positive rate 约 1%。

4.2 候选评估与轮转

  • 维护 16 个候选 offset prefetcher（初始 offset: -8 到 -1, +1 到 +8）
  • 每个候选评估周期为 256 次 L2 访问
  • 评估完一轮（16 个候选）后，淘汰 accuracy score 最低的 4 个，从 [-16, +16] 范围引入 4 个新 offset
  • 每个候选的 score 用 10-bit 计数器存储（最大值 1024）

4.3 Strided Stream 检测

评估时不仅检查当前地址是否在 Bloom filter 中，还回溯检查前 3 个 stride 位置（如 offset=+3 时，检查 A-3, A-6, A-9）。若连续命中则说明存在 strided stream，score 可增加最多 4（当前地址 + 3 个历史位置）。

4.4 预取动作与带宽控制

  • 候选评估完毕且 score 超过阈值后，该 offset prefetcher 被激活发出真实预取
  • Accuracy score 阈值：
    • 256 → 1 PF/access
    • 512 → 2 PFs/access
    • 768 → 3 PFs/access
    • …
  • 低 offset 优先发出预取
  • 每核预取度（prefetch degree）根据上一评估周期的带宽消耗动态计算，范围 1-8

4.5 硬件开销

组件 开销
Bloom filter 256 B
16 个 score 计数器 (10-bit) 20 B
Offset 存储 (5-bit x 16) 10 B
其他计数器 ~10 B
总计 296 B/core

对比：FDP 需要 3.1 KB/core，AMPM 需要 4 KB/core。SBP 仅为 FDP 的 9.5%，AMPM 的 7.2%。

实验 Setup

实验平台：Wind River Simics 全系统模拟器 + USIMM DRAM 模拟器

workload 选择：SPEC CPU 2006（14 个 memory-intensive benchmark）+ 3 个 multi-programmed mix + 6 个 CloudSuite 1.0 workload

系统设置：

  • ISA: UltraSPARC III, 1-4 cores, 3.2 GHz, 4-wide OoO, 128-entry ROB
  • L1 I/D-cache: 32KB, 8-way, 4 cycle
  • L2 cache: 2 MB（单核）/ 8 MB shared（四核），12 cycle，PACMan 替换策略
  • DRAM: DDR3-1600, 12.8 GB/s, USIMM 模型
  • 预取仅在 L2 级别，每核最多 32 个 outstanding prefetch
  • 对比方案：No PF, FDP, AMPM

实验结果

实验 1: 单核性能

设计：14 个 SPEC2006 benchmark，IPC 归一化到 No PF baseline

结果：

  • SBP 平均提升 47.6%（vs. No PF），18.7%（vs. FDP），2.4%（vs. AMPM）
  • SBP 在 GemsFDTD (+5.0%), lbm (+5.1%), leslie3d (+6.8%), milc (+7.2%), sphinx3 (+4.6%) 上超过 AMPM
  • AMPM 仅在 bwaves 上比 SBP 高 3.8%

结论：SBP 以极小的硬件开销（296B vs. 4KB）实现了与 AMPM 相当甚至更好的性能。

实验 2: 多核性能

设计：3 个 mix workload（4 核共享 8MB L2），SBP accuracy cutoff 提高 50% 以节约带宽

结果：

  • SBP 在 mix1 上比 AMPM 高 3.9%
  • mix2 和 mix3 上 SBP 分别低 6.6% 和 6.5%（多核带宽竞争下仍过于激进）
  • SBP 始终优于 FDP，平均高 19.2%，最大 26.0%（mix3）

结论：多核场景下 SBP 的带宽控制仍有改进空间，但整体表现强于 FDP。

实验 3: 带宽与 BPKI 分析

设计：比较各方案的内存带宽消耗和 Bus Transactions Per Kilo Instructions (BPKI)

结果：

  • SBP 通常消耗最多带宽，但多数情况下对应最高性能
  • 在 bwaves 和部分 mix workload 中，SBP 带宽高但性能不是最好
  • mcf 几乎不受预取影响（无 prefetcher 能发出有效预取）

结论：SBP 的高带宽消耗大部分是有效预取，但仍有少量浪费。

实验 4: Coverage

设计：L2 miss 减少百分比（vs. No PF）

结果：SBP 在大多数 workload 上 coverage 最高，因为其激进策略能覆盖更多 miss。

实验 5: 敏感性分析

评估周期长度：256 次 L2 访问最优。过短则候选来不及积累 score，过长则太多低质 prefetcher 被激活。

L2 cache 大小：SBP 用 512KB cache 即可达到 AMPM 用 4MB cache 的性能（zeusmp）。说明 SBP 对小 cache 更友好。

CloudSuite：SBP 平均提升 8.0%（vs. No PF），略低于 AMPM 的 8.3%，优于 FDP 的 6.9%。

Limits

  1. 仅通过 accuracy 来反馈，可能导致 coverage 有限
  2. 仅支持固定 offset pattern：SBP 只评估固定 offset 的 immediate prefetcher，无法处理变长 stride 或复杂访问模式（如 indirect/pointer chasing）
  3. 评估延迟：候选 prefetcher 需要经历完整评估周期才能被激活，对短暂的访问模式可能反应不及时