如何减少主 BTB 查找功耗？

Arm 分支预测专利解析 · 02
上一篇：分支跳过技术：Branch Sequence Detector · 下一篇：BTB 多分支命中要排序，单分支命中能否走捷径？

专利：US 11,029,959 B2，Branch Target Look Up Suppression
申请人及受让人：Arm Limited
发明人：Yasuo Ishii、Muhammad Umar Farooq、Chris Abernathy
申请号：16/120,674；申请日：2018-09-04；授权日：2021-06-08
原文：Google Patents（授权专利全文） · Justia（申请公开全文） · 授权 PDF

这项专利用一组随路径提前传递的 way prediction + flag 控制主 BTB。way prediction 关闭确定没有目标的 way；flag 确认 micro-BTB 已覆盖当前 block 的全部目标后，关闭整个主 BTB lookup。

控制信息针对“下一次将要预测的 block”生成。前端处理 block A 时已经知道预测后继 block B，于是把 B 的主 BTB way 分布和覆盖状态挂在 A→B 这条路径上。再次从 A 走向 B，主 BTB 在访问开始前就能决定开哪些 way。

1. 主 BTB 的功耗花在哪里

专利中的 main branch target storage 是 set-associative BTB。同一 instruction block 内可以有多条分支，每个 way 保存其中一条分支的 target prediction。以 Fig. 2B 的四路结构为例，一个 set 可同时返回 BNE 和 BGT 两个目标，方向预测逻辑再选择程序序最早的 predicted-taken 分支。

micro-BTB 是容量更小的 secondary branch target storage，用于缓存主 BTB 的常用目标。前端通常会并行查询 main BTB、micro-BTB 和方向预测器；micro-BTB 命中可以更快给出目标，但 main BTB 的多路阵列仍可能在同一拍被激活。

本专利把主 BTB 的访问分成三档：

提前得到的信息 主 BTB 动作
没有可靠信息 激活全部 way
way prediction 有效 只激活标为 1 的 way
coverage flag 有效，或 way prediction 全 0 完全抑制 lookup

2. Fig. 2B：四路只开 way 1 和 way 3

Fig. 2A 的 block 204 从地址 [X] 开始，其中有 BNE、BGT 两条分支。到达 [X] 有两条路径：block 200 中的 BL 跳到 [X]，或者 block 202 从 [X-32B] 顺序进入 [X]。

Fig. 2B 给出的主 BTB set 为：

way 0：空
way 1：BNE target
way 2：空
way 3：BGT target

way prediction = 0 1 0 1
flag = 0

前端只激活 way 1、way 3。way 0、way 2 的数据阵列和比较路径可以保持关闭。flag 为 0，因为 micro-BTB 的一个 entry 在该实施例中只能缓存这个 block 的一个 target，无法同时覆盖 BNE 和 BGT。

Fig. 2C 只在 way 1 保存 BNE：

way prediction = 0 1 0 0
flag = 1

BNE target 已经缓存进 micro-BTB，因而这个 block 在 main BTB 中的全部 target 都能从 secondary storage 得到。下次处理 [X] 时，main BTB 无需读取 way 1，也无需做 tag 比较；lookup control 直接关闭整个主 BTB。

Fig. 2A-2C：两目标时选择 way 1/3；单目标已被 micro-BTB 覆盖时设置 FLAG=1

flag 表示“覆盖关系”，不等同于“这个 block 只有一条分支”。授权 Claim 1 的表述是：main BTB 为预测后继 block 保存的全部 branch target predictions 都已经存在于 secondary branch target storage。Fig. 2C 使用“至多一个 main-BTB target，且这个 target 已被 micro-BTB 缓存”作为具体置位条件；该条件写进 Claim 4。

3. way prediction 和 flag 存在哪里

程序流进入下一 block 有两种来源，专利为两种来源各放一份元数据。

predicted taken 路径：放进 micro-BTB entry

