Title Patent Number Inc. Year url
Content-directed prefetch circuit with quality filtering US9886385B1 Apple Inc. 2018 https://patents.google.com/patent/US9886385B1/en

这篇专利提出一种 content-directed prefetcher (CDP) ：它不只看 PC、stride 或访问流，而是在从 lower level cache 填入 L1D 的 cache line 数据内容中扫描“像地址的值”，把这些值当作 memory pointer candidate，然后对这些候选地址发起 pointer-chasing 预取。

从微架构角度看，这是一种把“数据内容中的地址相关性”转化为硬件可学习统计信号的指针追踪预取器，适合链表、树、图、对象字段引用等间接访问，但通过分层质量门控限制副作用。

TLDR：

  1. 关键问题是“像指针”的值很多，全部预取会污染 cache、浪费带宽并抢占正常 miss
  2. 专利的核心是 quality filtering：对每个指针候选映射到一个 QF counter，发起预取时扣分，后续证明预取有用时加分，只有 counter 满足阈值才允许继续预取。
    • QF table 是多维索引表，主实施例使用 hashed PC 和 relative cache line offset 作为索引，从而学习“某条指令带来的某个字段”是否值得 pointer-chasing 预取
    • PC 区分哪条 load/store 带来的 line
    • relative offset 区分该 line 内哪个位置出现候选指针
  3. CDP 还叠加 history filter 抑制重复预取、global QF counter 在全局质量变差时临时关闭这类预取、adjacent-line counters 判断是否额外预取候选指针相邻 cache line
  4. prefetch request cache 记录已发出预取的 QF 索引信息。预取 refill 时，用物理地址 hit 该 request cache，找回 hashed PC、relative offset、adjacent-line bit 等信息，对相应 QF counter 记 successful prefetch credit

背景和动机

本专利关注 pointer chasing。典型场景是 producer load 读出一个地址值，consumer load 以后把该值加偏移后再作为地址访问。例如：

