Title Patent Number Inc. Year url
Array of pointers prefetching US12050916B2 Advanced Micro Devices Inc. 2024 https://patents.google.com/patent/US12050916B2/en

TLDR：

  1. 该专利面向的是典型 indirect memory access(IMA)：指针数组本身按 stride 顺序访问，但指针指向的目标地址随机，常规 next-line/stream/stride prefetcher 只能预取指针数组元素，难以提前预取最终 pointer target
  2. 核心思路:
    • 把已有 stride prefetcher 当作训练源：stride prefetcher 发现某个 load PC 以固定 step size 访问数组后，把 PC、stride、confidence 送到 decode 侧
    • decode 再观察该 load 的目的寄存器是否被后续内存操作用于地址计算
    • 如果后续 load/store 的 address compute 使用了该目的寄存器，则该后续内存操作被识别为 pointer target instruction
    • 系统记录这对 producer load 与 consumer memory op，并用 confidence 过滤偶发依赖
  3. 预取动作分两级注入：
    • 先注入 address load，从 load_addr + stride * N 取出未来指针值到临时寄存器；
    • 再注入 pointer target prefetch，用这个未来指针值替换原地址计算中的 producer 目的寄存器，生成最终目标地址并把目标数据预取进 cache

对 L2/IMA/DMP 研究的启发是：DMP 类预取器可以复用前端/解码处的寄存器依赖信息，避免在数据 cache 侧用大地址表暴力学习两跳相关性

背景和动机

数据预取的目标是在执行单元真正请求数据之前，把预测会用到的数据从 memory 或更高层级 cache 提前放入较低延迟的 cache。传统 prefetch controller 通常根据历史地址序列识别 next-line、stream、stride 等模式；这些方法对顺序数组、定步长数组效果好，但对指针数组和间接访问不够。

专利强调的困难来自数组中的元素是指针：

1
2
3
4
P[i]      P[i+1]      P[i+2]      ...   // 指针数组地址：规则 stride
 |          |           |
 v          v           v
T0         T1          T2              // pointer target 地址/数据：可能随机

在机器学习、图分析、稀疏线性代数等工作负载中，程序常见模式是先按 stride 读取一个指针/索引数组，再用读出的值参与后续地址计算。常规 stride prefetcher 可以较好地预测 P[i+k] 的地址，却不知道 P[i+k] 的值，因此不能直接发起 *P[i+k] 或 B[P[i+k]] 的目标预取。若等到真实执行 load 得到指针值再预取，IMA 的长延迟已经暴露出来。

与该专利相关的历史方向包括：

Title Authors, From url
Mechanism for prefetching targets of memory de-reference operations in a high-performance processor Intel Corporation, US5822788A https://patents.google.com/patent/US5822788A/en
System and method for pre-fetching for pointer linked data structures Sun Microsystems, Inc., US6782454B1 https://patents.google.com/patent/US6782454B1/en
System and method for improving index performance through prefetching Lucent Technologies Inc., US20030126116A1 https://patents.google.com/patent/US20030126116A1/en

Insight

Insight 1: 把 pointer-array prefetch 拆成两个可由硬件流水线自然表达的阶段：未来指针值获取和未来目标地址预取

对 IMA 来说，最终目标地址不是一个简单的历史地址序列，而是一个 data-dependent address：后续内存操作的地址计算依赖之前 load 的结果

  • 单纯在 L1/L2 miss stream 中观察地址，通常只能看到最终 target 地址(容易 late)
  • 单纯使用 stride prefetcher，又只能看到指针数组元素本身的线性地址

AMD 的做法是：

  1. 指针数组元素地址通常有 stride，因此未来 producer load 的地址可预测
  2. producer load 的目的寄存器被后续内存操作用于 address compute，因此该 load 的值就是后续 pointer target 地址计算的关键输入
  3. 如果先把未来 producer load 的值取到临时寄存器，就能在真实执行到未来 consumer memory op 之前合成未来目标地址

