何为分支预测
Categories:
为何需要分支预测？
分支预测主要有两方面的原因：一是程序的执行流中含有分支指令，二是高性能处理器使用流水线设计。
程序的执行流中含有分支指令
int x = 10;
int y = 20;
int result = 0;
if (x >= y) {
result = x + y;
} else {
result = x - y;
}
上述是一段C语言代码，这段代码首先定义了三个变量 x, y 和 result，然后根据 x 和 y 值的大小情况对result进行赋值。可以发现，程序在前三行对变量进行赋值时是顺序往下执行的，而在第 5 行时，由于 if 指令的出现，程序产生了分支，从第 5 行直接跳转到了第 8 行继续运行，这就造成了程序执行的分支。
翻译成 RISC-V 汇编之后的代码如下：
li a0, 10 # x = 10
li a1, 20 # y = 20
li a2, 0 # result = 0
blt a0, a1, else_branch # 如果 x < y，则跳转到 else_branch
add a2, a0, a1 # 否则执行 result = x + y
j end # 跳转到 end
else_branch:
sub a2, a0, a1 # result = x - y
end:
可以发现程序依然保持着先前的分支行为，在代码的前三行，指令顺序执行，之后，在程序的第 5 行，出现了一条特殊指令blt ，我们称之为分支指令，它会根据 x 和 y 的大小关系决定指令流顺序往下执行还是跳转到其他地方，该指令的出现导致程序的执行出现了分支。
高性能处理器使用流水线设计
因此有了分支预测的概念，如果我们可以在执行结果产生之前，精准的预测出下一条指令的地址，便可以使处理器一直高效的运行下去。
分支预测的可行性
为什么可以进行分支预测呢？我们看接下来一个例子
if (data >= 128)
sum += data;
假设该条指令将被重复执行，并且 data 从 0 开始递增，即 data = 0, 1, 2, 3 … 128, 129…，接下来我们可以分析每次执行这条指令的行为。
T = branch taken
N = branch not taken
data = 0, 1, 2, 3, s, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (easy to predict)
可以看出，在前 128 次，该分支都是 Not Taken （条件不成立）的，但在 128 次之后，分支一直都是 Taken （条件成立）的。如果我们用最简单的方法根据上一次是否 Taken，来预测本次是否 Taken，在整个预测过程中，我们只会产生一次预测错误。
上述现象的产生是源于一个基本事实的——分支指令是否跳转与该条指令以往的跳转行为有关联，我们通过总结以往跳转的规律，便可以对本次跳转产生较为精准的预测，这也使得分支预测变得可能。
事实上，分支指令的跳转还会与其他分支指令的跳转情况等因素相关，充分发掘有效信息，产生精准预测结果，是分支预测的主要任务之一。
分支预测的基本类型
在RISC-V 中，分支指令包含两种类型：
- 条件分支指令 (beq, bne, blt, bge, bltu, bgeu) 对于这类指令，是否跳转时候其中的条件决定，跳转目标可以在指令中获取，因此我们需要预测该指令是否跳转
- 无条件跳转指令 (jal, jalr) 对于这类指令，每当执行到它时是总是跳转，但跳转目标有可能由寄存器执行，因此我们需要预测该指令的跳转地址。
幸运的是，由于RISC-V架构设计的简洁，我们不需要处理条件跳转指令，每一个需要我们预测的跳转指令都是无条件的，这也给我们的设计提供了便利。
上述分析中，我们可以总结出分支预测的两大基本类型——方向预测 和 目标地址预测。
分支指令的方向预测
分支指令的方向预测对应到 RISC-V 指令就是条件分支指令，我们需要预测它是否需要跳转，也就是分支的方向，因此叫做方向预测。
两位饱和计数器
方向预测有一种非常简单并且十分高效的预测方法，叫做叫做饱和计数器法，它的大致思想可以参考下图。
两位饱和计数器被视作一个状态机，我们为每一个分支指令都维护这样一个状态机器，当一条分支指令发生跳转时，对应上图中的状态向右移动，否则状态向左移动。这样在下次遇到这条分支指令时，我们首先查找到它的两位饱和计数器，如果状态更偏右则预测其跳转，否则预测其不跳转。
当然，为每一条分支指令都维护一个两位饱和计数器是不现实的，因此在实际中，我们通常会采取PC部分位，或哈希的方法来索引两位饱和计数器，如下图所示。
分支历史
分支历史是方向预测中非常常用的数据，也是大多分支预测算法的基础，因为分支历史是指令以往跳转行为最直接的展示。
分支历史有以下两种基本类型：
- 局部分支历史 为每一条分支指令维护一组寄存器，记录该条指令的历史跳转情况
- 例如： 0101000000101 （0代表不跳转，1代表跳转）
- 全局分支历史 所有指令共用一组寄存器，记录程序执行过程中的分支跳转情况
-
例如：
beg a0, a1, label1 不跳转 记录0 bne a1, a2, label2 不跳转 记录0 -> beq a2, a3, label4 跳转 记录1执行完三条不同的分支指令后，全局分支历史变为 001
-
分支指令的目标地址预测
RISC-V架构中，分支指令的目标地址预测是指对无条件跳转指令（如jal、jalr）的跳转目标地址进行预测。由于这类指令总是执行跳转操作，我们需要预测其跳转的目标地址。
分支目标缓存（BTB）
BTB 是目标地址预测的一种常用方法，它的核心思想是使用一个缓存来存储以往无条件跳转指令的跳转目标，之后如果再次执行到这一条无条件跳转指令，就可以查看BTB中是存在该指令的记录，将记录的跳转目标作为本次预测的跳转目标。
示意图如下
预测指令类型
我们已经知道，在分支预测中，对于条件分支指令来说，我们需要预测其方向，对于无条件跳转指令来说，我们需要预测其跳转目标。但是出现了一个问题，拿到一个需要预测的PC之后，我们并不清楚这个PC所对应的指令是什么，也就是说我们根本不知道当前指令到底是一条普通指令还是一条分支指令，也就无法进行预测了。
如何解决呢？可以采取的一种方法是，在取出指令之后，对这条指令的行为进行预测。但取值需要从 ICache 或 Memory 中去取，有可能会耗费多个周期，这是这种方法的一大弊端。
更好的一种方法是，直接预测指令的类型，拿到一个PC之后，可以直接预测出这条指令是否是分支指令，并对指令行为进行预测。这样一来，我们就没有必要等待取值完成，并且预测出来的结果还可以指导 CPU 到什么地方去取值。
类型预测的方法，可以与BTB相似，在缓存中的某个字段中加入指令的类型，以供下一次预测使用。
分支预测的一般步骤
通过本节知识的介绍，我们可以总结出分支预测的一般步骤
- 获取 PC
- 预测是否是分支指令
- 如果是条件分支指令，预测其跳转方向和跳转目标
- 如果是无条件跳转指令 ，预测其跳转目标
注意，由于在预测中需要预测指令类型，没有获取到指令具体内容，所以对于条件分支指令来说，预测它的跳转目标也变成了我们的工作。