这篇论文提出的是 Streamline（Streamlined On-Chip Temporal Prefetching）：一个针对片上（on-chip）时序预取器的全新设计，核心是用 stream-based 元数据表示 取代 Triage/Triangel 使用的 pairwise 元数据表示。

TLDR：

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

背景和动机

时序预取（Temporal Prefetching） 靠记忆地址对（correlations）来预测任意不规则访问序列：若历史上 X 之后总是跟着 Y，那么下次遇到 X 就预取 Y。代价是需要海量 metadata。

元数据存放方式的演进：

  • Off-chip（GHB [36]、STMS [51]、ISB [20]、MISB [55]）：元数据放 DRAM，DRAM 带宽压力大。
  • On-chip（Triage [54]、Triangel [4]）：把元数据放到 LLC 的一个 partition，彻底消除 off-chip 元数据流量。

片上时序预取虽然摆脱了 DRAM 流量，但仍面临三大问题：

  1. 覆盖率不够：元数据分区容量有限，需要尽可能多塞入有用 correlations。
  2. 元数据 vs 数据分区竞争：需要动态调整两者比例，还要尽量压缩元数据分区以让出 LLC 给数据。
  3. 动态 resize 代价高：Triangel 用两级索引，resize 会把一半元数据「错位」，需搬运最多 1MB。

相关工作：

  • 《Triage: A high-performance, accuracy-guaranteed temporal prefetcher》 Wu et al., MICRO 2019 — https://doi.org/10.1145/3352460.3358300
  • 《Triangel: A high-performance, accurate, timely on-chip temporal prefetcher》 Ainsworth & Mukhanov, ISCA 2024 — https://doi.org/10.1109/ISCA59077.2024.00090
  • 《Practical temporal prefetching with compressed on-chip metadata》 Wu et al., IEEE TC 2022
  • 《Back to the future: Leveraging Belady’s algorithm for improved cache replacement》 Jain & Lin, ISCA 2016
  • 《Effective mimicry of Belady’s MIN policy》 Shah, Jain, Lin, HPCA 2022

Insight

作者提出的核心原则：Exploit the structure and semantics of streams。

现有方法把元数据当作「一条条无关的 key-value」来管理，在三个层面都吃亏：

  1. 格式：pairwise 格式 [A,B,C,D,E] → (A,B)(B,C)(C,D)(D,E)，B/C/D 各出现两次（一次 trigger、一次 target），这是纯冗余。
  2. 替换：Triage 用 Hawkeye、Triangel 用 SRRIP，把元数据当作 cache data 替换，最大化 trigger 访问命中，但 trigger 命中 ≠ prefetch 有用。
  3. 分区：Triangel 用 two-level index function，partition 一变 way 归属就变，结果 metadata 错位，必须花 1MB 的带宽去搬。

将元数据按 stream 语义（长度 4 的连续段）组织后：

  • 一条表项天然存 1 个 trigger + 4 个 target，存储密度 +33%。
  • 同一个 stream entry 的所有 target 都是被同一个 load PC 填充的，天然 PC-localized，预取准确率更高。
  • 一次元数据读可以 issue 高度数预取（不用像 pairwise 那样跳多条）。
  • 每个 metadata entry 代表一段程序行为，可以整体评估 utility 做替换/分区决策。

核心设计

Streamline 的核心设计可以概括为 4 点：

  1. Stream-based metadata：长度 4 的 stream，配合 stream alignment 消除 misalignment 冗余与过时数据。
  2. Tagged set-partitioning + filtered indexing：用定长 index + LLC tag array 内放 partial trigger tag，消除低关联度与昂贵 repartition。
  3. TP-Mockingjay 替换策略：把 Belady 的 MIN 改成 temporal-prefetching 版本（TP-MIN），用 Mockingjay [45] 方式近似，驱逐未来最远被使用的 correlation 而非 trigger。
  4. Utility-aware dynamic partitioning：基于 prefetch accuracy 而非 trigger hit rate 为元数据分区大小打分。

整体硬件如 Fig. 8 所示：在 Triangel 基础上，替换 history/second-chance sampler 为 TP-Mockingjay Sampler；Training Unit 保存 per-PC 的 stream、instability counter、MJ 预测、3-entry metadata buffer；Dynamic Partitioner 用 utility-aware 策略；元数据分区仍在 LLC 但变成 filtered tagged set-partition。

