分支目标缓冲 | Codeboy's Blog

“这次会跳”还没有回答“跳到哪里”。即使方向预测完全正确，取指端仍可能拿不到目标，或拿到同一条间接跳转上一次去过、这一次却不该去的地址。分支目标缓冲把这个问题单独做成一张可查询、可训练的表。它保存经验值，不保存一条跳转永远成立的证明。

形式陈述

从控制冒险到目标查询

分支冒险与冲刷要求实际控制流确定后取消错误路径。目标缓冲位于更早的预测一侧：给定当前分支的PC，希望立即得到一个候选目标，以便先继续取指。本页规定一个独立、可执行的带标记直接映射接口，不把某台处理器的全部前端细节藏进“BTB”这个名字。[1]

PC和目标都是无符号32位、4字节对齐地址，单条指令固定长4字节。顺序后继定义为 $s(p)=(p+4)\bmod2^{32}$ 。参考器只接受精确整数，拒绝布尔值、负值、越界值和未对齐地址。分支种类由已经解码或预解码的调用方提供；本页不通过一项可能过期的表内容猜测指令究竟是不是分支。

表有 $N=2^b$ 项，参考器允许 $0\le b\le12$ 。沿用标记与索引分解，把对齐PC变成30位字地址 $w=p/4$ ，再分成

i=w\bmod N,\qquad tag=\lfloor w/N\rfloor.

每项起初无效；有效项保存一个PC标记和一个30位目标字地址。lookup(p)只读表：槽 $i$ 有效且标记相同时，返回HIT和目标；否则返回MISS，不交出可用目标。结果同时列出索引和所查标记，便于检查冲突。它不修改替换状态。

train(p,t)验证PC和实际目标，再把槽 $i$ 覆写为 $(tag,t/4)$ 。这是同槽直接替换，不维护额外最近使用次序。独立接口由调用者决定何时训练；本单元的组合协议只在一条实际taken的记录按序提交时调用它。

方向与目标怎样组合

对条件分支，方向预测给出 $\widehat a\in\{0,1\}$ 。若预测不跳，选 $s(p)$ ；若预测跳且BTB命中，选表中目标；若预测跳但MISS，本教学接口仍暂取 $s(p)$ ，并标明这是缺目标时的猜测。实际机器也可以选择等待或其他目标来源，那会形成不同接口。

调用、返回和无条件跳转的已解码种类规定它们taken。返回还可以优先使用返回地址栈预测，只有该来源不可用时才采用BTB候选。方向为不跳时，参考器仍可把BTB是否命中写入日志，但不会采用其目标。

三件事不能混为一个命中率：方向是否正确，目标表是否HIT，所选nextPC是否等于实际nextPC。实际taken目标由后端调用方提供；表接口没有执行指令、检查寄存器或证明这个实际值真实的能力。

直觉

可以把每项理解成“我记得PC为谁的那次跳转去了哪里”。索引找到抽屉，标记确认抽屉里的记录属于谁，目标则是那条记录的内容。只有抽屉号相同，不能认定记录属于当前PC；即使人对了，上一次的去向也可能不适合这一次。

这里复用了缓存的索引和标记思想，但预测值的承诺更弱。缓存中的数据还要遵循它的存储一致性合同，BTB命中只表示表里确实有这个PC的历史记录。执行阶段仍要核对真正控制流。

例子与边界

两个PC争用一个槽

取 $b=2$ ，共4槽。0x100/4=64，故索引0、标记16；0x110/4=68，同为索引0、标记17。

动作	槽0内容，目标按字节地址显示	查询0x100	查询0x110
冷表	无效	MISS	MISS
train(0x100,0x200)	tag16，目标0x200	HIT 0x200	MISS
train(0x110,0x300)	tag17，目标0x300	MISS	HIT 0x300

第二步查0x110不能误拿0x200，第三步查0x100也不能误拿0x300。替换造成的是可解释的MISS，不是另一条PC的假命中。若只有索引而省掉标记，这个保证就消失。

