Title Patent Number Inc. Year url
Cache prefetching US12292834B2 ARM Ltd 2025 https://patents.google.com/patent/US12292834B2/en

该专利要解决的是间接访存场景：先 load 一个 index/pointer，再用它生成下一次 load 的地址。
传统 stride/pattern prefetcher 只能看见前半段规则访问，看不见后半段由数据值决定的任意地址。

TLDR：

  1. ARM 的方案是:
    • 在处理器侧识别“本次访问返回的数据会被用于生成后续访存地址”
    • 把 hint 绑定到 demand request 或相关 prefetch request 上
    • prefetcher 据此把该 request 关联为 indirect prefetch condition
  2. 当第一地址的数据已经在关联 cache 中可用时，address generation circuitry 用该数据直接作为 pointer，或与 offset/base 组合成第二地址，然后 prefetch request issuing circuitry 对第二地址发起预取
  3. 若第一地址的数据尚未进 cache，则 indirect prefetch buffer 记录第一地址或 request 标识，等数据填入 cache 后再触发地址生成和二级预取
  4. 更关键的扩展是：若一串规则 demand access 中至少一个被 hint 标为地址指示数据，prefetcher 可以把同一 pattern 外推出的“一级预取”也标为 indirect，然后使用预取回来的 index/pointer 继续生成“二级预取”，从而显著拉长预取距离

背景和动机

现代处理器依赖 cache 降低平均访存延迟。传统硬件 prefetcher 通常观察 demand access 的地址序列，并在发现 stride、stream 或其他规则 pattern 后外推未来地址。该机制对顺序数组、固定步长结构体遍历有效，但对许多 pointer chasing、稀疏矩阵、gather/scatter 类访问较弱。

本专利关注的访问形态可以抽象为：

1
2
3
load A[i]              ; A[i] 是 index 或 pointer
addr = base + f(A[i])  ; 或 addr = A[i]
load B[addr]           ; 第二次访问地址由第一次 load 的数据值决定
  • 这里第一段 A[i] 可能是规则地址序列，所以常规 prefetcher 可以预取 index array；
  • 但第二段 B[addr] 的地址取决于内存中的数据值，可能没有稳定 stride。
  • 仅靠观察 demand 地址，prefetcher 在真正执行第二次 load 前无法知道目标地址。

专利给出的典型动机是稀疏矩阵或类似结构：为了跳过零元素，内存中维护一个“非零元素位置数组”。处理器先访问该数组拿到 index，再用 index 加上矩阵基址访问实际非零元素。

index array 的访问很规则，但矩阵元素地址是稀疏、任意的。若只预取 index array，真正的矩阵数据仍可能 miss；若等 demand load 拿到 index 后才预取矩阵数据，预取距离又太短。

相关工作主要来自专利引用，方向集中在 hint-based prefetch、indirect prefetch 和 prefetch state 管理：

Title Authors, From url
Run-time updating of prediction hint instructions Dale Morris, 2006 https://patents.google.com/patent/US20060026408A1/en
Prefetch hardware efficiency via prefetch hint instructions Sun Microsystems, 2009 https://patents.google.com/patent/US7533242B1/en
Techniques for Multi-Level Indirect Data Prefetching Ravi K. Arimilli, 2009 https://patents.google.com/patent/US20090198906A1/en
Techniques for Prediction-Based Indirect Data Prefetching Ravi K. Arimilli, 2009 https://patents.google.com/patent/US20090198905A1/en
Data prefetch ramp implementation based on memory utilization IBM, 2016 https://patents.google.com/patent/US20160034400A1/en
Hardware prefetcher for indirect access patterns Intel, 2016 https://patents.google.com/patent/US20160188476A1/en
Prefetching from indirect buffers at a processing unit AMD, 2022 https://patents.google.com/patent/US20220091847A1/en
Producer prefetch filter Arm Limited, 2023 https://patents.google.com/patent/US20230229596A1/en

Insight

这个专利的核心 insight 有三层。

Insight 1: 间接目标地址不能从历史地址直接预测，但可以从已加载的数据中计算

传统 prefetcher 把地址序列当作主要信号，而这里的未来地址隐藏在 cache line 的数据内容中。
只要硬件知道某个 load 返回的是 address indicating data，就可以在数据到达 cache 时把它解释为 index/pointer，并主动生成下一跳地址

Insight 2: 处理器前端或执行 pipeline 比 prefetcher 更早知道数据依赖语义

