核心问题

  • 现代高性能 CPU，尤其是 server workload 上，分支预测器已经成为明显瓶颈
  • 但不能简单把现有 TAGE 预测器无限做大，因为面积、延迟、能耗都会失控

那能不能像 cache 一样，为分支预测也做一个“层次化设计”？

由于分支预测状态不是“按 PC 直接索引”的，而是按 PC + History 索引；
因此，传统按空间局部性分页/分块的方法不适合 TAGE 这种 heavily-hashed predictor

论文提出一种新的组织方式 LLBP:

  1. 用“程序上下文（program context）”来重组分支预测状态
  2. 难预测分支需要的大量 pattern 分散到不同 context 中，每个 context 内只保留很少的 pattern
  3. 然后再通过 context 预测 + 预取把这些 pattern 提前搬到核内小 buffer 中

动机：真实服务器场景

作者先用真实服务器和仿真做了动机分析，结论很直接：

  • 在 Intel Sapphire Rapids 服务器上，条件分支误预测会浪费 3.6%–20% 的执行周期，平均 9.2%
  • 用 64KiB TAGE-SC-L 作为基线时，14 个工作负载上的 MPKI 为 0.29–6.4，平均 2.91。
  • 如果把 TAGE-SC-L 的容量放到“无限”，平均可把误预测再降 36.5%
    • 这部分收益里，87% 基本来自 TAGE 主体表容量增大
      (真正的痛点还是 TAGE pattern table 容量不足)

所以论文真正研究的是：怎样用一种更“可物理实现”的方式，逼近大容量 TAGE 的收益

现有方法的局限

1. 直接增加 TAGE 容量

  • TAGE 在前端关键路径上，容量一大，访问延迟和能耗都会上升
  • 虽然 overriding 之类技术能缓和延迟问题，但存在极限
  • 在考虑延迟后，更大的 predictor 可能让 IPC 反而下降
    • 作者用 CACTI 估算出，若把 TAGE 容量增大 8 倍，访问能耗会增长到 4.58 倍

所以问题在于边际收益递减：

  • 精度收益增长很慢
  • 延迟/能耗代价增长很快

2. 传统层次化/分页式 TAGE: virtualized TAGE / paged TAGE

思路：把某段代码相关的 predictor metadata 聚在同一个 page 里，再像 cache 一样换入换出
(data prefetcher 中对于 Pointer-Chasing Prefetcher 的 prefetch table 也有类似的做法)

问题: TAGE 的索引是 hash(PC, history)：

  1. hash 影响了空间局部性
    • 相邻代码的分支，predictor entry 并不相邻
    • 很难像 I-cache 那样高效预取一组“附近的 predictor 状态
  2. 每个静态分支所需 pattern 数量极度不均匀
    • 大多数分支只需要很少 pattern
    • 少数复杂分支需要上百甚至上千个 pattern
    • 固定 page 大小：
      • page 小: 装不下复杂分支
      • page 大: 又浪费大量容量

LLBP 的核心研究点: Context Locality

论文的关键不是“再造一个更大的表”，而是先找到一种新的状态组织单位，使 predictor metadata 同时具备：

  • 可分层搬运的粒度
  • 相对紧凑的容量分布
  • 足够好的局部性

这就引出了论文最重要的观察：context locality

  1. 一个分支如果需要很多 pattern，本质上说明它依赖很长的 history
  2. 很长 history 会跨越多个函数和代码区域，其中会穿过大量 无条件控制流转移，例如 jump/call/return
  3. 这些无条件转移序列，可以看成当前程序执行状态的一种“指纹”，也就是 program context
  4. 如果用这个 context 去切分 branch behavior，那么原来“一个静态分支对应海量 pattern”的问题，会变成“一个 context 只对应很少 pattern”

