Title Patent Number Inc. Year url
Prefetcher with multi-cache level prefetches and feedback architecture WO2023287512A1 SiFive Inc 2023 https://patents.google.com/patent/WO2023287512A1/en

TLDR:

  1. 这份专利解决的问题是: L1 MSHR 少，长距离预取不能全部压到 L1。
  2. 预取器仍然用同一个 entry 学习 data stream 的 base、stride 和 window。
  3. 训练成功后，同一个 trained entry 可以同时向 L1、L2、L3 等多个 cache level 发预取。
  4. 近距离预取优先放 L1，远距离预取可以放到 L2/L3。
  5. 通过 MSHR 反馈决定是否发起预取
    • 各级 MSHR 给 prefetcher 反馈 fullness: 表示该级 outstanding miss 资源是否紧张。
    • 各级 MSHR 给 confirmation: 表示 demand 或 prefetch 命中了已有 pending MSHR。
    • confirmation 是正反馈，用来增加该 entry 的 prefetch distance 或 aggressiveness。
    • cache tag hit 是负反馈，用来判断某一级预取是否重复、太晚或没有收益。

top

背景和动机

传统硬件预取器通常从 L1 miss stream 中学习访问模式，目标是在 demand load 到达前把数据提前带入 cache，最好形成 L1 hit。为了隐藏 memory latency，预取器必须保持一定 ahead distance；distance 越大，需要同时挂起的 prefetch request 越多，也就越依赖 MSHR 资源。

L1 data cache 离 core 最近，但 MSHR 数量通常最少，而且 L1 MSHR 还要优先服务 demand miss。如果预取器为了扩大 coverage 把所有请求都送进 L1，容易占满 L1 MSHR，反而阻塞关键 demand miss。专利的基本观察是 lower-level cache 通常有更多 outstanding miss capacity，因此远距离预取可以下沉到 L2/L3，由低层 MSHR 提前打开 memory-level parallelism，L1 则只承担近端 pull-in。

专利要解决的核心问题包括:

问题 设计方向
同一个 stream 如何同时服务多个 cache level 一个 trained entry 维护 per-level pointer/counter
如何知道某一级是否适合接收预取 各级 MSHR 提供 fullness feedback
如何判断预取方向是否正确 demand/prefetch 与 pending MSHR 匹配产生 confirmation
如何抑制重复或过晚预取 各级 cache tag hit counter 提供负反馈
资源暂时不可用时如何处理 issue queue replay 和 level conversion

核心 Insight

Insight 1: 预取距离不应该只绑定 L1

预取距离用于隐藏延迟，L1 是最理想的命中位置，但不是最理想的 outstanding request 容器

  • L1 MSHR 少，适合承担近距离预取
  • L2/L3 MSHR 更多，适合承担更远距离的预取

该设计把 prefetch distance 拆成“近端 L1 段”和“远端 L2/L3 段”，让 L2/L3 先为远端地址建立 miss 状态，后续再由 L1 prefetch 或 demand 把数据拉近。

Insight 2: pattern detection 和 cache-level placement 解耦

专利并不要求每一级 cache 独立训练一个 stream。

  • 一个 trained entry 负责识别地址模式，记录 base、stride、window 等信息；
  • cache-level placement 逻辑再根据 feedback 决定地址应该发往 L1、L2 还是 L3

这样训练逻辑只做一次，多级投放只增加 per-level pointer、counter 和反馈状态。

Insight 3: MSHR confirmation 是更好的正反馈

cache tag hit 不一定说明预取有效，因为预取命中已有 line 可能只是重复或太晚。更适合作为正反馈的是 MSHR-level confirmation: prefetch 先建立 MSHR 后 demand 命中它，或 demand 先建立 MSHR 后 prefetch 命中它。

这类事件表示预测地址与真实 miss stream 对齐，而且发生在数据尚未填入 cache 前，更能反映 latency hiding 是否真正发生。

Insight 4: 负反馈必须按 level 区分 (Cache Hit Counter Per Level)

L1 prefetch 无效不代表 L2 prefetch 无效，L2 prefetch 重复也不代表 L1 pull-in 没有价值。

因此专利为每个 cache level 维护 cache-hit counter。

