CPU的冒险和预测
为什么叫做冒险
流水线设计中需要解决三大冒险问题，分别是结构冒险（Structural Hazard）、数据冒险（Data Hazard）和控制冒险（Control Hazard）。
搜索一下 Hazard 这个词，会发现它有两种词性，可以当名词讲，意思是危险，危害；也可以当动词，意思是冒....的风险；使处于危险。那么这里为什么当做冒险讲呢？
在 CPU 的流水线设计里，可能会遇到各种“危险”的情况，使流水线的下一条指令不能正常执行。但是，我们可以通过一些冒险的行为，拿到一个可能提升吞吐率的机会。这是我们为了提升 CPU 性能主动进行的冒险行为，而不是遇到一个致命错误后的解决方案。所以自然不需要翻译为危机了。
结构冒险
结构冒险本质上就是一个硬件层面的资源竞争问题，即硬件电路层面的问题。
CPU 在同一个时钟周期，同时在运行几条指令的不同阶段（Stage），有可能其中两个不同指令的阶段会用到同样的硬件电路。
典型例子就是内存的数据访问，看下面这张图。
同一个时钟周期，两个不同指令访问同一个资源
可以看出来，第一条指令的执行到第四个阶段访存（MEM）的时候，第四条指令执行第一个阶段取指（Fetch），访存和取指都需要读取内存的数据。而内存只有一个地址译码器作为地址输入，也就是在一个时钟周期内只能读取一条数据，没有办法同时执行第一条指令的读取内存数据和第四条指令的读取指令代码。
结构冒险一个直观的解决方案就是把内存分为两部分，一部分是存放指令的程序内存，另一部分是存放数据的数据内存。这种解决方案在计算机体系中被称为哈佛架构（Harvard Architecture），来自哈佛大学设计Mark I 型计算机时候的设计。与之对应的就是不拆分内存，这种架构被称为普林斯顿架构（Princeton Architecture）。
现代 CPU 虽然没有再内存层面进行对应的拆分，却在 CPU 内部的高速缓存部分进行了区分，把高速缓存分成了指令缓存（Instruction Cache）和数据缓存（Data Cache）。
几种CPU架构
内存的访问速度远比 CPU 的速度慢，所以现代的 CPU 并不会直接读取主内存。而是把主内存中的指令和数据加载到高速缓存中，这样后续的访问都是访问高速缓存。而指令缓存和数据缓存的拆分，使得我们的 CPU 在进行数据访问和取指令的时候，不会再发生资源冲突的问题。
数据冒险
分支冒险是硬件层面的问题，可以通过增加硬件资源来解决。而数据冒险是程序逻辑层面的问题，指的是在同时执行的多个指令之间，有数据依赖的情况。这些数据依赖，可以分为三大类，先写后读（Read After Write）、先读后写（Write After Read）、写后再写（Write After Wrtie）。
先写后读
int main(){
int a = 1;
int b = 2;
a = a + 2;
b = a + 3;
}输入以下指令反汇编这段代码
gcc -g -c test.c
objdump -d -M intel -S test.o// C的反汇编
int main(){
0: f3 0f 1e fa endbr64
4: 55 push rbp
5: 48 89 e5 mov rbp,rsp
int a = 1;
8: c7 45 f8 01 00 00 00 mov DWORD PTR [rbp-0x8],0x1
int b = 2;
f: c7 45 fc 02 00 00 00 mov DWORD PTR [rbp-0x4],0x2
a = a + 2;
16: 83 45 f8 02 add DWORD PTR [rbp-0x8],0x2
b = a + 3;
1a: 8b 45 f8 mov eax,DWORD PTR [rbp-0x8]
1d: 83 c0 03 add eax,0x3
20: 89 45 fc mov DWORD PTR [rbp-0x4],eax
23: b8 00 00 00 00 mov eax,0x0
}
28: 5d pop rbp
29: c3 ret可以看到，在内存地址为 16 的机器码，把 0x2添加到 rbp-0x8 对应的内存地址里面。接着，在内存地址为 1a 的机器码，又要从 rbp-0x8 这个内存地址里面，把数据写入到 eax 寄存器中。
所以就需要保证，在内存地址为 1a 的指令读取 rbp-0x8 里面的值之前，内存地址 16 的指令写入到 rbp-0x4 的操作必须完成，否则程序就会出错。
这个先写后读的依赖关系，一般称之为数据依赖（Data Dependency）。
先读后写
int main(){
int a = 1;
int b = 2;
a = b + a;
b = a + b;
}// C的反汇编
int main(){
0: f3 0f 1e fa endbr64
4: 55 push rbp
5: 48 89 e5 mov rbp,rsp
int a = 1;
8: c7 45 f8 01 00 00 00 mov DWORD PTR [rbp-0x8],0x1
int b = 2;
f: c7 45 fc 02 00 00 00 mov DWORD PTR [rbp-0x4],0x2
a = b + a;
16: 8b 45 fc mov eax,DWORD PTR [rbp-0x4]
19: 01 45 f8 add DWORD PTR [rbp-0x8],eax
b = a + b;
1c: 8b 45 f8 mov eax,DWORD PTR [rbp-0x8]
1f: 01 45 fc add DWORD PTR [rbp-0x4],eax
22: b8 00 00 00 00 mov eax,0x0
}
27: 5d pop rbp
28: c3 ret看地址为 19 的机器码，它把 eax 寄存器中的数据写入到 rbp-0x8，紧接着地址为 1c 处的机器码，又把 rbp-0x8 处的数据写入到 eax 寄存器中。
如果内存为 1c 处的 eax 写入先完成了，然后内存地址为 19 的代码执行取出 eax 寄存器数据的操作，程序就会出现问题。这个先读后写的依赖，叫做反依赖（Anti-Dependency）。
写后再写
int main(){
int a = 1;
a = 2;
}// C的反汇编
int main(){
0: f3 0f 1e fa endbr64
4: 55 push rbp
5: 48 89 e5 mov rbp,rsp
int a = 1;
8: c7 45 fc 01 00 00 00 mov DWORD PTR [rbp-0x4],0x1
a = 2;
f: c7 45 fc 02 00 00 00 mov DWORD PTR [rbp-0x4],0x2
16: b8 00 00 00 00 mov eax,0x0
}
1b: 5d pop rbp
1c: c3 ret内存地址 8 和内存地址 f 处的指令，都是将对应的数据写入到 rbp-0x4 内存地址中。如果内存地址 f 的指令在内存地址 8 指令之前写入，那程序就会出错。
这个写后再写的依赖，叫做输出依赖（Output Dependency）。
流水线停顿
除了读后再读之外，其他对于同一个寄存器或者内存地址的操作，都有明确强制的顺序要求。而这个顺序要求，也为我们使用流水线带来了很大的挑战。因为流水线架构的核心，就是在前一个指令还没有结束的时候，后面的指令就要开始执行。
所以，就需要有解决数据冒险的办法。其中，最简单也是最笨的办法就是流水线停顿（Pipeline Stall），也叫作流水线冒泡（Pipeline Bubbling）。
流水线停顿的思路很简单，就是如果发现后面执行的指令会有以上三种依赖关系，那就等一会。从逻辑层面，每条指令需要访问的地址都是确定的，CPU 中的冒险检测电路会检测出是否触发数据冒险，如果某条指令触发了数据冒险，那我们就可以决定，让整个流水线停顿一个或者多个周期。
CPU 的时钟信号会不停地在 0 和 1 之间自动切换。所以，CPU 并没有办法真的停顿下来。流水线的每一个操作步骤必须要干点事情。所以，在实践过程中，并不是真的让流水线停下来，而是在执行后面的操作步骤前面，插入一个 NOP 操作，也就是执行一个什么都不干的操作。
NOP 这个什么都不做的指令，就好像一个水管（Pipeline）里面，水流不停的流经每一个步骤，水流中间夹杂的 NOP 指令，就是一个空气泡，流到某个步骤的时候，没有把水送过来，所以什么都做不了。
操作数前推
再了解操作数前推之前，我们先了解一下指令对齐。
不同类型的指令，会在流水线的不同阶段进行不同的操作。以 MIPS 的体系架构举例。
指令类型 | 流水线阶段（Pipeline Stage） | ||||
|---|---|---|---|---|---|
LOAD | IF | ID | EX | MEM | WB |
STORE | IF | ID | EX | MEM | |
R型指令 | IF | ID | EX | WB | |
LOAD指令：从内存中读取数据到寄存器的操作，其中执行阶段（EX）会进行寻址的计算
STORE指令：从寄存器往内存中写数据，不需要有写回寄存器的操作，即没有数据写回（WB）阶段
R型指令：包括 ADD 和 SUB 这样的加减法指令，所有操作都在寄存器中完成，没有实际的访存操作（MEM）
有些指令没有对应的流水线阶段，但是我们不能跳过对应的阶段直接执行下一个阶段。不然，如果我们先后执行一条 LOAD 指令和一条 ADD 指令，就会发生 LOAD 指令的 WB 阶段和 ADD 指令的 WB 阶段，在同一个时钟周期发生，这相当于触发了结构冒险，产生了资源竞争。
所以在实际设计时，各个指令不需要的阶段，并不会直接跳过，而是会运行一次 NOP 操作。通过插入一个 NOP 操作，我们可以使后一条指令的每一个阶段（Stage），一定不和前一条指令的相同阶段（Stage）在一个时钟周期执行。这样，就避免先后执行的两条指令，在同一个时钟周期竞争相同的资源，产生结构冒险的问题。
指令类型 | 流水线阶段（Pipeline Stage） | ||||
|---|---|---|---|---|---|
LOAD | IF | ID | EX | MEM | WB |
STORE | IF | ID | EX | MEM | NOP |
R型指令 | IF | ID | EX | NOP | WB |
指令对齐需要插入 NOP 操作，流水线停顿也需要插入 NOP 操作。但是插入过多的 NOP 操作，表示 CPU 一直在空转，没有做什么有意义的工作。看下面的这个优化思路。
;汇编代码
add $t0, $s2,$s1
add $s2, $s1,$t0第一条指令，把 s1 和 s2 寄存器里面的数据相加，存入到 t0 这个寄存器中
第二条指令，把 s1 和 t0 寄存器里面的数据相加，存入到 s2 这个寄存器中
很明显可以看到，后一条指令的计算依赖前一条指令。所以后一条指令，需要等待前一条指令的数据写回阶段完成之后，才能执行，这意味着遇到了一个数据依赖类型的冒险。
流水线停顿是因为第二条指令的执行需要等待第一条指令的计算结果写回到寄存器中，其实不必非得等待第一条指令的计算结果写回寄存器，第二条指令才开始执行。只需要保证第二条指令的执行阶段（EX）能够拿到第一条指令的执行结果就可以。基于这个思路，我们完全可以将第一条指令执行阶段计算完成的数据直接传输到下一条指令，这样下一条指令不需要再插入两个 NOP 阶段才可以继续正常走到执行阶段。
这种解决方案，叫做操作数前推（Operand Forwarding）。或者叫做操作数旁路（Operand Bypassing）。
前推，指的是这个技术的逻辑含义，即将第一条指令的执行结果，往前推给第二条指令的 ALU 作为输入；旁路，指的是这个技术的硬件含义，为了实现前推的效果，在 CPU 的硬件里面，需要再单独拉一根信号传输的线路，使得 ALU 的计算结果，能够重新回到 ALU 的输入中。这样的线路就是旁路。它越过了写入寄存器，再从寄存器读出的过程，节省了 2 个时钟周期。
操作数前推的方案不但可以单独使用，还可以和流水线冒泡一起使用。比如说，先执行一条 LOAD 指令，再去执行 ADD 指令。LOAD 指令在访存阶段才能把数据读取出来，所以下一条指令的执行阶段，需要在访存阶段完成之后，才能进行。
乱序执行
操作数前推技术虽然可以减少插入 NOP 的次数，但是任然会遇到流水线停顿的情况。其实，前面讲解的技术全都是基于一个前提的，那就是指令是顺序执行的。在这个前提下，只要前面特定阶段还没有执行完成，后面的指令就会被“阻塞”住。
但是很多时候这个“阻塞”是没有必要的。因为尽管代码生成的指令是顺序的，但是如果后面的指令不需要依赖前面指令的执行结果，那完全可以不必等待前面的指令运算完成。看下面的例子。
int a = b + c;
int d = a * e;
int x = y * z;这个代码中，x 的计算是不依赖 a 和 d 的。但是如果按照顺序执行的话，需要等待 a 和 d 计算完成才可以计算 x。这完全没有必要，所以我们可以在 d 的计算等待 a 的计算的过程中，先把 x 的结果给算出来。
在流水线里，如果后面的指令不依赖前面的指令，那就不用等待前面的指令执行，它完全可以先执行。
可以看到，第三条指令并不依赖前两条指令的计算结果，所以在第二条指令等待第一条指令的访存和写回阶段的时候，第三条指令就已经执行完成了。这种技术就叫做乱序执行。
从今天开发的维度来思考，乱序执行好像是在指令的执行阶段，引入了一个“线程池”。使用了乱序执行的技术后，CPU 里的流水线就和之前看到的不太一样了。
在取指令和指令译码的时候，乱序执行的 CPU 和其他使用流水线架构的 CPU 是一样的。它会一级一级顺序地进行取指令和指令译码的工作。
在指令译码完成之后，CPU 不会像原来一样直接执行指令，而是进行一次指令分发，把指令分发到保留站（Reservation Stations）。就好像一列一列待命的火车。
保留站的指令不会立即执行，而是等待它们依赖的数据传递给它们之后才会执行。就好像一列列的火车要等到乘客来齐了之后才能出发。
指令依赖的数据到达之后，指令就交给后面的功能单元（Function Unit,FU）。这些功能单元可以并行运行，但是不同的功能单元能够支持的指令并不相同。
指令执行阶段完成后，会把结果存放到重排序缓冲区（Re-Order Buffer,ROB）。在这里，CPU 会按照取指令的顺序，对指令的计算结果重新排序。只要排在前面的指令都已经完成了，才会提交指令。完成整个指令的运算结果。
实际指令的计算结果数据，并不是直接写到内存或者高速缓存里，而是先写到存储缓冲区（Store Buffer）,最终才会写入到高速缓存和内存里。
可以看到，在乱序执行的情况下，只有 CPU 内部指令的执行层面，可能是乱序的。只要我们能在指令的译码阶段正确地分析出指令之间的数据依赖关系，这个乱序就只会在互相没有影响的指令之间发生。即便指令的执行过程是乱序的，在最终的指令的计算结果写入到寄存器和内存之前，依然会进行一次排序，以确保所有指令在外部看来仍然是有序完成的。
乱序执行技术，就好像在指令的执行阶段提供了一个“线程池”。指令不再是顺序执行的，而是根据池里拥有的资源，以及各个任务是否可以执行，进行动态调度。在执行完成之后，又重新把结果在一个队列里面按照指令的分发顺序重新排序。即使内部是“乱序”的，但是在外部看起来，仍然像是在顺序执行。
乱序执行，极大的提高了 CPU 的运行效率。核心原因是，现代 CPU 的运行速度比访问主内存的速度要快的多。如果完全按照顺序执行的方式，很多时间都会浪费在前面指令等待获取内存数据的时间里。CPU 不得不加入 NOP 操作进行空转。而现代 CPU 的流水线级数也已经相对比较深了，达到了 14 级。这意味着，同一个时钟周期内并行执行的指令数是很多的。乱序执行和高速缓存，弥补了 CPU 和内存之间的性能差异。同样也充分利用较深的流水线带来的并发性，使我们可以充分利用 CPU 的性能。
控制冒险
像 jmp 和 jle 这样的条件跳转指令，是无法确定下一条执行是否需要执行的。要等到 jmp 指令执行完成，去更新了 PC 寄存器后，CPU 才能知道是执行下一条指令还是跳转到其他的内存地址执行别的指令。为了确保能够取到正确的指令，而不得不进行等待延迟的情况，就叫控制冒险（Control Harzard）。
缩短分支延迟
条件跳转指令其实进行了两种电路操作
进行条件比较
进行实际的跳转
条件码比较的电路，只需要简单的逻辑门电路就可以了，并不需要一个完整而复杂的 ALU。所以，可以将条件判断、地址跳转都提前到指令译码阶段执行，而不需要放在指令执行阶段。对应的，需要再 CPU 里设计对应的旁路，在指令译码阶段，就提供对应的判断比较的电路。
缩短分支延迟本质上和数据冒险的操作数前推的解决方案类似。就是在硬件电路层面，把一些计算结果更早的反馈到流水线中。这样反馈变得更快了，后面的指令需要等待的时间就变短了。
不过只是改造硬件，并不能彻底解决问题。跳转指令的比较结果，仍然需要指令译码结束之后才知道结果。在流水线里，第一条指令进行指令译码的时钟周期里，其实就要取下一条指令了。这个时候，还没有开始指令比较，自然也不知道比较的结果。
分支预测
分支预测（Branch Prediction）技术是让 CPU 预测一下，条件跳转指令后应该去执行哪个指令。
最简单的分支预测技术，就是“假装分支不发生”。CPU 仍然按照原来的顺序，继续往下执行。实际上就是 CPU 预测，条件跳转一定不发生，无论是 if 分支或者 for/while 循环，下一次肯定不执行。这被称为静态预测技术，就好像猜硬币的时候，一直猜有国徽的一面，理论上说有 50% 的正确率。
如果分支预测正确，意味着我们节省下本来需要停顿下来等待的时间；如果分支预测失败，就需要把后面已经取出来开始执行的指令，将已经执行的部分给丢弃掉。这种丢弃操作，在流水线里面，叫做 Zap 或者 Flush。这些清除操作，也有一定的开销。只要这种清除操作的开销不是特别大，就是划得来的。
有静态分支预测策略，自然有对应的动态分支预测策略。动态分支预测的核心思想是：根据之前的预测结果预测。
如果我们需要预测明天的天气状况，一个简单的策略，就是根据今天的天气来预测。
上图是2022年7月份北京的天气情况。根据前一天的情况来预测下一天下雨情况。图中一共31天，可以预测30次，正确预测了20次，正确率是 66.7%，比随即预测 50% 好一点。
这样的预测策略，可以放在分支预测上。这种策略，叫做一级分支预测（One level Branch Prediction），或者叫 1比特饱和计数（1-bit saturating counter）。这种策略，其实就是用一个比特，记录当前分支的比较情况，直接使用当前分支的比较结果，来预测下一次分支的比较情况。
只用一天下雨，就预测第二天下雨，这个策略还是有点“草率”的。可以使用更多的信息，而不只是一次分支信息来进行预测。可以引入一个状态机（State Machine）来做这个事情。
如果连续发生连续下雨的情况，我们就认为更多可能下雨。之后如果只有一天放晴，我们仍然认为会下雨。在连续下雨之后，要连续两天放晴，才认为之后会放晴。下图是状态机的流转。
这个状态机里，一共有四个状态，所以需要 2 个比特来记录对应的状态。叫做 2 比特饱和计数，或者叫做双模型预测器（Bimodal Predictor）
使用这个策略重新预测一下上面的天气，共预测30次，预测成功25次，正确率83.3%。可以看到正确率较一级分支预测有所上升。请注意，某些情况下，双模型预测器的成功率与一级分支预测差不多甚至更低，实际的预测效果和实际执行的指令高度相关。
了解了分支预测，接下来看一个程序。
public class BranchPrediction {
public static void main(String[] args) {
long start = System.currentTimeMillis();
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 1000; j++) {
for (int k = 0; k < 10000; k++) {
}
}
}
long end = System.currentTimeMillis();
System.out.println("耗费时间：" + (end - start) + "ms");
start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
for (int j = 0; j < 1000; j++) {
for (int k = 0; k < 100; k++) {
}
}
}
end = System.currentTimeMillis();
System.out.println("耗费时间：" + (end - start) + "ms");
}
}两个三重 for 循环，使用两种不同的循环顺序各自执行一遍。看一下执行结果
耗费时间：0ms
耗费时间：16ms都是循环十亿次，第一段程序的执行时间不到1毫秒，而第二段程序的执行时间为16毫秒。执行效率差了十几倍甚至几十倍。
这个差异就和上面说的分支预测有关，循环其实是利用 cmp 和 jle 这样比较后跳转的指令来实现的。这些条件跳转指令上面介绍过，要比较条件码寄存器的状态，决定是顺序执行代码，还是要跳转到另外一个地址。即每一次循环发生的时候，都有一次“分支”。
分支预测最简单的一个方式是“假装分支不发生”。对应到上面的代码就是循环会始终执行下去。在这样的情况下，上面的第一段循环，也就是内层 k 循环 10000 次的代码，每隔 10000 次，才会发生一次预测上的错误。而这样的错误，在第二层 j 的循环发生的次数是1000 次。最外层的 i 循环是 100 次。所以一共发生 100 * 1000 = 10 万次。
同理，第二段代码会发生 1000 * 10000 = 1000 万次预测错误。
这就是为什么同样空转次数的循环代码，第一段代码运行的时间要少的多了。因为第一段代码发生“分支预测”错误的情况比较少，更多的计算机指令，在流水线里面顺序的运行下去了，而不需要把运行到一半的指令丢弃掉，再去加载新的指令执行。