这篇论文提出的是 1996 ASPLOS（Multiple-Block Ahead Branch Predictors）：

TLDR：

  1. 论文认为宽发射 out-of-order 处理器的前端瓶颈是 single I-fetch 每周期最多取一个基本块，难以喂饱 6-wide/8-wide 后端。
  2. 核心机制是 Two-Block Ahead Branch Predictor：用当前基本块末尾分支 Aa 及其历史 Ha，不预测下一块 Bi，而是预测下下块 Ci。
  3. 该机制由 two-block ahead Prediction Table、two-block ahead BTB、Return Address Stack、Second Address Stack 组成，可在 double I-fetch 中每周期预测两个非连续基本块，也可在 single I-fetch 中把取指地址生成流水化。
  4. 实验显示：CINT92 中 double I-fetch 对 6-wide/8-wide 处理器收益显著；two-block ahead 的 g-share/g-select 方向预测错误率与 conventional one-block ahead 基本相同；two-block ahead BTB 的命中率略低但差距通常小于 0.5%。

背景和动机

论文从一个基本约束出发：处理器不能以超过取指速度的速度执行程序。对于 1990 年代中期的高性能处理器，论文把设计路线分为两类：

  • Brainiac processors：追求高 IPC 和宽并行执行。问题是当前商业微处理器通常每周期只取同一个基本块内的指令，甚至不能跨 cache line；而整数程序平均基本块较短，单块取指会限制宽后端。
  • Speed-demon processors：追求高频率。问题是 BTB/PT/RAS 访问、fall-through 地址生成、方向选择、历史更新等都在取指地址生成路径上，branch predictor 容易成为电路关键路径；若拆成多周期，传统做法可能在 predicted taken branch 上插 bubble。

因此，论文试图同时解决两个问题：

  • 对宽发射处理器：如何在一个周期内预测并取多个非连续基本块
  • 对高频处理器：如何把 branch prediction / instruction address generation 流水化，而不在正确预测的 taken branch 上引入额外 bubble。

相关工作：

Title Authors, From url
Increasing the Instruction Fetch Rate via Multiple Branch Prediction and a Branch Address Cache Yeh, Marr, Patt, ICS 1993 论文参考文献 [19]
Control Flow Prediction with Tree-Like Subgraphs for Superscalar Processors Dutta, Franklin, MICRO 1995 论文参考文献 [4]
Optimization of Instruction Fetch Mechanisms for High Issue Rates Conte, Menezes, Mills, Patel, ISCA 1995 论文参考文献 [3]
Combining Branch Predictors McFarling, DEC-WRL TN-36, 1993 论文参考文献 [12]

Insight: 预测信息可以与前一个分支绑定

传统 one-block ahead predictor 用当前块中的分支 Bb 和历史 Hb 预测下一块 Ci。论文的关键观察是：可以把预测 Ci 所需的信息存到前一个控制流转换 Aa -> Bi 对应的位置上，也就是用 (Aa, Ha) 预测 Ci。

这个重映射带来两个直接收益：

  • 在 double I-fetch 处理器中，当前周期已有 Ai 和 Bi 两个取指地址，因此可以同时用 Aa 预测 Ci、用 Bb 预测 Di，形成每周期两个基本块的地址生成。
  • 在 single I-fetch 处理器中，当前周期可以先用 Ai 发起对 two-block ahead PT/BTB 的访问，下一周期再完成 tag check 和地址选择，从而把 instruction address generation 拆成两级流水。

论文的重要实验结论是：这种“用前一个分支的地址和历史预测后一个分支结果”的重映射并没有显著损害方向预测准确率。对于 g-share 和 g-select，在多个 PT 大小下，two-block ahead 与 one-block ahead 的错误率非常接近；64K-entry PT 上各 benchmark 差异不超过 0.30%。

核心设计

Two-Block Ahead Branch Predictor 的核心设计可以概括为：

  1. 用当前块末尾分支和历史预测下下个基本块，而不是下一个基本块。
  2. 将 BTB entry 关联到前驱分支地址和前驱转移类型，而不是被预测分支本身。
  3. 用 SAS 处理 procedure return 之后的下一块预测。
  4. 在 double I-fetch 中并行产生两个未来取指地址；在 single I-fetch 中把预测访问和地址选择流水化。

