锦标赛式分支预测器选择

形式陈述

有些分支通常朝一个方向走，另一些分支的方向依赖前面的执行情境。bimodal直接记住地址偏好，gshare把全局历史加入索引；一个小选择表可以尝试记住“对这个地址，最近哪一方更值得跟随”。这称为锦标赛式或组合预测。这里没有多轮淘汰赛，也不将两个方向取平均，而是每次输出其中一方已经给出的建议。

延用两分量的串行正确路径协议。记地址分量为B，历史分量为G；它们分别有 $2^{m_B}$ 、 $2^{m_G}$ 个二位计数器，G含 $h\le m_G$ 位历史。另外分配 $2^{m_C}$ 个二位选择计数器 $K$ 。本页参数均为非负整数，各索引位数不超过30，参考器限为12；分量默认初态1，G历史0，选择表也默认1。

对PC先同时取得B、G的反馈前建议 $b,g\in\{0,1\}$ ，以及它们各自的ticket。选择表索引为

j_C=(PC\mathbin{\mathrm{>>}}2)\bmod2^{m_C}.

若 $K[j_C]<2$ ，输出 $b$ ；否则输出 $g$ 。保存 $j_C$ 、旧选择状态、双方建议和选中方向。当前真实方向 $y$ 只能在这一步结束之后揭示。使用高状态偏好G是本页的编号约定，交换B/G与计数方向可给等价表示，但不能只改其中一项。

反馈时令

K[j_C]\leftarrow \begin{cases} \min(3,K[j_C]+1),&b\ne g\ \text{且}\ g=y,\\ \max(0,K[j_C]-1),&b\ne g\ \text{且}\ b=y,\\ K[j_C],&b=g. \end{cases}

然后B、G都按真实 $y$ 训练各自原来查询的槽，G也正常推进全局历史，不论这一轮选择器跟随了谁。二元建议发生分歧时恰有一方正确，因此三个分支覆盖全部情况。双方相同时，即使一起猜错，也没有证据证明其中一方更好，选择计数器不动；两分量仍应从这次真实结果学习。

一个组合实例仍只允许一个未决ticket。反馈错误实例、伪造副本、已用ticket或非0/1方向应拒绝，且在拒绝前不能先更新某一个分量。这个有限接口不实现多个分支并发决断、推测历史回滚或错误路径训练策略。

直觉

两位方向计数器记“更倾向T还是N”；两位选择计数器记“更倾向B还是G”。它们的状态形状相同，证据含义却不同。一个分量预测T并不会自动使选择器向它移动，只有后来揭示的真实方向才能说明它这一轮是否比对手正确。

为何未被选中的分量也要训练？设选择表冷启动偏好B，G第一次给出尚不成熟的建议。如果一直只训练B，G会停留在冷状态，选择器未来看到的仍是它未经训练的建议。这已不是在比较两条持续学习的完整轨迹，而是让选择行为改变了候选本身。这样的设计并非绝对不允许，但须另给状态机与评价，不能沿用本页接口的数字和证明。

先冻结两个方向建议，再选择其中之一；真实反馈同时训练双方，分歧才改变选择表 — 建议先于答案，双方持续训练

可以证明一个有限而有用的适应结论：固定一个选择槽，若此后所有分歧事件都由G正确，且没有其他共享该槽的相反赢家，那么从任何初态至多经过两次这样的事件，状态就进入2或3，随后的分歧会选择G。相同建议事件不移动它，也不影响这个以“分歧次数”计的结论。B持续获胜时对称。这里没有把两次分歧偷换成两个时钟周期，也没有保证程序未来保持同一赢家。

例子与边界

候选已经变好，选择器仍要学一次

同一PC=0x100运行 (TN)^8，三张表各四槽，G用两位历史；所有计数初值1，选择表低状态偏好B。前六步如下，其中 $K$ 是本轮查询前的选择状态：

次数	旧H	B建议	G建议	旧K	选择	实际	新K
1	00	N	N	1	B	T	1
2	01	T	N	1	B	N	2
3	10	N	N	2	G	T	2
4	01	T	N	2	G	N	3
5	10	N	T	3	G	T	3
6	01	T	N	3	G	N	3

第2次G已经正确，但选择器仍听B，随后才得到转向G的证据。第3次两方共同出错，不能处罚其中一方来伪造相对优势。最终B错16次，G错2次，组合错3次。选择器有适应开销，不能保证从第一步起就等于事后较好的分量。