1. Stream-Based Metadata 表示

格式（Fig. 7）：

  • Triangel：每 64B LLC block 存 12 条 (hashed trigger 10b, LUT idx + tag 11b, conf 1b) = 12 个 correlations。
  • Streamline：每 64B block 存 4 条 stream entry，每条 = 10-bit hashed trigger + 4 × 31-bit prefetch target = 4 × 4 = 16 个 correlations。替换 state 和 6-bit partial trigger tag 放在 LLC 原有 tag array 里。
  • 结果：同样大小的元数据分区，Streamline 比 Triangel 多 33% 的 correlations。

Stream 长度选择（Fig. 12a）：作者实测 stream length = 4 是「missed trigger rate 上升拐点前」且存储效率最高的点（错过 6.8% 的 trigger，相对 pairwise）。再长（8、16）错过的 trigger 就升到 24%+，性能反而下降。

1.1 解决 Missed Triggers

流长 4 意味着 trigger 数量少了约 4 倍，一旦 trigger miss 就可能漏掉整段 stream。作者的实测显示 4 是性能拐点，因此选择 4；5 个以上 missed trigger 会显著降低 coverage。

1.2 解决 Stream Misalignment：Stream Alignment（Fig. 3、Fig. 4）

问题：新旧 stream entry 共享子串但 trigger 不同（例如旧 [A,B,C,D,E]、新 [B,C,D,E,F]），naive 插入会造成 冗余（B~E 被重复）或 stale（已被新 stream 淘汰的 [D,E] 仍用旧 trigger A 去预取）。

方案：stream alignment — 新 entry 到来时，在 per-PC metadata buffer（3 条）里查找是否包含新 entry 的 trigger。如果是，把旧 entry 的 trigger 配上新 entry 更新后的 target，产生一条对齐的 entry，再用新 entry 剩下的 correlations 引导下一条。

  • 3-entry metadata buffer 能对齐 67% 的冗余 entry（Fig. 12c），把元数据冗余度从 ~20% 砍到 ~10%（Fig. 12b）。

1.3 解决 Conflict Miss：Tagged Set-Partitioning + Filtered Indexing

Stream entry 更大，能放进同一个 set 的条数更少 → 关联度下降 → 冲突失效上升。

  • Tagged set-partitioning：不像 Triangel 按 way 划分，而是按 set 划分 LLC；被分配做元数据的 set，其 8 ways 全部 给元数据使用，相当于每个 set 都是 full-associative 的元数据 cache。
  • 把 stream entry 的部分 trigger tag（6 bit）外放到 LLC 原有 tag array，使 metadata 读只需 1 次 LLC read 就能定位。
  • Filtered indexing（Fig. 5b）：统一按「最大分区规模」取模，真实分区变小时把不属于合法 metadata way 的条目直接丢弃。这样 partition 变化时 index function 不变，彻底消除 Triangel 的 repartition 搬运（最多 1MB）。
  • 作者 Table I 明确只有 FTS（Filtered + Tagged + Set）方案同时解决低关联度和昂贵 repartition。
  • Filter 会丢 correlations → 用 stream realignment 把被 filter 掉的 trigger「换」为邻近未被 filter 的地址，拿回 72–79% 的性能损失（Fig. 15）。

2. TP-MIN：Utility-Aware 元数据替换

现有方法把 trigger 访问当作 cache hit，套 Hawkeye/SRRIP 最大化 trigger 命中；但 Fig. 6a 显示：一个 trigger B 的 target 不稳定（每次跟着不同地址），trigger B 命中再多也预取不到什么。

TP-MIN（Temporal-Prefetching MIN）：

  • 定义：在多条 correlation 中，驱逐 未来最远被使用 的那条 correlation（而不是像 Belady MIN 那样驱逐未来最远被访问的 trigger 地址）。
  • 直觉：衡量的是 correlation 作为整体的未来被使用价值，而不是单纯 trigger 的未来命中。
  • 实现：用 Mockingjay [45] 的方式 近似 TP-MIN，叫 TP-Mockingjay。在 LLC 抽样 8 sets，每 set 设 32 条采样，只学习 stream entry 首条 correlation 的 reuse distance（3-bit ETR，比 Mockingjay 5-bit 更紧凑）。