Two-block ahead predictor double I-fetch overview

设计点: Two-Block Ahead Prediction Table

针对的问题：传统 PT 用 (Bb, Hb) 预测分支 Bb 的方向，从而决定 Ci。若要在同周期预测 Ci 和 Di，Bb 的信息可能要等 Bi 取出/解码后才知道，形成依赖。

解决的思路：把方向预测也前移一个基本块。用前一个基本块末尾分支 Aa 的地址和历史 Ha 来预测 Bb 的结果，即预测从 Bi 到 Ci 的控制流。

Two-block ahead prediction table

设计：

  • Pa = PT(Aa, Ha) 表示用前一个分支的上下文预测 Bb 的方向。
  • Pb = PT(Bb, Hb) 表示用当前第二个块的分支上下文预测 Cc 的方向。
  • PT 的索引可以采用已有分支预测方式，例如：
    • g-select：branch history bits 与 branch address bits 拼接。
    • g-share：branch address 与 branch history register 做 XOR。

这个设计的价值在于保持方向预测算法的可替换性。论文没有提出新的方向预测学习规则，而是证明 two-block ahead 的信息绑定方式不会明显破坏已有 predictor 的准确率。

设计点: Two-Block Ahead BTB

针对的问题：传统 BTB entry 通常按当前分支或当前块地址索引，返回下一块 target。Two-block ahead 需要通过 Aa -> Bi 的上下文，找到 Bi 中分支 Bb 的信息并计算 Ci。

解决的思路：BTB entry 不再绑定到被预测分支 Bb 本身，而是绑定到：

  • 前一个基本块末尾分支地址 Aa
  • 从 Aa 到 Bi 的转移类型

Two-block ahead branch target buffer

设计：

  • entry 记录 Bi 中分支 Bb 的信息：target Ci、branch type、branch position b
  • 转移类型包括：
    • T：Aa 是 non-return taken branch；
    • N：Aa 是 not-taken conditional branch 或非分支；
    • R：Aa 是 call，对应 return 相关特殊处理。
  • 若 AaX 命中 BTB，则可根据 entry 中的 Bb 类型、Pa 方向预测、RAS/SAS 栈顶或 fall-through 地址计算 Ci
  • 若 miss，则假设 Bi 中没有分支，下一块为 B + 1。

存储代价：

  • 单个 entry 比传统 BTB 多记录少量信息，例如 branch position b 和前驱转移类型。
  • 同一个 Aa 可能有 AaT 与 AaN 两类 entry，且若一个分支有多个 predecessor 可能产生冗余。
  • 论文实验显示，在现实 BTB 大小下，这种冗余没有导致明显更高的容量需求。

设计点: Return Address Stack 与 Second Address Stack

针对的问题：procedure return 的目标地址依赖调用点，同一个 return instruction 可能返回多个不同地址。传统 RAS 可以预测 return target Ci，但 two-block ahead 还需要预测 return target 所在块之后的下一块 Di。

解决的思路：Di 更依赖 return target Ci，而 Ci 与 call 指令 Pp = Ci - 1 强相关。因此论文把 return target 后继块的信息关联到 call 指令，并引入 Second Address Stack (SAS)。

Return address stack and second address stack

设计：

  • 当 call Pp 被 fetch 时，BTB 查找特殊 entry PpR。
  • 若 PpR 命中，将其副本 push 到 SAS；否则 push invalid entry。
  • 当 return 被 fetch 并从 RAS pop 返回地址时，同时从 SAS pop 一项，用来预测 return target block 之后的分支/目标。
  • RAS 与 SAS push/pop 次数保持一致。

这个设计避免了用 return instruction 自身预测其返回目标之后的控制流，因为该信息对同一个 return 来说不稳定。

设计点: I-cache/BTB/PT 的 double I-fetch 组织

针对的问题：double I-fetch 需要同周期读取两个可能不连续的基本块 A 和 B，并产生后续 C 和 D 的地址。单端口 I-cache 或单端口预测结构会形成结构冲突。

解决的思路：I-cache 需要 fully double-ported 或 interleaved；BTB 和 PT 也应采用相同方式支持两个读

