TLDR：

  1. 论文的核心 insight 是：不规则访存的地址本身可能几乎不重复，但生成这些地址的 instruction 及其 data-dependency relationship 往往会重复
  2. ICP 记录的是 (PCpre, PCsuc) 这类 instruction-level correlation，而不是 temporal prefetcher 记录的大量 address-level correlation，因此 metadata 小了三个数量级
  3. ICP 在 cache 侧利用 PCpre 的 cache-line response 触发一段轻量级 speculative execution，沿依赖链计算 PCsuc 的未来地址并发起 prefetch
  4. 相比 indirect prefetcher，ICP 不要求链条从 striding load 开始，也不局限于 nested array access，因此能覆盖 pointer、array-of-pointers、混合 array/pointer 等更一般的不规则模式
  5. 评估中 ICP 相对 basic prefetcher baseline 平均提升 25.51%，比 Triangel 快 13.99%，比 DMP 快 5.97%，总硬件存储约 2.1 KB

背景和动机

不规则访存通常难以被 stream/stride/spatial prefetcher 覆盖。现有高性能方案主要有三类：

  1. Temporal prefetcher
  2. Indirect prefetcher
  3. Runahead-based scheme
Title Authors, From url
Triage / Temporal Prefetching without the Off-chip Metadata Wu et al., MICRO 2019 论文参考文献 [54]
Triangel: A High-performance, Accurate, Timely On-chip Temporal Prefetcher Ainsworth and Mukhanov, ISCA 2024 论文参考文献 [7]
DMP: Differential-Matching Prefetcher for Indirect Memory Access Fu et al., HPCA 2024 论文参考文献 [19]
Tyche: An Efficient and General Prefetcher for Indirect Memory Accesses Xue et al., TACO 2024 论文参考文献 [57]
Vector Runahead / Decoupled Vector Runahead Naithani et al., ISCA 2021 / MICRO 2023 论文参考文献 [39], [40]

Temporal Prefetcher

Temporal prefetcher 的基本思想是记录历史地址序列：当地址 A 再次出现时，预取它过去相关的后继地址 B。问题在于这个机制依赖两个条件：地址要复现，metadata 要保留到下一次复现。论文指出这两个条件都很脆弱：

  1. 对 indirect memory access，很多地址只出现一次。例如同一段 loop/function block 被不同输入调用，b[i] 和 a[b[i]] 的动态地址都变了，address-level temporal correlation 无法命中。
  2. 即使地址会复现，temporal prefetcher 也要保存海量 address correlation。Triage/Triangel 类方案可占用数百 KB 到约 1 MB metadata，并需要 LLC way partitioning、metadata insertion/replacement 等复杂策略。
  3. 论文测得 temporal prefetcher 在 sparse/indirect workload 上只有 5.9% speedup，而 indirect prefetcher 有 42.9%；同时 temporal metadata 的 reuse ratio 比 ICP 低约 10^5。

Indirect Prefetcher

Indirect prefetcher 可以处理 a[b[i]]，但它通常假设 inner load 是 striding load(AOP)，并依靠 stride prefetcher 取回 b[i+d] 再计算 outer address。

这个假设限制很强：如果 inner load 不是规则 stride，或者模式不是标准 nested array，DMP/Tyche 这类方案就容易漏掉

Runahead-based scheme

Runahead-based scheme 可以通过提前执行未来指令来发 miss，但代价是侵入 CPU pipeline：额外 thread/subthread、mode-aware decode、vectorized address generation、checkpoint/recovery 等。

ICP 的目标是在 cache prefetcher 复杂度附近，获得部分 speculative execution 的好处。

Insight

Insight1: 地址不复现时，instruction correlation 仍然复现

论文用一个典型依赖片段说明：

1
2
3
PCpre: lw  t2, 0(t5)    # load b[i]
       add t3, a1, t2   # address of a[b[i]]
PCsuc: lw  t6, 0(t3)    # load a[b[i]]

不同 loop invocation 的输入不同，b[i] 和 a[b[i]] 的实际地址可能完全不重复。但 PCpre 产生的值被 add 消费，随后形成 PCsuc 地址，这条 instruction-level dependency path 是稳定重复的。

