Title Patent Number Inc. Year Source Filing Date Status
Prefetching using offset data to access a pointer within a current data element for use in prefetching a subsequent data element US10445241B2 ARM Ltd 2019 https://patents.google.com/patent/US10445241B2/en 2018-03-06 Grant

这件专利保护的是一种“结构感知”的硬件预取器：从程序迭代访问的数据元素中学习 memory address relationship，把关系编码为 offset data，并在当前元素被访问时提前推出下一元素地址

TLDR:

  1. 面向 linked-list 场景：offset data 表示“当前 data element 内部指针字段相对 data element/trigger address 的位置”，预取器用它读出当前元素中的指针，再据此预取 subsequent data element
  2. 专利还覆盖 array-of-pointers：Offset 1 是相邻 pointer slot 的距离，Offset 2 是 pointer target/reference address 到真正 trigger access 的距离；lookup 时先找下一 pointer，再用 Offset 2 定位下一元素的触发访问位置
  3. 与 Apple DMP/IMA 的关系：二者都属于“硬件根据数据值/指针值触发间接预取”的范畴；本专利更强调 PC/history/structure table 学习到的稳定数据结构，而 Apple DMP/IMA 通常被观察为数据值驱动、更容易把 pointer-looking data 当作地址的间接预取行为

背景和动机

专利的背景很直接：处理器执行循环时，连续迭代会访问一组 data elements；如果能够在当前迭代访问当前元素时提前取回下一迭代要用的元素，就可以隐藏 cache miss 和内存延迟。传统 stride/table 预取容易覆盖相邻数组或固定步长结构，但对链表、对象图、指针数组这类“下一地址需要先读一个指针才能知道”的访问不够有效。

这件专利的动机是把“数据结构关系”显式学习并缓存下来。预取器不是只看地址流是否等差，而是维护 data element structure memory / data structure table，记录 trigger PC、触发地址、关系类型、Offset 1、Offset 2 等字段。这样它可以对 table、linked list、array of pointers 以及多级指针组合使用不同的地址推导方式

Insight

核心洞察是：很多非规则访问并非完全随机，而是“当前元素内的固定字段”或“指针数组中的固定步长 slot”在表达下一元素地址。只要硬件能把这些字段位置学成 offset data，就可以把一次本来串行的 pointer chasing 拆成可提前执行的微流程

专利里 offset data 有几种含义：

  1. Table/array-of-structs：Offset 1 是连续 data element 的 trigger address 之间的位移，例如 B-A。预取器在 A 触发后直接预取 A+Offset 1。
  2. Linked list：Offset 1 是当前元素 trigger access 到该元素内 pointer 字段的距离；Offset 2 是 pointer 指向的 reference address 到下一元素 trigger access 的距离。预取器在当前元素触发后读 current + Offset1 处的 pointer，再计算 pointer_target + Offset2
  3. Array of pointers：Offset 1 是当前 pointer slot 到下一 pointer slot 的距离；Offset 2 是 pointer target/reference address 到目标 data element trigger access 的距离。预取器用 current_pointer_location + Offset1 找下一指针，再用返回的 pointer target 加 Offset 2 得到下一 trigger address。

与 Apple DMP/IMA 的关系

共同点：都落在 indirect / data-dependent prefetch 方向：硬件观察到某个数据值像地址，就可能据此发起下一层内存访问。尤其是专利中的 pointer detector 会扫描 cache line 中的 word，用地址高位匹配和对齐位判断它是否可能是 pointer；这与 Apple CDP 的 “pointer-looking value 触发预取”的外在行为很接近

差异在于:

  1. 触发条件：本专利以 trigger PC、迭代历史和已学习结构关系为入口；Apple DMP/IMA 更常被描述为对 load data value 的自动地址解释。
  2. 地址公式：本专利有明确公式，例如 current + Offset1 -> pointer -> pointer + Offset2 或 pointer_slot + Offset1 -> pointer -> pointer + Offset2；Apple CDP 的公开观察重点通常是“load 值被当作地址预取”，不一定暴露这种结构表和 Offset 1/2 模型
  3. 安全含义：二者都会制造数据依赖的 cache footprint。本专利若实现得激进，也可能把秘密数据中碰巧像指针的 word 送入 pointer cache 并造成可观测预取；但专利文本给出的阈值、PC history、MSB/LSB 检查和结构学习会限制其触发范围

核心设计

专利提出的整体结构由处理器、cache/memory system、prefetcher、structure memory 和 detector 组成。

  • detector 在学习路径上从历史访问、pointer-looking values 和触发 PC 中识别结构关系
  • prefetcher 在 lookup 路径上用 structure memory 中的关系推出 subsequent data element 并发起预取

Prefetcher 架构图

设计点 1: 用 offset data 表达数据结构关系

设计点 1：用 offset data 表达数据结构关系

针对的问题：普通地址流预取只能很好地覆盖线性/规则地址，无法表达“下一元素地址藏在当前元素的某个字段里”。

