介绍

论文原文

tage-sc-l分支预测器在大多数问题上都有很高的准确率，但是对于数据依赖型的分支却无能为力。例如判断一个数组中的某个数据是否为0，它依赖于数组的值，现有分支预测器都是基于过去分支的历史进行的，二者没有相关性，因此无法预测。

本文提出了一种提前执行分支指令的方法，通过一个小的处理器提前计算出分支结果，来处理分支预测器无法预测数据依赖型分支的问题

依赖链的计算

守护分支和影响分支

想要提前计算出分支指令，首先需要知道哪些指令和这个分支指令相关。这里首先需要给出两个定义

守护分支(Guard branch): 守护分支会决定另外的分支是否执行。例如两层的if，如果外层的if不执行，那么内层的if也不会执行，这时外层的if就是守护分支
影响分支(affector branch): 影响分支是可以影响其他分支源数据的分支。

要获得守护分支和影响分支首先需要知道分支正确路径和错误路径的合并点。由于现代乱序多发射的结构导致一次预测错误会多取上百条错误指令，因此可以使用正确路径的指令和错误路径的指令来找到两条路径的合并点。

守护分支的确定很简单，任何出现在合并点之前的分支都可以认为是被当前指令守护的分支

而影响分支的确定要困难一些。首先将所有合并点之前分支的源寄存器，目的寄存器和访存地址都标记为中毒(poison)。然后执行合并点之后的指令，如果源寄存器都没有中毒，那么将目的寄存器也标记为未中毒，直到到达最长距离或者遇到下一次预测错误分支。如果存在分支指令的寄存器被标记为中毒，那么这些指令看成被当前分支指令所影响

依赖链抽取分支的确定

我们仅对难预测分支抽取依赖链，那么首先需要确定哪些分支是难预测分支。文章中提出了一种难预测分支的检测算法，每次分支预测错误时分配一个表项，表项中有一个5bit的错误次数计数器，这个计数器每1000周期降低15.并且只有错误次数为0的表项才可以被分配。

并且这个被这个难预测分支影响/守护的分支也可以被分配表项，并且只有当难预测分支被清除时才可以替换表项。

依赖链的抽取

在确定了抽取范围之后，开始抽取相应分支的依赖链。首先文章使用了512项循环列表来保存退休指令。每次遇到难预测分支时，将该分支的源寄存器加入搜索列表，然后向前搜索。如果指令的目的寄存器在搜索列表中，那么将目的寄存器移出搜索列表，再将该指令的源寄存器加入搜索列表，并且将该指令加入依赖链中。

依赖链抽取的停止条件为：遇到第二个相同的分支指令或者遇到了守护/影响分支。

在抽取完依赖链后，它将组织成一个表项。表项中包含两大项： tag和chain。其中tag就是难预测分支的pc和方向，而chain就是相关分支的指令信息。

依赖链的使用

如图所示为加上了依赖链之后的流水线，下面为正常的乱序处理器流水线，上面是依赖链的流水线。依赖链计算的时机为依赖链中的tag和当前分支指令的pc和方向匹配。在匹配成功之后将加载依赖链并且提前计算出分支结果。