实验验证：

  • 对最复杂的分支，useful pattern 的历史长度可达到 5–1500 条 branch，平均约 200
  • 平均每两个无条件分支之间约有 3.89 个条件分支，因此历史长度 200 的 branch，大约跨越 50 多个 无条件分支，确实已经跨了很多上下文边界
  • 在不做 context 切分时（W=0），前 128 个复杂分支中，50% 需要超过 298 个 pattern，95% 需要 2384 个。
  • 如果 context 仅由前 2 个 无条件分支构成（W=2），50% 的 context 只需 3 个 useful pattern，95% 少于 40 个；
  • 如果 W=32，95% 的 context 最多只需 9 个 pattern

说明：
pattern 数量之所以爆炸，不只是 branch 本身复杂，而是传统分支预测器不区分不同程序的上下文，只看历史 pattern

一旦按 context 拆开，pattern working set 会急剧收缩

LLBP 设计思路

LLBP 不是替代 TAGE，而是给 TAGE-SC-L 增加一个高容量的后备层

其定位类似于“last-level cache”

设计点：

  1. 把 predictor metadata 按 context 重新组织成 pattern set
  2. 大容量存储放在核外/慢层，小容量活跃集放在核内
  3. 当前 context 和即将到来的 context 的 pattern set 被预取到核内的小 buffer
  4. 预测时，LLBP 与原始 TAGE 并行工作，采用匹配到更长 history 的作为真实预测结果

硬件组成

LLBP 主要由四个硬件部件组成：

LLBP

1. LLBP 大容量存储阵列

bulk storage: 保存大量 pattern set

  • 每个 entry 对应一个 context 以及该 context 对应的一组 pattern
  • 主要追求存储密度，不追求单周期低延迟
    • 因为真正预测时访问的是前面的小 buffer，而不是每次都直达 bulk storage

每个 pattern 包含：

  • prediction counter
  • pattern tag
  • history length 字段

和 TAGE 的区别：

  1. TAGE 把不同 history length 分布在不同表里
  2. LLBP 允许多个不同 history length 的 pattern 共存在同一个 pattern set

2. Pattern Buffer（PB）

核内的小 buffer，缓存：

  • 当前 active context 的 pattern set
  • 最近访问过的若干 context 的 pattern set
  • 即将到来的 context 的预取结果

相当于 LLBP 的 L1

3. Rolling Context Register（RCR）

  1. 记录最近 W 个无条件分支 PC
  2. 通过 rolling XOR hash 生成当前 context ID（CCID）

代表当前代码区域的上下文

4. Context Directory（CD）

  • 类似 cache tag array
  • 负责用 context ID 查到对应的 pattern set 是否存在，以及它在 LLBP 中的位置

预测流程

对当前 branch：

  • 和 TAGE 一样，先基于 branch PC 与 GHR 计算各个历史长度下的 hash；
  • PB 中当前 context 的 pattern set 会并行比较 tag
  • 命中后由 counter 给出 taken/not-taken

选择命中“最长 history”

TAGE 的一个核心原则是：长历史匹配优先于短历史匹配

LLBP 把不同 history length 放进同一个 set

  • pattern set 内部按 history length 排序
  • 匹配后的优先级仲裁，用与 TAGE 类似的 mux cascade 实现

LLBP 与基线 TAGE 仲裁

LLBP 与 TAGE 并行预测，然后比较二者命中的 history length：

如果 LLBP 命中的 history length 不短于 TAGE 的 provider 则 LLBP override TAGE ，否则沿用 TAGE 结果

PB Prefetching

不用额外预测器来预测 context，而是“用过去的 context 预取未来”: 把当前 context 的定义滞后 D 个无条件分支：

  • 当前用于预测的 CCID，不包含最近的 D 个无条件分支；
  • 而“prefetch CID”则用更近的历史来表示即将到来的上下文

这样做的效果是：
当某个即将生效的 context 已经“可知”时，真正进入该 context 还要再经过 D 个无条件分支，这段时间就成了预取窗口