某一级 prefetch 反复命中已有 cache line 时，只停止或抑制该级行为，而不是直接杀掉整个 stream。

Insight 5: fullness feedback 用相对值更通用

预取器不需要知道每一级 MSHR 的绝对数量。

MSHR 可以只输出 N-bit fullness indicator，表示当前相对占用程度；prefetcher 将它与可配置 threshold 比较。这样同一预取器可以适配不同 cache/MSHR 配置，也便于不同产品线复用。

核心架构

Prefetcher 不仅观察 demand stream，还接收来自各级 MSHR 和 cache tag 的反馈，用这些反馈控制每个 trained entry 发往不同 cache level 的预取数量。

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
demand load stream
       |
       v
+-------------+
|    Core     |
+------+------+ 
       |
       v
+-------------+          L1 prefetch
| Load/Store  | --------------------+
|    Unit     |                     |
+------+------+                     v
       |                      +-----------+
       | demand miss          | L1 Cache  |
       v                      | L1 MSHRs  |
+-------------+               +-----+-----+
| Prefetch    |                     |
| Issue Queue |                     v
+------+------+              +------------+
       | L2 prefetch         | L2 / L3    |
       +-------------------> | MSHRs      |
                             +-----+------+
                                   |
                                   v
                                 Memory

+----------------------------------------+
| Hardware Prefetcher                    |
| trained entries                        |
| per-level pointers/counters            |
| MSHR fullness + confirmation feedback  |
| cache-hit negative feedback            |
+----------------------------------------+

Entry 训练状态机

专利可以采用 region-based sequential stride prefetcher 或 window-based prefetcher。

  • 一个 entry 跟踪一个 data stream
  • 核心字段包括 base address、stride、window 和 trained state
  • 训练流程是典型的三步确认:
    1. 第一笔 L1 demand miss 分配 entry
    2. 第二笔 demand miss 计算候选 stride
    3. 第三笔 demand miss 如果继续匹配 window 和 stride，则 entry 进入 trained state。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Invalid
  |
  | first demand miss
  v
Detect1
  |
  | second demand in window, compute stride
  v
Detect2
  |
  | third demand confirms stride
  v
Trained
  |
  | too many stride/window mismatches
  v
Non-trained / Invalid

训练阶段只负责识别 stream，不决定所有预取都必须进入 L1。进入 trained state 后，多级反馈逻辑接管 target placement。

Per-level pointer 和 counter

为了让同一 entry 同时服务多个 cache level，专利引入 per-level 状态。

每一级有自己的 prefetch pointer、generate counter 和 threshold:

  • pointer 表示该级最近一次发送的 prefetch address
  • counter 表示该级还需要生成多少 prefetch 才能达到目标距离
  • threshold 表示该级允许保持的预取距离或数量上限
1
2
3
4
5
6
7
8
9
10
11
12
demand stream ---->

near future                      far future
    |                                |
    v                                v
[L1 PF PTR] -------------------- [L2 PF PTR]
    |                                |
L1 gencount                      L2 gencount
    |                                |
L1 threshold                     L2 threshold
    |                                |
L1 fullness limit                L2 fullness limit
  • 当 demand stream 前进时，ahead distance 被消耗，对应 counter 可以递减；
  • 当 prefetcher 发送新的 L1/L2 prefetch 时，对应 pointer 按 stride 前进，counter 增加

更高层 cache 可以用同样方式扩展。

Multi-cache-level arbitration

trained entry eligible 后，预取器要决定发往哪一级。

基本策略是

  • 优先检查 L1: 如果 L1 gencount 低于阈值且 L1 MSHR fullness 低于阈值，则发送 L1 prefetch；
  • 否则检查 L2: 如果 L2 也不满足条件，则暂停
  • 扩展到 L3 时，可以继续检查 L3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
      +----------------+
      | trained entry? |
      +-------+--------+
              |
              v
+-----------------------------+
| L1 gencount < L1 threshold? |
| L1 fullness below limit?    |
+------------+----------------+
       yes   | no
        |    v
        |  +-----------------------------+
        |  | L2 gencount < L2 threshold? |
        |  | L2 fullness below limit?    |
        |  +------------+----------------+
        |       yes     | no
        v        v      v
    send L1   send L2  send none

