[嵌入式]分支指令与分支预测

1.从汇编指令的逻辑理解分支跳转

这是一段C语言的if? else语句 ,它的执行过程非常简单，编译器会判断i和j的值是否相等，如果等，就执行f=g+h，否则执行f=g-h。那么MIPS的汇编代码是如何实现的呢？

if（i== j)
    f = g + h;
else    
    f = g -  h;

下边是对应的MIPS的汇编代码,编译器已经把i和j放到了s3和s4两个寄存器中，把g和h放到了s1和s2两个寄存器中，如果s3和s4两个寄存器的内容相等，就会跳转到add这条指令处执行；如果不等，就不发生分支转移，而是顺序执行后一条指令即这条sub指令对应的就是C语言中的else这条语句。执行完这条语句后，下一条指令是一条无条件的转移指令，直接跳到Next，这就是条件分支指令的MIPS汇编实现。

beq $s3, $s4, True              # branch  i == j
sub $s0, $s1, $s2               # f = g - h (flase) 
j Next                          # goto Next

True：add $s0, $s1, $s2         # f = g + h (true)
Next: ……

2.beq指令的执行过程

在MIPS指令系统中，分支指令需要占4个时钟周期，取指令周期，指令译码周期，执行有效地址计算周期和分支完成周期。

第一步 ：取指令，从PC所指的内存单元取出待执行的指令，同时PC+4指向下一条待执行的指令地址处

第二步：指令译码周期，根据MIPS的固定字段译码技术，根据操作码得知这是一条跳转指令，根据寄存器编号读取相应的寄存器的值，把低16位的Imm有符号扩展到32位。

第三步：有效地址计算

分支判断：判断 rs 和 rt 两个寄存器的内容是否相等，将判断结果存入临时寄存器Cond中

?if(rs - rt == 0)Cond = 1; else Cond = 0;

有效地址计算：更新程序计数器PC的值，跳转指令中imm立即数存放的是PC所指的当前待指令到跳转指令之间的指令条数，MIPS指令系统是32位的即一条指令占4字节，新的转移地址的计算公式如下：

PC = PC + 4 + SignExt[imm16] * 4

?第四步：分支完成周期,完成PC值的更新操作

???if(Cond == 1)
         PC = PC + 4 + SignExt[imm16] * 4;
    else
         PC = PC + 4;

3.分支跳转成功浪费三个时钟周期

从上述过程我们可以知道，只有在第四个周期分支指令才能得到新的PC值，也就是只有经过三个周期后才能读取跳转的指令。

在指令流水线中，在IF取指阶段会将PC值自动加4跳转到当前执行指令的下一条指令处，那么在流水线中会继续向下读取指令，分支指令在MEM段执行 后才能读取到跳转指令的地址，在第一条指令的ID，EX和MEM三个时钟周期中，流水线会顺序向下读取三条指令，但是分支跳转成功时，程序会发生跳转，会停止中间读取的这三条指令的执行，此时就是浪费三个时钟周期。

4.如何减少分支指令的时间开销

思考：上述流水线为何会浪费三个时钟周期？原因何在？（是因为分支指令更新PC值太慢了）

优化思路：将新的跳转地址的计算和分支跳转成功判断提前

改进1：

• 将“=0?”测试提前到ID段
• 在ID段增加一个加法器，计算分支目标地址

此时的流水线就是这样的，分支跳转提前了一个时钟周期，在第三段执行后就能将跳转指令地址更新到PC中，减少了一个时钟周期的开销

?再改进2：

• 将分支判断结果和目标地址提前到ID/EX站前

此时的流水线就可以是这样的，分支跳转在ID阶段就可以得到更新的PC值，又减少了一个时钟周期的开销

总体来看，分支操作提前两个时钟周期完成，减少了2个时钟周期的开销，中间还有一拍是分支操作的时间开销，它已经不能再减少了。

5.还能再减少流水线的分支损失吗？

(1)冻结或排空流水线

思路：在流水线中停住或删除分支后的指令，知道转移目标地址?

优点：结构简单

缺点：需要暂停，有时间的浪费

(2)预测分支转移失败

思路：流水线继续照常流动，如果分支转移成功，将分支指令后的指令转换成空操作，并从 分支目标处开始取指令执行，否则照常执行。

分支转移是失败，虽然读取的第i+1条指令周期顺序读的，因为分支转移时失败的，所以这条指令就是需要顺序执行的下一条指令，可以正常执行。

?当分支转移成功时，当前指令是i，顺序读取第i+1条指令，分支转移成功跳转到第j条指令处，取到跳转的指令后，前边顺序读取的第i+1条指令就作废掉了，清空然后转移到跳转的指令处执行了。

