Quartz 4

book - ch4 分支预测

17 min read

Ch4 分支预测

4.1 概述

分支指令之所以能够被实现，是由分支指令的特性决定的，因为分支预测本质上是对分支指令的结果进行预测，一般的分支指令包含两个要素：

  1. 方向：发生跳转 taken 和不发生跳转 not taken。有些分支指令是无条件执行的，如 jump，即总发生跳转，其他分支指令需要根据条件决定是否发生跳转，如 beq。
  2. 目标地址：这个地址也是携带在指令中，一般对于 RISC 指令集，目标地址在指令中可以有两种存在形式：
  • PC relative，也称直接跳转 direct，在指令中直接以立即数的形式给出相对于 PC 的偏移值 offset，当前分支的 PC 值（或者分支指令的下一条指令的 PC 值）加上这个偏移值就可以得到分支指令的目标地址。

Note

指令长度会限制立即数的大小范围，这种分支的跳转范围不大，但由于信息直接携带在指令中，很容易计算出目标地址，如在 decode 阶段将指令中的立即数分离出来。而且，由于指令的立即数一般不会变化，因此这类型的分支指令容易进行分支预测，很多处理器的手册也会建议尽量使用这种类型的分支指令，就是为了提高分支预测的正确率。

  • Absolute，也称间接跳转 indirect，分支指令的目标地址来自于一个通用寄存器的值，这个寄存器的编号由指令给出，它的目标地址是 32 位的值，因此可以跳转到处理器程序空间的任意地方。 但是这个通用寄存器的值一般来自其他指令的结果，因此对于分支指令来说，可能需要等待一段时间才可以得到这个目标结果，例如需要等到流水线的执行阶段，在这个时间内进入流水线的指令都可能是不正确的，这就增大了分支预测失败的惩罚 misprediction penalty。而且由于寄存器的值是会经常变化的，因此这种类型的分支指令很难对目标地址进行预测。但庆幸的是，程序中大部分间接跳转的分支指令都是用来调用子程序的 CALL/Return 类型的指令，而这种类型的指令由于有很强的规律性，是容易被预测的。除了 CALL/Return 指令外，一般的处理器都不会推荐使用间接跳转类型的分支指令。

对分支指令的预测就包含这这两方面特性。普通处理器的流水线深度不深，一般采用静态的分支预测方式，预测分支指令总是不执行，处理器总是顺序地取指令，在流水线的后续阶段，如执行阶段，得到了分支指令的实际方向和目标地址后，在进行判断。如果发生跳转，则抛弃在分支指令后进入流水线的所有指令；如果不发生跳转，则顺序地取指令来执行。

流水线短的处理器，分支预测失败并不会引起流水线过多指令被抛弃，如五级流水线，预测失败，流水线中只有取指令阶段的一条指令需要被抛弃。

而且，MIPS 为了减少这一周期的浪费，在分支指令后会放一条不相关的指令，这条指令总会被执行，无论分支指令是否发生跳转，被称为分支延迟槽 branch delay slot，需要编译器或者程序员从分支指令之前的指令找到一条不相关的指令放到言辞操的位置。这里只需要一条指令，找到一条指令还比较容易，后来发现随着处理器并行度的提高以及流水线的加深，分支指令预测失败时，流水线中很多指令都错误地进入了流水线中，需要被抛弃，即使采用延迟槽也难得到满意的结果，因为无法从分支指令之前的程序找到这么多不相关的指令。明显，这种只是预测分支指令不发生跳转的静态分支预测已经不能满足要求，需要更具处理器实际的执行情况，动态的对分支指令进行预测，即动态分支预测。

要进行分支预测，首先需要识别出取出的指令是否是分支指令，对于超标量处理器，需要从指令组 fetch group 中找出分支指令，如图：

容易想到，将指令组中的指令从 I-Cache 中取出后进行快速解码，只需要辨别解码指令是否为分支指令，然后找到分支指令对应的 PC 值送到分支预测器 branch predictor 中，就可以对分支指令进行预测了。当处理器周期时间比较小时，I-Cache 的访问可能需要多个周期才可以完成，采用快速解码 fast decode 预测，从开始取指令到分支预测得到结果中间需要间隔好几个周期，在这些周期内无法得到准确的预测结果，只能顺序地取指令，相当于这些周期都是预测分支指令不发生跳转，这降低了分支预测准确度。而且，快速解码和分支预测都放在了一个周期，影响了周期时间。

为解决这个问题，可以在指令从 L 2 Cache 写入 I-Cache 之前快速解码，也称预解码 pre-decode，然后将指令是否为分支指令的信息和指令一起写道 I-Cache，虽然这样会让 I-Cache 占用更多面积，但是可以省掉快速解码电路，一定程度缓解对处理器周期时间的影响。不过取指令到分支预测得到结果这两个阶段的间隔时间仍很长无法解决。

在流水线中，分支预测越靠前越好，如果指令从 I-Cache 取出来后才进行预测，如图 4.3，那么由于 I-Cache 中去除指令的过程可能需要多于一个周期才能完成，当得到分支预测结果时，已经有很多后续指令进入流水线，当得到预测值是要发生跳转时，这些指令都需要从流水线中抹掉 flush，这届降低了处理器的执行效率。因此分支预测的最好时机是在当前周期得到取指令地址时，在取指令的同时进行分支预测，这样在下个周期就可以根据预测的结果继续取指令。