设计：

  • 当前周期并行 fetch Ai 与 Bi。
  • 使用 A、B 两个 block address 并行索引 I-cache、PT、BTB。
  • 若 I-cache interleaved，则 PT/BTB 可以按相同方式 interleave；当两个块在 I-cache 冲突时，它们在预测结构中也冲突，避免额外性能损失。
  • RAS/SAS 在若干场景下也需要每周期提供两个地址，例如 Bb -> Ci 和 Cc -> Di 都涉及 return，或两个转换都涉及 call。

论文还提出一个轻量优化：当 Bb 是 cache block 中最后一个分支且预测 not-taken 时，若 BTB entry 中记录了 L bit，前端可直接把下一块预测为 (B+1)0..0，而不是先取 Bb+1，从而节省一次无用 fetch。

设计点: single I-fetch 中的预测流水化

针对的问题：在高频 single I-fetch 处理器中，BTB/PT/RAS 访问、fall-through 地址计算、预测结果选择、栈和历史更新都挤在取指地址生成路径上，可能成为 critical path。若传统 one-block ahead predictor 直接拆成多周期，taken branch 容易产生 bubble。

解决的思路：用 two-block ahead predictor 把“访问预测结构”和“选择下一取指地址”拆成两级。

设计：

  • cycle t：IF1 用 A 和 Ha 访问 two-block ahead PT/BTB，同时 I-cache 开始取 A。
  • cycle t+1：IF1 开始用 B 和 Hb 访问 PT/BTB；IF2 完成前一周期对 A 的 BTB/PT 访问、BTB tag check，并结合 Aa -> Bi 的转移类型、fall-through、RAS/SAS，选择 Ci。
  • cycle t+2：用 C 继续取指并产生 further-ahead 地址。

这样可以缩短 cycle time 或允许更大的预测结构，而不必在正确预测的 taken branch 上增加一周期 penalty。对 out-of-order 处理器，论文认为 misprediction penalty 不必额外增加，因为 checkpoint 中本来就需要记录 non-predicted path；two-block ahead 只需额外记录 IF2 阶段的 non-predicted path 和预测值。对 in-order 处理器，若没有额外结构保存这些值，则 misprediction penalty 可能增加一周期。

实验 Setup

实验平台：

  • Trace-driven simulator，建模 out-of-order speculative execution。
  • Benchmark 使用 SPEC92，包括 CINT92 与 CFP92。
  • 在 R4600-based SGI workstation 上用 cc 和 SPEC 标准 makefile 编译，开启所有优化。
  • 使用 PIXIE profiler 采集真实执行 trace，包括 library calls。
  • 总计采集超过 600M 条指令，trace 中去除 NOP。

机器模型：

参数 DW4 DW6 DW8
Dispatch Width 4 6 8
Lookahead Window Size 32 64 96
Issue Buffer Depth 28 48 72
Fixed-Point Units 3 4 5
Floating-Point Units 2 2 2
Branch Units 2 2 3
Data-Cache Ports 2 3 4

系统设置：

  • 第 3 节评估 single I-fetch 与 multiple I-fetch 时使用 perfect instruction/data cache，并按 dispatch buffer 深度、预测准确率、每周期取基本块数比较 IPC。
  • 第 6.1 节方向预测准确率实验假设 perfect BTB，以隔离 PT 本身差异。
  • 第 6.2 节 BTB 实验使用 512-entry 与 2K-entry BTB，改变 associativity；cache line size 假设为 16 条指令；替换策略为 pseudo-random。

实验结果

实验: single I-fetch 与 double I-fetch 的取指能力

设计：

  • 比较 single I-fetch 与 double I-fetch 在 DW4/DW6/DW8 上的性能。
  • 配置记为 1-N 或 2-N，其中 1/2 表示每周期取一个或两个基本块，N 表示 instruction-dispatch buffer 深度。
  • 横向改变方向预测准确率：90%、94%、97%、99%、100%。

