双态分支方向预测

单比特记忆只问“上一次怎样”，一次循环退出就足以把它改成N；下一次循环重新进入时又可能猜错。二位计数器多留一层惯性：已经很确信T的状态3遇到一个N只退到2，下次仍猜T。连续证据才能把方向翻过来。

“强”与“弱”只是状态的名字，不是校准过的概率。状态3并不表示有75%或100%的跳转概率，状态1也不是过去所有结果的精确频率。饱和会忘掉更早的次数：连续一百个T与连续三个T都可能停在3，随后两个N就能移到1。它实现的是有界记忆偏好，而不是保存完整票数。

若某槽从现在起收到的方向全是T，从任意初态最多先错两次：最不利的0先升到1、再升到2，第三次开始建议T。全为N的情况对称。注意前提是这个槽收到的所有更新方向一致，不只是某个PC自身稳定；另一个碰撞PC仍能把它拉走。若已在3，序列 N,T只错第一个；这才是抵抗单次反向结果的准确条件。从弱T的2出发遇N就会降到1，不能笼统说“任何状态都要连错两次才改方向”。

循环出口留下什么记忆 ​

令一个PC反复产生 TTTN，初态1。第一次四次查询的旧状态依次是1、2、3、3，建议N、T、T、T，因此第一项和退出项各错一次；更新后停在2。下一轮第一次T已经猜对，此后每轮只在N处错。

四轮共16次，二位计数器错5次。若比较“预测上次方向”的单比特规则，也须声明它的初值：从N开始，每轮入口和出口都错，四轮共8次。这里的差别来自这条明确trace，不能由循环例子推出二位规则在任意程序上都更准。若只报告热身后的结果，本文先真实执行前4次更新，再统计剩余12次中的3错；不能丢弃前4条输入后重新冷启动。

交替方向会卡在分界线 ​

同一PC产生 (TN)^8，从1开始：T来时预测N，更新为2；N来时预测T，又回到1。两步状态循环，所以16次全错。若初态是3，第一项T猜对，而每个N猜错，结论便不同。初始化是实验的一部分，不能把不合适的初态隐去后只报一个准确率。

更严重的错误是先把当前真实方向写入计数器，再询问它会预测什么。同样从1开始，T先把状态变2、N先把状态变1，记录出的16次竟然全“正确”。这只是把答案泄漏给预测器，不能当成算法改进。终点参考器实际运行这一错误变体，与合法的16错并列。

没有tag，碰撞不是一次缓存缺失 ​

取 $m=2$，只有四个槽。PC为 0x100 和 0x110 的字地址分别是64和68，低两位都为0。若前者总T、后者总N，按这两个PC交替查询，从状态1仍得到 1→2→1，16次全错。每条静态分支各自都十分稳定，失败来自共享计数器。

表中不保存tag，也没有“这是别人的槽所以拒绝”的valid判断。这与缓存的索引加tag核验理路缓存块、标记与直接映射Cache address mapping · Direct-mapped cache · Tag index offset按字节地址拆出块内偏移、索引与标记，区分地址映射、有效位和冲突缺失。不同：方向建议允许出错，由控制流恢复处理；把无tag预测表画成只有“命中/缺失”而无干扰的缓存，会掩盖真正的机制。

把表扩大为 $m=3$，两PC落在0和4，只在第一个T上错，共1错，但计数状态由8比特增加到16比特。也可保留四槽，把第二条分支移到 0x104，使其落在1，同样只错1次。这只是教学trace的地址重排实验，不保证任意代码重排都不改变指令布局、缓存行为或程序语义。

对固定字宽、随机访问数组的模型，一次查询和一次反馈各用常数次索引、比较和饱和加减，即 $O(1)$ 字操作；初始化 $2^m$ 个槽用 $\mathrm{\Theta }(2^m)$ 时间。计数状态恰为 $2\cdot 2^m$ 比特，不包括输入trace、计数统计或ticket。无tag节省的正是地址所有权信息，代价是混叠，而不是免费获得无限容量。

公开Python程序用整数列表，实际内存不是紧密打包的上述比特数。它为检查复制整表，记录完整事件，还保留序号；这些分别增加每次 $O(2^m)$ 检查开销、每事件含整表的输出和随事件数增长的序号位数。若保存 $N$ 条事件的全部快照，表与输出复制共可用 $O(N{2}^m)$ 项。不能用核心状态机的 $O(1)$ 为整个详细报告程序计费。

若同一PC在不同过去情境下方向不同，可以继续问“该读哪一个槽”。gshare理路gshare全局历史分支预测Gshare branch prediction · Global history with index sharing · gshare预测器将全局方向历史与分支地址异或索引，保存查询时上下文并展示历史能区分情境也会制造碰撞。把全局方向历史加入索引，在交替例子中拆开两种情境；它仍可能因新的哈希碰撞更差。再由预测器选择器理路锦标赛式分支预测器选择Tournament branch predictor · Combining branch predictors · 分支预测选择器同时收集地址与历史预测器的事前建议，只在分歧反馈中训练选择器，明确双边训练、适应滞后和无普遍胜出保证。比较两种建议时，也必须先冻结本轮建议、再使用反馈。

完整终点任务把循环、交替、PC碰撞、历史相关与阶段切换放在同一协议下，要求报告全部错数、热身后错数及真实状态预算。方向预测的准确率不直接给出CPI：还需要目标生成、错猜罚时、预测延迟和取指带宽模型，本页均未提供这些假设。