一种利用感知器改进的锦标赛分支预测方法

1.本发明属于计算机系统结构下流水线技术领域，涉及到一种基于传统分支预测方法的创新型改进。


背景技术：

2.为了提高当代计算机在面对大量重复的指令的效率，人们引入流水线技术来将一个指令的完整运行过程拆分成多个子过程，错开他们的执行时间来使得他们并行执行，最终达到了提高程序指令组整体运行效率的目的。理想的流水线，分级多少就应该有多少倍效率的提升，然而实际情况并非如此，流水线会因许多问题而导致效率降低，其中之一就是“指令相关”及由指令相关引发的“流水线冲突”。
3.指令相关指的是指令之间存在的相互依赖关系。这种关系使得许多指令无法并行执行，或者只能部分并行执行。指令相关会导致流水线冲突，即由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。流水线冲突可能会导致错误的执行结果，可能会导致流水线停顿，产生气泡从而降低流水线的效率和实际的加速比；为了解决这种冲突我们还需要暂停某些指令的执行以错开指令，消除冲突。不管那种结果，最后都会导致流水线的效率受到影响。
4.指令相关可以分为数据相关、名相关以及控制相关；由这些相关引起的流水线冲突可以分为数据冲突、控制冲突和结构冲突。其中控制相关与控制冲突的解决与改善是本组此次研究的方向。
[0005]“控制相关”，指受到分支指令引起的当前分支指令与目标跳转指令之间的相关。流水线的高效依赖于指令的不断输入，而这依赖于使用pc值进行指令的提取。然而分支指令只有执行到一定阶段才能判断出待跳转指令地址是什么，是否需要跳转也需要分支指令完全执行完毕后才能判断。这种遇到分支指令和其他改变pc值的指令所引起的冲突称为“控制冲突”。
[0006]
根据对spec89的统计，在整体分支执行程序中，仅有11％的分支指令执行超过10000次，但这些分支指令的执行时间占分支指令执行时间总体的90％以上；在所有的分支执行当中，60％的指令具有一个强烈的跳转方向，40％的指令的跳转方向是完全不确定的。通过以上统计结果可以得出，如果能够“预测”指令的跳转成功与否，并且能够提前获得下一条指令的地址，使得计算机能够取出指令放入流水线运行，可以大幅减小控制冲突对效率的影响。为此“分支预测”的理论被提出以用于解决控制冲突问题。
[0007]
分支预测可以分为静态预测和动态预测两种。静态预测含有单方向静态分支预测(预测总是成功或者总是失败，以及更适应循环执行的“向后分支”静态预测器。静态分支预测由于一旦确定策略就不能再改变，因此预测准确度很难提升，并且对程序的适应性较差。
[0008]
由于当下流水级数非常长，而流水线分支预测失败需要整个流水线废弃分支指令执行到写回阶段之前的所有已执行操作。对于复杂的流水线，可能会损失20个左右的时钟周期，因此更好的分支预测器非常重要。
[0009]
动态分支预测方法作为一种将分支指令过去的跳转历史考虑进当前分支预测决策的最新颖的分支预测方法，有着对不同程序的更好适应性，以及大幅提高的预测准确度。
[0010]
动态分支预测本身可以按照利用的分支历史记录长度的不同分成局部分支预测和全局分支预测；而后续研究发现，如果可以将两种预测方法通过某种方式结合在一起，在实际预测时从中选取成功率更高的一种，可以有效提高预测成功率。这种分支预测方法称为混合分支预测，其中典型之一就是锦标赛分支预测方法(tournament branch predictor)。
[0011]
全局分支预测的问题在于由于全局历史的记录单纯的记录了所有分支指令的所有分支记录，拥有相似分支历史记录的不同指令可能会因此产生混淆的情况。并且全局分支历史记录对于计数器的要求是指数级增长的，为了达成较好的预测效果需要大量的资源开销。感知器的应用使得全局历史得到了更好的学习，并且全局历史对于感知器的需求是线性增长的。在同等资源规模下，使用感知器的全局预测方法比传统全局预测效果更好。


技术实现要素：

[0012]
本发明提出一种分支预测器，称为p-tournament分支预测器。本分支预测器旨在利用感知器预测器对于过往历史的学习能力，改进tournament分支预测器的选择器。利用感知器代替以往的2为饱和计数器作为选择器可以更好的利用全局历史记录来进行选择，因为最后判断结果的得出依靠的是全局历史记录的加权和；在此基础上，为了进一步改进全局历史预测的效果，引入gshare分支预测技术将全局历史长度和预测器表长度解耦的思想来进一步提高预测准确度并节省更多的资源。
[0013]
本发明提出的分支预测器命名为p-tournament分支预测器。这种分支预测器主要由三种功能组成：全局预测器的选择，局部预测器的选择，以及感知器的训练。
[0014]
全局预测器的选择主要通过将分支指令的低几位与全局历史表的最后几位记录进行哈希或异或运算得出索引，再指向全局分支预测器表中取出对应的饱和计数器预测器。这种异或/哈希运算可以引入当前指令特征并将预测器表长度和全局历史长度解耦，以消除混淆状况并提高预测的准确率。
[0015]
局部预测器的选择由两层组成。第一层为通过分支指令低几位从局部模式历史表中选出对应的局部历史记录，并且一一对应指向一个局部预测器表进行二级索引。
[0016]
感知器选择器的选择同样通过指令地址低几位进行索引，值得注意的是感知器存储在一个特殊的表中，表中各项为每个感知器对应于全局历史每一位的权值。
[0017]
p-tournament的预测策略为从两个预测器表中选出对应的预测器后，根据感知器输出的正负进行预测器的选择。规定当感知器输出为负时选择局部预测器，为正时选择全局预测器。在分支指令执行完成后，根据下一分支是否采用，以及两个预测器谁预测正确进行更新：假如两个预测器的结果全部正确或者全部错误，不对感知器进行更新；假如只有其中一方正确，那么进行感知器的训练。
[0018]
感知器选择器的训练与一般的感知器差别不大，感知器对每一个分支历史都有一个对应的权值，最终选择结果根据加权和的正负决定。在训练时应加上一训练阈值应保证训练效果。
[0019]
有益效果
[0020]
本分支预测策略比起传统的tournament预测器，优势一方面在于利用了gshare分支预测器将全局历史记录和预测器表长度解耦的思路，通过引入当前指令的部分特征，可以缩小预测器表长度，最重要的是可以消除由于一部分指令的历史具有相似性导致预测混淆的情况；另一方面，这种分支预测方法利用了感知器预测器来代替传统的2位饱和计数器，因为感知器预测器对于历史的学习效果明显优于传统计数器，因为权值的训练过程可以看作是将历史中蕴含的知识存储下来的过程。
附图说明
[0021]
图1为整个方法的功能分组示意图；
[0022]
图2为方法的执行流程；
[0023]
图3为感知器加权模型。
具体实施方式
[0024]
为使本发明的目的，技术方案和优点更加清楚明白，下文中将结合附图对本发明的实施例进行详细说明。
[0025]
1.pt分支预测器模型的技术细节：
[0026]
图1里面涉及到了如何选取全局/局部分支预测器，以及整个预测过程的功能分组。值得注意的时，感知器表中存储的时各个感知器的权值。
[0027]
本节可以结合图1进行查看。
[0028]
①
全局预测器的选择：由当前指令的低8位和全局模式历史表的最后16位散列成一个12位的索引，对应一个拥有4k项的全局预测表，表中的每一项都是一个标准的2位饱和计数器。
[0029]
②
局部预测器的选择：由当前指令的低10位形成索引，指向一个拥有1k项的局部模式历史表，其中每一项都为10bit，记录近期10次跳转结果，而该表同时对一个拥有1k项3位计数器构成的局部预测器表一一对应进行索引。
[0030]
③
感知器选择器：使用pc低12位进行索引，共有4k个感知器，每个索引得到一个感知器，用来选择使用全局预测器还是局部预测器的结果。
[0031]
之后根据实际分支是否采用更新权值。
[0032]
2.pt分支预测器的更新策略为：
[0033]
本节可以结合图2进行查看。
[0034]
首先，根据当前指令地址的低8位与全局历史最后16位哈希运算形成12位索引，得到一个全局2位饱和计数器预测器。
[0035]
其次，根据当前指令的低10位作为索引选择对应的局部bht记录，并选择对应的3位饱和计数器预测器。
[0036]
最后，根据当前指令的低12位形成索引，得到对应的感知器选择器，进行选择。当感知器的输出为正，采用全局预测器结果，否则采用局部预测器结果。
[0037]
3.感知器选择器的更新规律：
[0038]
本节可以结合图1、图2以及图3查看。
[0039]
感知器本身为采用单层的感知器组成最为简单的神经网络，学习目标为以全局分
支历史的纪录的每一数位作为输入的布尔函数t(x1,x2,
…
,xn)。我们以目标函数的值来判断选择哪种预测器。
[0040]
图3中展示了作为饱和计数器替代品的感知器模型，其中w1…n是感知器分配给每个记录的权重，而w0则乘1以规范化输入向量，作为偏置量。
[0041]
感知器的输出y被定义为：
[0042][0043]
所有的感知器的权值初始化为使得感知器输出为负，即默认采用局部预测器结果作为预测。当全局预测与局部预测结果与实际采用结果均一致或均不一致时，不更新；若只有全局预测结果正确，设t＝1，反之若只有局部预测结果正确时，设t＝-1。
[0044]
设n为全局历史长度，wi为对应权重，θ为训练阈值，则感知器的训练伪代码为：
[0045][0046]
训练结束后将感知器权值存回对应的表中。

技术特征：
1.一种利用感知器改进的锦标赛分支预测方法，称为p-tournament分支预测方法，其特征在于包括以下步骤：
①
全局预测器的选择：由当前指令的低8位和全局模式历史表的最后16位散列成一个12位的索引，对应一个拥有4k项的全局预测表，表中的每一项都是一个标准的2位饱和计数器；
②
局部预测器的选择：由当前指令的低10位形成索引，指向一个拥有1k项的局部模式历史表，其中每一项都为10bit，记录近期10次跳转结果，而该表同时对一个拥有1k项3位计数器构成的局部预测器表一一对应进行索引；
③
感知器选择器：使用pc低12位进行索引，共有4k个感知器，每个索引得到一个感知器，用来选择使用全局预测器还是局部预测器的结果；之后根据实际分支是否采用更新权值。

技术总结
本发明提出一种利用感知器改进的锦标赛分支预测方法，称为P-Tournament分支预测器。本分支预测器旨在利用感知器预测器对于过往历史的学习能力，改进Tournament分支预测器的选择器。P-Tournament的预测策略为从两个预测器表中选出对应的预测器后，根据感知器输出的正负进行预测器的选择。规定当感知器输出为负时选择局部预测器，为正时选择全局预测器。在分支指令执行完成后，根据下一分支是否采用，以及两个预测器谁预测正确进行更新：假如两个预测器的结果全部正确或者全部错误，不对感知器进行更新；假如只有其中一方正确，那么进行感知器的训练。感知器的训练。感知器的训练。


技术研发人员：方娟 王轩
受保护的技术使用者：北京工业大学
技术研发日：2021.12.29
技术公布日：2022/3/8