这不是 fixed degree，而是 resource-aware placement。同一个 stream 的近端请求可以在 L1，远端请求可以在 L2/L3。

MSHR feedback

Fullness feedback

fullness feedback 表示某一级 outstanding miss 资源的压力

L1/L2/L3 MSHR 都可以输出 fullness indicator，prefetcher 将其与可配置阈值比较

  • 如果 L1 fullness 高于阈值，L1 暂停接收新预取
  • 如果 L2 fullness 低于阈值，远端预取可以下沉到 L2
  • 如果所有层级都过满，则停止发送

这个机制保护 demand miss，也避免预取器把低层 MSHR 全部打满

Confirmation feedback

confirmation 表示 pending MSHR 与后续真实访问对齐。

典型情况是 prefetch 先建立 MSHR、demand 后来命中该 MSHR，或者 demand 先建立 MSHR、prefetch 后来命中该 MSHR。

各级可以维护 MSHR confirmation counter，counter 达到阈值后产生 hit event。hit event 表示该 trained entry 方向正确，prefetcher 可以增加 aggressiveness，例如提高 prefetch distance 或 generate threshold。

专利描述的 aggressiveness 增长可以是分段式的: 低 aggressiveness 阶段逐次加一，超过某个阈值后倍增。这样稳定长流可以快速扩大距离，偶然匹配的短流不会立刻过度激进。

Cache-hit negative feedback

cache-hit feedback 统计 prefetch 请求命中已有 cache tag 的次数。

  • L1 prefetch 命中 L1 tag 可能表示重复、太晚，或 demand/其他请求已经把数据带入；
  • L2 prefetch 命中 L2 tag 也可能表示远端预取浪费带宽。

每一级 cache-hit counter 超过阈值后，可以停止该 entry 在对应 level 的 prefetch，更强的动作是 invalidate 该 level 的相关行为

关键点是负反馈按 cache level 生效。例如停止 L2 prefetch 后，L1 prefetch 仍然可以继续，因为 L1 prefetch 仍可能用于把 L2 MSHR 或 L2 cache 中的数据拉向 L1。

L1 prefetch 和 L2 prefetch 的关系

  • L1 prefetch 面向 near future，目标是最终形成 L1 hit；
  • L2 prefetch 面向 farther future，目标是更早建立低层 outstanding miss

L2 prefetch 不直接保证 L1 hit，但它可以让数据更早出现在 L2 路径中，后续 L1 prefetch 可以命中或 merge 到这条低层路径。

图 2 的核心例子是距离扩展: 初始阶段先使用 L1 MSHR，例如 L1 prefetch distance 为 4；随着 confirmation 增加，目标 distance 可能扩大到 16。如果 L1 最大只允许 8 个 ahead slot，则超过部分交给 L2，即 L1 gencount 保持 8，L2 gencount 设置为 16 - 8。当目标 distance 进一步扩大到 32 或 64，L1 仍只承担近端，L2/L3 承担更远端。

这个例子说明，多级预取不是复制同一个请求到多级 cache，而是在同一 stream 上分配不同距离区间。

Replay 和 on-the-fly conversion

预取请求可能因 L1 MSHR exhausted、page table cache miss、resource check 失败或 hazard check 失败而无法完成。issue queue 支持 replay，让有效预取不因瞬时失败直接丢弃。

专利还允许 on-the-fly conversion，例如原本的 L1 prefetch 可以转换成 L2 prefetch。如果 L1 MSHR 不可用而 L2 MSHR 可用，请求仍可继续推进。因此 target placement 不只发生在生成阶段，也可以发生在 issue 阶段。

Forgiveness counter

stride stream 可能有少量扰动。如果每次 mismatch 都立刻失效，预取器会过于敏感。

专利引入 forgiveness counter:

  • trained entry 遇到 stride mismatch 时 counter 增加；
  • 如果未超过 threshold，entry 保持 trained；
  • 如果超过 threshold，entry 退回 non-trained state。

该机制吸收短期 phase noise，减少真实 stream 被频繁重训，但 threshold 过大也会让错误 stream 存活更久。