因此，该方案不是“学习最终地址序列”，而是“学习 address-generation dependence”。
这比纯地址相关性更接近程序语义：decode 阶段虽然没有实际地址值，但能看到寄存器依赖、base/index 使用关系、PC 和指令类型

Insight 2: 复用现有 stride prefetcher

  • stride prefetcher 已经在 load-store unit 中维护 PC、stride、confidence 等信息
  • 专利没有为 pointer-array 单独从零开始学习 stride，而是让 stride prefetcher 训练 decode unit 可访问的 table
  • 这样 pointer-array prefetcher 只在“一个 load 已经被证明是 striding load，而且其结果稳定参与后续地址计算”时进入 insertion mode，减少错误预取和前端注入压力

核心设计

Pointer Array Prefetcher 架构图

  1. load-store unit 中的 stride prefetcher 发现 striding load，并把 {PC, step size, confidence} 作为 training event 写入 decode/pointer-array prefetch 共享表
  2. decode unit 在指令流中匹配 striding load 的 PC，捕获该 load 的 destination register，并监控后续内存操作的 address compute 是否直接或间接使用该寄存器
  3. pointer array prefetcher 维护 producer load 与 pointer target instruction 的配对关系、confidence、cache hit/miss 反馈和临时寄存器号
  4. 当表项训练充分且 cache 反馈显示仍有收益时，prefetcher 通过 injection bus 注入两类指令：address load 和 pointer target prefetch
    • address load 读取未来指针值
    • pointer target prefetch 用该未来值构造后续内存操作的未来目标地址，并把目标数据放入 cache
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
                     training event
        +-----------------------------------------+
        |                                         v
+-------+------+      +------------+      +---------------+
| Stride PF 122| ---> | Table 304  | <--> | Decode Unit   |
| PC,stride,cf |      | striding   |      | dep detector  |
+--------------+      | load table |      +-------+-------+
                              ^                   |
                              | pair/confidence   | pointer target detected
                              |                   v
                       +------+-------+      +------------+
                       | Table 306    | <--> | Pointer    |
                       | target table |      | Array PF   |
                       +------+-------+      +-----+------+
                              |                    |
                              | inject             | inject
                              v                    v
                         address load        pointer target prefetch
                              |                    |
                              v                    v
                         temp register       cache fill for target

设计点 1: 用 stride prefetcher 训练 pointer-array 入口

设计点 1：用 stride prefetcher 训练 pointer-array 入口

针对的问题: pointer-array 的第一跳地址 &P[i] 往往是规则 stride，但最终 target 地址随机。若 pointer-array prefetcher 自己从最终地址 miss stream 学习，会混入太多不规则性，且学习时机偏晚。

解决的思路: 复用 stride prefetcher 已经得到的 PC、step size、confidence，把“这个 load 正在遍历一个规则数组”暴露给 decode 侧

设计：

  • stride prefetcher 每次发起或更新 stride prefetch 时，可以向 table 发送 training event
  • training event 包含 program counter、step size/stride、confidence level
  • table 记录 striding load 相关字段：valid、program counter、stride、active、destination register、trained、striding load register number
  • 若新 training event 与已有 PC 匹配但 confidence 低，则对应 entry 可被 invalidated；若不匹配但 confidence 高，则分配新 entry
  • PC 可只存部分位或 hash，以减少表项宽度

pointer-array prefetch 的触发条件来自“数组元素地址可预测”

设计点 2: 在 decode 侧识别 address-generation dependence

设计点 2：在 decode 侧识别 address-generation dependence

针对的问题: 后续 pointer target instruction 的实际目标地址在 decode 时不可得，但是否依赖某个 load 的目的寄存器在 decode/rename 前后就可以观察

解决的思路: decode unit 对匹配 table 的 load 捕获 destination register，然后监控后续内存操作的 address compute 是否使用该寄存器

