CPU Study - Branch Prediction

参考来源：《超标量处理器设计》—— 姚永斌

分支指令

IFetch取指阶段，除了需要从I-Cache获取指令，还需要决定下个周期的取指令地址。
如果不执行分支预测，全部顺序执行指令，那么发生指令跳转时，就需要把流水线中的执行阶段之前的全部指令移除。
对于流水线深度较深的处理器是难以接受的，因此需要在硬件消耗、预测准确度和延时之间确认一个平衡点。
分支预测就是为了再取指阶段确定分支指令的方向和跳转地址信息，便于在下个周期从分支目标地址开始取指。

RISC中分支指令包含两个元素：

方向
发生跳转（taken）/ 不发生跳转（not taken）
MIPS - jump：总是跳转
MIPS - BEQ：指定两个数值相等则跳转

目标地址
一般被携带在指令中

PC relative 直接跳转
给出相对于PC的偏移值offset，会被指令长度限制，范围不大但是便于计算。
一般在解码decode阶段就可以分离出此数据并计算分支指令的目标地址。

Absolute 间接跳转
分支指令目标地址源于一个通用寄存器，寄存器编号由指令给出。
扩大了范围，但是选哟等待其他指令结果赋值到寄存器（例如等待流水线的execute阶段）。
一旦预测失败，会增大惩罚，适用于CALL/Return这类具有较强规律性的预测。

分支预测

基于上面对跳转指令的分析，对于分支预测而言，需要基于指令在过去时间的执行情况动态调整对指令的方向和地址信息的预测内容。
从I-Cache取指令后快速解码，值判断指令是否为分支指令，如果是分支指令则将对应的PC送入分支预测器（Branch Predictor）。

为了避免占用过的的处理器周期，可以在指令从L2 Cache写入I-Cache之前进行预解码（pre-decode）。
然后将是否为分支指令的信息放入I-Cache，虽然更加占用空间，但是能够缓解处理器周期占用。

对于一条指令来说，它的物理内存地址是可能变化的（取决于操作系统的存放替换行为），但是虚拟地址是不变的（除非进程回收）。
并且因为一个PC不可能对应多条指令，所以可以使用PC值进行分支预测，如下图所示。

并且因为程序一旦开始执行之后，PC值就会确定，每条CPU指令对应的取指地址也就固定了。
而如果当后续再执行到这个PC值时，就可以直接确定是否为分支指令。
但是这条分支指令的方向和目标地址等信息，还需要其他预测方法。

而分支预测本身的设计还是比较复杂的，需要在硬件资源占用、预测精度和延时之间找到合适的取舍。
并且由于超标量处理器每个周期会取出多条指令，所以还会出现不同的分支预测设计和预测失败的处理方法，在本专栏其他文章中会介绍。