HCoMB(Intel US20220129763A1)[2022]: High confidence multiple branch offset predictor

Title	Patent Number	Inc.	Year	url
High confidence multiple branch offset predictor	US20220129763A1	Intel Corp	2022	https://patents.google.com/patent/US20220129763A1/en

该专利提出 high confidence multiple branch offset predictor (HCoMB)，用当前 PC/last taken branch target 与 Branch History/Stew 查找 multiple-taken-branch (MTB) prediction table，一次给出后续 N 个 predicted taken branches 及其 target。

TLDR：

1. 与 conventional BPU 每遇到第一个 taken branch 就 re-steer 不同，HCoMB 在 hit 且 confidence 足够高时可直接跳到最后一个 predicted taken branch 的 target，使 BPU re-steering 频率从每个 taken branch 降到每 N 个 taken branches。
2. HCoMB 只关注 taken branches，并把 not-taken branches 隐式视为顺序控制流，因此单次 prediction 可跨越比 fixed-size trace predictor 更大的代码区域。
3. 训练方式依赖 main BPU：miss 时把 main BPU 输出写入 pre-allocate buffer，命中但低 confidence 时 snoop main BPU 并校验一致性；一致则增加 confidence/utility，不一致则 reset，真正预测错误时 pipeline flush 并 invalidate entry。
4. 关键低成本点是 HCoMB entry 不直接存完整 branch prediction，而是存向 BTB entry 的 Set-Way pointers；实际 branch PC/target 仍由 BTB 读出。

背景和动机

该专利的直接背景是 superscalar / deep Out-of-Order (OOO) core 对 Front-End sustained instruction bandwidth 的需求持续上升。描述中指出，Modern superscalar processors 通过扩大 OOO instruction window 提取更多 ILP，但 Front-End 必须持续供给足够指令流，否则后端宽度无法发挥。

conventional BPU 的限制在于：它使用 Program Counter (PC) 与 Branch History/Stew 对一个 cache line 内各 branch 做预测，然后选择第一个 taken branch；第一个 taken branch 之后的 fetched bytes 被丢弃，下一周期从该 branch target 重新开始 BPU operation。结果是每个 taken branch 都造成一次 BPU re-steering、未使用 fetch bytes 被丢弃，并带来 cycle change，从而限制 Front-End bandwidth。

专利希望解决的问题不是单个 conditional branch 的 taken/not-taken 准确率，而是 taken branch 密集区域中 control-flow advance 粒度过小的问题：如果一次只能跨过一个 taken branch，Front-End 带宽会被 branch-to-branch distance 和重定向频率限制。

相关工作/技术：

Title	Authors, From	url
Path-based Next Trace prediction (PNT)	description 中提到的 trace predictor 技术	-
Decoded Stream Buffer Simple-stream (DSS)	description 中提到的 DSB-based stream 技术	-
A case for (partially) TAgged GEometric history length branch prediction	André Seznec and Pierre Michaud, JILP 2006，HTML metadata citation	-

PNT 的问题是 trace size 或 branch count 有限制，并且把 taken/not-taken branch 都计入 trace 切分；HCoMB 只尊重 taken branches，因此 not-taken 密集区域不会把 trace 切碎。DSS 的问题是依赖 DSB inclusivity 与 branch stability，只适合 always-taken/always-not-taken 等极稳定区域；HCoMB 以 prediction stability 为依据，并把 branch history/Stew 纳入 lookup，可区分同一 branch 在不同 history 下的实例。

---

Insight

Insight: Front-End bandwidth bottleneck 来自 taken-branch re-steering 粒度

conventional BPU 的工作粒度是“找到 cache line 中第一个 taken branch，然后跳转”。这保证了局部正确性，但在 taken branch 密集的程序区域会频繁 re-steer，导致每次预测只推进一个控制流转折点。HCoMB 的核心 insight 是：如果某段控制流在历史上下文下可高置信地预测出多个连续 taken branch，就可以把 BPU 的推进粒度从 1 个 taken branch 扩大到 N 个 taken branches。

Insight: 只预测 taken branch offsets，可以天然跨过 not-taken 区域

not-taken branch 不改变 natural control flow，因此 HCoMB 不需要显式为它们产生 trace cut。它输出的是后续 N 个 predicted taken branches 的相对位置/BTB pointers，而不是 fixed-length instruction trace。这使单次 HCoMB prediction 覆盖的动态代码长度可变：如果 taken branches 间隔很远，单次 prediction 就能跨越很长代码区域。

Insight: prediction stability 比 branch stability 覆盖面更宽

