Title Patent Number Inc. Year url
Region pattern-matching hardware prefetcher US12360907B2 Advanced Micro Devices Inc. Filed 2022, Granted 2025 https://patents.google.com/patent/US12360907B2/en

TLDR：

  1. 这是一种 spatial / region footprint 预取器：把一个 memory region 切成多个 region subdivisions，观测 miss/hit 落在哪些 subdivision 上，再把这些位置记录为可重放的 access pattern
    (传统 spatial-prefetcher 的 subdivisions 固定为 cacheline 粒度)
  2. pattern matching：新 region 的观测 footprint 若与已有 recorded pattern 相同或足够相似，就把该 region 绑定到已有 region type，后续访问该 region 时按对应 bitmap 预取
    (传统 spatial-prefetcher 为每个 region 分配一个 bitmap)
  3. 专利给出两类组织方式：一种是 region type table -> recorded pattern table 的间接索引(多一拍，但在 L2 level 影响不大)，另一种是按 region 地址直接查找 direct pattern table (和传统 spatial-prefetcher 一样了，面积增加)
  4. 为了降低状态成本，同一个 recorded pattern 可以服务多个 region；为了降低混叠风险，专利加入 signature、way、confidence、accuracy aging、sparse-pattern threshold、duplicate-prefetch bit 等工程控制。

GPT-Arch

背景和动机

Cache miss 访问 backing memory 的代价高，硬件预取通过提前把可能访问的数据搬入 cache 来降低延迟。传统 stream/stride prefetcher 对连续访问很有效，但很多程序存在另一类行为：不同对象、page、bucket、node 或数组块上的局部访问 footprint 相似，访问位置相对 region 稳定，但全局地址序列不一定是简单 stride。

这类模式有三个典型特点：

  1. region-local：访问集中在一个地址区域内，例如一个 page、cache sector、object group 或自定义 region。
  2. spatial footprint 可重复：不同 region 上访问的相对 cache-line/subdivision bitmap 可能相同或很接近。
  3. 地址序列不一定连续：单纯看 miss stream 时可能像不规则访问，但把地址归一化到 region 内偏移后会出现可学习模式。

专利的动机是用硬件记录这种 region footprint，并在后续相同或相似 region 上重放预取。相比“每个 region 都保存一份 pattern”，它进一步引入 region type，让多个相似 region 共享同一份 recorded pattern，以减少存储成本。

Insight

专利的关键 insight 是：region 内的访问 footprint 可以作为比绝对地址序列更稳定的模式表示，并且相似 footprint 可以跨 region 共享。

假设 region 被切成若干 subdivision，通常可以把 subdivision 理解成 cache line 或若干 cache line 的组合。一次程序执行访问 region R0 的 subdivision {0, 3, 5, 7}，另一次访问 region R1 时也出现 {0, 3, 5, 7} 或只差一两个 bit。即使 R0 和 R1 的绝对地址相距很远，这两个 region 也可以共享同一个 prefetch pattern。

第二个 insight 是用短期观察和长期 replay 分离。pattern observation table 只负责在线收集当前 region 的访问 bitmap；entry eviction 时才把观察结果安装到 recorded pattern table 或 direct pattern table。这样可以避免每个 miss 都立即污染长期 predictor。

第三个 insight 是把“相似”作为硬件可调策略，而不是要求完全相同。专利允许两个 pattern 在差异数大于 0 且低于阈值时被归为同一 region type；也允许用 AND/OR merge、概率清 bit、counter、confidence、accuracy aging 等方式控制共享 pattern 的激进程度。

核心设计

用几句话概括：

  1. 将 memory address space 切分为 regions，每个 region 再切分为 region subdivisions。
  2. miss 或 hit 进入 prefetcher 后，先更新该 region 的 pattern observation entry，把对应 subdivision indicator 置位。
  3. observation entry 被 eviction 时，若 footprint 与已有 recorded pattern 相似，则该 region 映射到已有 region type；否则创建新的 region type 和 recorded pattern。
  4. 后续访问某个 region 时，prefetcher 通过 region address 找到 region type，再通过 region type 找到 recorded pattern，并按 bitmap 预取对应 subdivision。
  5. 另一种实现直接用 region address 查 direct pattern table，可把 recorded pattern 存在 cache 或 dedicated memory 中。
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
Memory request / cache miss or hit
        |
        v