结果：

  • CFP92 平均基本块接近 15 条指令，因此 single I-fetch 足够有效；8-wide single I-fetch 在预测准确率高于 90% 时可达到 perfect fetch 的 97.3% 以上。
  • CINT92 平均基本块约 5 条指令，single I-fetch 明显限制宽后端。
  • 4-wide 处理器基本不需要超出 single I-fetch 的机制，除非 dispatch buffer 很浅；8-deep dispatch buffer 已能达到约 93% perfect performance。
  • 6-wide，尤其是 8-wide 中，double I-fetch 相比 single I-fetch 有显著提升。
  • 对 8-wide 且 dispatch buffer 足够深的处理器，double I-fetch 带来约 20% 到 40% 性能提升，取决于方向预测准确率。
  • 在保持 binary compatibility 的前提下，8-wide 机器上每周期超过两个基本块的收益不明显，double I-fetch 已接近 perfect fetch。
  • dispatch buffer 至少需要约为 dispatch width 的两倍。

结论：

double I-fetch 的收益主要出现在整数程序和 6-wide/8-wide 这类宽后端场景。论文用这个实验为 two-block ahead predictor 的硬件价值建立动机：多块取指不是“更复杂但收益不明”的优化，而是宽后端前端供给不足时的关键机制。

评价：

baseline 的 single I-fetch 与 perfect fetch 对比是合理的，因为它直接刻画“每周期只能跨过一个基本块”造成的前端上限。不过实验假设 perfect I-cache/D-cache，会弱化真实系统中 cache miss、alignment、fetch queue backpressure 等影响。

实验: two-block ahead PT 的方向预测准确率

设计：

  • 使用 CINT92。
  • 假设 perfect BTB，排除 BTB miss 对方向预测统计的干扰。
  • 比较 one-block ahead 与 two-block ahead 的 g-share / g-select。
  • 改变 Prediction Table 大小，并在 64K-entry PT 下查看各 benchmark 差异。

结果：

  • 对 g-share 和 g-select，各 table size 下 two-block ahead 与对应 one-block ahead 的 misprediction rate 非常接近。
  • 64K-entry PT 上，各 benchmark 的错误率差异不超过 0.30%。

结论：

用前一个分支的地址和历史来预测后一个分支结果，在统计上仍然能代表被预测分支。Two-block ahead 的主要代价不在方向预测准确率。

评价：

perfect BTB 假设有助于隔离 PT，但也意味着该实验没有覆盖真实 BTB miss 与 wrong target 对前端吞吐的耦合影响。

实验: two-block ahead BTB 的命中率与 associativity

设计：

  • 使用 512-entry 与 2K-entry BTB。
  • 改变 associativity。
  • 比较 two-block ahead BTB 与 conventional one-block ahead BTB。
  • cache line size 为 16 条指令，同一 cache line 中的分支映射到同一 BTB set。

结果：

  • conventional BTB 在 associativity 为 2 左右基本达到最高 hit rate。
  • two-block ahead BTB 需要 associativity 约为 4 才接近最高 hit rate。
  • realistic BTB size 下，conventional BTB hit rate 略好于 two-block ahead BTB。
  • 但多数应用中差距小于 0.5%，包括 gcc。
  • 论文据此认为 two-block ahead BTB 不需要额外 storage，也不需要提高 associativity。

结论：

two-block ahead BTB 会引入一些冗余和别名压力，但在实验设置下代价较小，低于 double I-fetch 带来的前端吞吐收益。

评价：

论文给出了命中率层面的证据，但没有完整展示 BTB miss 对最终 IPC 的敏感性，也没有评估现代更深流水、更大 BTB、多级 BTB 设计下的交互。

Limits

  • return 后继块预测需要额外 SAS 机制：RAS 只能预测 return target，不能直接预测 return target 之后的控制流；SAS 是必要补丁。若扩展到更多 ahead blocks，call/return 嵌套与多返回场景可能进一步复杂化。
  • 连续 not-taken 分支 bypass 的一般情形没有简单解：论文只给出 last branch in cache block 的 L bit 优化；对于一个 fetched block 内多个连续 conditional branches 全部 not-taken 的理想 collapsing/bypass，作者明确表示尚未找到简单方案。
  • double I-fetch 需要更强的前端结构带宽：I-cache、BTB、PT 需要 double-ported 或 interleaved；RAS/SAS 在某些情况下也要每周期双读或双写
  • BTB/PT 结果偏向结构可行性：论文证明 two-block ahead PT 准确率接近 one-block ahead，BTB hit rate 差距很小，但对流水线恢复、更新时机、speculative history repair、multi-thread frontend 等工程问题覆盖较少。