DSS 依赖 branch 本身几乎总是稳定，而 HCoMB 依赖在给定 PC + Branch History/Stew 下预测是否稳定。即使某个 branch 行为随时间变化，只要它与 history 相关且可预测，HCoMB 仍能分别学习不同 history instance，从而覆盖 DSS 无法处理的 flaky branch pattern。

Insight: HCoMB 作为 control unit，而不是复制完整 predictor state

专利强调 HCoMB entry 不保存实际 prediction payload，而只保存 BTB Set-Way pointers；在 high-confidence hit 时，HCoMB 取消 main BPU 的正常路径，驱动 BTB 读出 branch PCs/targets。这样 HCoMB 更像一个 trace-level control unit，复用已有 BTB 存储实际目标，降低面积和 adoption cost。

---

核心设计

HCoMB 位于 processor Front-End，与 main BPU/MBP 并行工作。它用 last taken branch target/current PC 和 Branch History/Stew 访问 MTB/HCoMB table；若 table hit 且 confidence 超过 threshold，则读取记录的 BTB Set-Way pointers，得到 N 个 taken branch 的 PC/target，并把 BPU redirect 到最后一个 predicted taken branch 的 target。若 miss 或低 confidence，则使用 main BPU 输出继续训练。

flowchart LR
  PC["Lookup PC / last taken branch target"] --> HASH["Index + Tag hash"]
  HST["Branch History / Stew"] --> HASH
  HASH --> TBL["HCoMB / MTB table"]
  MBP["Main BPU / MBP"] --> BUF["Pre-allocate buffer"]
  TBL -->|miss or low confidence| BUF
  BUF --> TRAIN["Training: write trace, update confidence/utility"]
  TRAIN --> TBL
  TBL -->|hit + high confidence| PTR["BTB Set-Way pointers"]
  PTR --> BTB["BTB"]
  BTB --> PRED["N taken branch PCs + targets"]
  PRED --> REDIR["Redirect BPU to last predicted taken target"]
  PRED --> HISTUPD["Update taken branch history"]

此处生成一张总体架构图，要求包括 HCoMB、训练、预测的控制路径以及 HCoMB entry 以及训练和读出的控制/数据路径

设计点: Multiple-taken-branch trace abstraction

针对的问题：conventional BPU 只使用 PC + Stew 在当前 cache line 内找第一个 taken branch，之后丢弃 branch 后的 fetched bytes 并在下一周期重启预测。每个 taken branch 触发一次 re-steering，限制 Front-End bandwidth。

解决思路：HCoMB 把连续控制流中即将 taken 的 branch 组成 trace，trace 的长度由 taken branch 数 N 决定，而不是由 instruction count 或所有 branch count 决定。description 的例子使用 N=4，即一个 trace 包含 4 个 taken branches。

设计：

1. HCoMB snoop main branch predictor 输出的 fetched instruction stream。
2. 它把 observed taken branches 记录到 N-entry buffer。
3. buffer 满后，将该信息作为一个 Trace 写入 HCoMB table entry。
4. allocation/training 时，entry 使用 Trace entry PC（trace 中 first valid instruction）与 branch history 的 hash 来识别。
5. prediction lookup 时，使用 last taken branch target/current PC 与 Branch History/Stew 生成 index/tag，定位 set/way。

设计点: High-confidence gating 与 main BPU override

针对的问题：一次输出多个 taken branch 的错误代价高于普通单 branch prediction；若错误，会导致 pipeline flush 和较长路径回滚。因此 HCoMB 不能在低置信状态下随意覆盖 main BPU。

解决思路：HCoMB 与 main BPU 并行 lookup，但只有在 HCoMB hit 且 entry confidence 超过 threshold 或 saturate 时才真正接管预测。否则退回 main BPU 并继续训练。

设计：

1. Fetch cacheline 后，main BPU lookup 与 HCoMB lookup 同步发生。
2. 如果 HCoMB miss，启用 training，main BPU 正常提供 prediction。
3. 如果 HCoMB hit 但 confidence 不足，继续 training，不 override。
4. 如果 HCoMB hit 且 high confidence，取消 main BPU lookup / normal BTB lookup path。
5. HCoMB 读取 entry 中的 BTB Set-Way pointers，由 BTB 提供 branch PCs/targets。
6. HCoMB prediction 被送往 Icache/decoders，并把 BPU redirect 到最后一个 predicted taken branch 的 target。

设计点: Training、confidence 和 utility 管理

针对的问题：HCoMB 需要学习 main BPU 已经能够产生的稳定多 taken-branch sequence，同时过滤不稳定或错误 trace，避免污染 table。