也就是说，address-level temporal prefetching 需要学习许多动态地址对：

1
P1 -> S1, P2 -> S2, ..., P100000 -> S100000

ICP 只需要学习一个静态关系：

1
PCpre -> PCsuc

一个 PC correlation 可以隐式覆盖成千上万条动态 address correlation。这解释了为什么 ICP metadata 只有 KB 级，而 temporal prefetcher 需要 MB 级。

Insight2: prefetch target 应该是 miss-heavy irregular instruction，而不是 striding load 的后继

Indirect prefetcher 通常从 striding load 开始找依赖链。但论文指出，“依赖于 striding load”既不是 irregular load 的必要条件，也不是充分条件。

ICP 反过来做：先找 cache miss 多、basic prefetcher 没处理好的 PCsuc，再找能产生其地址输入的 PCpre。这样 target 是真正的问题 load，起点可以是任意 memory instruction，包括：

  1. pointer access：*p -> (*p).next
  2. array-to-pointer：a[i] -> *a[i]
  3. array-of-pointers：p[i] -> *p[i]
  4. 非 stride 的 indirect pattern：例如受条件控制的 a[b[i]]

这也是 ICP 比 DMP/Tyche 更 general 的原因

Insight3: cache-line response 可以作为轻量 speculative execution 的触发点

ICP 不在 core pipeline 中跑完整 runahead，而是等 PCpre 对应 cache line 返回后，在 cache 侧提取 PCpre 读到的值，并用一个 Lightweight Calculator 沿依赖链执行少量算术/逻辑操作，直到得到 PCsuc 的地址

这有两个好处：

  1. 如果 PCpre 的 line 是 basic prefetcher 提前取回的，ICP 可以比 demand execution 更早启动对 PCsuc 的预取。
  2. 如果 PCpre 不能被 basic prefetcher 准确预取，ICP 也能用 demand-fetched line 触发，降低错误数据导致的无效预取。

论文的路径长度分析支持这个设计：70% 以上依赖路径长度不超过 3 条指令，最长也只有 13 条，说明 cache 侧轻量执行器足够覆盖主要场景。

核心设计

ICP 分成两个阶段：

  1. PC Correlation Detection：识别 miss-heavy PCsuc，识别候选 PCpre，从 commit stream 中构建 data-dependency tree，并把 (PCpre, PCsuc) 路径写入 Correlation Table。
  2. Prefetching with PC Correlations：监听 cache-line response。当 response 对应已记录 PCpre 时，提取数据，轻量执行依赖链，计算 PCsuc 地址并发 prefetch。

设计点 1: PC Selector and Classifier

针对的问题：ICP 不能对所有 PC 做依赖检测，否则 storage 和检测开销都会失控。它需要挑出值得处理的 producer 和 target。

解决的思路：用每个 memory PC 的 prefetch hit 和 demand miss 统计来筛选。

设计：

  1. Sample Table 记录每个 PC 的 PF_Hits 和 Demand_Misses，L1/L2 各维护一份。
  2. PCsuc 选择 demand miss 数最高且超过阈值 theta_miss 的 PC。含义是：这些 load 是 basic prefetcher 仍然处理不好的 irregular target。
  3. PCfpre 选择 prefetch coverage 高于阈值 theta_cov 的 PC。含义是：它们的值可以由 basic prefetcher 提前带回来，适合用 prefetch response 触发后继预取。
  4. PCnfpre = PCsuc。论文观察到 irregular load 本身也可能是另一个 irregular load 的 producer，例如 *(*(*p)) 中中间 load 既是前一级 target，也是后一级 producer。
  5. Candidate Table 保存 PCfpre、PCnfpre、PCsuc，作为后续 dependency detection 的输入。

这个分类直接影响后续触发策略：basic-prefetcher-friendly 的 PCpre 可以用 prefetch line 和 demand line；non-friendly 的 PCpre 主要用 demand line，避免错误 prefetch line 放大污染。

设计点 2: PC Correlation Detector

针对的问题：ICP 要找出从 PCpre 到 PCsuc 的真实 data-dependency path，但不能像 full dataflow tracking 那样复杂。

