(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111681414.1 (22)申请日 2021.12.2 9 (71)申请人 北京工业大 学 地址 100124 北京市朝阳区平乐园10 0号 (72)发明人 方娟　王轩　 (74)专利代理 机构 北京思海天达知识产权代理 有限公司 1 1203 代理人 张慧 (51)Int.Cl. G06Q 10/04(2012.01) G06K 9/62(2022.01) G06F 9/38(2006.01) (54)发明名称 一种利用感知器改进的锦标赛分支预测方 法 (57)摘要 本发明提出一种利用感知器改进的锦标赛 分支预测方法， 称为P ‑Tournament分支预测器。 本分支预测器旨在利用感知器预测器对于过往 历史的学习能力， 改进T ournament分支预测器的 选择器。 P‑Tournament的预测策略为从两个 预测 器表中选 出对应的预测器后， 根据感知器输出的 正负进行预测器的选择。 规定当感知器输出为负 时选择局部预测器， 为正时选择全局预测器。 在 分支指令执行完成后， 根据下一分支是否采用， 以及两个预测器谁预测正确进行更新： 假如两个 预测器的结果全部正确或者全部错误， 不对感知 器进行更新； 假如只有其中一方正确， 那么进行 感知器的训练。 权利要求书1页 说明书4页 附图3页 CN 114154763 A 2022.03.08 CN 114154763 A 1.一种利用感知器改进的锦标赛分支预测方法， 称为P ‑Tournament分支预测方法， 其 特征在于包括以下步骤： ①全局预测器的选择： 由当前指令的低8位和全局模式历史表的最后16位散列成一个 12位的索引， 对应一个拥有4K项的全局预测表， 表中的每一项都是一个标准的2 位饱和计数 器； ②局部预测器的选择： 由当前指令的低10位形成索引， 指 向一个拥有1K项的局部模式 历史表， 其中每一项都为10bit， 记录近期10次跳转结果， 而该表同时对一个拥有1K项3位计 数器构成的局部预测器表一 一对应进行索引； ③感知器选择器： 使用PC低12位进行索引， 共有4K个感知器， 每个索引得到一个感知 器， 用来选择使用全局预测器还是局部预测器的结果； 之后根据实际分支是否采用更新权 值。权　利　要　求　书 1/1 页 2 CN 114154763 A 2一种利用感知器改进的锦标赛分支预测方 法 技术领域 [0001]本发明属于计算机系统结构下流水线技术领域， 涉及到一种基于传统分支预测方 法的创新型改进。 背景技术 [0002]为了提高当代计算机在面对大量重复的指令的效率， 人们引入流水线技术来将一 个指令的完整运行过程拆分成多个子过程， 错开他们的执行时间来使得他们并行执行， 最 终达到了提高程序指令组整体运行效率的目的。 理想的流水线， 分级多少就应该有多少倍 效率的提升， 然而实际情况并非如此， 流水线会因许多问题而导致效率降低， 其中之一就是 “指令相关 ”及由指令相关引发的 “流水线冲突 ”。 [0003]指令相关指的是指令之间存在的相互依赖关系。 这种关系使得许多指令无法并行 执行， 或者只能部分并行执行。 指令相关会导致流水线冲突， 即由于相关的存在， 使得指令 流中的下一条指令不能在指定的时钟周期执行。 流水线冲突可能会导致错误的执行结果， 可能会导致流水线停顿， 产生气泡从而降低流水线的效率和实际的加速比； 为了解决这种 冲突我们还需要暂停某些指 令的执行以错开指 令， 消除冲突。 不管那种结果， 最后都会导致 流水线的效率受到影响。 [0004]指令相关可以分为数据相关、 名相关以及控制相关； 由这些相关引起的流水线冲 突可以分为数据冲突、 控制冲突和结构冲突。 其中控制相关与控制冲突的解决与改善是本 组此次研究的方向。 [0005]“控制相关 ”， 指受到分支指令引起的当前分支指令与目标跳转指令之间的相关。 流水线的高效依赖于指令的不断输入， 而这依赖于使用PC值进行指令的提取。 然而分支指 令只有执行到一定阶段才能判断出待跳转指令地址是什么， 是否需要跳转也需要分支指令 完全执行完毕后才能判断。 这种遇到分支指令和其他改变PC值的指令所引起的冲突称为 “控制冲突 ”。 [0006]根据对SPEC89的统计， 在整体分支执行程序中， 仅有11％的分支指令执行超过 10000次， 但 这些分支指 令的执行时间占分支指令执行时间总体的90％以上； 在所有的分支 执行当中， 60％的指 令具有一个强烈的跳转方向， 40％的指令的跳转方向是完全不确定的。 通过以上统计结果可以得出， 如果能够 “预测”指令的跳转成功与否， 并且能够提前获得下 一条指令的地址， 使得计算机能够取出指令放入流水线运行， 可以大幅减小控制冲突对效 率的影响。 为此 “分支预测 ”的理论被提出以用于解决控制冲突问题。 [0007]分支预测可以分为静态预测和动 态预测两种。 静态预测含有单方向静态 分支预测 (预测总是成功或者总是失败， 以及更适应循环执行的 “向后分支 ”静态预测器。 静态分支预 测由于一 旦确定策略就 不能再改变， 因此 预测准确度很难提升， 并且 对程序的适应性较差 。 [0008]由于当下流水级数非常长， 而流水线分支预测失败需要整个流水线废弃分支指令 执行到写回阶段之前的所有已执行操作。 对于复杂的流水线， 可能会损失20个左右的时钟 周期， 因此 更好的分支预测器非常重要。说　明　书 1/4 页 3 CN 114154763 A 3