背景与问题

这篇论文讨论的是 temporal prefetching（时序/相关性预取）
主要用于记忆“某个地址之后通常会访问哪个地址”这样的关联，用于覆盖不规则访存序列，特别适合图计算、稀疏访问、复杂控制流等场景

难点：要记住足够多的地址相关性，需要非常大的 metadata 存储

更具体的问题是：

如何在有限片上空间内存更多有用的相关性
如何减少 metadata 对 LLC 空间和带宽的挤占
如何在动态调整 metadata 分区时，避免巨大数据搬移成本

先前工作

Triage / Triangel

虽然已经把 temporal metadata 放到 LLC 里，避免了 off-chip metadata traffic
在 metadata 表示、替换、分区管理上仍然不够高效

Metadata 管理

先前的 metadata 管理均采用 pairwise metadata: 把一条访问流 [A, B, C, D, E] 存成

(A, B)
(B, C)
(C, D)
(D, E)

问题：

冗余: 中间地址 B/C/D 既作为前一对的 target，又作为后一对的 trigger，被重复存储
高 degree 预取需要多次 metadata 读取 (table storage 带宽需求高)

Triangel 的问题

动态分区会引发代价较高的 metadata 重排
- Triangel 的 metadata 存在 LLC 的 way partition 中，metadata 位置由两级索引决定
- 当 metadata/data partition 大小变化时，索引函数本身会变，原来正确放置的 metadata entry 可能一下子“放错 way”
- Triangel 只能在 repartition 后把这些 entry 搬移重排
- 一次重排可能需要在 LLC 内搬 最多 1MB 的 metadata，平均 516KB 量级
用“缓存数据”的思路管理“预取元数据”
- Triage/Triangel 在 replacement 和 partitioning 上，主要优化 trigger hit，而不是优化 prefetch utility
- 对于 temporal metadata 来说：
  - trigger hit 多，不等于 useful prefetch 多
  - 某个 trigger 即使常出现，若后继 target 不稳定，也没有价值

Belady’s MIN 如果只最大化 trigger reuse，可能会偏好一个 trigger 频繁但 target 不稳定的相关项；
而更合理的是最大化“整个 correlation”的未来复用价值

核心思想：把 pair 变成 stream

采用 stream-based metadata

Streamline 改成按流存，比如把 [A, B, C, D, E] 变成一个以 A 为 trigger、后面跟着多个 target 的 stream entry

论文选择 stream length = 4，即一个 entry 对应 4 个 correlation

这样做有三个好处：

去掉 pairwise 冗余
- 在相同 metadata store 大小时，Streamline 能比 Triangel 多存 33% correlations
更好的空间局部性，降低 metadata read traffic
- 一个 stream entry 里已经包含后续多个 target，高 degree prefetch 可以更少地访问 metadata
- 在 1MB metadata store 下，Streamline 的 metadata traffic 只有 Triangel 的 61%
- 在更小的 store 下，由于 filtered indexing 的帮助，甚至能降到 13%
为“固定索引 + 过滤”式分区提供可能
- 可以彻底避免 Triangel repartition shuffle

Streamline 设计

管理 Stream Metadata

把 metadata entry 从 (trigger, target) 扩展成 (trigger, target1, target2, target3, target4)

对比 Triangel：

Triangel：每个 cache block 里放 12 个 pair correlation
Streamline：每个 cache block 里放 4 个 stream entry，总共 16 个 correlation

Stream Alignment

问题

stream representation 去掉了 pairwise 的显式冗余，但会引入新的问题：

问题 1: 不同 stream entry 之间可能重叠，但 trigger 不同，导致 misalignment

例如：

老 entry: [A, B, C, D, E]
新 entry: [B, C, D, E, F]

问题 2: stale metadata：

老 entry: [A, B, C, D, E]
新 entry: [B, C, X, Y, Z]

如果不对齐，trigger A 仍然会错误预取 D/E，而不是新的 X/Y，造成 useless prefetch 并丢失 coverage

解决

Streamline 在 TU 里给每个 PC 分配了一个 3-entry metadata buffer
在写入完整 stream entry 时，会检查 per-PC metadata buffer 中是否存在包含该 trigger 的最近 stream

如果有，就进行 stream alignment：

以旧 entry 的 trigger 为基准
用新 entry 的更新后相关项覆盖后半段
剩余部分再去 bootstrap 下一条 entry

效果

stream alignment 能把 metadata redundancy 大约减半
3-entry buffer 处在 alignment rate 与 storage overhead 的拐点位置

Filtered Indexing

使用 固定索引函数，与最大 metadata partition 对应

如果某个 metadata entry 映射到当前被分给 data 的 set/way，就直接过滤掉，不保存
(避免产生 misplaced metadata，不需要 repartition shuffle)

如果有 trigger 被过滤掉，可以直接 realign 到前一个未被 filter 的 trigger
(因为 metadata 是 stream，不是 pair, 因此 stream metadata 和 filtered indexing 必须强耦合)

Partitioning

Tagged Set Partitioning

