超标量处理器设计4-分支预测
1. 简介
分支预测的准确率对性能的影响很大，主要是预测方向和预测跳转地址。其中跳转指令也分为直接跳转和间接跳转，直接跳转的跳转地址就在指令码中；而间接跳转的跳转地址在寄存器中，需要先访问寄存器的值，才能得到地址，一般只有call/return 指令才会是间接跳转。
要进行分支预测，首先需要知道从I-Cache 取出来的指令中哪条指令是分支指令。
a. 最容易的办法是从I-CACHE取出来之后，进行快速的解码，然后找到对应分支指令的PC值送到分支预测器中进行预测。这个办法的缺点是从Cache中取指需要多个周期，导致分支跳转的预测滞后了，影响准确度；而且指令快速解码和分支预测的过程都放在了同个周期，严重影响了处理器的周期时间；
b. 在指令从L2 CACHE写入到I-CACHE之前进行快速解码，称为预解码，然后将指令是否是branch指令的信息和指令一起写到ICACHE中，这样I-CACHE会变大，但是减少了快速解码电路，降低了对处理器周期时间的影响。
c. 分支预测越靠前越好，如果指令从I-CACHE中取出来之后才进行分支预测，当得到分支预测结果时，已经有很多指令进入了流水线。因此分支预测的最好时机时在当前周期得到取指令地址(PC)的时候，在取指令的同时进行分支预测，这样就可以在下个周期就可以根据预测结果进行取指.在PC值刚刚产生的那个周期，根据这个PC值来预测本周期的指令组中是否存在分支指令，以及分支指令的方向和目标地址。
2. 分支指令的方向预测
- 基于两位饱和计数器的分支预测方法(two-taken):一般来说使用strongly not taken 或者 weekly not taken作为初始态
分支预测都是以PC值为基础的，正常来说，每一个PC值都应该对应一个两位的饱和计数器，但是实际上不可能所有的PC都是branch指令，因此我们只需要PC的k-bit来记录， 其中k=13, 预测精度可以到93%。我们一般会在流水线的提交阶段，也即当分支指令要离开流水线时，更新PHT - 基于局部历史的分支预测: 使用一个寄存器(BHR, branch history register) 记录一条分支指令在过去的历史状态。 这种方法也称为自适应的两级分支预测(adaptive two-level predictor) , 一个位宽为n的BHR 寄存器可以记录一条分支指令过去n次的结果， 去BHR使用一个两位的饱和计数器来捕捉它的规律, 注意PHT里的每个entry是2bit的reg, 而PHT外围有一个2bit的状态级跳转, 根据BHR的值来索引PHT.
3.基于全局历史的分支预测： 记录多条分支指令的跳转情况，如果A和B发生了跳转，C一定发生跳转，通过全局历史寄存器(GHR)来记录多条分支指令的跳转情况。
- 竞争的分支预测法
3. 分支指令的目标地址预测
3.1 BTB(branch taget buffer)
- 对于直接跳转指令： 它的目标地址有两个： 一个是当前分支指令的PC值+sizeof(fetch group); 另一个是当前分支指令的PC值+ sign_extend(offset)
- BTB本质上是cache, 所以它的结构和Cache也是一样的，使用PC值的一部分来寻址BTB(index), PC值的其它部分作为Tag, BTB中存放着分支指令的目标地址，可以采用组相连的方式来实现BTB.
- 为了最大限度地利用BTB中有限的存储资源，只将发生跳转的分支指令对应的目标放到BTB中，哪些预测不发生跳转的分支指令，他们的目标地址就是顺序去指令的地址，因此并不需要预测。
3.2 BTB缺失的处理
- 停止执行: 当一条分支指令在BTB中没有找到对应的目标地址时，可以暂停流水线的取指令，知道这条分支指令的目标地址被计算出来为止，如果是直接跳转指令，目标地址就在指令码中，目标地址计算比较快，暂停周期较少；如果是间接跳转，那么流水线中产生的气泡会比较多，降低处理器的执行效率
- 继续执行: 用顺序执行的地址当作目标地址继续取指执行，有总比没有好，缺点是有功耗损失，性能会好些。
3.3 间接跳转类型的分支预测
- CALL/RETURN 指令的分支预测： CALL指令可以用BTB来进行预测，但return指令的目标地址总是等于最近一次CALL指令的下一条指令的地址，因此我们可以保存该地址，并且Last in first out, 也即一个堆栈，用来进行return指令的跳转地址预测，称为地址堆栈(return address stack, RAS)
- 在BTB中保存了所有发生跳转的分支指令，并且需要增加一项来标记分支指令的类型。