1
2
load x0, [x1]        // producer load, x0 得到一个指针
load x2, [x0, #16]   // consumer load, 使用 x0 + 16B 访问对象字段

这类访问在链表、树、图、对象对象引用、哈希桶链等数据结构中常见。

传统 stride 或 stream prefetcher 很难处理，因为下一次访问地址不是当前地址加固定 stride，而是藏在当前取回的数据内容里。

一个直接方案是在 cache line 中扫描所有看起来像地址的值并预取，但这很容易过度激进。原因是普通整数、bit pattern、对象数据也可能碰巧像地址；即使真的是指针，也未必马上会被 dereference。

因此，专利要解决的问题不是“如何识别一个可能的指针”这么简单，而是：

  1. 如何在 L1D fill 路径上低成本地找出 memory pointer candidate。
  2. 如何判断某类候选指针历史上是否值得预取。
  3. 如何避免重复预取同一候选地址。
  4. 如何在整体预取质量变差时快速降噪。
  5. 如何在预取完成后把“成功/失败”的反馈记回正确统计项。

相关工作：

Title Authors, From url
A Decoupled Predictor-Directed Stream Prefetching Architecture Suleyman Sair, Timothy Sherwood, Brad Calder, UCSD, 2003 PDF 首页引用
Prefetching using Markov Predictors Doug Joseph, Dirk Grunwald, ISCA 1997 PDF 首页引用
Dependence based prefetching for linked data structures Amir Roth, Andreas Moshovos, Gurindar S. Sohi, ASPLOS 1998 PDF 首页引用

Insight

Insight 1: PC + Cacheline Offset

  1. pointer-chasing 预取的“稳定性”并不只属于某个地址，也不只属于某条指令，而经常属于“某条产生 line fill 的指令 + 该 cache line 中某个相对位置的字段”

举例来说，一条 load 可能反复读取某类对象的 header 或 node 结构。该结构中 offset 0 可能是 key，offset 8 可能是 next pointer，……仅用 PC 作为统计索引，会把同一条 load 带回 line 中多个位置的候选混在一起；仅用候选地址或 offset 又无法区分不同上下文。专利用 hashed PC + relative cache line offset 建立二维 QF table，就是为了学习“这个访问上下文下，这个字段位置的候选指针是否经常带来有用预取”

Insight 2: 把预取质量建模成 credit/debit 机制，而不是用简单 allowlist

  • 发起一个预取先记 cost，例如 decrement counter；
  • 后续如果 prefetch-initiated fill 被识别为成功，再记 credit，例如 increment counter
  • 这样 counter 的值近似反映该类候选的近期收益余额。只要成本多于收益，counter 会降到阈值以下，该类候选自动被抑制
  • 周期性 reset 又让模型可以适应 phase change，避免旧 workload 统计长期污染新阶段

Insight 3: 质量过滤应分为局部和全局两层

  1. QF table 的局部 counter 负责判断“某个 PC/字段模式是否好”。
  2. global QF counter 负责判断“整个 content-directed pointer prefetching 当前是否好”

这很重要，因为某些阶段下大部分 pointer candidate 都不可靠，即便少数局部 counter 尚未被扣到阈值以下，系统层面也可能已经在浪费带宽。global QF counter 对所有预取统一扣 cost，对任何成功预取 reset，可以作为粗粒度熔断器，临时关闭 CDP 活动。

Insight 4: 把“预取发出时的统计索引”和“预取数据回来时的物理地址”通过 prefetch request cache 连接起来

  • 预取完成时硬件看到的是 fill 的地址和 prefetch 标记
  • 而 QF table 需要的是当初发请求时的 hashed PC、relative offset、adjacent-line 标记

request cache 用 hashed physical address 建索引，保存这些 QF index metadata，使成功反馈可以回写到合适 counter。

专利也给出替代方案：把 QF index metadata 随 prefetch request 传到 LLC，再随 fill 返回，省掉 request cache 但增加 LLC 复杂度

核心设计

CDP

执行流程：

  1. L1D 从 LLC 收到 cache line fill
  2. pointer detection circuit 扫描 line 内容，找出像地址的 memory pointer candidate
  3. 对每个候选计算 metadata：候选虚拟地址、relative cache line offset、hashed PC，必要时进入候选队列。
  4. pointer filter circuit 依次检查 history filter、QF table counter、global QF counter，以及可选 adjacent-line counter
  5. 过滤通过后，对 LLC 发出候选指针地址的预取请求，并对相关 counter 记 prefetch cost。
  6. 同时在 prefetch request cache 中记录“该预取对应的 QF table 索引信息”。
  7. 后续 LLC 返回 prefetch-initiated fill 时，查 request cache，命中则对相应 QF counter 记 successful prefetch credit；无论 request cache 是否命中，global QF counter 可被 reset 或更新
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
34
35
36
37
                 +-----------------------------+
                 |        Execution Pipeline   |
                 |                             |
                 |  +-----------------------+  |
                 |  | Load/Store Unit       |  |
                 |  |                       |  |
Demand loads --->|  |  +-----------------+  |  |
stores           |  |  | L1 Data Cache   |<-+--+-- L1D fills from LLC
                 |  |  +--------+--------+  |  |
                 |  |           |           |  |
                 |  |           v scan fill |  |
                 |  |  +-----------------+  |  |
                 |  |  | Content-Directed|  |  |
                 |  |  | Prefetcher      |  |  |
                 |  |  |                 |  |  |
                 |  |  | Pointer Detect  |  |  |
                 |  |  |       |         |  |  |
                 |  |  |       v         |  |  |
                 |  |  | Pointer Filter  |  |  |
                 |  |  |  - History      |  |  |
                 |  |  |  - QF table     |  |  |
                 |  |  |  - Global QF    |  |  |
                 |  |  |       |         |  |  |
                 |  |  |       v         |  |  |
                 |  |  | Prefetch Req    |<-+--+-- prefetch-initiated fills
                 |  |  | Cache           |  |  |
                 |  |  +-------+---------+  |  |
                 |  +----------|------------+  |
                 +-------------|---------------+
                               |
                               v
                     CDP prefetch requests
                               |
                               v
                         +-----------+
                         |    LLC    |
                         +-----------+

设计点 1: Pointer Detection Circuit 检测候选指针

在数据 cache line fill 到达时扫描 line 内容，把“看起来像地址”的数据 word 提取为候选指针，然后尝试预取候选地址对应的 cache line

扫描设计：

  • 扫描对象:
    1. 可以是从 LLC 到 L1D 的 fill (专利使用 arriving fills)
    2. 也可以是已经 resident in L1D 的 cache line
  • 扫描场景：
    1. 可限制只扫描 load 导致的 fill
    2. 也可扩展到 store 或 load/store 混合场景
  • 扫描过滤：可跳过 LLC 标记为 do-not-scan 的 fill，避免同一 line 被重复扫描。
  • 扫描粒度: 为降低硬件比较成本，可以按指针对齐粒度扫描。例如 64B cache line、8B 指针对齐时，每条 line 只需检查 8 个候选位置。

判断设计：

  • 判断候选指针的基本规则是：候选 word 的若干高位与引发该 fill 的 load/store 地址的相应高位匹配
    • 专利例子给出最高 16 bit、20 bit 等，但 bit 数和是否连续都可实现相关
  • 对全 0 或全 1 等极端高位情况，可额外检查更多 bit，以避免小整数、负数、特殊值被误判为指针
  • 检测可基于虚拟地址，后续在真正发 LLC 预取前再做地址翻译

电路设计：

  • pointer detection circuit 位于 L1D fill 数据路径旁路上，不阻塞 fill
  • 候选信息至少包括 candidate virtual address、relative offset、hashed PC
    • 若不是 FIFO 队列，也可加 timestamp 维护顺序。
  • 候选队列满时可选择 stall scanning、丢弃新候选或覆盖旧候选
    • 专利指出从能耗角度可能更偏向 stall，因为前面已消耗能量找到了可用候选

设计点 2: History Filter 抑制重复候选

针对的问题：同一个候选指针可能在短时间内被多条 fill 或重复扫描发现，如果每次都发预取，会浪费带宽和 LLC 端口

解决的思路：维护一个记录“最近已发起预取的 pointer candidate”的 history filter。候选命中 history filter 时直接丢弃，不再发预取；未命中且其他 filter 通过时，插入 history filter。

设计：

  1. history filter 可实现为 direct-mapped 结构
  2. 可用候选虚拟地址的一部分作为 index，另一部分作为 tag
  3. 为节省面积，可先将 32 bit 或更长虚拟地址 hash 到较短位宽。例如 hash 到 16 bit 后，128-entry 结构用 7 bit index 和 9 bit tag；256-entry 结构用 8 bit index 和 8 bit tag。

hash collision 会导致误判，但专利认为预取本来就是 speculative task，不要求绝对精确。面积、能耗、性能可通过 workload modeling 调参

设计点 3: QF table

用 hashed PC 和 relative offset 学习局部预取质量

QF table 存储多个 saturating 或有限范围 counter。候选指针根据多个独立索引值定位 counter。若 counter 满足阈值，例如非零，则允许预取；否则抑制。

counters 由两个维度索引：hashed PC 和 relative cache line offset

  • hashed PC 来自引发该 cache line fill 的 load/store 指令 PC
  • relative offset 定义为：候选指针在 cacheline 中的 entry index 减去 fill address 低位对应的 entry index

relative offset 计算：

  1. 对 64B line、8B 扫描粒度，有 8 个可能位置，可用地址 bits [5:3] 参与计算
  2. 对 128B line、4B 扫描粒度，有 32 个可能位置，可用地址 bits [6:2] 参与计算
  3. 原始 offset 可能为负数。例如 8 个位置时范围为 -7 到 +7。硬件可通过加常量映射成非负范围 0 到 14，便于索引 table。

逻辑上 QF table 可看作多张 table：hashed PC 选择哪一张 table，relative offset 选择表项。物理上也可实现成二维 SRAM 或其他布局

counter 更新规则：

  1. reset 时 counter 可设为最大值
  2. 发起候选指针预取时，counter 被更新以反映 prefetch cost，典型是 decrement
  3. 后续识别到该预取成功时，counter 被更新以反映 successful prefetch credit，典型是 increment
  4. 若某类候选长期 cost 多于 credit，counter 会降到阈值以下，后续同类候选不再预取
  5. 所有 counter 可周期性 reset，例如扫描一定数量 cache line fill 后 reset，避免统计 stale，也缓解 hash collision 带来的长期污染
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
                     QF table

                 hashed PC
              +------+------+------+
relative      | PC0  | PC1  | PC2  | ...
offset 0      | cnt  | cnt  | cnt  |
offset 1      | cnt  | cnt  | cnt  |
offset 2      | cnt  | cnt  | cnt  |
...           | ...  | ...  | ...  |

candidate metadata:
  hashed_pc = hash(PC of fill-causing load/store)
  rel_off   = position(candidate word) - position(fill address bits)

selected_counter = QF[hashed_pc][rel_off]
prefetch allowed if selected_counter >= threshold

专利还允许更多索引维度，例如：

  • 该 line 中检测到的候选指针总数
  • 候选的 recursive depth
  • 候选所在虚拟地址 region

通过 adjacent-line counters 决定是否额外预取相邻 line

QF table 还可包含 adjacent-line counters

针对的问题：候选指针指向的数据结构可能跨越多个 cache line。只预取指针目标 line 可能不足以覆盖后续访问

解决的思路：除目标 line 预取外，CDP 可额外预取与候选指针相邻的 cache line，但这个更激进的动作使用独立 adjacent-line counter 控制

设计：

  1. 专利中 adjacent-line counters 只用 hashed PC 索引，以节省面积；(备选方案：多维索引)
  2. 当普通 QF counter 允许候选预取时，再检查 adjacent-line counter 是否满足 adjacent-line threshold
    • 若通过，则发起 separate prefetch request，地址可为 candidate + K，其中 K 是 cacheline size
  3. adjacent-line counter 同样在发起时 -cost，成功时 +credit，可独立 reset

设计点 4: Global QF Counter

针对的问题：即使局部 counter 尚未全部失效，某个程序 phase 中 content-directed pointer prefetching 整体可能已经弊大于利

解决的思路：维护一个 global QF counter，所有候选共享。

设计：

  • 发起任意 pointer candidate 预取时，对 global counter 记 global prefetch cost
  • 识别到任意成功预取时，将其 reset 到初始值
  • 候选只有在 global counter 满足阈值时才允许发出
  • 也可周期性 reset，周期可与 QF table 独立

设计点 5: Dispatch Policy

针对的问题：pointer detection 可能基于虚拟地址，但 LLC 常是物理地址索引；预取请求真正发出前可能需要 TLB 翻译和仲裁

解决的思路：过滤通过后的候选进入等待/dispatch 结构，满足物理地址可用、年龄顺序、LLC 端口仲裁等条件后发出。

设计：

  1. 在 Dispatch Queue 中若 TLB miss，可以选择直接丢弃候选，而不是等待 page walk
  2. 候选记录可包含 virtual address、physical address、translation transaction id、relative offset、hashed PC、adjacent-line indication
  3. 多个 ready 候选可按 oldest-first dispatch，也可使用其他选择策略
  4. CDP 需要与其他 prefetch requester 仲裁 LLC 访问。
  5. 预取完成后，数据可以只保存到 LLC，不立即 refill 到 L1D。之后 L1D demand miss 到该地址，再由 LLC 快速 fill L1D (备选方案：也可同时安装到 LLC 和 L1D)

设计点 6: Prefetch Request Cache

针对的问题：预取发出时知道 hashed PC 和 relative offset；预取 fill 回来时看到的是地址和 prefetch 标记。要给正确 QF counter 加 credit，必须恢复当初的 QF table index information

解决的思路：发出预取时，把 QF index metadata 存入 prefetch request cache。fill 回来时用 hashed physical address 查 request cache，命中后取出 metadata，对相应 counter 加 credit

设计：

  • cache 组织形式
    • 可为 set-associative cache，也可 direct-mapped
    • index 使用 hashed physical address 的一部分，tag 使用剩余部分
    • entry 保存 QF table index information，例如 hashed PC、relative offset，以及 adjacent-line prefetch indication bit
  • prefetch-initiated fill 到达时
    • 若 request cache hit，则用 entry 中 metadata 更新 QF table entry, 任意成功预取还可 reset global QF counter
    • 若 request cache miss，可能因为 entry 被容量冲突驱逐。此时无法准确给局部 QF table credit，但仍可更新 global QF counter

替代实现: 把 QF index metadata 随 prefetch request 发送给 LLC，再随 fill 返回。这样可省 request cache 并避免 request cache miss/collision，但增加 LLC 接口和存储复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Prefetch issue path:

candidate -> filters pass -> send prefetch(addr=Paddr) to LLC
                       |
                       +-> request_cache[hash(Paddr)] =
                           { tag, hashed_pc, rel_offset, adjacent_bit }

Prefetch fill return path:

LLC fill(addr=Paddr, prefetch_initiated=1)
        |
        v
request_cache lookup by hash(Paddr)
        |
        +-- hit  -> recover {hashed_pc, rel_offset, adjacent_bit}
        |          QF[hashed_pc][rel_offset] += success_credit
        |          if adjacent_bit: AdjQF[hashed_pc] += success_credit
        |          GlobalQF = initial_value
        |
        +-- miss -> local QF not credited
                   GlobalQF may still be updated/reset

整体流程

候选检测和预取发起：

flowchart TD
    A[600: incoming L1D fill from LLC] --> B[identify memory pointer candidate]
    B --> C[602: apply filters]
    C --> D{history miss? QF ok? global QF ok?}
    D -- no --> X[discard candidate]
    D -- yes --> E[604: initiate prefetch to LLC]
    E --> F{adjacent-line counter ok?}
    F -- yes --> G[also prefetch adjacent cache line]
    F -- no --> H[no adjacent prefetch]
    G --> I[606: debit counters for prefetch cost]
    H --> I
    I --> J[608: store QF index info in request cache]

预取 fill 回来后的 credit：

flowchart TD
    A[700: detect CDP prefetch-initiated fill] --> B[702: lookup prefetch request cache]
    B --> C{hit?}
    C -- yes --> D[704: use QF index metadata]
    D --> E[credit QF counter and optional adjacent counter]
    E --> F[reset/update global QF counter]
    C -- no --> G[706: update global QF only]