分支转移失败和成功就差一个时钟周期，这个时钟周期也是我们可以挖掘的潜力，优化的着手点。

(3)预测分支转移成功

思路：始终假设分支成功，直接从分支转移的目标处取指令执行

对应分支转移失败来说取指的方向不一样，但是这对MIPS流水线没有任何好处

(4)延迟分支

思路：分支开销为n的分支指令后紧跟着有n个延迟槽，流水线遇到分支指令时，按正常方式处理，顺带执行延迟槽中的指令，从而减少分支开销。

延迟槽中的指令是可以前后调度过来，不影响系统程序运行。

分支指令后有n条指令需要等待的话，分支指令后就有n个延迟槽，失败时，继续顺序执行；成功时，跳转到j指令处执行；

无论分支失败还是成功，这几条指令都是有效的和其他指令不想关的，不影响程序的正确性。这就是延迟分支的思路，把这个延迟槽占用，用来执行和分支成功或失败都不想关的指令。

?MIPS流水线具有一个分支延迟槽的情况：

?什么样的指令可以放入分支延迟槽呢？

三种调度方法：从前调度，从目标处调度，从失败处调度

?三种方法的要求及效果：

从前调度：要求被调度的指令与分支结果无关即可，任何情况都适用

从目标处调度：必须保证在分支失败时执行被调度指令不会导致错误，可能需要复制指令，也就是也许需要重复执行一遍但是不能导致错误，适用与分支预测成功概率较高的情况。

从失败处调度：必须保证在分支成功时执行被调度指令不会导致错误，适用于分支失败预测较多的情况。

编译分支预测是否成功的概率以及选择何种指令放入延迟槽对延迟分支都是至关重要的。

• 取消分支

思路：分支指令中包含预测方向，若预测正确，正常执行延迟槽中的指令，否则将其转换为空操作。

6.如何预测分支是否成功呢？

分支预测技术是指处理器在遇到分支指令时不再傻傻地等待分支结果，而是直接在取指阶段预测分支“跳”或者“不跳”以及跳转目标地址，目的是根据预测结果来实现不间断的指令流，从而让处理器的CPI再度接近理想情况中的1?.

(1)静态预测

要进行分支预测，就是要预测分支跳还是不跳，最简单的一种思想就是预测一直跳或一直不跳，这样的方法虽然很简单，但是也比完全不预测要高明。完全不预测意味着在发生分支跳转的时候会100%阻断流水线，而预测一直跳或者预测一直不跳还有机会预测对，预测对就是赚到了，因为我们可以在这个时钟周期采用延迟分支调度与当前指令 不相关的指令把这一个时钟周期利用起来。

假设一个1000次的for循环，这个循环前999次都是跳转，最后一次是不跳转，如果预测设置为一定跳转，那么执行这段指令的时候分支预测准确率高达99%，性能远远高于不做分支预测的情况。

(2)根据最后一次结果进行预测

静态分支预测虽然要比不预测的时候好，但是性能并不是很好，比如，当我们预测分支一直跳的时候，在遇到分支不跳转的情况，错误率就高达100%，可见静态分支预测不灵活的特点使其性能受到了影响。一种简单的思想就是根据上一次分支指令的执行情况来预测当前分支指令，如果上一次分支不跳转，那么下一次碰到这条指令就预测不跳转，用这个方法预测不跳转的话，正确率就高达100%.

(3)基于两位饱和计数器的预测

根据最后一次结果进行预测确实有一些效果，但是当遇到分支跳转和不跳转交替出现的情况时，正确率又可能降低到 0%，还不如静态预测，静态预测可能还又50%及以上的正确率。

解决的办法是：基于两位饱和计数器的预测，两位饱和计数器用一个状态机来表示，如下图所示

两位饱和计数器包含四种状态：00、01、10、11。其中00 、01表示不跳转，10、11表示跳转。

00表示强不跳转，当计数器处于这个状态，分支预测不跳转，如果预测正确，计数器保持计数值，如果预测错误，状态转变为01，即弱不跳转。

当计数器处于01弱不跳转状态时，如果仍然预测分支不跳转，预测正确，状态转变回00，如果预测错误，状态 转变为弱跳转10。

当计数器处于10弱跳转状态时，分支预测跳转，如果预测正确，状态转变为强跳转11；如果预测 失败，状态转变为弱不跳转01；

在强跳转状态11下，分支预测跳转，如果预测成功，状态保持不变，如果预测错误，状态转变为弱跳转10。

分支预测更多的内容可参考

计算机体系结构-分支预测 - 知乎 (zhihu.com)