在同一套参数下，PC产生四轮 TTTN 时，B错5次、G错11次、组合错5次。把这一循环片段、上述16次交替、最后16次全T连续接起来且不重置状态，共48次，B错13、G错15、组合错11。最后这个有限例子展示不同阶段可以使组合受益，并不是任意切换序列上的定理。

必须比较旧建议

设某次反馈前B的方向计数器为1、G为2、选择计数器为1，实际结果T。旧建议分别是N、T，G独胜，正确选择更新为2。若先训练两分量，B变为2、G变为3，再读取建议，看到的却是T、T，于是错误地让选择器留在1。

这份错误实现改变了“这一轮谁曾猜对”的事实。公开参考器把它作为真实变异运行，得到正确2与错误1；ticket保存的是事前建议，不是反馈后临时重读的输出。类似地，默认先选B的第一条T也应把未被选中的G从1训练到2；只训练B会把G错误地留在1。

同样有全信息，不代表同样有遗憾界

真实 $y$ 出现后，两方是否正确都可计算，所以反馈具有专家建议预测的全信息形式。不过，本页的四状态确定选择器不等于指数权重算法，也没有继承其相对最佳固定专家的次线性遗憾保证。

直接把选择接口接到两个常量候选B=0、G=1，选择初态1，让实际方向为 $(1,0)^k$ 。第一轮选B而错，状态升至2；第二轮选G而错，状态退至1。每两轮都回到起点，所以组合总错 $2k$ 次，而任一固定候选只错 $k$ 次，相对最好固定候选的额外错误为 $k$ ，线性增长。

这是对选择规则的一般保证的反例；两常量候选在这段论证中由外部接口提供，并非声称它们就是前一算例的bimodal和gshare内部运行。具体B/G组合也已有16次交替中3错大于G的2错这一更小见证。可执行结果与一般反例分别回答两个不同问题。

选择表也会混叠

选择表不含tag。两个PC若共享槽，一个经常由B独胜、另一个经常由G独胜，其更新可以互相抵消。即使每个PC各自有稳定的最佳候选，一个共享四状态槽也未必学会区分它们。扩大分量表不必然消除选择表冲突，三张表的容量是三个不同参数。

推论与应用

双边训练给出一个可检验的不变量：若独立运行一份B和一份G，使用与组合内部相同的初态、同一合法trace和反馈次序，那么每次预测前后，它们的状态分别与组合内部完全相同。归纳证明的关键是选择结果从不决定是否训练分量；每轮双方都读同一旧状态、接受同一真实方向，下一状态自然相同。参考器逐事件核对这个性质，避免选择器“顺便改变候选”却仍拿独立候选的错数作比较。

三张计数表加历史的逻辑存储为

2\bigl(2^{m_B}+2^{m_G}+2^{m_C}\bigr)+h\quad\text{比特}.

三表各四槽、 $h=2$ 时为26比特；独立四槽B只要8比特，四槽G为10比特。因此不能把26比特组合胜过8比特B的某条trace，写成同存储预算的胜出。限定26比特上限时，可以实际比较八槽B（16比特）、八槽两位历史G（18比特）与该组合（26比特），并明确未使用的预算。

例如前页32次相关分支trace上，这三者分别错16、2、16次，组合反而输给更大的G。阶段切换trace上则分别错13、15、11次。预算相同是上限相同，实际用量仍须列出；这里没有搜索所有参数，更不宣称这些配置达到预算下的最优准确率。

固定字宽和数组访问模型中，每条事件做常数个槽读写，核心时间 $O(1)$ ；三表初始化按总槽数计。硬件的多表读端口、选择延迟、功耗，以及目标预测仍未建模。Python的对象、完整状态快照、oracle与输出日志不按上述紧密比特数或常数核心时间计。

共同终点任务要求同时提交本轮双方建议、选择结果、分歧赢家和更新后状态，并运行只训练选中者、读新建议和看未来答案的错误变体。只有在完整反馈边界上比较，错误计数才说明预测行为，而不是测量程序自己制造出的优势。

参考资料

Scott McFarling，Combining Branch Predictors，DEC WRL TN-36，1993，§8、Figure 12：两个分量与按相对正确情况更新的二位选择表；§8也把三个数组计入组合器容量。本文高状态选择G，数值方向与候选命名一并固定。

形式陈述 ​

候选已经变好，选择器仍要学一次 ​

必须比较旧建议 ​

同样有全信息，不代表同样有遗憾界 ​

选择表也会混叠 ​

反向链接

形式陈述

候选已经变好，选择器仍要学一次

必须比较旧建议

同样有全信息，不代表同样有遗憾界

选择表也会混叠