+------------------+      observe subdivision bits
| Cache Controller | ------------------------------+
+---------+--------+                               |
          |                                        v
          |                              +-------------------------+
          |                              | Pattern Observation Tbl |
          |                              | region -> bitmap        |
          |                              +-----------+-------------+
          |                                          |
          |                            eviction / aging / no space
          |                                          v
          |                              +-------------------------+
          |                              | Pattern matching logic  |
          |                              | identical / near match  |
          |                              +------+------------------+
          |                                     |
          |                 +-------------------+-------------------+
          |                 |                                       |
          v                 v                                       v
+------------------+  +----------------------+          +----------------------+
| Region Type Tbl  |  | Recorded Pattern Tbl |          | Direct Pattern Tbl   |
| region -> type   |  | type -> bitmap       |          | region/tag -> bitmap |
+---------+--------+  +----------+-----------+          +----------+-----------+
          |                      |                                 |
          +---------- lookup ----+                                 |
                         |                                        |
                         v                                        v
                  prefetch selected region subdivisions into cache

设计点 1: Region / subdivision 表示

针对的问题: 绝对地址模式难以跨 region 泛化，且不规则地址序列很难用 stride 表示。

解决的思路: 把地址归一化为 (region address, subdivision offset)。长期记录的是 region 内哪些 subdivision 被访问，而不是完整地址序列。

设计：

Concept 专利含义 工程理解
region memory address space 的一段连续地址范围 page、sector、若干 cache line 或实现自定义大小
region subdivision region 内更小的分块 常见实现可对应 cache line
region address region 的地址标识 可由高位地址形成，低位作为 region 内 offset
access pattern 一组 subdivision indicators bitmap / bit vector / small counter vector

当 cache miss 或可选的 cache hit 发生时，prefetcher 根据访问地址计算 region 和 subdivision offset，然后更新 pattern observation entry。如果该 region 已有 observation entry，则置位对应 bit；否则创建 entry，并只置位当前访问的 subdivision bit。

1
2
3
4
5
6
7
8
9
Address
+-------------------------+------------------+
| region address          | subdivision/byte |
+-------------------------+------------------+
             |
             v
Pattern observation entry for region:
bit:       0 1 2 3 4 5 6 7 ...
access:    1 0 0 1 0 1 0 1 ...

设计点 2: Pattern observation table 作为短期构造表

针对的问题: 一个 region 的 footprint 需要在一段时间内逐步观察，单次 miss 信息不足；但长期表容量有限，不能把所有短期噪声直接写入。

解决的思路: 用 pattern observation table 暂存正在构造的 footprint。entry 因容量、超时或其他事件被 evict 时，再把观察到的 bitmap 安装到长期结构。

设计：

  1. miss/hit 到来时查 observation table。
  2. 命中 observation entry：置位访问 subdivision 对应的 indicator。
  3. 未命中 observation entry：创建新 entry，初始化所有 indicator 为 0，再置位当前 subdivision。
  4. eviction 条件可以是 table 无空位、entry 长时间未更新、entry 已到观察窗口结束等。
  5. eviction 时 observation entry 已包含该 region 在观察窗口内被访问过的 subdivision 集合。

专利还讨论了多线程/多应用处理：同一应用的多个线程可以共享 observation entry；不同应用可分开维护，或在 context switch 时 flush/save prefetcher 状态；也可以由 OS/软件指定哪些应用组可以共享训练状态。

flowchart TD
    A[Cache access observed] --> B[Compute region and subdivision]
    B --> C{Observation entry exists?}
    C -->|yes| D[Set subdivision indicator]
    C -->|no| E[Allocate entry and set current indicator]
    D --> F{Evict / age out?}
    E --> F
    F -->|no| A
    F -->|yes| G[Install or merge into recorded pattern]

设计点 3: Region type table + recorded pattern table

针对的问题: 如果每个 region 都保存完整 footprint，状态开销会随 region 数量线性增长，且同类 region 的 pattern 无法复用。

解决的思路: 引入 region type。region type table 记录 region address 到 region type 的映射；recorded pattern table 记录 region type 到 recorded pattern 的映射。多个 region 可以映射到同一个 type，从而共享同一份 bitmap。

设计：

Structure Entry 作用
Region type table 212 region address -> region type 访问 region 时先找 type
Recorded pattern table 216 region type -> recorded pattern type 对应的 subdivision bitmap
Pattern observation table 220 region address -> temporary bitmap 收集当前 region footprint

安装流程：

  1. observation entry eviction。
  2. 在 recorded pattern table 中查找相同或足够相似的 pattern。
  3. 若找到：把该 region 的 region address 映射到已有 region type。此时多个 region 可能指向同一个 recorded pattern。
  4. 若未找到：创建新的 region type，并把 eviction 出来的 bitmap 作为新的 recorded pattern。
  5. 若已有 mapping 需要更新：可把 observation bitmap merge 到已有 recorded pattern，例如 bitwise OR 或 bitwise AND。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Evicted observation pattern P(region A)
        |
        v