设计：

  • 当 decode unit 看到 load instruction 的 PC 与 table 中某个 striding load entry 匹配时，记录其 destination location，例如目的寄存器
  • decode unit 继续监控后续 load/store/load-execute/floating-point load 的地址计算式
  • 如果后续指令的 base register 或 index register 直接使用该 destination register，则识别为 pointer target instruction
  • 如果该 destination register 先经过 LEA/add/sub 等独立指令，再由其结果参与后续内存操作地址计算，也可以作为间接使用识别
  • 检测到后，在 table 中为 pointer target instruction 建 entry，记录 PC、use-index-register bit、other source register、confidence、striding load entry、cache status、cache miss 等

示例化表达：

1
2
3
4
5
load P1 <- [P_base + i * stride]      // striding load，P1 是指针值
load R2 <- [B2 + P1 * s2 + D2]        // P1 参与 address compute
              ^
              |
        pointer target instruction

这里的关键不是 R2 的历史地址，而是 P1 这个 producer load result 在地址生成中的位置。专利进一步记录该寄存器是作为 base 还是 index 使用，便于后续用临时寄存器替换。

设计点 3: 两级指令注入把未来指针值变成未来目标预取

设计点 3：两级指令注入把未来指针值变成未来目标预取

针对的问题: 仅知道 P[i+N] 的地址还不能预取 *P[i+N]，因为目标地址要等 P[i+N] 的值被读取后才知道

解决的思路: 先注入一个未来 address load，把 P[i+N] 的指针值取到临时寄存器；再注入 pointer target prefetch，用临时寄存器替换原 consumer 指令地址计算中的 producer destination register

设计：

  • 当 load instruction 的 table entry 已 trained，且其关联的 table pointer-target entry confidence 达阈值时，load 进入 insertion mode
  • pointer array prefetcher 通过 injection bus 注入 address load
  • address load 的地址为：future_pointer_addr = load_data_source_addr + stride * number_of_steps
  • load-store unit 执行这个注入 load，把未来 load 的数据，即未来指针值，写入 striding load register number 指向的临时寄存器
  • pointer array prefetcher 随后注入 pointer target prefetch
  • 若原 pointer target instruction 的地址计算为 [B + P1 * S + D]，则注入 prefetch 的地址计算可视为 [B + TMP * S + D]，其中 TMP 是 address load 提前得到的未来指针值
  • pointer target prefetch 由 load-store unit 接收，最终把未来 pointer target 写入 cache

NOTE: 这里专利没有提到 pointer target instruction 的地址计算 [B + P1 * S + D] 中，B,S,D 如何训练得到

1
2
3
4
5
6
7
8
9
时间线:

当前迭代 i:
  demand load: P1 = load P[i]
  demand use : load [B + P1*S + D]

注入预取 i+N:
  address load           TMP = load P[i+N]
  pointer target prefetch prefetch [B + TMP*S + D]

这个设计本质上是硬件生成的轻量级预执行，但它只执行 address-generation 需要的那一小段，并把结果限制在临时寄存器和 prefetch 指令中，不改变程序语义状态

设计点 4: confidence, miss-rate 和资源门控

设计点 4：confidence, miss-rate 和资源门控

针对的问题: 指令注入会消耗前端带宽、LSU 资源、MSHR/cache 空间和临时寄存器；错误 IMA 预取还可能造成污染

解决的思路: 只有在 producer/consumer 配对稳定、后续访问确实有 miss benefit 时才保持 insertion mode

设计：

  • table 的 confidence 可在多次检测到同一 pointer target instruction 时递增，缺失检测时递减
  • 其他 source register confidence 可用于过滤额外源寄存器被覆盖导致地址计算不稳定的情况
  • table 的 trained 可由 table 的 confidence 共同决定，trained 后才允许注入
  • cache status 和 cache miss 为每个 pointer target entry 维护 hit/miss 反馈，尤其可跟踪 L1 data cache miss rate
  • 当 status counter 达到阈值时，可通过右移除二衰减计数；如果 status 足够多但 miss rate 低，可关闭或 detrain 该 entry
  • 临时寄存器不需要永久保留；未使用时可回到 integer register pool
  • 比较对象以寄存器号为主，而不是 64-bit memory address。专利指出 register number 典型宽度远小于地址宽度，因此硬件比较和表项成本更低。