对一条指令来说，它的物理地址是会变化的（取决于操作系统将它放到物理内存的位置），而它的虚拟地址，也就是 PC 值，是不会发生变化的。因为在一个进程中，每一个 PC 值对应的指令是固定的，不可能出现一个 PC 值对应多条指令的情况，所以可以使用 PC 值进行分支预测，只不过要在进行进程切换之后，需要将分支预测器中的内容进行清空，保证不同进程之间的分支预测不会相互干扰。若果使用了 ASID，可以将它和 PC 值一起进行分支预测，此时就不需要再进程切换时清空分支预测器了。

在 PC 值刚刚产生的那个周期，根据这个 PC 值来预测本周起的指令组 fetch group 中是否存在分支之狂，以及分支指令的方向和目标地址，如图 4.4 所示。

基于取指令的地址（取指令的 PC 值）进行分支预测是有根据的，因为一旦程序开始执行，每条指令对应的取指令地址也固定了，因此完全可以根据一条指令的 PC 值来判断这条指令是否为分支指令。只要这条指令第一次被执行完后，后面再次遇到这个 PC 值，就知道当前要取的指令是分支指令，即使发生了自修改 self-modifying 的情况，也会将分支预测器清空，重新开始进行分支预测，并不影响分支预测的过程。

分支预测本身比较复杂，是影响一款处理器性能的关键因素，需要在硬件消耗、预测准度、延迟 latency 之间折衷。

4.2 分支指令的方向预测

分支指令的方向只有两个：发生跳转（taken）和不发生跳转（not take），用 1 和 0 表示。很多分支指令的方向是有规律可寻的，如：

for (i = 0; i < 1000; i++) {
}

for 对应的分支指令会跳转 1000 次。

动态分支预测的一个主要方面是对方向预测，其方法可繁可简。最近简单的方法是直接使用上次分支的结果，称为根据最后一次的结果进行预测（last-outcome prediction）。相比静态分支预测，很多情况可以获得更优结果，但当分支指令的方向发生变化时，仍会引起预测失败。当分支方向变化频繁时预测准确率变得很差。现代处理器中最广泛的分支预测方法都是基于两位饱和计数器（2-bit saturating counter），并以之为基础引申出的各种方法。

4.2.1 基于两位饱和计数器的分支预测

这种方法更具一条分支指令前两次的结果来预测本次的方向，可以用 4 状态的状态机表示：

  1. Strongly taken：饱和状态，本次预测 taken 11；
  2. Weakly taken：不饱和，本次预测 taken 10；
  3. Weakly not taken：不饱和，本次预测 not taken 01；
  4. Strongly not taken：饱和，本次预测 not taken 00。 状态机处于饱和状态时，只要两次预测失败才会改变预测结果。分支总朝着一个方向时，状态机会处于饱和，此时预测正确率较高；但是分支的方向总是变化时，状态机无法处于饱和状态，预测正确率较低。图 4.8 只是基于两位饱和计数器的一种，事实上可以有很多实现方式。对一般的基准测试 benchark，图 4.9 并不会有更优的结果，因此使用并不广泛。状态机的初始状态可以任意，需要根据情况来定，一般使用 00 或 01。 可以使用格雷码对状态机编码，保证在状态转换时每次只有一位发生变化，减少出错的概率降低功耗。两个饱和状态计数器打到最值，若分支方向不变，状态会停留在原地，即为饱和。两位饱和由于上一次结构的分支预测方法，如考虑下面：
for (i = 0; i < m; i++){
}

第一次执行，假设处于 Wekly not taken，预测错误；状态跳转到 Weakly taken，最后稳定在 Strongly taken，直到循环第二次到 m-1 次，分支预测都正确。在最后一次循环的最后一次错误，这时不跳转了。因此整个循环产生了两次错误，出错概率 。再次执行该循环，第一次预测也正确，只有循环的最后一次错误，此次错误概率 。

基于两位饱和计数器的分支预测核心理念就是当一条分支指令连续两次执行方向一样时，下一次也有同样的方向；若一条指令只是偶尔发生一次变化，这个预测值不会马上变化。这种方法已经可以获得较高正确率，增加计数器位宽会引起复杂度上升和存储需求，额外开销大于实际精度提高。

分支预测以 PC 值为基础的，如果每一个 PC 值都对应一个两位饱和计数器，32 位 PC 需要 大小存储器，显然不现实。考虑不是所有指令都是分支指令，一般采用下图方法。

, 如果是需要送入方向和地址预测模块:

  • 分支预测最好的时机就是当前周期取到指令地址的时候, 就进行预测, 这样就可以在下个周期根据预测结果取指
  • 进行分支预测的 PC 实际是虚拟地址, 在一个进程内 PC 值对应唯一一条指令, 只不过在进程切换后需要将分支预测器的内容清空, 才能保证不同进程互不干扰.

Graph View

Backlinks