解决的思路：利用 ROB commit 信息，以 PCpre 为根，在 commit path 外侧构建小型 dependency tree。

设计：

  1. 当 committed instruction 的 PC 属于 PCfpre 或 PCnfpre 时，触发一次 dependency tree construction。
  2. 检测期间暂时阻止新的检测请求，并用 Candidate Table 中的 Count 限制同一个 PC 反复占用硬件资源。
  3. Node Table 记录树节点：PC、compressed instruction、parent ID、属性等。
  4. Produce Map 记录物理寄存器 tag 到 producer node ID 的映射，类似简化版 register renaming。
  5. 每条 commit 指令到来时，先查 source register 是否由已有 node 产生；若命中，就把该指令作为 child node 插入 Node Table，并记录 parent。
  6. 如果该指令的 destination register 覆盖了 Produce Map 中旧 producer，需要 invalidate 旧映射，保证依赖关系正确。
  7. 构建过程受两个参数限制：最多处理 128 条 committed instruction，Node Table 最多 16 个节点。
  8. 构建结束后，从每个 PCsuc node 沿 parent pointer 回溯到 root PCpre，得到 correlation path。

论文还估算了 path reconstruction 开销：16-entry Node Table 最坏 120 次 parent-pointer dereference；实际树很浅，用 DFS 可降到 O(N)，相对程序执行时间可忽略。

设计点 3: Correlation Table

针对的问题：需要把检测到的 instruction correlation 保存下来，供后续 cache-line response 触发预取。

设计：

  1. 每个 PC entry 最多保存两个 successor。原因是同一个 producer 可能有多个 consumer，且不同 phase 会观察到不同 successor。
  2. Counter 用来在 successor 超过容量时保留更常见的路径。
  3. Friendly 记录该 PC 是否 basic-prefetcher-friendly，决定后续是否允许使用 prefetch response。
  4. Level 记录 correlation 来自哪个 cache level，对应 L1/L2 独立统计。
  5. Corr PC 保存 successor PC。
  6. Corr Inst 保存 successor 的 operation type 和 immediate。ICP 只保留 Lightweight Calculator 支持的路径。
  7. Src Pred 表示执行 successor 时是否需要预测依赖链外的 source register。

这张表是 ICP 的核心 metadata。评估配置中 Correlation Table 为 64 entry，每 entry 约 7B，总计 448B。

设计点 4: Data Extractor

针对的问题：当 cache line 返回时，ICP 需要从 line 中拿到 PCpre 实际 load 的 word。Demand request 有精确地址，prefetch request 通常只有 line address。

解决的思路：demand line 直接用地址 offset；prefetch line 用历史 offset 分布预测。

设计：

  1. 对 demand-fetched line，Data Extractor 直接根据 demand address 的 offset 抽取对应 word。
  2. 对 prefetch-fetched line，Data Extractor 为 basic-prefetcher-friendly PC 维护历史 line offset 计数。
  3. 某个 offset 的概率超过阈值 0.1 时，就用该 offset 从 prefetched line 取值。
  4. 这样 ICP 可以利用任意已有 cache-line prefetcher 的 line response，而不是依赖 exact-address stride prefetcher。

Ablation 说明 Data Extractor 对 SPEC 特别关键。去掉它以后要尝试 line 内所有 offset，会产生大量 useless prefetch 和 cache pollution。GAP 中影响较小，因为部分 PCpre 会以固定 stride 访问同一 line 内多个元素。

设计点 5: Lightweight Calculator

针对的问题：拿到 PCpre 的值后，需要执行依赖链上的 address-generation 指令，但不能引入 runahead 那样的 pipeline 复杂度。

设计：

  1. 支持简单 arithmetic 和 logical 操作：ADD、SUB、SHL、SHR、AND、OR、XOR。
  2. 如果 successor 是 memory instruction，就计算目标地址并发出 prefetch。
  3. 如果 successor 是中间计算指令，就继续沿 Correlation Table 递归执行，直到 PCsuc。
  4. 不支持的 operation 会在 correlation recording 阶段被排除。

该设计成立的关键是依赖链通常很短，且地址计算多为简单整数运算。论文测得大多数路径 1 到 3 条指令，最长 13 条。