效果（Fig. 13c）：correlation hit rate 在 SPEC06/17/GAP 上显著高于 Triangel 和 Triangel+TP-MJ。

3. Utility-Aware Dynamic Partitioning

Triangel 的 set-dueling 分区以 trigger hit rate + data hit rate 为目标；Streamline 把 trigger hit 换成 prefetch accuracy 加权的 metadata hit：

  • 3 档分区：0MB / 0.5MB / 1MB（而 Triangel 有 9 档）。
  • 每次 data hit 让 set-dueling 计数器 +16；每次 metadata hit 按当前全局 prefetch accuracy 打分：10%–25% 加 2、25%–50% 加 3、50%–70% 加 4、70%–90% 加 6、90%–95% 加 7、95%+ 加 8。
  • 每 2^15 sampled accesses 重估一次。

4. Stability-Based Degree Control

每 1024 次 access 统计每个 PC 的 metadata buffer insert 次数（反应其 stream 的不稳定程度）：

  • <400 → prefetch degree = 4（稳定，跑满整个 stream length）。
  • <600 → degree = 3。
  • <800 → degree = 2。
  • 否则 → degree = 1。

直觉：稳定 PC 命中 metadata buffer 75% 的时间，每 4 次访问才需 fetch 一次新 entry；不稳定 PC 每次都 miss，激进预取反而浪费。

5. 整体硬件开销（Fig. 8）

  • TU（Training Unit）：256 个 entry，每 entry = 3-entry metadata buffer + 2 个 10-bit instability counter + TP-Mockingjay 3-bit 预测 = 17.8KB。
  • TP-Mockingjay Sampler：每 entry = valid + 2×8-bit 地址哈希（trigger/target）+ 8-bit timestamp + 8-bit hashed PC，再加 5-bit per-set clock 1.3KB ≈ 10.3KB。
  • 合计辅助结构 29.4KB/core；元数据本身复用 LLC 的 tagged 分区（0/0.5/1 MB）。

实验 Setup

实验平台：ChampSim（trace-driven）。单核 warmup 200M inst、评估 800M inst；多核 warmup 200M、评估 200M。

系统参数（Table II）：

  • Core：4GHz 6-wide OoO，352-entry ROB，hashed perceptron 分支预测。
  • L1I 32KB/8way/4-cycle；L1D 48KB/12way/5-cycle，带 PC-localized stride prefetcher (degree=3)。
  • L2 512KB/8way/10-cycle。
  • LLC 2MB/core/16way/20-cycle，64 MSHRs。
  • DRAM 3200 MT/s、1/2/4/8 channel 视核数、64K rows、tCAS=tRP=tRCD=12.5。

Workload：SPEC 2006、SPEC 2017、GAP，选取 LLC MPKI >1 的内存密集子集；多核 150 个 4 核 mix，分别跑 2/4/8 核。

Baseline：对比 Triangel（SOTA），二者都基于 stride L1D prefetcher 之上。Triangel 尺寸扩到 30KB 不影响性能，故用原尺寸。也对比了 Berti（L1D）、IPCP / Bingo / SPP-PPF（L2）。

实验结果

实验 1：单核性能（Fig. 9）

设计：SPEC06/17/GAP 上单核跑 Triangel vs Streamline，相对 stride baseline 的 speedup。

结果：

  • SPEC06 +2.7pp、SPEC17 +1.2pp、GAP +6.2pp（Streamline 相对 Triangel 的净增益）。
  • 在内存密集子集 Streamline 8.1% vs Triangel 5.1%；irregular 子集 17% vs 11.5%。
  • SPEC06 mcf 上 Triangel 反超：mcf 存在扫描型无时序复用，Triangel 能 bypass，而 Streamline 没 bypass 机制。

结论：Streamline 在不规则 workload 上收益最大；缺点是对非时序访问没有 bypass 能力。

实验 2：多核性能（Fig. 10a/b）

设计：2/4/8 核 mix。

