MOP(Intel US20230195469A1)[2023]: Device, method, and system to facilitate improved bandwidth of a branch prediction unit

Title	Patent Number	Inc.	Year	url
Device, method, and system to facilitate improved bandwidth of a branch prediction unit	US20230195469A1	Intel Corp	2023	https://patents.google.com/patent/US20230195469A1/en

该专利提出 multi-offset predictor (MOP)：基于当前 PC 与 branch history/Stew，在一个 branch prediction cycle 内直接给出后续 N 个预测为 taken 的 branch 及其 target，而不是像传统 BPU 一样每遇到一个 taken branch 就重新 redirect。

TLDR：

1. MOP 的核心性能收益来自把前端 redirect 粒度从“每个 taken branch”放大到“每 N 个 taken branch”：执行流可以直接跳到第 N 个 taken branch 的 target，从而提升 Front-End 向宽/深 OOO 核提供指令流的持续带宽。
2. 与 HCoMB 只在整个 trace 都 high confidence 时才启用不同，MOP 即使部分预测 low confidence 也照常向 execution pipeline 提供多个预测；low-confidence 预测被送到另一套更可靠的 prediction unit 后台复核。
3. 复核路径通过 verification queue (VQ) 与前端供给路径解耦：low-confidence prediction 可以排队验证；当队列为空时可 bypass，队列占用过高时可 stall 或降低 execution pipeline 的 operational rate。

背景和动机

现代 superscalar processor 通过更宽、更深的 out-of-order (OOO) window 暴露更多 instruction level parallelism (ILP)。这要求 Front-End (FE) 持续提供高指令带宽，否则后端窗口再大也会被取指、预测、redirect 的节奏限制。

传统 Branch Prediction Unit (BPU) 的一个典型行为是：给定当前 Program Counter (PC) 和 Branch History/Stew，在一个 cache line 中预测多个 branch，然后选择第一个 taken branch；该 taken branch 之后的 fetched bytes 被丢弃，下一周期从该 taken branch 的 target 重新开始。直接问题是，每个 taken branch 都触发一次 BPU re-steering，造成周期切换和 fetch bandwidth 浪费。

该专利的动机是提高 BPU/FE 对 taken branch 密集代码的持续供给能力。其基本方向不是把单个 branch prediction 做得更复杂，而是让预测器一次产生一段控制流：只关注改变 natural control flow 的 taken branch，把若干 not-taken branch 隐式跨过去，减少 redirect 次数。

HTML 中出现的相关工作和对比对象如下：

Title	Authors, From	url
Confidence Estimation for Branch Prediction Reversal	Juan L. Aragón, José González, José M. García, Antonio González, Springer-Verlag, 2001	http://scholar.google.com/scholar?q=%22Confidence+Estimation+for+Branch+Prediction+Reversal%22
High confidence multiple branch offset predictor	Intel Corporation, US20220129763A1	https://patents.google.com/patent/US20220129763A1/en
Prophet/critic hybrid predictor	Jared W. Stark, US20060036837A1	https://patents.google.com/patent/US20060036837A1/en
Branch prediction in a data processing apparatus	Arm Limited, US20170139717A1	https://patents.google.com/patent/US20170139717A1/en
Predicting upcoming control flow	Arm Limited, US20230195468A1	https://patents.google.com/patent/US20230195468A1/en

专利正文重点比较了三类已有方向：

• Path-based Next Trace prediction (PNT)：按 trace 预测，但 trace size 或 branch 数量受限；遇到连续 not-taken branch 时仍可能把区域切成多个 trace，不能充分放大 taken-branch 间距。
• Decoded stream buffer (DSB) simple-stream (DSS)：记录稳定 code region 的 DSB pointers，可跨多个 taken branch 供给 micro-op stream，但依赖 DSB inclusivity 和 branch stability；若 uops 不在 DSB 或 branch 行为不稳定，则覆盖率受限。
• High confidence multiple branch offset (HCoMB)：每周期也可预测多个 taken branch，但通常只有当 trace 内所有预测 high confidence 时才启用；任一预测 low confidence 会回退到 main BPU，导致 coverage 低。

---