解决思路：HCoMB 使用 main BPU 作为训练 teacher。miss 时用 pre-allocate buffer 收集 trace；低 confidence hit 时将 HCoMB entry 与 main BPU 输出逐项比较；正确则加强，错误则清零。

设计：

1. Miss during lookup：HCoMB 把 main branch predictor 输出记录到 pre-allocate buffer。
2. pre-allocate buffer 满后，将 trace 写入 HCoMB table 的 empty entry。
3. 若对应 set 没有 empty entry，则递减该 set 中 entries 的 utility；当某 entry utility 变为 0 时替换。
4. Low-confidence valid entry：HCoMB snoop main BPU predictions，并与 table entry 中记录的信息匹配。
5. 匹配则 increment confidence count 和 utility count。
6. 不匹配则将整个 entry 的 confidence 与 utility reset to zero。
7. 当 confidence 超过 threshold 或 saturate 后，entry 可执行实际 HCoMB prediction。
8. 实际 prediction 还会与 branch execution 输出比较；若预测错误，发生 pipeline flush，并 invalidate HCoMB table entry。

设计点: BTB pointer based low-storage entry

针对的问题：如果 HCoMB 为 N 个 taken branches 直接存 full branch PC/target，存储成本会迅速增大，也容易与已有 BTB 信息重复。

解决思路：HCoMB entry 只记录指向 BTB entries 的 Set-Way pointers，实际 branch PC/target 仍由 BTB 读出。

设计：

1. stage N：HCoMB 与 Main Branch Predictor 并行 lookup；N-1 stage 提供 lookup PC 和 last available branch history。
2. high-confidence hit 时，HCoMB 在 stage N 读取 entry content。
3. entry content 是 BTB Set-Way pointers，而不是完整 prediction。
4. pointers 在 N+1 stage 送入 BTB，BTB 读出所有 prediction information，包括 branch PCs 与 targets。
5. 后续 pipeline stages 根据 HCoMB predictions 发起 BPU redirection，并像标准 BPU 一样更新 taken branch history。

该设计使 HCoMB 更像一个 branch trace selector/control unit，专利认为这显著减少 storage cost，也更容易并入现有 processor designs。

设计点: 与 Front-End/BPU 的集成位置

FIG. 1A 将 HCoMB 表述为 integrated circuit 10 中与 front end unit 11 耦合的 circuitry 13。FIG. 1B 更具体地把 HCoMB offset predictor 24 放入 electronic apparatus 20 的 front end unit 21，与 BPU 23 communicatively coupled。后续通用 core architecture 段落说明该技术可集成到 processor core 990 的 front end unit 930，尤其是与 branch prediction unit 932 关联。

这意味着 HCoMB 并不是替代整个 Front-End，而是作为 BPU complex 中的并行辅助 predictor/control path：默认由 main BPU 保持覆盖和训练，只有 high-confidence trace 才走 HCoMB 快路径。

---

价值与适用场景

该设计适合 branch fraction 较高、branch-to-branch distance 较小、且多 taken-branch sequence 在给定 history 下具备稳定预测性的 workload。description 声称 HCoMB 可在预测约 30% dynamic branches 的情况下带来 IPC improvement，并且 larger tables 可进一步提升性能。

HCoMB 相比 PNT 的价值在于不被 fixed trace size 或 not-taken branch 数量限制；相比 DSS 的价值在于不依赖 DSB inclusivity，也不要求 branch 本身 always stable。它将高置信 trace prediction 的收益集中用于减少 Front-End re-steering，而不是试图替代 main BPU 的基础覆盖能力。

实现关注点

1. HCoMB 的收益依赖 high-confidence hit rate；若 workload 难以形成可重复 taken-branch trace，HCoMB 只能退化为旁路训练结构。
2. Entry aliasing 是潜在问题：index/tag 由 last taken branch target/current PC 与 Branch History/Stew 生成，history 长度、hash 设计和 table associativity 会影响误命中与覆盖率。
3. BTB Set-Way pointers 降低 storage，但要求 BTB entry 生命周期与 HCoMB entry 保持一致；BTB replacement、way movement 或 target update 需要与 HCoMB invalidation/repair 协同。
4. 预测错误代价较高，因为一次 HCoMB prediction 跨越多个 taken branches；专利用 confidence threshold、mismatch reset 和 execution-time invalidation 控制风险。
5. 与 main BPU 的并行 timing 需要谨慎：HCoMB high-confidence hit 需要及时 cancel MBP/normal BTB path，并在 N+1 stage 完成 BTB read-out，否则可能抵消带宽收益。