这篇论文提出的是 TPC（2018, Division of Labor: A More Effective Approach to Prefetching）：

TLDR：

单体预取器面临 scope 与 accuracy 的内在权衡：扩大覆盖范围必然降低精度
提出”分工”思想：用多个专注简单模式的子组件（T2 strided + P1 pointer + C1 spatial locality）组成复合预取器 TPC
TPC 几何平均加速比 1.41x，优于所有 SOTA 单体预取器（1.21-1.33x），且内存流量开销仅 6%

背景和动机

预取是隐藏访存延迟的经典手段，多年来出现了大量预取算法。然而所有预取器都面临一个内在权衡：

Scope（覆盖范围）：预取器试图覆盖多少 miss 地址空间
Accuracy（精度）：发出的预取中有多少真正有用

论文通过分析 AMPM、BOP、SMS 三个 SOTA 预取器在 SPEC 2006 上的表现，发现：

AMPM -> BOP -> SMS，scope 从 67% 增到 87%，但 accuracy 从 58% 降到 48%
扩大 scope 并不一定带来更好的性能，因为不准确的预取会污染 cache、浪费带宽

核心问题：单体预取器试图用一个状态机/算法同时覆盖多种访存模式，但越复杂的模式越难准确捕获。能否换一种思路？

Insight

Scope 和 Accuracy 的目标应该解耦：

Scope 的扩大通过组合更多专注子组件来实现（每个子组件覆盖一类简单模式）
Accuracy 的提升通过让每个子组件只关注自己擅长的简单模式来实现

这就像人类社会的分工：一个人不需要精通所有领域，只需在自己的专业方向上做到精准即可。复合预取器的整体 scope 是各子组件 scope 之和，而每个子组件的 accuracy 不会因为整体 scope 扩大而受损。

论文定义了两个关键度量：

Prefetching Scope S(P)：预取器覆盖的 miss footprint 加权比例
Effective Accuracy：考虑 cache pollution 后的实际有用预取比例（可为负）

核心设计

TPC（The composite Prefetcher with T2+P1+C1）由三个专注子组件 + 一个协调器构成：

T2：专注 canonical strided streams（循环内单指令产生的等步长访存）
P1：专注 pointer chasing patterns（指针数组 + 链表遍历）
C1：专注 high spatial locality regions（密集访问区域的”地毯式轰炸”预取）
Coordinator：基于指令静态信息的硬编码优先级调度（T2 > P1 > C1）

T2: Strided Stream Prefetcher

T2 只针对最简单的 canonical strided stream：同一静态指令在循环内部产生的等步长访存。

三个阶段：

识别循环：通过检测连续出现的 backward branch 来标记内层循环边界。用 Loop-Branch Register + Non-Loop PC Table（NLPCT, 20 entries）过滤非循环分支
检测 stride：用 Stride Identifier Table（SIT）跟踪每条访存指令的 PC、上次地址、delta。连续 16 次 delta 相同标记为 strided；连续 4 次 delta 变化则标记为 non-strided
预取：一旦识别 strided，在 I-cache 中标记该指令，每次执行时通知 T2 发射预取。预取距离 $d = \frac{AMAT + m}{T_{iter}}$，基于循环迭代时间动态调整

两个改进：

多条指令访问同一 stream 时（循环展开），只在触发 L1 miss 时激活跟踪，避免重复
用 PC XOR RAS 栈顶来区分不同调用点的同一指令

存储开销：32-entry SIT + 2KB I-cache state bits + 16-entry NLPCT = ~2.5KB

P1: Pointer Chasing Prefetcher

P1 针对两类指针模式：

1. Array of Pointers：strided 访存的值被用作后续 load 的地址（偏移常量）

在 decoder 处用 Taint Propagation Unit（TPU, 64-bit vector）检测哪些寄存器依赖于 strided load 的值
如果某条 load 的源寄存器被 taint，且其地址与 strided load 的值保持恒定偏移（4 次迭代确认），则识别为 pointer array pattern
稳态时，strided 指令 $i$ 执行时同时发射 stride prefetch 和 pointer prefetch

2. Pointer Chains：load $j$ 的地址 $= M[A_n + \Delta]$，即链表遍历

检测方式类似，但 FSM 不同：pointer chain 必须等上一个预取返回才能发射下一个（串行依赖）
“catch-up” 阶段每周期发射一个预取；稳态后按实际 prefetch distance 发射
纠错机制：保存 SIT 中一个预取地址，与实际地址比对，偏差时重置

存储开销：1-entry PtrPC + 8-entry SIT + TPU(64 bits) + 1KB state bits = ~1.07KB

C1: Spatial Locality (Carpet Bombing) Prefetcher

C1 针对高空间局部性区域：某些指令的访问区域足够密集，直接把整个 region（16 cache lines = super cache line）都预取进来。

两个核心结构：

Instruction Monitor (IM)：16 entries，监控候选指令。每条指令分配一个 entry，收集其访问行为直到做出决策（是否为 dense）
Region Monitor (RM)：16 entries，跟踪 region 的空间局部性。每个 entry 包含 tag + cache line bit vector + PC bit vector

判定流程：

指令触发 primary miss 时进入 IM
RM 持续跟踪该指令触及的 region 的 cache line 使用情况
当 TotalRegions 达到阈值（4），检查 DenseRegions 占比是否 > 3/4
若为 dense，标记该指令为 C1 trained，后续执行时触发整个 region 的预取

