Skip to content

沿方向预测路线,把二位方向偏好、全局历史索引与分量选择接到同一反馈协议。交付物应能回答“本次看到答案之前到底建议什么”,不能只有一张准确率排名。

完整标准库参考器与一整份可重现结果均可下载。运行 python foundation-branch-prediction-check.py,程序只向标准输出打印JSON;再用 python -O运行,结果应逐字一致。需要保存文件时由运行者重定向标准输出,程序自身不读写外部文件。

一、先固定你允许预测器知道什么 ​

PC为32位四字节对齐地址,真实方向T=1、N=0。每条记录先调用 predict(pc),把ticket上的旧history、索引、计数器、双方建议与最终建议抄入账本,再调用 resolve(ticket,actual)。上一条反馈完成后才预测下一条;trace只含正确路径条件分支,不包含目标、并发未决分支或错误路径事件。

默认B、G、选择表各四槽,即 mB=mG=mC=2;G用两位历史,初值00;所有计数器初值1。选择表0、1跟随B,2、3跟随G。另一个短历史配置用 h=1,历史放到索引高位,也就是先左移一位再与PC字地址低两位异或。

先提交完整四状态转移表与预测标签。说明3收到N后仍预测T,但2收到N后下一次改预测N。再提出两次非法操作:不反馈就再次predict、拿另一个实例的ticket反馈。记录拒绝后表、history、未决ticket和序号不变;参考器还检查伪造副本、重复反馈、非法PC与方向。布尔值True不能作为PC、方向、位数配置或计数器初值输入。

二、同一个PC,循环与交替为什么相反 ​

第一份trace为PC=0x100、方向 TTTN 重复四轮。第二份仍是该PC,方向 TN重复八轮。两份都从冷态重新建立实例,均有16条。

trace B全部错数 G全部错数 组合全部错数 执行前4条后,剩余12条错数 B/G/组合
循环 TTTN×4 5 11 5 3 / 7 / 3
交替 TN×8 16 2 3 12 / 0 / 0

交替trace提交前六条组合账本:旧H依次为 00,01,10,01,10,01,选择状态依次为 1,1,2,2,3,3;实际选择 B,B,G,G,G,G。第1、2、3条组合均错,此后全对。第2条G独胜,选择器下一条才切到G;第3条双方都错,选择状态不变。

再改用 m=h=1 的独立G。前四次索引应为0、1、0、1,旧计数为1、1、2、0,完整16次只错1次;存储是两个二位槽加一位history,共5比特。不要拿这个初态结论替代其他初态的结果,试把初值改为0或3并重做。

热身统计必须真的先执行前4条更新,再继续同一状态计分。另交一个空trace,事件和错误都为0;若你输出错误率,应标为无样本,而不是由0/0编出一个百分比。

三、让两个稳定PC互相干扰,再拆开它们 ​

令A=0x100永远T,B=0x110永远N,按A、B交替八轮。四槽bimodal会把字地址64、68都映到0,每轮状态 1→2→1,16次全错。

做两个独立迁移,并保留其余条件:

  1. 扩到八槽,使两PC分别用0和4;完整trace只错1次,计数状态从8增至16比特
  2. 保留四槽,将第二个PC改成 0x104,映到1;也只错1次,计数状态仍8比特

报告这里没有cache tag核验,也不会因“槽原来属于别人”而产生一种自动修复的缺失。第二项只是输入地址实验,不是对任意真实二进制程序作安全重排的承诺。把这些变化接回程序布局需要额外条件。

四、相关信息变多,为什么反而从2错到23错 ​

改用A=0x100、B=0x108。第 k 轮(从0起)A、B的方向都为 kmod2,每轮先A后B;16轮共32条,方向为 (NNTT)^8。

固定四槽,先跑 h=1,再跑 h=2。结果如下:

配置 逻辑状态比特 完整32次错数
四槽B,即h=0 8 16
四槽G,h=1,高端对齐 9 2
四槽G,h=2 10 23
八槽G,h=2 18 2
八槽G,h=3 19 23

对四槽h=1,说明稳定后槽0为何只接收T、槽2为何只接收N。对四槽h=2,找出两组相反证据:A在旧H=00时的T与B在旧H=10时的N都访问槽0;B在旧H=01时的T与A在旧H=11时的N都访问槽3。提交一次完整稳定四步中的旧计数和错猜位置,解释完整trace为什么是23而非24。

参考器还遍历 m=0,1,2,3 的每个合法h。任选一个未列出的配置手算前四步,再对照输出。你应交付的是容量、取位和实际情境共同作用的解释,而非“越长越好”或“越短越好”的口诀。

五、组合器的预算与持续学习 ​

将16条循环、16条交替、16条全T顺序连接,PC始终为 0x100,段与段之间不重置状态。48条上默认B/G/组合错数为13、15、11;执行前4条热身后,剩余44条为11、11、9。

核算默认逻辑状态:B为8比特,G为10比特,组合为26比特,后者包含两分量、选择表和history。现在统一给26比特上限,比较八槽B(16比特)、八槽h=2的G(18比特)、默认组合(26比特),同时标出未使用预算:

trace 八槽B错数 八槽G错数 默认组合错数
16条循环 5 11 5
16条交替 16 2 3
32条相关分支 16 2 16
48条阶段切换 13 15 11

这些配置不是预算下的穷尽优化。选择其中一行,说明“组合可能受益”和“组合必然胜出”的差别。另逐步核对组合内部两分量与独立分量状态相同,因为双方每次都训练;当前选B并不是让G停课的理由。

再把选择规则单独接到恒N与恒T两位候选,初态1、实际 (TN)^8。选择器16次全错,任一固定候选只错8次。一般化到 2k 次,写出额外错误为k的两步循环证明,并明确这一外部候选反例不是宣称恒定输出就是当前B/G内部状态。

六、运行错误变体,并给检查本身计费 ​

公开程序会实际运行以下区分性见证:

  • 先移动history再重算训练槽:一位G在16条交替上从正确的1错变成16错;第一条应教槽0,错误变体却教槽1
  • 先训练再记录“预测”:bimodal交替从合法16错变成表面0错,原因是本轮答案已经泄漏
  • 用训练后建议更新选择器:旧B=1、旧G=2、旧K=1、实际T,本应让K变2,错误实现保持1
  • 只训练被选中的B:第一条T后未选G错误地仍为1,完整规则应为2

提交至少一份错误轨迹与正确ticket逐字段的第一处分歧,不要只写“该变体不正确”。有限测试用于发现实现错误,恒方向两错界、history后缀不变量、h=0逐步等价和选择器两步反例仍须由正文证明。

参考器用独立转移表与字面历史字符串复算状态:所有长度0至4、由三个PC与两方向组成的短trace,在24种容量/初态配置下共37,320完整配置、141,840事件;另有1,600固定种子随机trace、49,899事件,20份h=0等价检查和47次非法操作/配置拒绝。普通与优化解释器结果相同。这些数量是可复现检查范围,不是对无限trace正确性的替代。

核心查询/反馈为常数次字操作,初始化按表槽数收费;完整事件报告却存每条之后的整表快照,N条、总T槽时可用 O(NT) 项输出空间与复制工作。测试oracle还保存字面历史前缀,其字符串拼接有自己的成本。Python对象并非紧密比特,PC与ticket、统计数和序号也不在小表预算里。最后说明你没有从方向错数推算CPI:缺少目标预测、恢复罚时与硬件读表延迟时,这一步没有依据。