设计点 6: Source Predictor

针对的问题：依赖链中的某条指令可能有多个 source operand，其中一个来自 PCpre 路径，另一个不在路径内，例如 base address。

解决的思路：许多外部 source register 是稳定的 base pointer，因此可用历史值预测

设计：

  1. 当某个 Correlation Table entry 的 Src Pred 置位时，Source Predictor 分配对应 entry。
  2. 它监听 ROB commit，记录目标 source register 的历史值。
  3. 新值与记录值相同则 confidence bit 置位，不同则清零。
  4. 只有 confidence bit 置位时才给 Lightweight Calculator 提供预测值。

Ablation 显示 Source Predictor 对 GAP 影响更明显，因为 GAP 中 indirect pattern 常需要一个稳定 base array value 作为链外操作数。

NOTE:

  1. 如果链外的源寄存器预测和链内的发生重复，设计就出现冗余，且没有办法同时拿到两个源寄存器的值
  2. 链外 base addr 预测错误的影响会很大
  3. RISC-V 的访存指令只有一个源寄存器（src + imm）

Integration

ICP 需要三类接口：

  1. Demand request：普通 prefetcher 已经能看到。
  2. Cache-line fill response：通过 snoop data bus 获取返回数据，并在 MSHR target entry 中扩展 compressed PC 字段
  3. Commit instruction information：通过小 FIFO 从 commit stage 异步传给 ICP

论文强调这些接口非侵入式：commit 信息不在 core critical path 上，检测晚一点只会推迟少量 prefetch；MSHR 扩展示例为 16 MSHR、每个 8 target、10-bit PC，总计 160B。

实验 Setup

实验平台：

Module Configuration
Simulator gem5 full-system mode
Core 5-wide fetch/decode, 10-wide issue/commit, 120-entry IQ, 85/90-entry LQ/SQ, 288-entry ROB, L-TAGE
L1 I/D 64KB each, 4-way, 64B line, 16 MSHRs, 2-cycle hit
L2 512KB, 8-way, 64B line, 32 MSHRs, 9-cycle hit, inclusive
L3 2MB/core, 16-way, 64B line, 36 MSHRs, mostly exclusive, 20-cycle hit
Memory LPDDR5 5500 1x16 BG BL32

Baseline prefetching 环境：

  1. L1D 部署 IPCP 中的 stream、stride、spatial prefetcher。
  2. 使用 Alecto 在这些 basic prefetcher 之间做 selection/scheduling。
  3. ICP、Tyche、DMP 集成在 L1 cache level；Triangel 按原设计集成在 L2；VR/DVR 集成进 CPU pipeline。

对比对象：

  1. Temporal prefetcher：Triangel。
  2. Indirect prefetcher：Tyche、DMP。
  3. Runahead：VR、DVR。
  4. Hybrid：DMP+Triangel。

Workload：

  1. SPEC CPU 2006 irregular benchmarks：论文用于代表 temporal prefetcher friendly、地址有一定复现但模式复杂的场景。
  2. GAP benchmark：代表 non-recurring address 但 instruction-level indirect dependency 稳定的场景。
  3. GAP 输入图使用与 DMP 相同设置。
  4. 所有 workload 使用 SimPoint checkpoint；每个 checkpoint warmup 200M instructions，再模拟 20M instructions；按权重汇总。

实验结果

实验 1: Overall performance

设计：比较 baseline、Triangel、Tyche、DMP、VR、DVR、DMP+Triangel、ICP 在 SPEC 和 GAP 上的 IPC speedup。

结果：

  1. ICP 相对只有 basic prefetcher 的 baseline 平均提升 25.51%。
  2. ICP 分别比 Triangel、Tyche、DMP、VR、DVR 高 13.99%、10.86%、5.97%、15.03%、3.74%。
  3. ICP 与 DMP+Triangel 的平均性能接近：ICP 25.51%，DMP+Triangel 25.61%。
  4. Triangel 在 SPEC 上较强，但 GAP 上弱，因为 GAP 地址很少重复。
  5. DMP/Tyche 在 GAP 上较强，但 SPEC 中许多复杂 irregular pattern 不符合 nested array 假设。
  6. VR 因 runahead 时间不足效果有限；DVR 更好，但对 mcf、gcc 这类复杂依赖仍受限，因为它也偏向从 striding load 发现链。