结果：

  • 相对 Triangel 的增益：2 核 +7.2pp、4 核 +6.9pp、8 核 +6.7pp。
  • 77% 的 4 核 mix 上 Streamline 胜 Triangel（Fig. 10b）。

结论：片上元数据竞争在多核更激烈，Streamline 的存储效率收益被放大。

实验 3：DRAM 带宽敏感性（Fig. 10c）

设计：200~3200 MT/s 扫 DRAM 带宽。

结果：Streamline 在低带宽下也能维持 1.1~2.7pp 的优势，总体 off-chip 流量只多 1.3pp。

结论：Streamline 不以牺牲带宽换取 coverage，兼顾 bandwidth efficiency。

实验 4：覆盖率与准确率（Fig. 10d/e）

结果：

  • Coverage：Streamline 相对 Triangel +12.5pp（SPEC06 +7.4、SPEC17 +5、GAP +24.6）。
  • Accuracy：+3.6pp。

结论：stream 格式和 TP-Mockingjay 同时提升 coverage 和 accuracy。

实验 5：Degree 扫描（Fig. 10f）

结果：Streamline 在 degree=4（= stream length）达峰；Triangel 对 degree 不敏感。

结论：stream 格式允许「一 entry 发 4 次预取」，比 pairwise 跨 stream 跳更准。

实验 6：叠加 Berti / IPCP / Bingo / SPP-PPF（Fig. 11）

结果：

  • Berti + Streamline：单核 +4.1/+3.9/+3.8pp（2/4/8 核）over Berti+Triangel；8 核时 Berti+Triangel 基本无收益，但 Berti+Streamline 仍有 3.8pp。
  • 配 L2 规则预取器时 Streamline 仍多提供 ~2× 于 Triangel 的额外 coverage。

结论：Streamline 与强 L1/L2 预取器互补，而非被它们覆盖。

实验 7：存储效率（Fig. 13a）

结果：0.5MB Streamline ≈ 1MB Triangel-Ideal（Triangel 的元数据放 LLC 外专用 store），即元数据减半仍不输。

实验 8：Ablation（Fig. 14）

结果（逐项叠加到 Streamline-unopt）：

  • +Metadata Buffer & +Stream Alignment：只有同时加才能减冗余并提升 coverage +8.7pp、speedup +1pp。
  • +Tagged Set-Partitioning：减冲突失效，进一步 coverage↑。
  • +TP-Mockingjay：accuracy +2.9pp、perf +2.1pp。
  • 合计 +TSP +TP-MJ → coverage +10.7pp / accuracy +2.9pp / perf +2.1pp over Triangel。

结论：每一个组件都承担独特角色，移除任一项都退化。

实验 9：Filtering 带来的 coverage 损失 vs Realignment / Hybrid-Partitioning（Fig. 15）

结果：Realignment 收回 72–79% 的因 filter 丢的性能；小分区场景下 Hybrid-Partitioning（way + set 混合）甚至超过 unfiltered。

实验 10：Partial Tag Aliasing（V-D5）

结果：6-bit partial tag 时只有 3.8% 元数据 alias，性能影响极小。

Limits

  1. 缺 bypass 机制：SPEC06 mcf 这类扫描型无时序复用的 workload，Streamline 反不如 Triangel，因为它无法识别「这 PC 的 stream 永远不会被复用」并跳过训练。
  2. stream length 固定为 4：好处是存储/覆盖均衡，但对于真实 stream 天然很长或很短的 PC，固定值非最优；stream realignment、stability degree control 只能缓解。
  3. metadata buffer + TP-Mockingjay 只学习首条 correlation 的 reuse：stream 尾部 correlation 的 utility 没被独立建模；长流中中段质量差时无法细粒度驱逐。
  4. partial trigger tag 占用 LLC tag array：在不改 LLC tag 存储器的芯片上实现会受限；对 LLC 几何布局有假设。
  5. Utility-aware partitioner 粒度粗（0 / 0.5 / 1MB 三档）：介于两档之间的最佳尺寸可能拿不到。
  6. 仅在 ChampSim 上评估：没有 FPGA/RTL 成本验证，29.4KB/core 的辅助结构在真实 SoC 的面积/功耗代价未披露。