设计点 5: 与 cache hierarchy 的关系

设计点 5：与 cache hierarchy 的关系

针对的问题: pointer target 预取到底应落在 L1、L2 还是更高层级，与 lookahead、带宽、污染和命中收益有关

解决的思路: 专利把 cache 泛化为 L0/L1/L2/L3/L4 层级中的某一级；在示例中常把 pointer target 写入 L1 data cache，但权利要求也覆盖 L1/L2/L3

设计：

  • number of steps 可为常数，也可调节；还可根据 cache type 调整，例如 L1 使用较小 lookahead，L2 或更高层级使用更大 lookahead
  • 对 L2 预取而言，address load 和 pointer target prefetch 可以分离策略：第一跳未来指针值可能需要更近的时机，第二跳目标数据可以提前进入 L2，避免 L1 污染
  • cache miss counter 可以改为按层级维护，例如 L1 miss 但 L2 hit、L2 miss、prefetch late 等，以决定 target 应填入哪一级
  • 若 prefetch target 进入 L2 而不是 L1，DMP/IMA 预取器可以把目标设置为“降低 L2 miss 或 DRAM latency”，而不是强行追求 L1 hit

专利没有给出完整 L2 policy，但它的机制为 L2 IMA prefetch 提供了清晰接口：前端识别依赖和计算未来目标地址，cache 侧根据 miss-rate/level feedback 决定是否填充、填到哪里、提前几步。

对 L2/IMA 预取研究启发

  1. AoP 预取应显式建模两跳关系。P[i] 的地址序列和 *P[i] 的目标序列有不同统计性质：第一跳常规整齐，第二跳依赖 load value。L2 预取器若只看 miss address stream，会把这两类信号混在一起
  2. DMP 类设计可以把“未来 load value”作为 first-class state。该专利通过 address load -> temp register -> pointer target prefetch 把未来值显式化，这是 DMP 的核心动作。
  3. Decode/rename 侧的寄存器依赖信息很适合作为 IMA 检测信号。相比在 L2 侧用大表学习地址相关性，decode 侧能直接看到 base/index/source register 的 def-use 关系，误配概率更低。
  4. 现有 stride prefetcher 可以作为 DMP 的 producer detector。对很多 IMA workload，producer load 的 PC 与 stride 很稳定；与其让 DMP 再做一套 stride 检测，不如复用已有 confidence。
  5. L2 版本需要重新设计 fill policy。AMD 示例偏向把 target 填入 L1，但 L2 研究可以把 pointer target prefetch 作为 L2-fill 或 L2-prefetch request，使用更长 lookahead，同时避免污染 L1。
  6. 评估时需要区分“first-hop lateness”和“second-hop lateness”。如果 address load 本身晚了，pointer target prefetch 一定晚；评估时应分别统计未来指针值是否及时到达、目标数据是否及时到达。
  7. 表项设计建议包含 producer PC、stride、consumer PC、base/index 使用方式、其他源寄存器稳定性、temporary register mapping、per-level miss feedback。仅存最终 target PC 或最终 miss address 不足以复现该机制。
  8. 对稀疏矩阵/图遍历等负载，可以把该专利看成硬件化的 prefetch(A[i+N]); prefetch(B[A[i+N]])。研究问题不再是“是否能生成这两个 prefetch”，而是如何选择 N、填充层级、throttle policy 和污染控制。
  9. 与一些 IMA/DMP 论文方法对比，该专利的优势是低成本地利用寄存器号和 decode address compute；潜在弱点是需要前端注入指令、临时寄存器管理，以及对复杂控制流/多 producer、多 consumer 配对的覆盖能力有限。