+------------------------------+
| Search recorded pattern table|
+---------------+--------------+
                |
       +--------+---------+
       |                  |
 similar P' exists        no similar pattern
       |                  |
       v                  v
region A -> type(P')      allocate type(Tnew)
optional merge P/P'       recorded[Tnew] = P
                           region A -> Tnew

“相似”的专利主张包括：第二个 memory region 的 access pattern 与第一 pattern 的差异数大于 0 且小于阈值。换句话说，它不是只保护完全相同的 bitmap，也保护 near-match clustering。

设计点 4: Prefetch replay

针对的问题: 训练完成后，后续访问 region 时需要快速决定应预取哪些地址。

解决的思路: 访问触发时用 region address 查 type，再取 recorded pattern，按 pattern 中置位的 subdivision 生成预取。

设计：

  1. cache miss 发生，或其他触发条件满足，例如 hit、miss/hit 组合且带宽充足。
  2. prefetcher 用 miss address 的 region address 查 region type table。
  3. 若找到 region address -> region type，用 region type 查 recorded pattern table。
  4. 读取 recorded pattern bitmap。
  5. 对 bitmap 中置位的 subdivision 生成地址：region_base + subdivision_offset。
  6. 将对应数据从 backing memory 预取到 cache。
1
2
3
4
5
6
7
8
9
10
11
12
13
on_cache_miss(addr):
    region = region_addr(addr)
    type = region_type_table.lookup(region)
    if type is absent:
        update_pattern_observation(region, addr)
        return

    pattern = recorded_pattern_table.lookup(type)
    if signature_check_fails(region, pattern):
        return

    for each set bit in pattern:
        prefetch(region.base + bit_to_subdivision_offset(bit))

专利强调：prefetch 不影响程序正确性，所以即便共享 recorded pattern 后带来一些额外预取，也可以用简单性换取实现收益。但这并不等于没有性能代价，错误预取仍会消耗 bandwidth、MSHR、prefetch queue 和 cache capacity。

设计点 5: Signature / way / confidence 降低 aliasing

针对的问题: region type 和 recorded pattern table 都可能发生混叠、替换或同 type 多 region 共享后的 stale mapping。错误 mapping 不影响正确性，但可能造成大量无效预取。

解决的思路: 在 mapping 中加入 signature、way 和 confidence 等元数据，限制错误 replay。

设计细节：

  1. Set-associative recorded pattern table：如果 recorded pattern table 是组相联结构，region type table 除了保存 type，还可保存 way。prefetch 时用 (type, way) 定位 entry，降低 type identifier 被复用导致的碰撞。
  2. Signature check：recorded pattern entry 和 region type table entry 可同时保存一个由 observation pattern 计算出的 signature。prefetch 前比较两个 signature，不匹配则不预取。这个机制用于防止 recorded pattern 被新 pattern 覆盖后，旧 region mapping 仍指向同一 type 而误触发。
  3. Multiple candidate types + confidence：一个 region type table entry 可以映射到多个 recorded pattern entry，并为每个候选保存 confidence。预取时选择最高 confidence 的 region type / recorded pattern。若 prefetch 后仍发生 miss，可降低 confidence；若没有 miss，可提高 confidence。
  4. Lowest-count eviction：记录每个 type 关联了多少 regions，容量不足时优先替换关联 region 数较少的 pattern。
1
2
3
4
5
6
7
8
9
10
Region Type Entry
+----------------+----------+---------+------------+
| region address | type id  | way     | signature  |
+----------------+----------+---------+------------+
                              |
                              v
Recorded Pattern Entry
+----------+---------+------------+----------------+
| type id  | way     | signature  | subdivision bm |
+----------+---------+------------+----------------+

设计点 6: 预取范围、重复预取和多预取器协同

针对的问题: recorded pattern 可能很大，全部预取会产生资源压力；同一 pattern 在短时间内多次触发会重复预取；系统中可能还有其他更适合当前访问流的 prefetcher。

解决的思路: 对 replay 增加范围限制、in-flight bit 和动态 disable/协同策略。

设计：

  1. Subset prefetch：不一定预取 recorded pattern 中所有置位 subdivision，可以只预取距离触发地址足够近的一部分，例如阈值字节范围内的 subdivision。
  2. Duplicate-prefetch bit：recorded pattern entry 可保存一个“prefetch 已开始”的 bit。若 bit 已置位且同一 entry 再次触发，则不重复发起预取；bit 可在预取完成、超时或其他事件后清除。
  3. Eligibility filtering：prefetcher 可以只跟踪 address space 的部分区域，例如根据 region address 的某些位判断该 region 是否 eligible。
  4. Multi-prefetcher disable：当系统判断另一个 prefetch technique 更有收益时，可以禁用本技术的更新、使用或两者；也可以把该机制集成到 combined prefetcher 中。

设计点 7: Direct pattern table 变体

针对的问题: region type table + recorded pattern table 的间接索引需要维护 region type 聚类；某些实现可能希望按 region 地址直接查 pattern。

解决的思路: 使用 direct pattern table 保存 region/tag -> recorded pattern。observation entry eviction 后直接写入 direct table；后续 region 访问时直接查找 recorded pattern 并预取。

设计：

  1. direct pattern table 可以放在 dedicated memory 中，也可以复用 cache 本身。
  2. 每个 table location 可对应一个 region，也可像 set-associative cache 一样由 region address 的一部分选择 set，再用 tag 区分具体 region。
  3. 若 direct pattern table 与普通 data cache line 共用 cache，需要 tag metadata 区分该 entry 是 recorded pattern 还是 data line。
  4. 如果整个 cache 被用来放 direct pattern table，则可以另设 buffer 保存 prefetched regions；也可以让 pattern entries、prefetched data 和普通 fills 共享 cache。
  5. direct table 可以按 recorded pattern accuracy 动态修改：低准确率 pattern 可清空 bitmap，或通过 replacement age 更快淘汰；高准确率 pattern 可变“年轻”以保留更久。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Direct pattern table organization

region address
      |
      v
+-------------------+
| index / tag lookup |
+---------+---------+
          |
          v
+----------------------------+
| recorded pattern bitmap    |
| optional age / accuracy    |
+-------------+--------------+
              |
              v
prefetch region subdivisions

设计点 8: Pattern merge 与激进度控制

针对的问题: 多个 region 共享一个 recorded pattern 时，merge 策略决定了预取的覆盖率和准确率。OR 太激进，AND 太保守；完全覆盖又可能被偶发样本污染。

解决的思路: 专利给出多种可选策略，让实现者在 coverage 和 pollution 之间调节。

设计选项：

策略 行为 倾向
OR merge 任一 observation bit 为 1 就置位 recorded pattern 覆盖率高，可能更污染
AND merge 多个 observation 都置位才保留 准确率高，可能漏预取
随机/概率清 bit 旧 pattern 有 bit、新 pattern 没 bit 时按概率清除 平滑更新，避免剧烈抖动
频率相关概率置位 高频 region 更容易安装/保留 bit 偏向热 pattern
Counter gate counter 达阈值才替换或 merge 降低偶发样本影响
Aggressive overwrite 新 observation bit 更多时覆盖旧 pattern 追求覆盖
Conservative overwrite 新 observation bit 更少时覆盖旧 pattern 追求准确
Sparse threshold set bits 低于阈值则不安装 过滤低价值 pattern
Very-hot-region filter 过于频繁访问的 region 不安装 避免热数据/特殊流污染 table
External prefetch cleanup 若其他实体已预取某 subdivision，安装时清对应 bit 降低重复预取

这部分体现了专利的工程取向：同一个“region pattern replay”框架可以配置成激进型、保守型或反馈自适应型 prefetcher。

与其他空间预取器的区别

  1. DSPatch
    • DSPatch 的关键贡献是把空间 bit-pattern 锚定到 trigger access，并用 OR/AND 学出 coverage-biased 与 accuracy-biased 两个模式，再根据 DRAM 带宽利用率选择模式。
    • US12360907B2 与 DSPatch 的交叉点是 OR/AND 合并，但专利没有要求“两个 pattern 同时保存”或“按带宽选择 CovP/AccP”。它更宽泛：相似但不完全相同的 observation pattern 可以合并到已有 recorded pattern，合并可用 OR 或 AND
  2. PMP
    • 聚类依据不同
      • PMP 的核心观察是：如果多个 memory region 中第一次访问的 offset 相同，那么这些 region 的后续访问 pattern 往往高度相似。因此 PMP 直接用 Trigger Offset 把 pattern 聚类到一起
      • US12360907B2 直接按照 region access bits 的差异性分类为 region type
    • 合并后的模式表示不同
      • US12360907B2 存的是 recorded access pattern （bit-vector）
      • PMP 存的是 counter vector （用每个 offset 的出现次数来表示 merged pattern）

局限和风险

  1. table aliasing 复杂：region type、recorded pattern、signature、way、direct table tag 都可能发生不同层面的混叠。