论文实验中使用：

  • context window W = 8 个无条件分支
  • prefetch distance D = 4 个无条件分支
  • 预取延迟建模为 6 cycles

LLBP 训练与替换

如果 LLBP override 了 TAGE，那么 TAGE 会取消本次更新，只更新 LLBP 的 provider

分配 pattern 策略: 根据置信度而非时间局部性

当 provider 预测错时，LLBP 分配一个更长 history 的新 pattern。过程大致四步：

  1. 若当前 context 还没被 LLBP 跟踪，则先为其创建新的 pattern set
  2. 在当前 pattern set 中选一个置信度最低的 pattern 作为 victim
  3. 填入新 tag / history length / 初始 counter
  4. 维护 pattern set 内按 history length 排序

Pattern Set 分 Bucket 排序

一个 set 内 16 个 pattern 任意 history length 排序: 复杂度太高

策略：把 16 个 pattern 分成 4 个 bucket，每个 bucket 只允许放一段历史长度范围内的 pattern

好处：

  • 分配时只需在 bucket 内局部排序
  • mux 复杂度和延迟更低
  • history length 字段只需 2 位

实验

Workload and Setup

14 个 workload，包括：

  • NodeApp、PHPWiki 两个 web 服务
  • DaCapo、Renaissance、BenchBase 中的多种 Java workload
  • Google 提供的 4 个数据中心 trace

仿真平台是 ChampSim，基线 core 为：

  • 4GHz
  • 6-way OoO
  • 512 ROB
  • 64KiB TAGE-SC-L
  • 16K-entry BTB
  • 32KiB L1I / 48KiB L1D / 2MiB L2 / 8MiB LLC

LLBP 的具体配置是：

  • 每个 pattern：18 bits
  • 每个 pattern set：16 个 pattern，共 288 bits
  • LLBP 使用 16 个 history length（从基线 TAGE 的 21 个中选取）
  • CD + LLBP 共可容纳约 14K pattern sets
  • CD 容量 8.75KiB
  • LLBP 容量 504KiB
  • PB 容量 2.25KiB，缓存 64 个最近 pattern set
  • W: context ID 由几个无条件分支 hash 得到，设置为 8
  • D: prefetch distance , Prefetch CID 和 CCID 之间滞后的无条件分支数，设置为 4

MPKI 降低

主结果是：

  • 512KB LLBP + 64KB TAGE-SC-L
  • baseline: 64KB TAGE-SC-L
  • MPKI 降低 0.5%–25.9%
  • 平均 8.9%。

理想无延迟版本 LLBP-0Lat 的平均提升是 9.9%

说明真实实现（带预取延迟）已经达到了理想情况的大约 90%

缺陷：

  • 同等大致存储预算的“512K TAGE-SC-L”平均能降 27.3% MPKI
  • 但 512K TAGE-SC-L 并不现实，因为延迟太高

IPC 提升

  • 平均 speedup 0.63%
  • LLBP-0Lat 为 0.71%
  • 512K TAGE-SC-L 为 1.26%
  • ideal bpu 的平均 speedup 为 3.6%
    • ideal bpu 的收益明显低于先前工作和真实硬件上的 Top-Down 分析结果
    • 作者归因于 ChampSim 的 core model 可能低估了分支预测改进的真实性能收益

工程可实现性

1. 带宽

LLBP 与 PB 之间传输的是整个 pattern set:

  • 16-entry PB 时，总带宽约 12.1 bits/instruction
  • 64-entry PB 时降到 9.9 bits/instruction
  • 256-entry PB 时低于 1 byte/instruction。

论文选用 64-entry PB，认为这是容量与带宽的折中

和 L1I-L2 流量：64-entry PB 下，LLBP 的读带宽比 L1I miss 流量还低 41%

从互连带宽角度，LLBP 至少不是一个完全不切实际的方案

2. 延迟