Insight

该专利的关键 Insight 是：前端带宽瓶颈不只来自单个 branch 的预测准确率，也来自 taken branch 的 redirect 频率。若能把预测对象从“当前 cache line 中第一个 taken branch”提升为“未来 N 个 taken branch 构成的控制流片段”，则即使单个预测器本身并不比 main predictor 更精确，也可以显著降低 FE re-steering 次数。

Insight1: 用 taken-branch trace 放大 BPU 带宽

MOP 不试图完整预测每条 branch 的 taken/not-taken，而是直接产生后续 N 个 taken branch 的相对位置和 target。由于 not-taken branch 不改变程序自然顺序流，MOP 等价于把一段可能很长的 control flow 压缩成 “taken branch offsets + targets”。

这带来两个微架构收益：

• 对传统 BPU：从每个 taken branch redirect 一次，变成每 N 个 taken branch redirect 一次，理想情况下 BPU bandwidth 提升约 N 倍。
• 对 PNT/DSS 类 trace 技术：MOP 的 trace 长度由 taken branch 的数量界定，而不是由 instruction count 或所有 branch count 界定，因此能跨过大量 not-taken branch，覆盖更长代码区域。

Insight2: 覆盖率优先，可靠性由后台校验补足

HCoMB 的保守策略是“只有 trace 中全部预测 high confidence 才使用”，这保护了准确性，但牺牲 coverage。MOP 的策略相反：只要 trace table 命中，就可以向 execution pipeline 输出 N 个预测；confidence 不决定是否输出 trace，而决定是否把某个预测送去复核。

这样 MOP 把性能路径和纠错路径拆开：

• 性能路径：MOP 直接给 execution pipeline 多个 branch predictions，使 FE 继续向前推进。
• 纠错路径：low-confidence prediction 送到另一个更复杂或更可靠的 prediction unit，用同一 branch instruction 产生 second branch prediction。
• 恢复路径：若 MOP prediction 与 second branch prediction 不一致，则 prediction unit 发出 clear/flush 信号，清除 execution pipeline 的部分或全部 state。

Insight3: VQ 让复核路径不反向限制 FE 带宽

如果每个 low-confidence prediction 都同步等待 main predictor 复核，MOP 的带宽收益会被复核延迟抵消。因此专利引入 verification queue (VQ)：需要验证的 prediction 可以入队，prediction unit 后台逐个处理。

VQ 的作用不仅是提高预测准确率本身，而是控制验证吞吐与前端推进之间的耦合强度：

• VQ 空时，prediction 可通过 bypass path 直接送到 prediction unit，降低额外排队延迟。
• VQ 非空时，prediction 入队等待复核，避免阻塞 MOP 向 execution pipeline 供给预测。
• VQ 占用超过 threshold 或 full 时，buffer manager/monitor selector 触发 backpressure，stall 或降低 execution pipeline 的 operational rate，防止验证 backlog 失控。

Insight4: confidence metric 是调度复核资源的信号，而不是 trace 使用门槛

每个 trace table entry 中不只保存 offsets、branch types 和 targets，还保存每个 branch prediction 的 confidence metric。这些 metric 在预测成功时增加，在预测失败或校验失败时降低或 reset。

该设计的重点是将 confidence metric 用作“是否需要额外复核”的资源调度信号，而不是“是否允许 MOP 输出”的硬门槛。这是 MOP 相对 HCoMB 覆盖率更高的原因。

---

核心设计

该专利的核心设计可以概括为以下数据流：

1. MOP 基于当前 PC 与 branch history/Stew 在一个周期内检测 N 个 successive taken-branch predictions。
2. controller 查询 trace table/MTB table，命中时向 execution pipeline 指示这些 predictions，并读取每个 prediction 的 confidence metric。
3. low-confidence prediction 被选择性发送给更可靠的 prediction unit；该 unit 对同一 branch instruction 独立生成 second prediction 并比较一致性。
4. 若复核不一致，则发出 front-end clear 或 clear execution pipeline state 信号；若一致或 high confidence，则 pipeline 继续执行。
5. VQ 缓冲待复核 predictions，并在队列压力过高时对 execution pipeline 施加 stall 或降速。