解决的思路：把访问关系抽象为结构类型和 offset data，而不是只保存下一地址。结构表至少能表达 table、linked list、pointer table/array-of-pointers，以及更复杂的多级组合

设计：

  • 学习阶段比较连续 trigger addresses；如果差值小于阈值，可记录为 table 的 Offset 1
  • 对 pointer table，比较连续 parent/pointer addresses；如果差值小于阈值，可记录 pointer slot 之间的 Offset 1
  • 对 linked list，比较 pointer target/reference address 与当前/下一 trigger address 的关系，得到当前元素内 pointer 字段位置和 Offset 2

设计点 2: pointer within current data element

设计点 2：pointer within current data element

  • subsequent data element 的内存位置由 current data element 内某个 pointer 字段指向；
  • memory address relationship 里的 offset data 表示该 pointer location 相对 data element 的位置
  • 预取器对当前元素应用这个 offset，访问当前元素内部的 pointer，然后用 pointer value 预取下一元素。
1
2
3
4
5
6
7
8
current element
+-------------------------------+
| trigger @ A                   |
| ...                           |
| pointer field @ A + Offset1 --+----> reference address of next element
+-------------------------------+                |
                                                 v
next element                           trigger @ pointer + Offset2

这个机制本质上是在硬件里提前执行一段简化的链表遍历：当前迭代刚碰到当前元素时，prefetcher 通过 Offset 1 找到下一节点指针；pointer 返回后，再用 Offset 2 定位下一迭代的触发访问位置。

专利还提到可以继续递归：预取 subsequent data element 后，再检测其中指向 further data element 的 pointer，形成多步预取

设计点 3: linked-list 与 array-of-pointers 的统一处理

设计点 3：linked-list 与 array-of-pointers 的统一处理

Linked-list 场景：

  • Offset 1：当前元素 trigger access 到当前元素内 next pointer 字段的距离。
  • Offset 2：next pointer 指向的 reference address 到下一元素 trigger access 的距离。
  • lookup：读 A + Offset1，得到 pointer target；再预取 pointer target + Offset2 附近的 cache line。

Array-of-pointers 场景：

  • 当前访问位置可能是指针数组中的某个 pointer slot。
  • Offset 1：相邻 pointer slot 的地址间隔。
  • Offset 2：pointer target/reference address 到目标元素 trigger access 的偏移。
  • lookup：读 current_pointer_slot + Offset1 得到下一元素指针，再预取 next_pointer_target + Offset2。
1
2
3
4
5
array of pointers: P[i] ----> element i reference ----> trigger i
                   P[i+1] --> element i+1 reference --> trigger i+1
                    ^  ^
                    |  +-- current pointer slot + Offset1
                    +----- current pointer slot

统一性：

  • linked list 的 Offset 1 是“元素内字段位置”
  • pointer array 的 Offset 1 是“指针槽之间的步长”

但二者都被存入结构表，并且都需要等待一个间接读返回后才能加 Offset 2 完成下一 trigger address 计算

设计点 4: detector、pointer cache、history buffer 和 pending table

设计点 4：detector、pointer cache、history buffer 和 pending table

  • History buffer 保存触发访问的 PC，用当前 PC 命中历史项来启动 lookup
  • Pointer cache 在 cache line fill 时扫描每个 word
    • 64-bit 架构下要求若干 MSB 与 trigger address 匹配且低 3 位为 0；
    • 32-bit 架构下低 2 位为 0
    • hit 则被当作 potential pointer，记录 location 和 target
  • Global history buffer 汇总 trigger address、parent/pointer address、Offset 2 等信息，用于识别 table、pointer table、linked list。
  • Data structure table 记录 triggering history index、triggered history index、relationship type、Offset 1、Offset 2。
  • Pending table 在 linked list / array-of-pointers lookup 中保存 Offset 2 和 SMS pattern，因为预取器需要先发起一次读 pointer 的请求，等 pointer data 返回后才能计算下一 trigger address
1
2
3
4
5
6
7
8
update path:
line fill -> scan words -> pointer cache -> global history -> structure table

lookup path:
PC hit -> trigger address -> structure table
  table:          next = trigger + Offset1
  list/pointer[]: pointer_load = trigger_or_slot + Offset1
                  next = returned_pointer + Offset2

设计点 5: 与 Spatial Memory Streaming 的组合

设计点 5：与 Spatial Memory Streaming 的组合

专利明确说该技术可与 Spatial Memory Streaming 共存。这里的分工是：

  • 本专利负责跨 data element 找到“下一元素的 trigger access”
  • SMS 负责在一个 data element 内，根据相对 trigger access 的多个稳定访问位置，预取同一元素内部的其他 cache lines

因此结构表查到下一 trigger address 后，可以连同 SMS history buffer 中的相对访问模式一起发起预取：先到下一元素，再取下一元素内部预计会被访问的多个位置