BTB 多分支命中要排序，单分支命中能否走捷径？——Arm US10817298B2 专利解析
BTB 多分支命中时要排序，但单分支命中能不能走捷径，提前重定向？
Arm 分支预测专利解析 · 03
上一篇：如何减少主 BTB 查找功耗？ · 下一篇：预测 taken 的分支实际 not-taken 时，前端如何快速恢复？
支持一个 fetch block 内多个分支目标的 BTB，可以提高预测覆盖率，却也把 offset 比较和目标排序带进了前端关键路径。这篇文章解析 Arm US10817298B2：如何为常见的单命中场景增加一条 shortcut path，在保留多分支预测能力的同时，更早给出 next fetch address。
1. 背景：BTB target prediction 的延迟会直接影响前端取指
在高性能处理器前端中，Branch Target Buffer，也就是 BTB，用于预测分支指令 taken 时的目标地址。当前端要取一个 fetch block 时，BTB 会根据 fetch block address 查找这个 block 中是否存在分支指令，以及这些分支的 predicted target address。
如果 BTB 命中，并且对应分支被 branch direction predictor 预测为 taken，那么该 target address 就会反馈给 fetch stage，用作下一次取指地址。
这篇 Arm US10817298B2 专利的标题是：
Shortcut path for a branch target buffer
分支目标缓冲器的捷径路径
专利摘要中说明：BTB 可以为同一个 fetch block 返回多个 predicted target addresses；当 lookup 发现该 fetch block 中有多条 branch 的预测目标时，需要 branch target selecting circuitry 从多个 target 中选择 next fetch block address。但当满足预定条件时，可以通过一个绕过 selecting circuitry 的 shortcut path，直接把 lookup 得到的 predicted target address 作为 next fetch block address。
2. 先说结论
这篇专利的核心可以概括为：
一个支持同一 fetch block 多个 branch target 命中的 BTB，正常情况下需要排序逻辑选择 program order 中最早的 predicted taken branch；但如果本次 BTB lookup 只有一个 branch target 命中，那么根本不需要排序，可以通过简单 AND-OR shortcut path 直接输出 target address，从而比完整 branch target selecting circuitry 至少早一拍得到 next fetch block address。
更短地说：
多命中：走完整排序逻辑；
单命中：走 shortcut path，绕过排序逻辑。它优化的是：
BTB target selection latency不是 BTB 容量，也不是 predictor accuracy 本身。
3. 为什么 BTB 需要支持一个 fetch block 多个 branch？
如果一个 fetch block 包含多条指令，就可能包含多条 branch。
例如 32B fetch block：
Fetch block X:
instr0
B1
instr2
B2
instr4
B3如果 BTB 每个 fetch block 只允许存一条 branch target，那么它最多只能预测 B1、B2、B3 中的一条。
如果第一条 branch 实际 not-taken，后面的 branch 可能 taken，但 BTB 已经没有后续 target 信息，前端就会 miss 掉这次控制流变化。
所以更强的设计是：
同一个 fetch block 可以在 BTB 中命中多个 branch target。例如：
BTB lookup for block X:
way0 -> B1 target
way1 -> B2 target
way2 -> empty
way3 -> B3 target这样 branch coverage 更好。
专利中也说明，若限制 BTB 每个 fetch block 只返回一个 target，会无法预测同一 block 内第二条或更多 branch；因此使用可以为同一 fetch block 存储多个 target addresses 的 BTB 能提高 branch prediction coverage。
4. 多个 target 命中时，为什么需要排序？
如果同一个 fetch block 中有多个 branch target 命中，并且不止一条被方向预测器预测为 taken，那么前端必须选择 program order 中最早的 predicted taken branch。
例如：
Fetch block X:
0x100: instr
0x104: B1 predicted not-taken
0x108: instr
0x10C: B2 predicted taken
0x110: B3 predicted taken正确的 next fetch block address 应该是：
target(B2)而不是 target(B3)。
因为如果 B2 taken，B3 根本不会执行到。
所以 branch target selecting circuitry 要做：
1. 找到哪些 BTB ways hit；
2. 结合 BDP 判断哪些 branch predicted taken；
3. 比较这些 branch 在 fetch block 内的 offset；
4. 选择 offset 最小的 predicted taken branch；
5. 输出它的 target address。这就是完整 target selection / sorting path。
问题是，这条路径会比较慢。
5. 完整排序路径为什么慢？
完整路径有依赖链：
BTB SRAM read
↓
tag compare / hit detect
↓
BDP taken qualification
↓
offset compare / earliest taken selection
↓
target mux
↓
next fetch block address特别是：
必须先知道哪些 way hit、哪些 branch predicted taken，
才能比较 offset 并选择 earliest predicted taken branch。专利中也指出，branch target selecting circuitry 可能需要考虑 branch addresses 和 taken/not-taken 预测，因此会增加 branch prediction latency。
对高频 superscalar core 来说，这个路径可能无法在一拍内完成。
6. 关键观察：多数 fetch block 其实只有 0 或 1 条 branch
专利的关键观察是：
虽然一个 fetch block 中存在多条 branch 的情况并不少，因此支持 multiple hits 是值得的；但实际中大多数 fetch block 只有 0 条或 1 条 branch。对于只有 1 条 branch 的情况，根本不需要完整排序逻辑。
专利中还给了一个典型统计口径：以 32B fetch block 为例，某些 benchmark 中大约 30% fetch block 没有 branch，40% 有 1 条 branch，约 30% 有多条 branch。
所以：
多分支 block:
需要 sorting，不能省
单分支 block:
target 唯一，不需要 sorting
无分支 block:
顺序取指，不需要 target selection这就是 shortcut path 的动机。
7. 整体结构：BTB + sorting path + shortcut path
简化后的结构如下：
Fetch block address
↓
+-------------------+
| BTB lookup |
| multi-way SRAM |
+-------------------+
| |
| +------------------------+
| |
↓ ↓
Shortcut path Full sorting path
AND-OR tree hit + taken + offset compare
| |
+-------------+-------------------+
↓
Next fetch block address其中：
| 路径 | 用途 |
|---|---|
| Full sorting path | 多个 BTB ways 命中时，选最早 predicted taken branch |
| Shortcut path | 只有一个 BTB way 命中时，直接输出唯一 target |
| Control circuitry | 判断是否可以用 shortcut path |
| Onehot detection | 检测本次 BTB lookup 是否只有一个 hit |
8. BTB 的 set-associative 结构
专利中的 BTB 是 N-way set-associative 结构。
一个 fetch block address 会索引到一个 set，该 set 中有 N 个 way。
例如 N=4：
BTB set indexed by fetch block X:
way0: tag + offset + target + type
way1: tag + offset + target + type
way2: tag + offset + target + type
way3: tag + offset + target + type每个 entry 可以包含：
tag
offset
predicted target address
branch type indicator
function return indicatoroffset 表示该 branch 在 fetch block 内的位置。
例如：
fetch block X starts at 0x100
branch at 0x108:
offset = 0x08
branch at 0x11C:
offset = 0x1C排序逻辑就是根据 offset 来判断哪条 branch 更早。
9. Hit 条件：tag match + offset 有效性
专利中 BTB lookup 不只是 tag match，还考虑 offset。
因为有时 fetch block address 可能不是自然对齐边界，或者 fetch 从 block 中间开始。
此时如果 BTB entry 对应的 branch 在 fetch start 之前，就不应该被认为是当前 fetch block 的有效命中。
所以 hit 条件可以理解为：
hit =
entry.tag == fetch_block.tag
AND
entry.offset >= fetch_start_offset这样可以避免命中当前 fetch 起点之前的 branch。
专利中明确描述，BTB entry 的 offset value 会与 fetch block address 的 offset portion 比较，若 entry offset 大于等于 fetch offset，且 tag 匹配，则该 way hit。
10. Full sorting path：多命中时选择 earliest predicted taken branch
完整路径大致如下：
for each way:
way_hit = tag_match && offset_valid
way_taken = BDP predicts taken for this branch
way_valid_taken = way_hit && way_taken
select way with smallest offset among way_valid_taken
next_fetch_block_address = selected_way.target伪代码：
candidates = []
for way in BTB_ways:
if hit[way] && taken[way]:
candidates.append((offset[way], target[way]))
if candidates not empty:
select candidate with smallest offset
next_pc = candidate.target
else:
next_pc = sequential_pc这个路径准确，但慢。
11. Shortcut path：单命中时不排序
如果本次 BTB lookup 只有一个 way hit：
hit vector = 0100那就没有必要比较 offset。
因为只有一个候选 target，直接输出即可。
于是 shortcut path 可以做：
target_shortcut =
OR over all ways:
hit[way] & taken[way] & target[way]当只有一个 hit 且它 predicted taken 时，AND-OR tree 输出就是正确 target。
如果多个 hit：
hit vector = 1010AND-OR tree 可能把多个 target OR 在一起，结果是 garbage / corrupt value。
所以 shortcut path 只能在 onehot 条件下使用。
专利中明确描述，shortcut path 可由多个 AND gates 和 OR gates 组成，每个 target address 与对应 taken signal 相与，再把各路结果 OR 起来；当只有一个 hit 时结果正确，多 hit 时结果可能损坏，因此必须由 control circuitry 控制是否采用。
12. Onehot detection：判断 shortcut 是否安全
核心判断是：
BTB 是否只命中一个 predicted target？也就是 onehot：
hit vector = 0001 => onehot
hit vector = 0010 => onehot
hit vector = 0100 => onehot
hit vector = 1000 => onehot
hit vector = 0000 => no hit
hit vector = 1010 => multiple hits当 onehot 成立：
shortcut output == full sorting output当 onehot 不成立且有多个 hits：
shortcut output may be corrupt
must use full sorting path专利主权利要求中也明确写到，control circuitry 包含 onehot detection circuitry；当检测到 BTB lookup 对 fetch block 只存储一个 branch instruction 的 predicted target address 时，选择 shortcut path 输出的 predicted target；当检测到有多个 predicted target addresses 时，选择 branch target sorting circuitry 的输出。
13. 图 5 方法流程
流程可以整理为：
Step 1:
lookup BTB using fetch block address
Step 2:
BTB returns hit vector + target addresses + offsets + branch info
Step 3:
determine whether shortcut condition passes
Step 4a:
if shortcut condition passes:
next fetch block address = shortcut output
next BTB lookup can start earlier
Step 4b:
if shortcut condition fails:
next fetch block address = full sorting output
next BTB lookup starts later伪代码：
lookup_result = BTB.lookup(fetch_block_pc)
if onehot(lookup_result.hit_vector) and no_exception:
next_pc = shortcut_path(lookup_result)
else:
next_pc = full_sorting_path(lookup_result)专利中说明，当 predetermined condition 满足时，下一次 BTB lookup 可以比条件失败时至少早一个 processing cycle。
14. 为什么能省一拍？
专利中给了一个很直观的 pipeline 例子。
如果 branch prediction 需要 2 cycles 才给出 target：
Stage 0: X X+1 X+2 Y
Stage 1: X X+1
Stage 2: X当 X 在 Stage 2 才发现 next fetch 应该是 Y 时，前面已经发起了 X+1、X+2 的 fetch，这些都要丢弃。
如果 shortcut path 能让 prediction 只用 1 cycle：
Stage 0: X X+1 Y
Stage 1: X那么只浪费 X+1，Y 能更早开始。
这既提升性能，也减少 I-cache 和 branch predictor 上的无效访问功耗。
专利中也明确指出，若 branch prediction result 可从 2 cycles 缩短到 1 cycle，就能减少 unnecessary fetches，使正确 fetch 更早发起，从而节省功耗并改善性能。
15. Shortcut path 的硬件形态：AND-OR tree
shortcut path 可以非常简单：
for each way:
gated_target[way] = target[way] & hit[way] & taken[way]
shortcut_target = OR(gated_target[0],
gated_target[1],
...
gated_target[N-1])如果只有一个 way 有效：
shortcut_target = that way's target如果多个 way 有效：
shortcut_target = targetA OR targetB
=> meaningless但没关系，因为 onehot check 会阻止它被采用。
这是一种典型的 speculative fast path：
先用简单逻辑快速生成一个可能正确的 target；
再用 onehot/control 判断是否允许提交这个 target。16. 如果 onehot check 还没算完，可以先投机使用 shortcut 吗？
可以。
专利提到：如果判断 predetermined condition 需要一些时间，BTB 可以先使用 shortcut path 提供的 next fetch block address，投机发起下一次 lookup。之后如果发现 condition 其实失败，就丢弃投机 lookup 结果，并用 full sorting path 的 target 重新发起 lookup。
也就是：
cycle N:
shortcut target produced early
speculatively start BTB lookup for shortcut target
cycle N+1:
condition resolved
if condition passed:
keep speculative lookup
if condition failed:
discard speculative lookup
restart using sorted target这类似很多前端 predictor 的 design philosophy：
fast path 先跑；
slow path 校验；
错了再 squash/restart。17. 为什么不是所有 onehot 都一定用 shortcut？
专利虽然以 onehot 为核心条件，但还提出了一些 exception。
也就是说：
onehot 是必要条件；
但不一定是充分条件。有些情况即使 BTB 只有一个 hit，也可能不适合 shortcut。
18. Exception 1：branch prediction resource 快满了
如果某些前端资源快满，例如：
fetch queue 快满
return address predictor 快满此时过快地产生下一个 fetch address 反而可能造成 pipeline stall。
不走 shortcut、慢一拍输出 target，反而给资源释放留出时间。
专利中提到，如果至少一个 branch prediction resource 的 spare capacity 小于等于阈值，则 predetermined condition 可以判定失败，不使用 shortcut path。资源例子包括 fetch queue 和 return address predictor。
可以理解为：
前端资源紧张时，不急着加速；
避免把队列推爆。19. Exception 2：特殊 branch type，例如 polymorphic branch
有些 branch target 不稳定，例如 indirect / polymorphic branch。
专利中特别提到 polymorphic branch：
同一条 branch 历史上出现过多个不同 target address这种 branch 可能需要更复杂的 predictor 来判断 target，而不是简单使用 BTB 中当前 target。
如果 shortcut path 太早输出 target，可能会绕过更准确但更慢的预测逻辑。
所以：
if branch type == polymorphic:
disable shortcut
use full selecting/sorting path or other predictor专利中说明，BTB 可以为每个 predicted target address 存 type identifying information，用于指示该 branch 是否属于不应使用 shortcut 的类型；polymorphic branch 是一个例子。
20. Exception 3：其他 branch target predictor 也命中
现代前端可能不只有 main BTB，还可能有：
micro predictor / L0 BTB
return address predictor
main BTB
polymorphic target predictor如果同一个 fetch address 在多个 predictor 中都命中，就需要更高层的 sorting / selection logic 决定谁优先。
例如：
main BTB hit
micro predictor hit
return address predictor hit这种情况下，即使 main BTB 自己只有 onehot，直接走 main BTB shortcut 也未必正确，因为可能应该采用 micro predictor 或 RAS 的结果。
所以专利提出：
如果至少一个 further branch target predictor 也提供了 predicted target address，
则 shortcut condition 可以失败。进一步的 predictor 可以是 micro-predictor，它比 BTB 更快但覆盖更少。
21. 图 8：和 micro-predictor / return address predictor 协同
专利图 8 中描述了更完整的系统：
Main branch predictor:
BTB + BDP + shortcut path
Micro-predictor:
更小、更快，覆盖更少
Return address predictor:
专门预测 function return target
Sorting logic:
多个 predictor 同时命中时选择最终 next fetch block address如果 micro-predictor 命中，可能已经通过更快的 shortcut path 给出 target。
如果 return address predictor 命中，并且 BTB entry 表明这是 return branch，则 sorting logic 可能优先使用 return predictor 的结果。
这时 main BTB shortcut 就不一定有意义。
所以 shortcut path 不是孤立机制，它必须和整个 predictor hierarchy 协同。
22. Shortcut path 和前一篇 BTB lookup suppression 的区别
这篇专利和前面那篇 Branch target look up suppression 很像，但优化点不同。
| 专利 | 核心目标 | 关键机制 |
|---|---|---|
| Branch target look up suppression | 降低 main BTB 访问功耗 | micro BTB coverage flag 有效时 suppress main BTB lookup |
| Shortcut path for BTB | 降低 BTB target selection latency | onehot 命中时 bypass sorting path |
前一篇是：
这次 main BTB 要不要查？这一篇是：
main BTB 查出来后，要不要走完整排序？所以它们发生在不同阶段：
Lookup suppression:
BTB lookup 前/lookup 控制阶段
Shortcut path:
BTB lookup 后/target selection 阶段二者可以组合使用：
如果 main BTB 根本不用查：
走 micro BTB
如果 main BTB 查了且只有一个 hit：
走 shortcut path
如果 main BTB 查了且多个 hit：
走 full sorting path23. 这个方案的收益
23.1 降低单命中 BTB lookup 的 target latency
只有一个 branch target 命中时，可以绕过 offset compare / sorting logic，提前得到 next fetch block address。
23.2 减少无效顺序 fetch
target 越早反馈，X+1、X+2 等错误顺序 fetch 越少。
23.3 降低功耗
减少不必要的 I-cache lookup、fetch queue entry、branch predictor lookup。
23.4 保留多分支 fetch block 的预测覆盖
多命中时仍然走完整 sorting path，保留同一 fetch block 多 branch target 的能力。
23.5 实现成本低
shortcut path 可以由简单 AND-OR gate tree 实现；onehot detection 也相对简单。
24. 这个方案的代价
24.1 需要额外 shortcut datapath
虽然逻辑简单，但仍然增加一条并行路径。
24.2 onehot / exception 检查增加控制复杂度
不能只看 hit 数，还可能需要考虑资源压力、branch type、其他 predictor 命中等。
24.3 多命中时 shortcut output 可能是错误值
必须确保多命中时不采用 shortcut output，或能丢弃 speculative lookup 结果。
24.4 如果投机使用 shortcut，需要 restart 机制
当 shortcut 被提前使用但之后发现 condition failed，需要 discard lookup result 并用 sorting target 重启。
24.5 对前端时序设计敏感
shortcut path 目的是进关键路径，因此 AND-OR tree、onehot detection、taken qualification 都要非常短。
25. 和普通 BTB 设计的区别
普通多路 BTB 设计：
lookup all ways
detect hits
combine with taken predictions
sort by offset
select earliest predicted taken target
feedback next PC本专利增加：
parallel shortcut path:
target = OR(hit & taken & target)
onehot check:
if exactly one BTB hit:
use shortcut target early
else:
use full sorting target也就是：
不是取消完整排序逻辑；
而是让 common case 绕过它。26. 权利要求核心翻译
Claim 1：主权利要求
主权利要求保护的是一种 apparatus，包括：
1. branch target buffer，包含多个 ways；
2. BTB 根据 fetch block address 查找该 block 内一个或多个 branch target；
3. branch target sorting circuitry；
4. 当多个 ways 命中多个 predicted target addresses 时，
sorting circuitry 比较这些 branches 的 offsets，
找出 block 中最早 predicted taken branch；
5. shortcut path 绕过 sorting circuitry，
直接转发某个 way 中的 predicted target address；
6. control circuitry 包含 onehot detection circuitry；
7. 如果 lookup 只发现一个 branch target，则选择 shortcut path；
8. 如果 lookup 发现多个 branch target，则选择 sorting circuitry 输出。这是整篇专利的核心保护范围。
Claim 2：N-way set-associative BTB
Claim 2 保护的是：
BTB 是 N-way set-associative，
并根据 fetch block address 并行查 N 个 ways，
最多识别 N 条 branch instructions 的 predicted target addresses。Claim 4–6：低资源时禁用 shortcut
这些权利要求保护：
如果某个 branch prediction resource 的 spare capacity
小于等于 threshold，则 shortcut condition failed。资源可以包括：
fetch queue
return address predictorClaim 7–9：特殊 branch type 禁用 shortcut
这些权利要求保护：
如果 BTB 命中的是 predetermined type branch，
则 shortcut condition failed。
BTB entry 可以存 type identifying information。
该 predetermined type 可以是 polymorphic branch。Claim 10–11：其他 target predictor 命中时禁用 shortcut
这些权利要求保护：
如果至少一个 further branch target predictor
也对同一 fetch block address 提供 predicted target address，
则 shortcut condition failed。进一步 predictor 可以是 micro-predictor：
更快，但覆盖更少。Claim 12–14：提前 speculative lookup 和失败重启
这些权利要求保护：
1. shortcut condition 满足时，BTB 可以至少早一个 cycle 执行 next lookup；
2. BTB 可以在 condition 尚未完全确定前，先用 shortcut target 做 speculative next lookup；
3. 如果后来发现 condition failed，则丢弃该 speculative lookup，并用 sorting circuitry target 重启。Claim 15：AND-OR shortcut path
Claim 15 保护 shortcut path 的具体逻辑：
1. 多个 AND gates：
each target address AND corresponding taken signal
2. 一个或多个 OR gates：
combine all AND outputs
3. OR output 作为 next fetch block address。这是硬件实现层面的关键 claim。
27. 这篇专利真正保护的技术点
这篇专利真正保护的不是普通 BTB，也不是普通多路 set-associative cache，而是：
1. BTB 支持同一个 fetch block 多个 branch target 命中；
2. 多命中时，通过 sorting circuitry 比较 offset，选择最早 predicted taken branch；
3. 同时提供 shortcut path，绕过 sorting circuitry；
4. onehot detection 检测本次 lookup 是否只有一个 branch target 命中；
5. onehot 时使用 shortcut path 提前输出 next fetch block address；
6. 多命中时使用完整 sorting path；
7. shortcut path 可以由 AND-OR tree 实现；
8. 可以在 condition 完全判定前先 speculative next lookup；
9. condition failed 时丢弃 shortcut lookup 并重启；
10. 低资源、特殊 branch type、其他 predictor 命中等情况可禁用 shortcut。核心思想是：
保留多 branch BTB 的覆盖能力，
但让单 branch common case 绕过昂贵排序逻辑。28. 从微架构角度看，它的本质是什么？
我认为这篇专利的本质是：
在 BTB 多 target 支持带来的复杂 target selection 路径旁边，增加一条针对 onehot common case 的快速旁路路径，使单命中 fetch block 不必为多命中 case 的排序代价买单。
可以抽象成：
BTB 多 way：
为 coverage 服务
sorting circuitry：
为 multi-branch correctness 服务
shortcut path：
为 single-branch latency 服务这是一种典型的 common-case fast path：
少数复杂情况保留完整逻辑；
多数简单情况走快速路径。它和处理器里很多 bypass / forwarding / early wakeup 思路类似，都是：
不要让 common case 等 worst case 的完整处理链路。29. 总结
Arm US10817298B2 这篇专利解决的是一个很具体的前端时序问题：支持同一 fetch block 多个 branch target 命中的 BTB 可以提高预测覆盖率，但多个 target 命中时需要 branch target sorting circuitry 来比较 offset、结合 taken prediction，选择 program order 中最早的 predicted taken branch。这个排序路径比较慢，会增加 next fetch block address 的反馈延迟。
专利的方案是在 BTB 后增加一个 shortcut path：
当 BTB lookup 只有一个 predicted target address 命中时，
绕过 branch target sorting circuitry，
直接用简单 AND-OR tree 输出 target address。只有一个命中时，shortcut path 的结果和完整 sorting path 相同；多个命中时，shortcut path 结果可能错误，因此必须由 onehot detection 和 control circuitry 控制是否采用。
这个机制的价值在于：
既保留多分支 fetch block 的预测能力，
又避免单分支 common case 承担完整排序延迟。从整个 Arm 分支预测专利系列看，这篇可以和 BTB lookup suppression 放在一起理解：
BTB lookup suppression：
尽量不查大 BTB，省功耗。
BTB shortcut path：
查了 BTB 后，尽量不走慢排序，省延迟。二者共同体现了一个方向：
现代前端分支预测器不仅要“预测得准”，还要在每个 cycle 内尽可能早、尽可能省地给出 next fetch address。
