branch-prediction-notes

发表于 本文字数： 1.4k 阅读时长 ≈ 1 分钟

分之预测笔记

基础定义

  1. 分支预测的作用:

    • 跳转指令会改变指令流，导致顺序取指的指令做了无用功，分支预测就是在取指阶段根据pc值预测可能发生的pc改变， 从预测的pc去取指令，避免无用功
    • 预测包含两部分内容：预测是否跳转、预测跳转的地址

  2. 分支预测的种类:

    • 静态分支预测：对于流水线比较短的处理器核，分支预测的性能要求不高，可以使用静态分支预测
    • 动态分支预测：对于超标量乱序处理器核，其流水线比较深且一次取多条指令，需要比较复杂的动态分支预测

  3. 分之延迟槽(branch delay slot):

    • 分之指令后面的指令可能是无效指令，需要被冲刷掉
    • MISP在分支指令后面插入无关的且必须执行的指令，今儿避免冲刷指令
    • 分支延迟槽需要编译器或者程序员的支持
    • 不适用于复杂的处理器核设计中，因为找到无关的指令变得更复杂

  4. Q: 为什么通过PC来进行动态分支预测？

    • 通过PC预测，在取指的时候就可以根据PC去进行分之预测；如果根据指令内容再进行分支预测，至少需要进行预译码，不如通过PC快 （分支预测越早作出预测，效果越好)
    • PC对应的指令，其内容是不变的，即PC跟指令内容之间存在映射关系，因此一定程度上通过PC进行预测等价于通过指令内容进行预测

方向的预测

PHT

  1. 一位饱和计数器（又叫做 last-outcome prediction)
    • 采用1 bit来记录上一次是否跳转
    • 缺点：对于跳转来换切换比较频繁的情况，其预测准确率可能低到0%
  2. 两位饱和计数器(2 bit saturating prediction)
    • 采用2 bit来记录上一次是否跳转，分别是strongly taken, weakly taken, strongly not taken, weakly not taken
    • 可以解决一位饱和计数器在频繁切换时的问题
    • 采用格雷码可以减少出错的概率、功耗
    • 当下比较常用的分支预测器，从2bit增加到3bit并不会提升多少准确率，反而会大大增加硬件复杂度
  3. PHT(Pattern History Table)
    • 无法为所有的PC都准备一个2bit分支预测器
    • 将分之跳转的情况记录在PHT中，每一个PHT表项就是一个2bit分支预测器，通过PC某些位来索引
    • 多个PC会同时索引到同一个表项，这称之为分支别名(aliasing)， 不直接采用PC索引PHT，对PC进行Hash之后再索引PHT可以优化别名的问题
    • PHT的表项越多，预测越准确、占用的存储越多
    • 在乱序处理器中，在指令提交的时候，对PHT进行更新， 所有的表项公用同一个更新硬件电路即可，因为一次只会索引到一个表项

BHR

  1. 考虑指令的局部历史(local history)，对每个PC额外提供一个BHR(branch history register)存储最近几次的跳转情况
  2. BHR本身是一个移位寄存器，通过BHR再去索引PTH，找到PHT中的某个表项，这种方法称为自适应两级预测(Adaptive two-level predictor)
  3. BHR的位宽：用1表示跳转、0表示不跳转，则历史跳转记录就是一串由01构成的序列，该序列里连续相同的数最多有p位，则BHR位宽为p即可
  4. 训练时间(training time)，由于1个n bit的BHR对应一共有\(2^n\)PHT表项，这些表项都是需要时间去更新从而达到稳定

预测分支指令是跳转(taken)还是不跳转(not taken)

参考资料

  1. 《超标量处理器》第四章分支预测