Streamline 不再按 LLC ways 做 metadata partition，而是按 sets 来分配:

每个 metadata set 固定 8 个 way，形成更高等效相联度
effective associativity 为 32（每个 metadata set 的 8 ways × 每 way 4 entries）
把部分 trigger tag 放入 LLC tag store，避免单独维护复杂的两级索引结构 (partial tag 可能 alias，但实验表明影响很小)

utility-aware dynamic partitioning

Triangel 的 set dueling 给每个 metadata hit 相同权重
Streamline 根据当前 prefetch accuracy 给 metadata hit 不同权重，从而更合理地决定 metadata/data 分区大小
和使用 Triangel Partitioning 的版本相比，Streamline 选择到最佳 partition size 的次数高 22 %

Replacement

TP-MIN for Replacement

Belady’s MIN 用在 temporal metadata 上，如果目标是最大化 trigger hit，并不是最优策略

提出 Temporal-Prefetching-MIN (TP-MIN)：
优化目标从“trigger 未来最晚使用”改成“correlation 整体未来最晚使用”

原因：

temporal metadata 不是普通 cache line
其价值不在于“被访问”，而在于“能否产生有用预取

所以 replacement policy 应该围绕 prefetch utility，而不是 trigger reuse

TP-Mockingjay 近似实现 TP-MIN

采样 LLC sets，用 sampler 学习 correlation reuse distance，并修改 sampler entry 的内容，使其以 correlation 为学习对象

论文结果表明：

相比基于 MIN 的版本，TP-MIN 能把 correlation hit rate 提高 9.3 个百分点
提高 prefetch accuracy 4 个百分点
提高 speedup 1.9 个百分点
TP-Mockingjay 让 Streamline 的 correlation hit rate 比 Triangel 高 21.5 个百分点

Prefetch Degree

Triangel 主要靠 confidence
Streamline 定义了一个 instability metric：表示某个 PC 的 metadata entry 需要多频繁地重新从 storage 取回到 metadata buffer
- 如果 hit in buffer 很稳定，说明访存流比较稳定，可以用更高 prefetch degree

实验

存储开销

auxiliary structure 开销：

Streamline：29.4KB/core
Triangel：17.6KB/core（论文提到把 Triangel 扩到 30KB 并不会改变其性能）

1. 单核性能

在 memory-intensive benchmarks 上，相比带 stride L1 预取器的 baseline：

Triangel：5.1%
Streamline：8.1%

按子集看：

SPEC 2006：+2.7 个百分点
SPEC 2017：+1.2 个百分点
GAP：+6.2 个百分点

在 irregular subset 上：

Triangel：11.5%
Streamline：17%

说明 Streamline 对 irregular access 的优势更明显，这和 temporal prefetching 的适用场景一致

2. 多核性能

在 2/4/8-core 上，Streamline 相比 Triangel 的额外提升分别是：

7.2%
6.9%
6.7%

在 4-core heterogeneous mixes 中，Streamline 在 77% 的 mix 上优于 Triangel

多核优势原因分析：
因为多核下 LLC 和带宽都更紧张，metadata efficiency 价值更高：

多存 correlations → 更高 coverage
更少 metadata traffic → 更少 LLC port / bandwidth 干扰
无需 repartition shuffle → 避免额外干扰

这几个效应在多核下都会被放大

3. coverage / accuracy / bandwidth

prefetch coverage +12.5 个百分点
prefetch accuracy +3.6 个百分点

在 bandwidth 受限场景下，仍保持 1.1~3.3 个百分点优势
总体 off-chip traffic 只比 Triangel 高 1.3 个百分点

4. 元数据存储效率

Streamline 用 0.5MB metadata store，就能打赢 1MB 的 Triangel
当双方都是 1MB metadata 时，Streamline 甚至能打赢把 metadata 放到 LLC 外独立存储的 Triangel-Ideal。

说明：单位 metadata 容量的利用率更高

5. 消融实验

单独加 metadata buffer 无效
单独加 stream alignment 无效
metadata buffer + stream alignment 组合起来，coverage 才显著提升
说明: alignment 机制依赖 buffer 提供局部上下文，两者是协同关系
tagged set-partitioning 显著提升 coverage
TP-Mockingjay 显著提升 accuracy

说明 Streamline 的增益是各个优化点协同作用的结果

Limit

1. 依赖“访存流可稳定复现”

Streamline 的所有收益都建立在“访问序列可以被短 stream 反复复用”之上
如果程序的 temporal sequence 本身波动很大，或者 PC-local stream 稳定性不够，stream representation 的收益会下降

在某些 workload 上不如 Triangel，比如 SPEC2006 mcf，因为 Streamline 没有对 scan-like、无 temporal reuse 的 PC 做 bypass

2. 辅助结构复杂，开销较高

29.4KB/core 的 auxiliary overhead

3. utility-aware 仍是近似

实际实现的 TP-Mockingjay 仍只是启发式近似，而不是对 coverage/accuracy/timeliness 收益的完整联合优化