结论：ICP 的优势不是单一 workload 上最高，而是在 SPEC/GAP 两种不同 irregular 场景中都比较稳，同时硬件代价比 hybrid/runahead 小。

评价：对比 baseline 合理，因为 baseline 已有多种 basic prefetcher；对比 DMP+Triangel 也重要，因为它代表“把 temporal 和 indirect 简单叠加”的强 baseline。

实验 2: DRAM traffic and hybrid comparison

设计：比较各 prefetcher 的 DRAM traffic，归一化到 baseline。

结果：

  1. ICP 比 baseline 增加 13.98% DRAM traffic。
  2. Triangel 增加 9.04%，DMP 增加 16.21%，DMP+Triangel 增加 20.82%。
  3. DMP+Triangel 比 ICP 多 6.84% DRAM traffic。
  4. DVR 比 ICP 多 8.02% DRAM traffic。

结论：DMP+Triangel 虽然性能接近 ICP，但组合方案会叠加两个 prefetcher 的过度请求和硬件代价；ICP 的 traffic 更低。

实验 3: ICP vs Temporal Prefetcher metadata reuse

设计：比较 ICP instruction-level metadata 和 Triangel address-level metadata 的 reuse ratio。定义为 metadata accesses / metadata insertions。

结果：

  1. ICP 的 metadata reuse ratio 比 Triangel 高约 10^5。
  2. GAP 上 Triangel reuse ratio 极低，说明动态地址基本不复现。
  3. 结合 Figure 1，ICP 存储开销比 temporal prefetcher 低三个数量级。

结论：instruction-level correlation 的单位信息量更高。一个 PC correlation 能覆盖大量动态地址实例，而 temporal metadata 需要逐地址保存。

实验 4: ICP vs Indirect Prefetcher generality

设计：在 SPEC 上统计 Tyche、DMP、ICP 能识别的 correlation 数量，并把 DMP 识别但无法有效预取的 pattern 标为 unsolved。

结果：

  1. ICP 平均识别 22 个 instruction correlation。
  2. Tyche 平均识别 7 个，DMP 平均识别 6 个。
  3. DMP 识别的 6 个中约 2 个无法有效预取。

结论：ICP 覆盖的不是“nested array indirection”这个子类，而是更一般的 producer-consumer instruction dependency，因此在 SPEC 中明显更广。

实验 5: ICP vs Runahead hardware complexity

设计：定性比较 ICP 与 DVR 的 integration complexity。

结果：

  1. ICP 不需要额外 hardware thread；DVR 需要 dedicated subthread。
  2. ICP 不改 decode/execute；DVR 需要 mode-aware decode 和 vectorized address-generation 支持。
  3. ICP commit 侧只需异步 buffer；DVR 需要保证 speculative ops 不更新 architectural state，并处理 termination/recovery。
  4. ICP 使用 demand training 和 cache fill interface；DVR 还需要 memory pressure throttling。

结论：ICP 的 speculative execution 能力弱于 runahead，但抓住了 irregular prefetch 所需的短地址计算链，因此复杂度低很多。

实验 6: Learning rate and dependency path length

设计：统计 ICP 发现 correlation 的速度，以及 PCpre -> PCsuc 依赖路径长度。

结果：

  1. 所有 benchmark 中，ICP 在小于总执行时间 10% 的阶段内完成全部 instruction correlation 识别。
  2. SPEC 中大多数 correlation 在前 4% 执行时间内识别；GAP 多数在前 1% 内识别。
  3. 超过 70% 的路径长度不超过 3 条指令。
  4. 最长路径为 13 条指令。

结论：ICP 的 online learning 成本可控，且轻量执行器不需要覆盖复杂通用执行。

实验 7: Correlation Table size sensitivity

设计：将 Correlation Table entries 从 8 调到 128。

结果：

  1. 从 8 增加到 32 时性能提升明显。
  2. 从 32 继续增加到 128，收益很小。