存储开销：16-entry IM (640 bits) + 16-entry RM (1248 bits) + 1KB state bits = ~1.2KB

Coordinator: 协调器

协调器负责将访存请求分配给合适的子组件：

自定义组件（T2+P1+C1）之间：硬编码优先级 T2 > P1 > C1。每条访存指令先尝试 T2，T2 不认识则尝试 P1，最后尝试 C1。由于三个组件都是基于指令的，各自只认领自己 trained 的指令，天然形成分工
预取目的地：T2 和 P1 精度高，预取到 L1；C1 精度略低，预取到 L2
与现有预取器组合时：round-robin 分发访存给各组件试探，demand access 命中谁的预取行就由谁后续负责该指令。coordinator 过滤掉已被 T2/P1/C1 认领的指令，只把剩余的交给外部预取器

TPC 总存储开销：~4.57KB

实验 Setup

实验平台：gem5 execution-driven simulator

Workload 选择：

SPEC CPU2006（reference input）
CRONO 图算法套件（google, amazon, twitter, math-overflow, california road-networks）
STARBENCH 嵌入式应用（large inputs）
NPB 科学计算（C class）
4-thread mixes（4 核环境）
每个 benchmark 5 个 SimPoints，每个 10M 指令

系统设置：

1-4 核 OoO, 4-wide, 3.0GHz, 192 ROB, 96 LSQ
L1: Split I/D, 64KB, 4-way, 64B blocks, 3 ports, 1ns, 32 MSHRs
L2: 256KB, 8-way, 2 ports, 5ns, 32 MSHRs
L3: 2MB/Core, 16-way, 12ns (shared)
Main Memory: 4GB DDR3, 1600MHz, 2 channels

对比对象：GHB-PC/DC, FDP, AMPM, SMS, VLDP, SPP, BOP + TPC

实验结果

实验 1: 总体性能（SPEC 单核）

设计：比较 TPC 与 7 个 SOTA 单体预取器在 SPEC 2006 上的加速比（Figure 8）

结果：

TPC 几何平均加速比 1.41x，单体预取器最高 1.33x（BOP）
TPC 比最近竞争者快 6%
TPC 在 21 个 benchmark 中 11 个是最佳，其余在最佳的 5% 以内

结论：复合预取器在性能上全面优于单体预取器

实验 2: 内存流量效率（Figure 9）

设计：比较各预取器归一化的内存流量

结果：

TPC 内存流量开销仅 6%（最低）
次优 BOP 为 12%
解耦 look-ahead 系统约 4%，但那是专用全定制线程

结论：TPC 不仅性能最好，带宽效率也最高

实验 3: 不同 workload 套件（Figure 11）

设计：在 CRONO、NPB、STARBENCH、4-thread mixes 上测试

结果：

TPC 在所有套件上一致优于其他预取器
全部 68 个 workload 几何平均加速 1.39x，其他预取器 1.22-1.31x

结论：TPC 的优势在不同类型负载上具有鲁棒性

实验 4: Scope vs Accuracy 深度分析（Figure 10, 12, 13）

设计：

分析每个预取器的 effective accuracy vs scope（Figure 10）
将预取分为 LHF（strided）、MHF（non-strided high spatial locality）、HHF（其他）三类难度（Figure 13）

结果：

单体预取器 effective accuracy 范围 45%-69%；TPC 平均 82%，最差应用也有 49%
LHF 类：T2 精度显著高于所有单体预取器，是 strided 预取的最佳组件
MHF 类：C1 effective accuracy 61%，优于所有单体预取器在该类的 32%-56%
HHF 类：单体预取器在此类表现极差（平均 38%，部分接近 -1），P1 在此类 effective accuracy 86% 但 scope 有限

结论：分工让每个子组件在自己的”easy target”上达到极高精度，这是性能和效率优势的根本原因

实验 5: Compositing vs Shunting（Figure 15）

设计：将 TPC 与现有预取器以 compositing（分工协作，coordinator 知道各组件专长）和 shunting（并行运行，互不感知）两种方式组合

结果：

Compositing：性能与 TPC alone 持平或略优（+3-8%）
Shunting：性能几乎总是更差（-1% 到 -6%）

结论：分工（compositing with coordinator）远优于简单并行（shunting），coordinator 的知识对资源利用至关重要

实验 6: 预取目的地分层（Figure 16）

设计：比较统一预取到 L2、L1，以及按类别分层预取（LHF->L1, MHF/HHF->L2）

结果：分层预取（TPC 天然支持）优于统一目的地策略

结论：TPC 的组件精度分层天然适合决定预取目的地

Limits

组件数量有限：目前只有 T2+P1+C1 三个组件，HHF 类覆盖不足，TPC 在该类的 scope 较小
Coordinator 设计初步：硬编码优先级 + 简单分发，没有动态适应机制（如基于运行时 accuracy 反馈调整）
组件设计耦合于循环结构：T2 和 P1 都依赖循环检测硬件，对非循环代码中的 strided/pointer 模式无法捕获
实验平台局限：gem5 模拟器 + SPEC 2006，未验证真实硅片行为和更现代的 workload
多核场景探索不足：主要实验在单核，4 线程 mix 实验较简略，未深入分析共享资源竞争下的 coordinator 行为
子组件间无信息共享：T2 的 stride 信息未传递给 C1 帮助过滤已覆盖的 region，可能存在冗余预取

TPC (2018 ISCA): Division of Labor: A More Effective Approach to Prefetching