当前 block 中有一条 predicted-taken branch，下一 block 从该分支的 target 开始。micro-BTB entry 保存：

字段 Fig. 3A 编号 内容
source 304 源分支地址
target 306 预测目标地址
way prediction 308 target block 在 main BTB 中需要激活的 way
flag 310 target block 的全部 main-BTB target 是否已被 micro-BTB 覆盖

sequential 路径：放进 way predictor entry

当前 block 没有 predicted-taken branch，下一 block 为当前地址加 32B。way predictor entry 保存 source + way prediction + flag，无需再保存 target，因为顺序后继地址可以直接计算。

Fig. 3A-3C：micro-BTB 和 way predictor 都携带下一 block 的 way prediction 与 flag

方向预测完成前，前端还不知道这次会走 taken target 还是 sequential successor。Fig. 4 让 micro-BTB 406 和 way predictor 408 在 P1 并行读取，branch prediction logic 420 得出方向后，pipeline control 412 选择对应路径的元数据。

4. Fig. 4：lookup control 在主 BTB 访问前拿到控制位

Fig. 4 的预测流水线包含 P0-P4：

  • P0：instruction fetch control 402 选择当前 block 地址；
  • P1：main BTB 404、micro-BTB 406、way predictor 408 发起访问；
  • P2：主 BTB 输出进入寄存级 418，micro-BTB/way predictor 信息进入 414/416；
  • P3-P4：保存连续两个 prediction unit 的结果，供 way prediction and flag generation 424 建立前后继关系。

main BTB 前端有 lookup control 410。它可以激活全部 way、激活 way prediction 指定的子集，或完全阻止 lookup。micro-BTB 命中且分支方向预测为 taken 时，target 可直接送往 instruction fetch control；main BTB 的结果则作为容量更大的后备来源。

Fig. 4：main BTB、micro-BTB、way predictor 与 lookup control 的流水线连接

这里的节能动作发生在阵列激活前。等主 BTB 读完再丢弃多余 way，只能减少后续选择逻辑，无法省下阵列读取本身的动态功耗。

5. 元数据如何从相邻 prediction unit 学出来

Fig. 5 把 block A 和其预测后继 B 同时放在流水线中观察。当 A 在 P4、B 在 P3 时，电路已经知道两件事：

  1. A 是被 predicted-taken branch 截断，还是顺序结束；
  2. B 的 main BTB 哪些 way 实际含有 target，以及这些 target 是否都在 micro-BTB 中。

虚线框 500 就是这对相邻 prediction unit。

Fig. 5：P4 中的 A 与 P3 中的 B 形成前后继对，用于生成 B 的 way prediction/flag

更新位置由 A 的退出方式决定：

  • A 由 predicted-taken branch 结束：把 B 的 way prediction/flag 写进该源分支的 micro-BTB entry；
  • A 顺序结束：把 B 的 way prediction/flag 写进以 A 为 source 的 way predictor entry。

之后再次遇到 A，micro-BTB 与 way predictor 两套候选都会提前读出。方向预测决定走 taken 或 not-taken 路径，并选择 B 对应的主 BTB 激活配置。

6. Fig. 6 的实际控制流程

Fig. 6 从 step 600 开始：

  1. 取下一 instruction block；
  2. step 602 查看当前控制信息是否要求激活至少一个 BTB way；
  3. 有 way 要开：step 604 并行查询 main BTB、micro-BTB、way predictor；
  4. 没有 way 要开，或 flag 已置位：step 606 只查 micro-BTB 与 way predictor；
  5. 当前 block 没有 predicted-taken branch：用 way predictor 命中的元数据配置顺序后继；
  6. 当前 block 有 predicted-taken branch：用 micro-BTB 命中的元数据配置 target block；
  7. 对应的小表未命中：恢复 full BTB way activation。

Fig. 6：flag/way prediction 命中时选择性激活，元数据缺失时恢复全路访问

