NTB Predictor(Intel US20230100693A1)[2023]: Prediction of next taken branches in a processor
| Title | Patent Number | Inc. | Year | url |
|---|---|---|---|---|
| Prediction of next taken branches in a processor | US20230100693A1 | Intel Corp | 2023 | https://patents.google.com/patent/US20230100693A1/en |
该专利提出 next taken branch (NTB) prediction：不再对当前 fetch path 上遇到的每个 branch 逐个预测 taken/not taken 再组合，而是直接预测从当前 target instruction 到下一个 predicted taken branch 的 offset distance。
TLDR：
- 核心硬件是 NTB prediction circuit，内部包括 NTB predictor、BTB、path history updater，以及用于训练的 update buffer
- NTB predictor 维护 prediction data entry
- 将 path information/path history 与 offset distance 关联
- 命中 entry 后读取 offset field
- 用 offset 加到 instruction pointer 上定位 predicted next taken branch。
- BTB 负责把 predicted next taken branch 转换为 target instruction；path history updater 用 predicted branch 和 target 更新 path history，使预测可以从一个 taken branch target 递归推进到下一个 taken branch target。
- update buffer 将 out-of-order execution 的 branch completion 重建为 program order，并以 update group 为单位训练 tag/offset；unconditional branch 或 offset 超过 threshold 时设置 EOL flag，回退到 BTB lookup。
背景和动机
处理器中的 branch predictor 通常在 branch 的真实方向确定之前预测控制流方向，以便 front-end 提前 fetch/speculatively execute 后续指令。预测正确时可以降低控制相关停顿；预测错误时会带来 pipeline flush、重新 fetch 和执行时间增加。
传统方式通常对执行中遇到的每个 branch instruction 做 taken/not taken 预测，然后组合这些预测以确定第一个 predicted taken branch。该方式的问题是：
- 每个 branch 都要预测，front-end 对多个候选 branch 的处理时间和能耗较高。
- 为大量 branch 缓存预测数据需要更多 predictor storage。
- 如果目标只是找到控制流中第一个会改变顺序执行路径的 taken branch，那么逐个预测中间 not taken branch 存在冗余。
本专利的动机是把预测对象从“每个 branch 的方向”提升为“下一个 taken branch 的位置”，用 path history 索引一个 offset distance，从而跳过中间 predicted not taken branches。
相关工作：
| Title | Authors, From | url |
|---|---|---|
| Branch cache | Advanced Risc Machines Limited, US5506976A | https://patents.google.com/patent/US5506976A/en |
| Next branch table for use with a branch predictor | The Regents Of The University Of Michigan, US20130290679A1 | https://patents.google.com/patent/US20130290679A1/en |
| Power Efficient Branch Prediction through Early Identification of Branch Addresses | Yang et al., CASES 2006 | HTML cited non-patent literature |
Insight
Insight: 将预测粒度从 branch direction 改为 next taken branch
传统 predictor 的基本粒度是 branch instruction：每个 branch 需要判断 taken/not taken。该专利观察到，front-end 真正需要尽快知道的是“顺序路径何时会跳走”，也就是下一个 predicted taken branch。若能够直接预测从当前 target instruction 到下一个 predicted taken branch 的距离，就可以避免对中间 predicted not taken branches 的逐一方向预测。
该 insight 的关键点是：not taken branch 不改变顺序 fetch path，因此对“寻找下一个控制流跳转点”而言，中间 not taken branches 可以被压缩成一个 offset distance。
Insight: 用 path history 绑定 offset distance
next taken branch 的位置不是静态常量，而与最近执行路径有关。专利用 path information 作为索引，典型内容包括 path history、target instruction identifier 或两者组合。prediction data entry 的 tag field 记录 path information，offset field 记录从当前位置到 predicted next taken branch 的 instruction distance。
这使 predictor 可以学习“在某类执行路径之后，下一个 taken branch 通常出现在多远处”，而不是只记住某个 branch 的局部 taken/not taken 行为。
Insight: 用 update group 训练 skipped branches
NTB prediction 会跳过一串 predicted not taken branches，因此训练时不能只看单个 branch completion。专利引入 update buffer，把两个 predicted taken branches 之间的 predicted not taken branch set 组织成 update group，并在 out-of-order execution 完成后重建 program order。这样可以在 update group 完成后更新对应 prediction data entry 的 tag 和 offset。
Insight: EOL flag 处理不适合 offset prediction 的边界
当 next taken branch 是 unconditional branch，或 offset distance 超过 threshold，entry 的 EOL field 会被置位。EOL 表示 offset field 不再有效，预测应回到 BTB lookup。这是一个 pragmatic guard：NTB predictor 只覆盖适合用有限 offset 表达的情形，把难以压缩的控制流交给已有 BTB 机制。
核心设计
该专利的核心设计是一个嵌入 branch prediction circuit 的 NTB prediction circuit。它从 initial instruction 或 previous taken branch 的 target instruction 触发，基于 path history 查询 prediction data entry，得到 offset distance 后定位 predicted next taken branch，再用 BTB 找到该 branch 的 target instruction 并更新 path history，形成连续预测链。
flowchart LR
T[initial instruction / target instruction] --> P[path information: path history + target id]
P --> N[NTB predictor]
N --> E[prediction data entry: tag/useful/confidence/offset/EOL]
E -->|valid offset| B[predicted next taken branch]
E -->|EOL set| BTB[BTB lookup]
B --> BTB
BTB --> NT[target instruction fetched]
NT --> U[path history updater]
U --> P
X[execution circuit] --> UB[update buffer]
UB -->|completed update group| N设计点 1: 直接预测 next taken branch
针对的问题：传统 branch predictor 需要对每个 branch 做 taken/not taken prediction，再组合出第一个 predicted taken branch，导致 front-end 预测时间、功耗和 predictor storage 增加。
解决的思路：在检测到 initial instruction 或 previous taken branch 的 target instruction 时，NTB predictor 直接预测下一个 predicted taken branch。预测结果不是单个 branch 的方向，而是 offset distance。
设计：
- 输入 path information，包括 path history、target instruction identifier 或组合。
- 用 path information 匹配 prediction data entry 的 tag field。
- 读取 offset field，得到从当前 target instruction 到 predicted next taken branch 的 offset distance。
- 将 offset distance 加到 instruction pointer 或当前位置，得到 predicted next taken branch。
- 中间 predicted not taken branches 不需要逐个预测方向。
设计点 2: Prediction data entry 的字段组织
针对的问题：NTB predictor 需要同时表达匹配条件、预测距离、置信度、替换/有效性以及边界 fallback。
解决的思路：每个 prediction data entry 存储一个 path-to-offset 映射，并附带 useful/confidence/EOL 元信息。
设计：
tag field：保存与 path history、target instruction 或其组合相关的 tag。offset field：保存从当前位置到 next taken branch 的 offset distance。confidence field：可作为 counter；预测正确时增加，错误时减少，降低到 threshold 后可 reset/update offset。useful field：标记该 entry 曾产生 useful next taken branch prediction，可用于替换或保留策略。EOL field：当 offset field 不应被使用时置位，例如遇到 unconditional branch 或 offset 超过 threshold。- NTB predictor 可以包含多张 table，不同 table 使用不同 tag length，以覆盖短 path history 和长 path history 的不同 aliasing/容量权衡。
设计点 3: BTB 与 path history updater 形成预测循环
针对的问题：offset distance 只能定位 predicted next taken branch，本身不提供该 branch 的 target instruction；下一轮 NTB prediction 又需要更新后的 path history 和 target。
解决的思路：用 BTB 查 predicted next taken branch 的 target instruction，并把 branch/target 信息送入 path history updater。
设计：
- NTB predictor 输出 predicted next taken branch 后，BTB 以该 branch 为索引查 target instruction。
- fetch circuit fetch 该 target instruction。
- path history updater 接收 predicted next taken branch 与 target instruction，生成 updated path history。
- updated path history 和 target instruction 再送回 NTB predictor，进行下一次 NTB prediction。
- FIGS. 31A-31C 的示例中，预测从 Inst 1 到 Branch A，再 fetch Inst 3；之后跳过 predicted not taken Branch B，预测 Branch C 并 fetch Inst 6；再预测 Branch D 并 fetch Inst 8。
设计点 4: Update buffer 与 update group 训练
针对的问题：out-of-order execution 会乱序完成 branch instructions，而 NTB entry 的训练需要知道 program order 中两个 taken branches 之间的结构。
解决的思路：update buffer 接收 execution circuit 的 branch completion 信息，按 program order 重建并组织为 update groups。
设计：
- update buffer 从 NTB predictor 接收 predicted next taken branch 信息。
- 每个 update group 由两个 predicted taken branches 定义，包含位于两者之间的 predicted not taken branches，以及结尾的 predicted taken branch。
- update buffer 收集 out-of-order branch completion，并判断某个 update group 是否全部完成。
- update group 完成后通知 NTB predictor。
- NTB predictor 用该 group 对应的 path information 更新 tag field，用 group 的 offset distance 更新 offset field。
- 更新完成后，该 update group 可从 update buffer 删除。
设计点 5: EOL fallback 规则
针对的问题：并非所有 next taken branch 都适合用有限 offset 表达；例如 unconditional branch 可能不需要或不适合训练 offset，过长 offset 也会扩大 field 或降低预测质量。
解决的思路：在 entry 内设置 EOL flag，作为 offset field 无效的显式信号。
设计：
- 如果 completed update group 以 unconditional branch 结束，则设置 EOL field。
- 如果 offset distance 超过 predefined threshold，也设置 EOL field。
- EOL set 时，不使用 offset field 预测 next taken branch，而由 BTB lookup 决定 branch prediction。
- 该机制把 NTB predictor 的适用范围限制在“可压缩、可学习、offset bounded”的控制流片段。
Claims 摘要
HTML 中 claims 总数为 20。权利要求覆盖 processor、method 和 system 三类对象。
- 独立 claim 1 覆盖 processor：execution circuit 执行 instructions；prediction circuit 在检测到 first target instruction 后，识别与该 target 的 path history 关联的 prediction data entry，并用其中的 offset distance 决定 predicted next taken branch。
- claims 2-4 限定 first target instruction 可以是 previous taken branch 的 target，也可以是 program initial instruction；prediction circuit 还可通过 BTB 找到第二 target instruction 并更新 path history。
- claims 5-7 限定 prediction data entry 字段：tag field、offset field、EOL flag、useful field、confidence field。
- claim 8 加入 update buffer：update groups 由 predicted taken branches 定义，update buffer 判断 group completion，并驱动 prediction circuit 修改第二 prediction data entry。
- 独立 claim 9 覆盖 method：检测 target instruction、按 path history 找 entry、按 offset distance 决定 predicted next taken branch。
- claims 10-16 展开 method：tag matching、BTB target fetch、path history update、update buffer training、conditional/unconditional 判断、threshold 判断、EOL flag 设置。
- 独立 claim 17 覆盖 system：processor 具有 prediction circuit，并与 external memory 耦合。
- claims 18-20 将 BTB/path history update、update buffer 和基于 completed update group 修改 entry 的能力加入 system 范围。
Figures Captions 覆盖
| Figure | Caption/内容摘要 | 与核心设计关系 |
|---|---|---|
| FIG. 1 | system portion block diagram | 通用 system/processor context |
| FIG. 2 | processor block diagram | 通用 processor context |
| FIG. 3 | multi-domain processor block diagram | 通用 processor context |
| FIG. 4 | processor with multiple cores | 通用 core context |
| FIG. 5 | processor core micro-architecture | 通用 OOO core context |
| FIG. 6 | another processor core micro-architecture | 通用 low-power/Atom-like core context |
| FIG. 7 | another processor core micro-architecture | 通用 in-order core context |
| FIG. 8 | still further processor core micro-architecture | 通用 high-performance OOO core context |
| FIG. 9 | another processor block diagram | 通用 processor/accelerator context |
| FIG. 10 | representative SoC block diagram | 通用 SoC context |
| FIG. 11 | another example SoC | 通用 SoC context |
| FIG. 12 | example system | 可部署系统示例 |
| FIG. 13 | another example system | 可部署系统示例 |
| FIG. 14 | representative computer system | 可部署系统示例 |
| FIGS. 15A-15B | systems in accordance with embodiments | multiprocessor/system context |
| FIG. 16 | IP core development system | IC design/fabrication context |
| FIGS. 17A-17B | generic vector friendly instruction format and templates | ISA/vector boilerplate |
| FIGS. 18A-D | specific vector friendly instruction format | ISA/vector boilerplate |
| FIG. 19 | register architecture | ISA/register boilerplate |
| FIG. 20A | in-order pipeline and OOO pipeline | core pipeline context |
| FIG. 20B | in-order architecture core and OOO architecture core | core front-end context，含 branch prediction unit |
| FIGS. 21A-21B | specific in-order core architecture | core implementation context |
| FIG. 22 | multi-core processor with IMC/integrated graphics | processor implementation context |
| FIGS. 23-24 | exemplary computer architectures | deployment context |
| FIG. 25 | software instruction converter | ISA translation context |
| FIG. 26 | example system | 核心图：processor 2600、system memory、fetch/decode/execution、branch prediction circuit、NTB prediction circuit |
| FIG. 27 | example processor components | 核心图：NTB predictor、BTB、path history updater、update buffer、dispatch/execution |
| FIG. 28 | example prediction data entry | 核心图：tag/useful/confidence/offset/EOL fields |
| FIG. 29 | example update buffer | 核心图：update group 组织与训练 |
| FIG. 30 | method for next taken branch prediction | 核心流程：path input、entry match、offset、BTB target、fetch、path update |
| FIGS. 31A-31C | example data operations | 核心示例：跳过 predicted not taken Branch B，连续预测 Branch A/C/D |
| FIG. 32 | method for prediction training | 核心流程：update group completion、tag/offset update、EOL handling |
| FIG. 33 | method for next taken branch prediction | 精简方法 claim 对应流程 |
| FIG. 34 | storage medium | machine-readable medium / IC fabrication claim context |
Description 结构摘要
- FIELD/BACKGROUND：专利领域是 processor branch prediction；传统 predictor 逐个 branch 预测方向，带来时间、功耗和存储开销。
- BRIEF DESCRIPTION OF DRAWINGS：FIG. 1-25 是通用 processor/system/ISA context，FIG. 26-34 是 NTB prediction 的核心附图。
- DETAILED DESCRIPTION 前半部分：覆盖 multicore processor、power domain、OOO/in-order core、SoC、computer architecture、vector friendly instruction format、register architecture 等可实施环境。这些内容主要用于扩大可实施范围，不是本专利的创新点。
- DETAILED DESCRIPTION 后半部分：从 “Prediction of Next Taken Branch” 开始描述 NTB prediction circuit、prediction data entry、update buffer、prediction method、training method、example data operations 和 storage medium。
- Embodiments/Examples：Examples 1-31 基本复述 claims 的 processor、method、system、apparatus 版本，并强调可组合实现。
评估
可能收益
- 降低 front-end branch prediction latency：直接预测 next taken branch，可减少对中间 branch 的逐项方向预测。
- 降低 predictor energy：不必对连续 not taken branches 全部访问/组合 predictor。
- 降低存储压力：prediction data entry 存 path-to-offset，而不是为每个 branch 都保留同等粒度的 cached prediction data。
- 适合宽 fetch/deep pipeline：front-end 若每周期看到多个 branch，快速定位 first predicted taken branch 的价值更高。
实现风险
- Path aliasing：path history/tag length 太短会让不同控制流映射到同一 offset，太长又会增加 table capacity/latency。
- Offset stability：next taken branch 的距离需要有重复性；若代码路径高度数据相关，confidence 会快速下降。
- BTB dependency：NTB predictor 只给 branch 位置，仍依赖 BTB 提供 target instruction；BTB miss 会削弱收益。
- Recovery cost：如果 NTB 直接跳过多个 branches，一次错误可能覆盖更长窗口，需要清晰的 misprediction recovery。
- Update buffer complexity：需要在 OOO branch completion 下重建 program order，并维护 update groups，增加 front-end/back-end 之间的训练状态。
与常规 predictor 的关系
该设计更像是 conventional branch predictor/BTB 之前或旁路的一层 higher-level predictor。它预测“下一个会 taken 的 branch 在哪里”，而 BTB 和原有方向预测机制仍可处理 target、fallback、unconditional branch、long offset、low confidence 等情形。合理实现应当把 NTB predictor 作为 front-end acceleration structure，而不是完全替代 BTB。
一句话总结
US20230100693A1 的核心是把 branch prediction 从逐个 branch direction prediction 转化为基于 path history 的 next taken branch offset prediction，并用 BTB/path history feedback 与 update buffer training 形成可训练的 front-end 控制流预测机制。