这篇论文的前置工作：2024 MICRO: The Last-Level Branch Predictor

  • 重新审视 LLBP 解释它为什么“概念很好但效果还不够好”
  • 提出一个改进版 LLBP-X，用“动态上下文深度适配”来同时缓解两类关键问题：模式集冲突和上下文复制冗余

背景问题

  1. 分支预测仍然是高性能服务器 CPU 的硬瓶颈 (同 2024 MICRO LLBP 论述)
  2. TAGE-SC-L 预测器的容量需求依旧很大，但难以继续扩展
  3. 原始 LLBP 存在的问题
    1. 精度收益明显，但提升有限
    2. IPC 收益偏小
    3. 对间接分支、pipeline reset 较敏感
    4. context hash 是近似，不是精确调用链
    5. 存储效率低

LLBP 问题剖析: LLBP 的精度损失拆解

limit study: 逐步去掉 LLBP 的设计限制，看每一步能回收多少 MPKI

  • 去掉工程性简化（bucketing、删掉部分 history length、SC 不覆盖）：MPKI 再降 4.6%
  • 增大 tag：再降 1.3%
  • 无限 contexts：再降 3.9%
  • 无限 pattern/set：再降 9.1%
  • 取消 contextualization：再降 4.3%
  • 全都放开后，LLBP 几乎追平无限 TAGE；剩余小差距主要来自 D 带来的时间窗口

结论是：影响 MPKI 的主要因素是

  1. 每个 pattern set 太小；
  2. contextualization 带来的复制和训练开销。

瓶颈1 ：pattern set 冲突

进一步分析每个 context 里有多少 useful patterns:

  • 只有 14% 的 context 超过 LLBP 每个 set 的 16-pattern 上限
  • 68% 的 context 只有 8 个或更少 useful patterns

说明总容量并不是真的不够，问题在于：pattern 在各个 context 之间分布极不均匀
(2024 MICRO Uneven Cache Block 也是基于类似的观察: ICache Line 里不是所有的 Instruction 都有用到)

更进一步，观察这些热点 context 中 useful patterns 的平均 history length，发现：

pattern 最多的那些 context，正好也是平均 history length 最长的那些 context

结论是：
真正导致 pattern set 冲突的，不是普通 branch，而是 hard-to-predict branches 对长历史模式的大量需求

瓶颈 2：contextualization 带来的 pattern duplication

原始 LLBP 用固定 W=8，把 pattern 按上下文切碎

  • 好处: 帮助分散困难分支模式
  • 副作用是：短历史模式会被复制到很多 context 里

定量分析 duplication 随 history length 和 W 的变化:

  • history 越短，重复越严重
  • W 越大，重复越严重

duplication 带来的问题：

  1. 浪费容量；
  2. 训练时间变长，因为每个 context 要独立训练
  3. 适应行为变化更慢，因为更新被分摊到多个 context

核心思想：不同 branch/context 需要不同的上下文深度

基于上面的分析，作者提出最核心的思想：

  • 对短历史、容易预测的分支，应该用 浅上下文，减少复制与训练开销
  • 对长历史、困难分支，应该用 深上下文，把大量 pattern 分散到更多 context，减少热点 set 冲突

作者做了一个按 history length 分层的实验：

  • 对短 history（6–37），W=2 相比基线 W=8，useful predictions 增加 63–213%
  • 对长 history（232–3000），W=64 相比 W=8，useful predictions 增加 4.2–95%

结论：单一固定 W 并不是最优策略，应该按 context 动态选择深浅

LLBP-X 的设计

LLBP-X

LLBP-X 的基本思路：

  • 默认都用 W=2
  • 一旦发现某个 context 的 pattern set 冲突较多，而且新分配的模式偏向长 history，就把该 context 切换到 W=64

新增结构：CTT（Context Tracking Table）

LLBP-X 引入的主要新结构是 CTT:
作用是跟踪哪些 shallow context 开始表现出 deep-context 的需求

CTT 的每个表项包含：

  • tag（6b）
  • avg-hist-len counter（3b）
  • depth bit（1b）
  • replacement bits（2b）

整体容量约 9KB，可跟踪 6K contexts

context 深度切换机制

切换逻辑分两步：

  1. overflow 触发跟踪

    • 当 PB 中某个 pattern set 的高置信度 pattern 数超过阈值时，发出 overflow 信号，让 CTT 开始跟踪该 context
    • 论文最终选择的阈值是 7 个高置信度 patterns

  2. 平均历史长度决定深度切换: CTT 监控该 context 新分配 pattern 的 history length：

    • 若分配的 history 超过阈值 Hth=232，avg-hist-len 计数器加一，否则减一；
    • 当它饱和到阈值后，把该 context 切换为 deep（W=64）