回退到全路访问保证了正确性。way predictor 或 micro-BTB 未命中只会损失节能机会，不会让前端永久看不到 main BTB 中的目标。

7. flag 会失效，专利给了明确的维护规则

coverage flag 依赖 main BTB 与 micro-BTB 的内容关系。任一侧发生替换或新增，旧 flag 都可能失真。说明书和从属 Claim 给出几种处理方式：

  • micro-BTB 中 target block 的 entry 被替换时，使对应 way prediction 失效；
  • 简化实现可以清除 micro-BTB 中全部 flag；
  • 同一次替换也可以清除 way predictor 中全部 flag；
  • main BTB 为某 block 新增 branch target prediction 时，使对应 source 的 way prediction 失效。

全局清 flag 比精确反向追踪更简单，代价是短时间回到全路访问。新路径重新经过流水线后会再次生成元数据。

8. 授权 Claim 1-20 覆盖什么

Claim 1：主组合

Claim 1 要求：instruction fetch circuitry、main branch target storage、缓存其目标的 secondary branch target storage、两级并行 lookup 能力、set-associative main storage、标识下一 block 有效 way 的 way prediction，以及表明 secondary 已覆盖全部 main target 的 flag。flag 处于 active value 时抑制下一 block 的 main lookup。

Claim 2-10：两种后继路径与三档访问

  • Claim 2：顺序后继的元数据放在 way prediction storage；
  • Claim 3：taken target 后继的元数据与 secondary storage 中的 branch target prediction 关联；
  • Claim 4：至多一条 main target 且已缓存时置 flag；
  • Claim 5-6：secondary 容量小于 main，且一个 secondary entry 可只保存一个 block target；
  • Claim 7：way prediction 全部为 0 时抑制 main lookup；
  • Claim 8：way prediction 为 0 的 way 不激活；
  • Claim 9：最早 predicted-taken branch 决定 target 后继，无 taken 则选择 sequential successor；
  • Claim 10：micro-BTB 与 way predictor 并行读取，方向预测结果选择其一。

Claim 11-18：流水线学习与一致性

  • Claim 11-14：用相邻流水级中的前后 block 生成、写入 way prediction/flag；
  • Claim 15-17：secondary entry 替换时使相关预测或全部 flag 失效；
  • Claim 18：main storage 新增 target 时使对应 way prediction 失效。

Claim 19 把 Claim 1 的组合写成方法，Claim 20 使用 means-plus-function 形式再次覆盖装置。

四个 way、32B block、P0-P4 都来自附图实施例。独立 Claim 1 没有限定 way 数量、block 字节数或具体流水级数。

9. 这项设计的边界

flag 需要全覆盖证明

micro-BTB 命中一条 target 并不足以关闭 main BTB。flag 只有在该 block 的全部 main-BTB target 都能由 secondary storage 提供时才有效。Fig. 2B 中 BNE 已缓存也不能关主 BTB，因为 BGT 仍只存在于 main BTB。

way prediction 节省的是动态激活

main BTB 的总容量没有减少，未命中和内容变化时仍会全路访问。收益取决于有效元数据的命中率、每个 block 的 target 分布以及多路阵列读取的功耗占比。

元数据描述的是路径相关的后继

同一个 block 可能由 jump target 到达，也可能由 sequential flow 到达。专利分别使用 micro-BTB 和 way predictor 保存两条来源的后继信息，避免用单一表项混合不同路径。

结语

这项专利给主 BTB 加了两级关断条件。0 1 0 1 + FLAG=0 只读 way 1、way 3；0 1 0 0 + FLAG=1 直接跳过 main BTB。前端利用相邻 prediction unit 学出下一 block 的 way 分布，再按 taken target 或 sequential successor 把元数据写进 micro-BTB 或 way predictor。

主 BTB 继续提供容量，micro-BTB 继续提供低延迟目标，way prediction 和 coverage flag 负责减少不必要的阵列激活。

原文与文件