结论：每个 phase 中活跃 instruction correlation 数量有限，小表足够。论文默认 64-entry 表是合理折中。

实验 8: Ablation study

设计：分别移除 Data Extractor、Source Predictor、Demand-trigger execution，观察性能变化。

结果：

  1. 去掉 Data Extractor 后，SPEC 性能明显下降，因为需要尝试 line 内所有 offset，产生 useless prefetch 和 cache pollution。
  2. 去掉 Source Predictor 后，GAP 下降更明显，因为很多 indirect pattern 需要预测稳定 base address。
  3. Demand-trigger execution 贡献小于 prefetch-trigger execution，但仍有价值。SPEC 中 prefetch-trigger 带来约 9.02% speedup，demand-trigger 单独约 4.92%。
  4. 论文观察到 gcc 中 PCpre 和 PCsuc 之间虽然 data-dependency path 短，但可能被大量 control-flow dependent 指令隔开，间隔可达数千 cycles；此时 demand-trigger 仍比 core 真正执行到 PCsuc 更早。

结论：ICP 的几个组件都不是装饰性结构。Data Extractor 解决 timeliness 和污染，Source Predictor 解决链外 operand，Demand-trigger 覆盖 basic prefetcher 不能提前拿到 PCpre 的情况。

实验 9: Storage and energy

设计：统计 ICP 各硬件结构存储，并估算 memory hierarchy energy。

结果：

Structure Storage
PC Selector & Classifier 95B
PC Correlation Detector 536B
Correlation Table 448B
Data Extractor 150B
Source Predictor 74B
Lightweight Calculator 24B
MSHR Extension 160B
Commit FIFO Buffer 128B
ROB Extension 576B
Total 2.1KB

补充结果：

  1. 若换算到 gate-equivalent，ICP 总体约 40k 到 53k NAND2，约等价于 3.3 到 4.3 KB 6T-SRAM。
  2. ICP 相比 Triangel、Tyche、DMP、VR energy 分别高 2.4%、3.7%、1.8%、7.3%。
  3. ICP 相比 DVR 和 DMP+Triangel energy 分别低 6.0%、4.9%。
  4. ICP 内部组件能耗约为 memory-hierarchy energy 的 0.24%，主要来自 table access 和 Lightweight Calculator activation。

结论：ICP 不一定比单个简单 prefetcher 更省能，但相比复杂 runahead 或 hybrid 方案更高效；其核心卖点是 KB 级 metadata 下获得接近 hybrid 的性能。

Limits

  1. ICP 依赖稳定的 instruction-level dependency。如果程序 phase 变化频繁，或者同一个 PC 在不同 context 下对应完全不同的依赖关系，两 successor slots 和小表可能覆盖不足。
  2. ICP 的 Lightweight Calculator 只支持简单整数/逻辑操作。遇到复杂地址计算、乘法、数据相关分支、函数调用、复杂 control dependency 时会放弃这些路径。
  3. Source Predictor 假设链外 operand 多为稳定 base value。如果 base pointer 或 index 变化频繁，confidence 会下降，ICP 可能无法执行对应路径。
  4. Data Extractor 对 prefetched line 的 offset 预测可能带来错误抽取。论文用阈值和 PC classification 控制污染，但 workload 变化后准确性仍是风险。
  5. ICP 需要 commit stream 中的 source/destination register 信息。论文把最坏 ROB extension 计入 576B，但实际 CPU 是否容易暴露这些信息、是否影响物理设计，需要更具体实现验证。
  6. 评估基于 gem5 full-system simulation，真实 OoO core 中 cache-fill PC plumbing、commit FIFO backpressure、prefetch arbitration 与已有 prefetcher 的交互可能更复杂。
  7. ICP 与 DMP+Triangel 平均性能几乎相同，论文主要胜在 storage、traffic、energy 和 complexity；如果系统已有大容量 temporal metadata 预算，ICP 的性能优势未必绝对。
  8. 论文没有给出多核共享 LLC 下 prefetch interference 的深入分析。ICP DRAM traffic 仍比 baseline 高 13.98%，在 bandwidth-constrained 多核场景中可能需要 throttling。