一个准确度很高的分支预测器branch predictor是提高处理器性能的关键部件。但是在现实世界中,准确度高意味着更复杂的算法,也就是占用更多的硅片面积和消耗更多的功耗,同时,还会影响处理器的周期时间。更不幸的是,不同的程序会呈现不同的特性,因此很难找到一种放之四海而皆准的分支预测算法。
如果能够在取指令阶段,就可以“预知”本周期所取出的指令是否存在分支指令,并且可以知道它的方向(跳转或者不跳转),以及目标地址(target address)的话,那么就可以在下个周期从分支指令的目标地址开始取指令,这样就不会对流水线产生影响,也就避免了做无用功。
这样不用等到分支指令的结果真被计算出来,而是提前就预测结果的过程就是分支预测。
分支预测之所以能够实现,是由分支指令的特性决定的,
分支指令包含两个要素:
(1)方向,对于一个分支指令来说,它的方向只可能有两种,一种是发生跳转(taken),另一种是不发生跳转(not token)。而有些分支指令是无条件执行的,例如jump指令
(2)目标地址,如果分支指令的方向发生跳转,就需要知道它跳转到哪里,这个目标地址也是携带在指令中,对于RISC指令集来说,目标地址在指令中可以有两种存在形式:
a:PC relative,也称为直接跳转(direct)。在指令中直接以立即数的形式给出一个相对PC的偏移值offset,当前分支指令的PC值(或者分支指令的下一条指令的PC值)加上这个偏移值就可以得到分支指令的目标地址。由于指令长度32位,它限制了立即数的大小范围,因此这种类型的分支指令,它的跳转范围一般不大。例如在流水线的解码decode阶段就可将指令中的立即数分离出来,进而计算出分支指令的目标地址。由于所携带的立即数一般是不会变化的,因此这种类型是容易进行分支预测的,很多处理器手册建议尽量使用这种类型的分支指令,就是为了提高分支预测的正确率,从而提高处理器的性能。
b:absolute,也称为间接跳转indirect。分支指令的目标地址来自于一个通用寄存器的值,这个寄存器的编号由指令给出,它的目标地址是32位的值,因此可以跳转到处理器程序中间中任意地方。但是,这个通用寄存器的值一般来自于其他指令的结果,因此对于分支指令来说,可能需要等待一段时间才可以得到这个目标地址,例如需要等到流水线的执行execute阶段,在这段时间内进入到流水线中的指令都是有可能不正确的,这就增大了分支预测失败时的惩罚misprediction penalty。程序中大部分间接跳转的分支指令都是用来调用子程序的CALL/Return,而这种类型的指令由于有着很强的规律性,是容易被预测的。
由于分支指令有着方向和目标地址两方面。对方向预测而言,需要预测这条指令是否会发生跳转,对于目标地址的预测来说,需要预测这条分支指令在发生跳转时的目标地址。对于普通处理器来说,由于它的流水线深度并不深,一般都是使用静态的分支预测方式,预测分支指令总是不执行,处理器总是顺序地取指令,在流水线的后续阶段,例如执行阶段,得到分支指令实际的方向和目标地址后,再进行判断。如果分支指令需要跳转,抛弃在分支指令之后进入到流水线的所有指令;如果不跳转,则继续顺序地取指令来执行,就好像这条分支指令从来未发生过。
对于流水线比较短的简单处理器,分支预测失败时并不会引起流水线中过多的指令被抛弃。
而且,MIPS处理器wield减少一个周期的浪费,在分支指令之后会放置一条不相关的指令,这条指令总是会被执行,而不管分支指令是否发生跳转,分支指令之后的那个位置就被MIPS称为分支延迟槽branch delay slot。
根据处理器实际的执行情况,动态地对分支指令进行预测,这就是动态分支预测。动态分支预测需要消耗不菲的硬件资源。
要进行分支预测,首先需要知道从I-Cache取出来的指令中,那条指令时分支指令,这对于每周期取出多条指令的超标量处理器来说,更为不容易。
最容易想到的办法是将指令组中的指令从I-Cache取出来之后,进行快速的解码,之所以称为快速,是因为只需要辨别解码指令是否分支指令,然后将找到的分支指令对应的PC值送到分支预测器branch predictor。
指令快速解码fast decaode和分支预测都放在同一个周期,严重影响了处理器的周期时间。为了解决这个问题,可以在指令从L2 Cache写入到I-Cache之前进行快速解码,被称之为预解码pre-decode,然后将指令是否是分支指令的信息和指令一起写到I-Cache中,这样会使I-Cache占用更多的面积,但是可以省掉快速解码电路,在一定程度上缓解对处理器周期时间的影响。但是,取指令知道分支预测得到结果这两个阶段的间隔时间仍然是过长的,无法得到解决。
在流水线中,分支预测是越靠前越好,如果指令从I-Cache取出来之后才进行分支预测,当得到预测结果时,已经有很多后续的指令进入了流水线,当得到的预测值是要发生跳转时,这些指令都需要从流水线中flush,降低了处理器的执行效率。因此分支预测的最好时机就是根据当前周期得到取指令地址的时候,在取指令的同时进行分支预测,这样在下个周期就可以根据预测的结果继续取指令。
对于一条指令来说,它的物理地址是会变化的(这取决于操作系统将它放到物理内存的位置),而它的虚拟地址在,也就是PC值,是不会变化的。
在进行进程切换之后,需要将分支预测器中的内容进行清空,这样可以保证不同进程之间的分支预测不会互相干扰。如果使用了ASID,那么可以将它和PC值一起进行分支预测,此时就不需要在进程切换时清空分支预测器。
根据PC值来预测本周期的指令组是否存在分支指令,以及分支指令的方向和目标地址,这个过程如下:
基于取指令的地址进行分支预测是由根据的,因为一旦程序开始执行,每条指令对应的取指令地址也就固定好了,因此完全可以根据一条指令的PC值来判断这条指令是否是分支指令。只要这条分支指令第一次被执行完之后,当后面再次遇到这个PC值,就可以知道当前要取的指令是分支指令。
分支预测本身是比较复杂的,不同的处理器有不同的实现方法,它使影响一款处理器性能高低的关键因素之一,以便在硬件消耗、预测准确度和延迟latency之间找到一个平衡点。