两个PC映射同槽但标记不同，命中必须同时验证身份；下方同一PC交替目标说明命中仍可能预测错误 — 表项身份与未来目标正确性是两项检查

同一PC每次换一个目标

让无条件间接跳转PC0x100的真实目标依次为0x200、0x300、0x200、0x300。每次都在解析、提交后才开始下一次预测。第一次冷表退回0x104；后三次分别预测0x200、0x300、0x200。因此四次nextPC都错，后三次却全部BTB命中。

这里没有标记冲突，方向也始终taken。失败来自“上次目标”不能刻画交替规律。历史相关的间接目标预测器可能改进这类输入，但不属于本页的最近一次目标表。

对齐、回绕与缺失

$b=0$ 是合法的单槽表；所有PC都争用它，标记包含全部30位字地址。0xfffffffc的顺序后继是0；这只是显式32位模型的回绕约定，不是任意ISA的地址异常规则。

MISS不等于预测不跳；目标为0也不等于MISS。接口用独立hit字段和无目标的 None区分这两种情况。一次非法训练在写槽之前失败，不应把旧目标改掉。

推论与应用

标记究竟证明了什么

对任意槽作训练次数归纳。初始槽无效；每次训练只把对应槽写成该PC的标记和给定目标，其他槽不变。因此有效槽始终保存“最近一次写这个槽的训练”。

若查询PC $p$ 命中，索引与标记共同唯一恢复字地址 $w=tag\,N+i$ 。所以最近写该槽的PC必为 $p$ ，返回目标恰是那次训练提供的值。反过来，只要最近写这个槽的训练确实来自 $p$ ，查询就会命中。证明到此为止：它没有推出当前动态分支仍会去那个目标。

这个边界也是推测预测状态恢复的起点。目标错时，即使方向对了，年轻记录也可能来自错误路径；必须取消它们，并修复它们对其他预测状态造成的修改。只有实际提交的taken记录训练本页的表，便能避免已取消记录留下新的BTB目标。

费用和实现范围

在固定字长下，一次查询或训练只做常数次地址拆分、比较和槽访问，时间 $O(1)$ 。初始化与全表快照需要 $O(N)$ ，空间为 $O(N)$ 个字。若只核算一种紧凑逻辑编码，每槽需要1个有效位、 $30-b$ 个PC标记位与30个目标位，共 $61-b$ 位； $b=2$ 时为每槽59位、全表236位。它不包含外围读写端口、ECC、方向状态、种类识别、日志或Python对象开销。

BOOM文档中的快速预测器使用全相联BTB，并带取指包位置等信息。[1] 本页刻意选择每条已解码分支对应一次查询的直接映射表，以便把身份、冲突和预测责任证明清楚。该文档说明方向和目标来源的分工，不意味着其硬件组织就是这里的四槽程序。

共享可执行终点先复算上面的冲突表和交替目标，再把BTB接到返回预测与多条在途分支的恢复协议中。程序同时交出实际预测、解析、取消与提交事件，不把函数调用次数称为处理器周期。

参考资料

[1] RISCV-BOOM，The Next-Line Predictor：BTB目标查询、RAS与方向预测的组合；本文采用不同的直接映射、已解码种类模型
Kevin Skadron、Pritpal S. Ahuja、Margaret Martonosi、Douglas W. Clark，Improving Prediction for Procedure Returns with Return-Address-Stack Repair Mechanisms，MICRO1998，§2.1及§3.1：返回目标来源、taken目标表与方向正确但目标仍错的情形；本页不移用其中周期或性能数字

形式陈述 ​

从控制冒险到目标查询 ​

方向与目标怎样组合 ​

两个PC争用一个槽 ​

同一PC每次换一个目标 ​

对齐、回绕与缺失 ​

标记究竟证明了什么 ​

费用和实现范围 ​

反向链接