将 occupancy + long-history tendency 结合起来，
避免了把“短历史但活跃”的 context 误判成困难 context

LLBP-X 只选了 W=2 和 W=64（二元切换），原因是：

  • 更多档位理论上能更细粒度适配
  • 但每次切换深度，旧深度下学到的 pattern 基本都要重新学习
  • retraining penalty 会抵消更细粒度的收益

双 context ID：CID2 和 CID64

为了支持双深度，RCR 不再只维护一个 context ID，而是同时维护：

  • CID2
  • CID64

访问时：

  • 先用 CID2 去查 CTT
  • 若命中，看 depth bit 决定本 context 应该用 CID2 还是 CID64；
  • 然后再去查 Context Directory 和发起 prefetch

这个选择过程不在 critical prediction path 上

History Range Selection 机制

原始 LLBP 只保留了 TAGE 21 个 history length 里的 16 个，目的是简化硬件

LLBP-X 利用“深度与 history 自然相关”这个观察，把 history range 也分层管理：

  • shallow context（W=2）：保留较短 history (论文最终参数是 6–232)
  • deep context（W=64）：保留较长 history (最终参数是 37–3000)

这样做的意义是：

  1. shallow set 不再被长 history 模式占坑
  2. deep set 专门服务困难模式
  3. 四个 bucket 的利用率更高，冲突更少

本质是让浅上下文和深上下文各自服务不同类型的 history

实验结果

MPKI 精度增益

  • LLBP-X 相对 64K TAGE-SC-L，可实现 1.4–27% 的 MPKI reduction，平均 12.1%
  • 相对原始 LLBP，带来 0.8–11.5% 的绝对额外精度增益，平均 3.6%
  • 相当于比原设计平均再提升 36%

作者还构造了一个理想版本 LLBP-X Opt-W：预先知道每个 context 最优应该选 W=2 还是 W=64 ，因而没有切换后重训练的代价

  • 平均 MPKI reduction 是 12.6%
  • LLBP-X 真正动态实现的是 12.1%，相当于达到了理想选择的 97%

IPC 性能收益

gem5 全系统仿真结果显示：

  • LLBP-X 相对 64K TAGE-SC-L，平均 1.0% speedup，范围 0.08–2.7%
  • 原始 LLBP 平均 0.71%
  • 理想化 512K TSL 平均 2.4%

作者将 LLBP-X 的性能收益较低归因于：

  1. branch predictor 只是整个系统的一部分
  2. 在 server workload 中还受 cache、memory、MLP 等因素共同限制

Prefetch 效率分析

  • 84% 的 prefetch 能按时到达 PB，覆盖率不错
  • 但只有大约三分之二的 prefetch 真正用于预测
  • 40% 属于 over-prefetch

说明：LLBP-X 的 energy/efficiency 还有待提高

还分析了 false-path prefetch：

  • 如果把错误路径带来的 prefetch 全去掉
  • over-prefetch 会下降 56%
  • 但 coverage 会下降 8%
  • prediction accuracy 还会额外下降 1.4%

说明 false-path prefetch 虽然“浪费”，但也在帮助系统提前把未来可能需要的上下文带进来

敏感性分析 DSE

1. Hth 阈值

history threshold 从 37 扫到 1444：

  • 最优是 Hth=232
  • 最差是 Hth=1444
  • 大多数 benchmark 对最优点附近并不特别敏感

2. CTT 大小

CTT 从 4K 扫到 8K entries：

  • 6K entries 后基本不再继续改善
  • 最终选 6K-entry, 6-way，增加约 9KB 存储

3. 容量扩展性

pattern store 从 8K 扩到 128K contexts 时：

  • MPKI reduction 从 10.5% 持续提升到 17.6%，说明 LLBP-X 具有扩展性
  • 配一个 4 倍更小的 16K TAGE-SC-L，LLBP-X 仍可带来 2.6% MPKI reduction

预测一种 BPU 形态：小 TAGE + LLBP-X

面积和复杂度代价

LLBP-X 的附加开销：

  • 主要来自 CTT：9KB
  • RCR 从 8 扩到 64 unconditional branches，增加 224B
  • CD replacement bits 从 2 增到 3，增加 142B
  • 总开销约 9.36KB，相对原始 LLBP 只增加 1.8% 容量

局限 Futurn Work

  1. 离理想 512K TSL 仍有明显差距
  2. prefetch 的能耗效率不够理想
    • over-prefetch 意味着主存储访问和 PB 填充仍有明显冗余
  3. 深度切换存在 retraining penalty
  4. 启发式控制: overflow + avg-history-length
    • 不是最优策略，只是很好的近似 (97% of Opt-W)