flowchart LR
    PC[Current PC + Stew] --> MOP[MOP / first prediction circuitry]
    MOP -->|N taken-branch predictions in one cycle| CTRL[Controller]
    CTRL --> TT[Trace table / MTB table<br/>tag, utility, confidence, offsets,<br/>branch types, targets]
    TT --> CTRL
    CTRL -->|N predictions / next target indications| EXE[Execution pipeline]
    CTRL -->|low-confidence prediction| SEL[Selector / mux]
    LP[Line predictor] --> SEL
    SEL --> VQ[VQ / verification queue]
    VQ --> PRED[Second prediction unit]
    SEL -->|empty-queue bypass| PRED
    PRED -->|mismatch| CLR[Clear / flush pipeline state]
    EXE -->|outcome| CTRL
    PRED -->|validation result| CTRL
    CTRL -->|update| TT

设计点 1: MOP 单周期产生多个 taken-branch predictions

针对的问题: 传统 BPU 在每个 taken branch 后重新 redirect，discard 该 taken branch 之后的 fetched bytes，FE 带宽受限。

解决的思路: 把预测粒度从单个 taken branch 扩展为 N 个 successive taken branches。MOP 直接生成未来 N 个 taken branches 的 pointers、PC/offset 和 target，使下一周期可跳转到第 N 个 taken branch 的 target。

设计：

• 输入使用当前 PC 与 branch history/Stew，tag 可基于 last taken branch 与 branch history 生成。
• MOP 访问 multiple-taken-branch (MTB) prediction table 或 trace table，找到与当前控制流状态对应的 entry。
• 每个 entry 代表一个 trace，trace 中包含 N 个 taken-branch predictions；这些 predictions 具有程序执行顺序，其中后面的 prediction 可依赖前面的 prediction。
• 对 execution pipeline 输出的不一定只是 branch taken/not-taken，也可以是每个 predicted branch 后的 expected next instruction，尤其包括第 N 个 branch 后的 target。

该设计的性能本质是把 not-taken branch 隐式视为 fall-through，不让它们消耗 redirect 带宽；MOP 只把真正改变控制流的 taken branch 编码到 trace 中。

设计点 2: trace table entry 的字段组织

针对的问题: 若要一拍输出多个 taken branches，预测器必须同时携带 lookup、定位、目标和可信度信息；否则仍需串行解析 branch。

解决的思路: 使用 set-associative trace table 或类似 registry，将一个控制流 trace 的元数据集中放在一个 entry 中。

设计：

• tag field：用于 trace lookup，可由 branch PC、target PC、branch history 等 hash 得到。
• utility field：记录该 entry 被命中的次数或 usefulness，用于替换/管理策略。
• confidence metrics：每个 prediction 一个 metric，如 Conf1...ConfN，用于判断 high/low confidence。
• offset fields：记录对应 branch 在 instruction cache line 或 fetch block 中的相对位置。
• branch type fields：记录 branch type，帮助后续处理 conditional/direct/indirect 等控制流。
• target fields：记录每个 predicted taken branch 的 target。

训练路径中，MOP snoop instruction stream，将 taken branches 收集到 N-entry buffer；当 buffer 满时，把这 N 个 taken branches 作为一个 trace 注册到 trace table，并初始化 confidence metrics。

设计点 3: confidence-based selective validation

针对的问题: MOP 若为了 coverage 在 low confidence 时也输出多分支 trace，会增加错误预测导致 pipeline flush 的风险；若只在全部 high confidence 时启用，又退化成 HCoMB 的低覆盖率。

解决的思路: confidence metric 不阻止 MOP 输出 trace，而是决定是否让某个 prediction 接受第二预测器校验。

设计：

• controller 对每个 prediction 的 confidence metric 与 threshold 比较，threshold 可由制造商、管理员、test unit 或其他配置提供。
• high-confidence prediction 直接被认为足以供 execution pipeline 推进。
• low-confidence prediction 经 signal 发送到第二 prediction unit。
• 第二 prediction unit 使用不同预测依据、更复杂算法或更大的 BTB 等资源，对同一 branch instruction 生成 second branch prediction。
• 若 MOP prediction 与 second prediction 一致，则该 low-confidence prediction 通过 validity test；若不一致，则 second prediction unit 发出 clear signal，清除 execution pipeline state。