例如 decode 阶段看到类似下面的指令序列：

1
2
LD1SW {Z4.D}, P2/Z, [X26, X20, LSL #2]
LD1D  {Z5.D}, P2/Z, [X25, Z4.D, LSL #3]

第一条把内存数据装入向量寄存器 Z4，第二条用 Z4 的元素作为 index 生成多个 load 地址

对 prefetcher 来说，第一条只是普通 load；对 pipeline 来说，这是一条 producer load，其结果随后会作为 address operand。
专利把这种语义信息压缩成 hint，随 request、旁路消息或共享状态传给 prefetcher，使 prefetcher 不必自己做复杂的数据依赖推断

Insight3: 把间接预取条件传播给由常规 pattern prefetcher 生成的 request，可以把二级预取提前到 demand 之前

如果 demand 访问 [000]、[001]、[002] 是规则访问 index array，pattern detection circuitry 会外推出 [003]、[004] 并发出一级 prefetch

若同一序列中的 demand [000] 已经带 hint，硬件可以合理假设该序列访问的都是 address indicating data，于是把 [003]、[004] 的 prefetch 也标为 indirect。这样当 [003]、[004] 的 index 被预取回来时，硬件可进一步发出 [109]、[101] 等二级目标预取。这个动作发生在 CPU demand 真正访问 [003]、[004] 之前，因此比“等 demand load 返回 index 后再预取”有更长的隐藏延迟窗口

从体系结构角度看，这是一种“语义提示 + 数据驱动预取 + pattern 外推”的组合：

  1. 语义提示解决“哪些数据可以被当成地址”。
  2. 数据驱动预取解决“任意地址如何产生”。
  3. pattern 外推解决“如何把时机提前到 producer demand 之前”。

核心设计

该专利定义的硬件围绕一个增强型 prefetcher 展开: 在已有 stride/pattern prefetcher 旁边加入 indirect prefetch condition 的标记、追踪和消费机制

Hint-based indirect prefetcher 架构图

整体路径如下：

  1. CPU/coprocessor 观察指令或访存语义，在某个 demand memory access request 上附带 hint，表示该 request 返回的数据将用于生成后续访存地址
  2. associating circuitry 观察 demand request 和 prefetch request，把带有 hint 或间接继承 hint 的 request 关联到 indirect prefetch condition
  3. address generation circuitry 在 address indicating data 可用时生成第二地址：数据可以直接是 pointer，也可以是 index，需要与 offset/base 组合
  4. prefetch request issuing circuitry 对第二地址发出 prefetch，使目标数据提前进入关联 cache
  5. 若 address indicating data 暂不可用，indirect prefetch buffer 保存 request/address 标识，等待 cache fill 后再触发地址生成
  6. pattern detection circuitry 仍负责识别常规规则序列，并将其外推出的一级 prefetch 与 indirect prefetch condition 结合，从而发起二级预取
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
             +----------------------+
             |   CPU / Coprocessor  |
             |  decode/execute hint |
             +----------+-----------+
                        |
        demand request + hint / pattern hint
                        |
                        v
+------------------------------------------------+
|                   Prefetcher 40                |
|                                                |
|  +----------------+      +------------------+  |
|  | Associating    |<---->| Pattern Detect   |  |
|  | Circuitry 304  |      | Circuitry 308    |  |
|  +-------+--------+      +---------+--------+  |
|          |                         |           |
|          | indirect condition      | pattern   |
|          v                         v           |
|  +----------------+      +------------------+  |
|  | Address Gen    |<---->| Indirect Prefetch|  |
|  | Circuitry 306  |      | Buffer 310       |  |
|  +-------+--------+      +------------------+  |
|          | generated second/further address     |
|          v                                      |
|  +---------------------------+                  |
|  | Prefetch Request Issuing  | 312              |
|  +-------------+-------------+                  |
+----------------|-------------------------------+
                 |
                 v
           +-----------+
           | Cache 318 |
           +-----------+

设计点 1: hint 标记地址指示数据

针对的问题：prefetcher 仅看地址流，不知道某次 load 返回的数据是否会变成下一次访存地址。若盲目把数据当地址，会产生大量错误预取；若完全不做，则无法处理间接访问

解决的思路：让 associated processing circuitry 负责识别语义，prefetcher 只消费低成本 hint。hint 可以来自指令序列检测、特定指令类型识别，或者 pattern metadata

设计：

  1. CPU/coprocessor 在检测到 producer load 和 consumer load 的依赖关系时发 hint
    • 例如第一条指令 load 到寄存器，后续指令用该寄存器作为地址生成输入。
  2. hint 可以随 demand access request 编码发送
    • request 字段包括 request type、address indication、other information，以及 hint information/offset indication
  3. hint 字段可以是一个 flag，表示 request 访问 address indicating data；也可以携带 offset/base 信息，供 address generation circuitry 计算第二地址
  4. 如果 offset 太大，也可以分布在多个 request 中，或者由处理器以其他共享方式提供
1
2
3
4
Demand access request
+--------------+--------------------+-------------------+---------------------------+
| Request type | Address indication | Other information | hint / offset indication  |
+--------------+--------------------+-------------------+---------------------------+

这个设计的要点是: 把“数据值是否可解释为地址”的判断放在更有语义上下文的处理器侧，而不是要求 prefetcher 从历史 miss 或寄存器依赖中反推

设计点 2: indirect prefetch condition 的关联与消费

针对的问题：有了 hint 后，还需要把 hint 与具体 memory access request 精确绑定，并在数据到达 cache 时触发后续动作

解决的思路：引入 associating circuitry，把某个 first memory access request 标成 indirect prefetch condition；address generation circuitry 只对满足该条件的 request 消费返回数据并生成第二地址

设计：

  1. associating circuitry 同时观察 CPU demand request 和 prefetcher 自己发出的 prefetch request
  2. 当 request 带有 hint，或者通过同一 pattern 间接继承 hint 时，将该 request 关联到 indirect prefetch condition
  3. 如果第一地址的数据已经在关联 cache 中，address generation circuitry 直接读取该 address indicating data
  4. 如果该数据是 pointer，则第二地址等于该数据值；如果是 index，则与 offset/base 组合得到第二地址
  5. prefetch request issuing circuitry 发出对第二地址的 prefetch

该路径本质上把“load value prediction”问题降级为“load value consumption after arrival”：硬件不预测 index/pointer 的值，而是在它真实到达 cache 后尽快用它生成下一跳预取。

设计点 3: indirect prefetch buffer 处理数据尚未可用的窗口

针对的问题：当 hint/request 到达 prefetcher 时，第一地址的数据可能还没有命中 cache。若此时放弃，很多低层 cache 或内存返回的数据就无法用于间接预取

解决的思路：indirect prefetch buffer 记录需要等待的数据来源，当 cache 中出现对应数据后再触发地址生成

设计：

  1. 当 request 被关联 indirect prefetch condition，但第一地址数据尚不可用时，address generation circuitry 把该 request 或第一地址的标识写入 indirect prefetch buffer
  2. buffer entry 至少需要能匹配“哪个 cache fill 或 cache-resident line 对应待消费的 address indicating data”
  3. 硬件可以轮询或通过 cache fill 事件检查 buffer entry 是否满足
  4. 一旦对应数据可用，address generation circuitry 读取数据生成第二地址，并由 issuing circuitry 发 prefetch
  5. 该机制同样适用于 demand request 和被标为 indirect 的 prefetch request

这避免了设计被限定为 L1 hit 才能工作。只要第一 request 最终使 index/pointer 进入可见 cache，硬件就能延迟生成二级预取

设计点 4: 与 pattern detection 结合拉长预取距离

针对的问题：若只在 demand producer load 返回后生成第二地址，预取距离可能仍然太短。尤其是 producer load 和 consumer load 紧邻时，二级预取未必赶得上真实 demand

解决的思路：对 producer load 所在的规则序列做一级预取，并把 indirect condition 传播到这些一级 prefetch 上。这样“预取回来的 index/pointer”也能作为地址生成输入

设计：

  1. pattern detection circuitry 观察 demand request，识别出一串相关地址，例如 [000]、[001]、[002] 的 +1 stride
  2. prefetch request issuing circuitry 外推出 [003]、[004]，先预取 index array 中更远的位置
  3. 如果该 demand 序列中至少一个 request 已经关联 indirect prefetch condition，则 associating circuitry 假设同一序列访问的也是 address indicating data
  4. [003]、[004] 这些一级 prefetch 也被关联 indirect prefetch condition
  5. 当 [003]、[004] 的 index/pointer 返回后，address generation circuitry 继续生成 [109]、[101] 等任意地址，并发出二级 prefetch
1
2
3
4
5
6
7
8
9
10
Index array / address indicating data        Target data region

ADDR[000] -> index[008] -- offset[100]+008 --> ADDR[108]   D -> P
ADDR[001] -> index[002] -- offset[100]+002 --> ADDR[102]   D -> P
ADDR[002] -> index[004] -- offset[100]+004 --> ADDR[104]   D -> P
ADDR[003] -> index[009] -- offset[100]+009 --> ADDR[109]   P -> P
ADDR[004] -> index[001] -- offset[100]+001 --> ADDR[101]   P -> P

D: CPU demand access to producer/index array
P: prefetch generated either for index array or target data

先通过 pattern prefetch 预取 producer 数据，再把 producer 数据当作二级 prefetch 的地址源”：

该设计点是本专利相对常规 indirect prefetch 的关键增强。它不只是“根据 demand load 的返回值预取下一跳”，而是让被 pattern prefetch 提前取回的数据也能触发下一跳，从而把预取链条前移

设计点 5: 指令级识别和 ISA/微架构接口

针对的问题：硬件需要在 request 发出之前尽早知道哪些访问是 producer load，否则 hint 到达太晚

解决的思路：在 pipeline 较早阶段检测指令类型或指令序列。例如 decode 阶段看到某 load 的结果会被后续地址生成指令消费，就在该 load 对应的 demand request 上携带 hint

设计：

  1. 通过指令序列识别：第一条指令产生 load，第二条指令使用第一条结果生成访存地址
  2. 通过预定指令类型识别：某些 gather load 或加载 index vector 的指令在特定 workload 中高度暗示后续间接访问，即使尚未看到 consumer，也可发 hint
  3. hint 不一定需要暴露为软件可见 ISA。它可以是 decode/issue/load-store unit 内部生成的微架构 metadata
  4. 若需要 offset/base，处理器可在 demand request 的 hint field 中携带，也可以通过单独通道或共享存储提供

该接口的优势是成本较低：prefetcher 不必理解完整指令流，只需要看到 request metadata；CPU 也不必负责真正发出目标预取，只负责告诉 prefetcher“这个 producer 值值得被当作地址源”

优点

  1. 能覆盖传统 stride/pattern prefetcher 难以处理的任意目标地址。目标地址由真实 index/pointer 生成，不要求目标地址流本身有规律
  2. 误判控制比纯硬件 value-based indirect prefetch 更好。hint 来自处理器侧的指令语义或 request metadata，减少把普通数据误当地址的概率
  3. 与已有 prefetcher 兼容。pattern detection circuitry 仍然负责规则 producer stream，新增逻辑主要消费 hint 和 prefetched producer data
  4. 可显著增加预取距离。通过把 indirect condition 传播到 pattern 外推出来的一级 prefetch，二级目标预取可发生在 producer demand 之前
  5. 适合向量 gather、稀疏矩阵、索引数组遍历等场景。这些场景中 producer 地址规则而 consumer 地址稀疏，正好匹配专利假设
  6. 支持 pointer 和 index 两种数据形式。地址生成既可以直接使用 pointer，也可以组合 offset/base，覆盖更广数据布局
  7. indirect prefetch buffer 使机制不依赖 immediate cache hit。只要 producer 数据稍后进入关联 cache，仍可触发二级预取

缺点和实现代价

  1. 需要处理器和 prefetcher 之间新增 hint 通道或 request metadata。若 request encoding 已经紧张，加入 hint/offset 字段会增加协议和验证成本
  2. 需要额外硬件状态。associating circuitry、address generation circuitry、indirect prefetch buffer，以及 pattern state 中的 indirect 标记都会占面积和功耗
  3. 需要读取 cache data 并把 data path 接入地址生成逻辑。prefetcher 不再只处理地址流，还要在合适时刻消费 cache 中的数据值，这会增加时序、端口和一致性设计复杂度
  4. 错误 hint 或过度传播会导致污染。若某个 pattern 序列中只有部分元素是真正的 address indicating data，把 condition 传播到整条 stream 可能产生无用二级 prefetch
  5. 安全和隔离需要谨慎处理。硬件根据数据值主动访问第二地址，必须遵守权限、地址翻译、异常抑制、side-channel 缓解和 prefetch 不可见语义
  6. 对不规则 producer stream 帮助有限。若 index/pointer 本身也无法被提前预取，则机制退化为 demand producer 返回后再发二级预取，预取距离可能不足
  7. 可能增加 cache 带宽压力。二级 prefetch 访问任意地址，局部性可能弱，若 confidence 不足会挤占 demand miss、普通 prefetch 和写回流量