CACTI 估算结果显示：

  • 64KiB TAGE-SC-L：约 2 cycle
  • 512KiB TAGE-SC-L：约 4 cycle
  • LLBP lookup：约 4 cycle
  • CD / PB：1 cycle 内

所以作者在仿真中把 LLBP 的预取延迟设为 6 cycles，用于覆盖 CD + LLBP 顺序访问和额外逻辑延迟

3 能耗

单次访问能耗上：

  • 512KiB TAGE-SC-L 是 64K TAGE-SC-L 的 4.58 倍
  • LLBP 本体单次访问是 4.44 倍
  • 但 CD 和 PB 的单次访问只分别是 0.3 倍 和 0.25 倍

访问频率：

  • 基线 TAGE 和 PB 每周期都用
  • CD 只在 context 切换时用，平均约每 6.3 cycles
  • LLBP 本体只在 PB miss 且存在该 context 时访问，平均约每 7.7 cycles 一次

综合访问频率: LLBP 全部结构合计能耗大约是 64K TAGE-SC-L 的 51%–57%

敏感性与有效性分析

1. prefetch distance 与 history 选择

作者比较了不同 history 类型用于 context 的效果，发现：

  • 只用 unconditional branch history 最好
  • D = 4 时达到最佳 MPKI reduction
  • 若把 conditional branch 也混进 context history，会引入噪声，反而更差

说明对“context”定义很重要：抓的是 跨代码区域的全局控制流骨架，而不是所有控制流细节

  • 若 context 太细，会过拟合；
  • 若太粗，又无法区分

2. pattern set 的大小与 context 数量

  • 16K contexts，每个 8 patterns 时，就能得到约 11% 的 MPKI reduction
  • 每个 context 从 8 patterns 提到 16 patterns，还能再多拿 2.6%
  • 再继续加到 32 或 64，收益已经明显递减

同时，增加 context 数量基本接近线性提升，直到大约 14K sets 后才开始放缓。

作者据此认为，LLBP 的收益主要还是由总体存储容量驱动，而 context-based 组织能有效把高度偏斜的 working set 打散。

3. LLBP 实际预测覆盖率

  • LLBP 只为 14.8% 的动态条件分支提供预测；
  • 一旦提供预测，其中 77% 的情况下会 override 基线；
  • 但坏 override 只有 6.8%；
  • 不过其中 59% 的 override 实际是“冗余的”: 即使 override 了，结果也和基线一致

表明：

  1. LLBP 不是一个通用大而全 predictor，而是一个针对复杂分支的专门补丁层
  2. 很准，但存储效率不够高

Futurn Work

1. MPKI 收益明显，但提升有限

  • 同等大致容量预算的 512K TAGE-SC-L 参考值是 27.3% (因延迟不可实现)
  • LLBP 平均 MPKI 降低 8.9% (从“精度上限”看，LLBP 提升有限)

2. IPC 收益偏小

  • 平均 speedup 只有 0.63%
  • 作者解释: 用 Top-Down 和 prior work 来说明这更可能是 ChampSim 的问题，而不是设计本身无用

3. 对间接分支、pipeline reset 较敏感

针对某些 workload 例如 PHPWiki 上，由于 indirect call misprediction 多，pipeline flush 会重置 LLBP 的预取过程，导致收益明显不如理想情况

说明 LLBP 对“前端频繁清空”的场景有脆弱性，其有效性依赖于预取窗口能稳定存在

4. context hash 是近似，不是精确调用链

  • RCR 使用的是无条件分支 PC 的 rolling XOR hash，并不是精确的 call chain
  • 成本低，但一定会引入 collision 和信息丢失

5. 存储效率低

  • LLBP 只覆盖 14.8% 的动态条件分支
  • 59% 的 override 其实和基线相同

说明有不少存储和带宽花在“正确但不必要的重复确认”上

这篇论文的后续工作：2026 HPCA: The Last-Level Branch Predictor Revisited