该结构把 fast predictor 与 accurate predictor 组合成类似 producer/checker 的关系：MOP 负责带宽，第二 predictor 负责对风险项抽查。

设计点 4: confidence metric 的在线更新

针对的问题: 固定 confidence 无法适应 branch 行为变化；某些 branch 随 history 改变时可能在不同上下文下表现不同。

解决的思路: 每次检测到 prediction 的 outcome 后更新对应 confidence metric。

设计：

• prediction successful 时，增加 confidence metric，例如 saturating increment，直到最大值。
• prediction unsuccessful 或 validity test 失败时，降低、decrement 或 reset 到 baseline。
• metric 与 trace entry 内的具体 branch prediction 对应，而不是只给整个 trace 一个统一 confidence。

这种粒度允许 MOP trace 中 high-confidence 和 low-confidence predictions 混合存在：trace 仍可整体输出，但只有风险较高的 branch 被送去复核。

设计点 5: VQ 与 backpressure

针对的问题: 第二 prediction unit 可能更复杂、延迟更高或吞吐不足；若 low-confidence predictions 同步等待复核，会重新拉低 FE bandwidth。

解决的思路: 用 verification queue (VQ) 缓冲待验证 predictions，并由 monitor/selector 控制 bypass、enqueue 和 backpressure。

设计：

• low-confidence prediction 或 line prediction 先进入 selector/mux。
• 若 VQ 为空，prediction 可通过 bypass path 直接送到 second prediction unit，减少验证延迟。
• 若 VQ 非空，prediction 入队，随后由 VQ dequeue 给 second prediction unit。
• monitor/selector 监测 VQ occupancy；当 occupancy 超过 threshold 或 full 时，发送控制信号降低 execution pipeline operational rate。
• backpressure 可以是完全 stall，也可以是降低到较低但仍为正的执行速率；当 VQ 低于 threshold 后可恢复更高速率。

从 claims 和 method 640 的表述看，空队列 bypass、非空 enqueue 是主要权利要求覆盖的机制。description 段落中对 signal 562/564 的文字方向存在轻微不一致，但不影响整体设计意图。

设计点 6: line predictor 与 selector 的 fallback

针对的问题: trace table 可能 miss，MOP 不能保证每个控制流位置都有注册 trace。

解决的思路: 保留 line predictor 作为 fallback，并用 selector/mux 在 MOP trace 与 line prediction 之间选择。

设计：

• controller 对 trace table 查表命中时，mux 选择 MOP 的 N branch predictions 输出到 execution pipeline，并把 low-confidence prediction 输出到校验路径。
• trace table miss 时，line predictor 的 prediction 通过 mux 输出给 execution pipeline 和 prediction unit。
• selector circuitry 是权利要求中的独立补充点：controller 可选择 N predictions 之一的 indication，而不是其他 predictor 的 prediction indication。

该 fallback 让 MOP 不需要覆盖所有路径，miss 时系统仍能以 conventional line prediction 工作。

实现启示

该专利适合在宽取指、宽 decode、深 OOO window 的高性能 core 中考虑，因为这些设计对 FE bubble 和 taken-branch redirect 频率更敏感。若实现类似机制，需要重点权衡：

• trace table 容量、associativity、tag hash 与 replacement policy 会决定 MOP coverage。
• N 越大，理想 bandwidth 越高，但 trace entry 更大，target/offset/confidence 存储更多，错误恢复代价也可能更高。
• second prediction unit 的验证吞吐必须与 low-confidence prediction 产生率匹配，否则 VQ 会频繁 backpressure，抵消 MOP 收益。
• confidence threshold 太高会增加验证流量，太低会放过更多错误预测；它实际控制的是性能与恢复风险之间的平衡。
• 对间接分支、call/return、跨 cache line branch、self-modifying code 或 instruction cache miss 场景，专利文本没有给出完整细节，工程实现需要额外定义训练和恢复边界。