结构冒险

结构冒险，本质上是一个硬件层面的资源竞争问题，也就是一个硬件电路层面的问题。CPU 在同一个时钟周期，同时在运行两条计算机指令的不同阶段。但是这两个不同的阶段，可能会用到同样的硬件电路。
fff791c9c4066ba86dcce350e9710822.webp
可以看到，在第 1 条指令执行到访存（MEM）阶段的时候，流水线里的第 4 条指令，在执行取指令（Fetch）的操作。访存和取指令，都要进行内存数据的读取。内存只有一个地址译码器的作为地址输入，那就只能在一个时钟周期里面读取一条数据，没办法同时执行第 1 条指令的读取内存数据和第 4 条指令的读取指令代码。

类似的资源冲突，最常见的就是薄膜键盘的“锁键”问题。常用薄膜键盘，并不是每一个按键的背后都有一根独立的线路，而是多个键共用一个线路。如果我们在同一时间，按下两个共用一个线路的按键，这两个按键的信号就没办法都传输出去。

“全键无冲”这样的资源冲突解决方案，本质就是增加资源。同样的方案一样可以用在 CPU 的结构冒险里面。对于访问内存数据和取指令的冲突，一个直观的解决方案就是把我们的内存分成两部分，让它们各有各的地址译码器。这两部分分别是存放指令的程序内存和存放数据的数据内存。（哈弗架构）e7508cb409d398380753b292b6df8391.webp
现代的 CPU 虽然没有在内存层面进行对应的拆分，却在 CPU 内部的高速缓存部分进行了区分，把高速缓存分成了指令缓存（Instruction Cache）和数据缓存（Data Cache）两部分。（中间层思想）

内存的访问速度远比 CPU 的速度要慢，所以现代的 CPU 并不会直接读取主内存。它会从主内存把指令和数据加载到高速缓存中，这样后续的访问都是访问高速缓存。而指令缓存和数据缓存的拆分，使得我们的 CPU 在进行数据访问和取指令的时候，不会再发生资源冲突的问题了。

数据冒险

结构冒险是硬件层面的问题，而数据冒险就是程序逻辑层面的问题。

数据冒险，其实就是同时在执行的多个指令之间，有数据依赖的情况。这些数据依赖，我们可以分成三大类，分别是先写后读（Read After Write，RAW）、先读后写（Write After Read，WAR）和写后再写（Write After Write，WAW）。下面，我们分别看一下这几种情况。

先写后读

  1. int main() {
  2.   int a = 1;
  3.   int b = 2;
  4.   a = a + 2;
  5.   b = a + 3;
  6. }
  8. int main() {
  9.    0:   55                      push   rbp
  10.    1:   48 89 e5                mov    rbp,rsp
  11.   int a = 1;
  12.    4:   c7 45 fc 01 00 00 00    mov    DWORD PTR [rbp-0x4],0x1
  13.   int b = 2;
  14.    b:   c7 45 f8 02 00 00 00    mov    DWORD PTR [rbp-0x8],0x2
  15.   a = a + 2;
  16.   12:   83 45 fc 02             add    DWORD PTR [rbp-0x4],0x2
  17.   b = a + 3;
  18.   16:   8b 45 fc                mov    eax,DWORD PTR [rbp-0x4]
  19.   19:   83 c0 03                add    eax,0x3
  20.   1c:   89 45 f8                mov    DWORD PTR [rbp-0x8],eax
  21. }
  22.   1f:   5d                      pop    rbp
  23.   20:   c3                      ret

在内存地址为 12 的机器码，把 0x2 添加到 rbp-0x4 对应的内存地址里面。然后，在紧接着的内存地址为 16 的机器码，从 rbp-0x4 这个内存地址里面，把数据写入到 eax 这个寄存器里面。

所以，需要保证在内存地址为 16 的指令读取 rbp-0x4 里面的值之前，内存地址 12 的指令写入到 rbp-0x4 的操作必须完成。这就是先写后读所面临的数据依赖。如果这个顺序保证不了，我们的程序就会出错。这个先写后读的依赖关系，一般被称之为数据依赖，也就是 Data Dependency。

先读后写

  1. int main() {
  2.   int a = 1;
  3.   int b = 2;
  4.   a = b + a;
  5.   b = a + b;
  6. }
  8. int main() {
  9.    0:   55                      push   rbp
  10.    1:   48 89 e5                mov    rbp,rsp
  11.    int a = 1;
  12.    4:   c7 45 fc 01 00 00 00    mov    DWORD PTR [rbp-0x4],0x1
  13.    int b = 2;
  14.    b:   c7 45 f8 02 00 00 00    mov    DWORD PTR [rbp-0x8],0x2
  15.    a = b + a;
  16.   12:   8b 45 f8                mov    eax,DWORD PTR [rbp-0x8]
  17.   15:   01 45 fc                add    DWORD PTR [rbp-0x4],eax
  18.    b = a + b;
  19.   18:   8b 45 fc                mov    eax,DWORD PTR [rbp-0x4]
  20.   1b:   01 45 f8                add    DWORD PTR [rbp-0x8],eax
  21. }
  22.   1e:   5d                      pop    rbp
  23.   1f:   c3                      ret

在内存地址为 15 的汇编指令里，要把 eax 寄存器里面的值读出来，再加到 rbp-0x4 的内存地址里。接着在内存地址为 18 的汇编指令里，再写入更新 eax 寄存器里面。

如果在内存地址 18 的 eax 的写入先完成了，在内存地址为 15 的代码里面取出 eax 才发生，我们的程序计算就会出错。这里同样要保障对于 eax 的先读后写的操作顺序。这个先读后写的依赖，一般被叫作反依赖，也就是 Anti-Dependency。

写后再写

  1. int main() {
  2.   int a = 1;
  3.   a = 2;
  4. }
  6. int main() {
  7.    0:   55                      push   rbp
  8.    1:   48 89 e5                mov    rbp,rsp
  9.   int a = 1;
  10.    4:   c7 45 fc 01 00 00 00    mov    DWORD PTR [rbp-0x4],0x1
  11.   a = 2;
  12.    b:   c7 45 fc 02 00 00 00    mov    DWORD PTR [rbp-0x4],0x2
  13. }

这里如果地址 b 的指令先执行，然后再执行 4 地址指令，最后内存中的数据就会是错误的，所以要保障数据写入的顺序。写后再写的依赖，一般被叫做输出依赖，也就是 Output Dependency。

通过流水线停顿解决数据冒险

除了读之后再进行读，对于同一个寄存器或者内存地址的操作，都有明确强制的顺序要求。而这个顺序操作的要求，也为我们使用流水线带来了很大的挑战。因为流水线架构的核心，就是在前一个指令还没有结束的时候，后面的指令就要开始执行。

最简单的解决方法就是流水线停顿（Pipeline Stall），或者叫流水线冒泡（Pipeline Bubbling）。

流水线停顿的办法很容易理解。如果发现了后面执行的指令，会对前面执行的指令有数据层面的依赖关系，那最简单的办法就是“再等等”。进行指令译码的时候，会拿到对应指令所需要访问的寄存器和内存地址。在这个时候，判断这个指令是否会触发数据冒险。如果会触发数据冒险，我们就可以决定，让整个流水线停顿一个或者多个周期。d1e24e4b18411a5391757a197de2bdc8.webp 时钟信号会不停地在 0 和 1 之前自动切换。其实，我们并没有办法真的停顿下来。流水线的每一个操作步骤必须要干点儿事情。所以，在实践过程中，我们并不是让流水线停下来，而是在执行后面的操作步骤前面，插入一个 NOP 操作，也就是执行一个其实什么都不干的操作。0d762f2ce532d87cfe69c7b167af9c2a.webp
就像水管中进入了一个空气泡，水流经过的时候，没有水传给下一个步骤，而是给了一个什么都没有的气泡，这也是为什么流水线停顿又叫做流水线冒泡。

不过，流水线停顿这样的解决方案，是以牺牲 CPU 性能为代价的。在最差的情况下，流水线架构的 CPU，又会退化成单指令周期的 CPU 。

注意在采用流水线停顿的解决方案的时候，我们不仅要在当前指令里面，插入 NOP 操作，所有后续指令也要插入对应的 NOP 操作，就像有一路纵队，前边有人停下系鞋带，后边所有人都得原地踏步踏，不然就得踩着脑袋过去了。

NOP 操作和指令对其

首先回顾 MISP 体系结构下的几个指令和五级流水线“取指令（IF）- 指令译码（ID）- 指令执行（EX）- 内存访问（MEM）- 数据写回（WB） ”。b1ade5f8de67b172bf7b4ec9f63589bf.webp1e880fa8b1eab511583267e68f0541ad.webp 以 MIPS 的 LOAD，这样从内存里读取数据到寄存器的指令为例，来仔细看看，它需要经历的 5 个完整的流水线。STORE 这样从寄存器往内存里写数据的指令，不需要有写回寄存器的操作，也就是没有数据写回的流水线阶段。至于像 ADD 和 SUB 这样的加减法指令，所有操作都在寄存器完成，所以没有实际的内存访问（MEM）操作。b66ea9ca3300c7f71e91aaa6b6428fd4.webp
存疑：cmp 和 jmp 都有流水线中的哪几部？

有些指令没有对应的流水线阶段，但是我们并不能跳过对应的阶段直接执行下一阶段。不然，如果我们先后执行一条 LOAD 指令和一条 ADD 指令，就会发生 LOAD 指令的 WB 阶段和 ADD 指令的 WB 阶段，在同一个时钟周期发生。这样，相当于触发了一个结构冒险事件，产生了资源竞争。9e62ab3b42e445d65accf0549badf45f.webp
所以，在实践当中，各个指令不需要的阶段，并不会直接跳过，而是会运行一次 NOP 操作。通过插入一个 NOP 操作，可以使后一条指令的每一个 Stage，一定不和前一条指令的同 Stage 在一个时钟周期执行。这样，就不会发生先后两个指令，在同一时钟周期竞争相同的资源，产生结构冒险了。c16643d83dd534d3d97d0d7ad8e30d42.webp

操作数前推

  1. add $t0, $s2,$s1
  2. add $s2, $s1,$t0
  3. 第一条指令，把 s1 和 s2 寄存器里面的数据相加，存入到 t0 这个寄存器里面。
  4. 第二条指令，把 s1 和 t0 寄存器里面的数据相加，存入到 s2 这个寄存器里面。

易知这里出现了一个数据类型的冒险，于是使用流水线停顿来解决这个冒险问题：94dda2330b07c08530540ae11838c569.webp
虽然解决了数据冒险的问题，但是浪费了两个时钟周期。

不过，第二条指令的执行，未必要等待第一条指令写回完成，才能进行。如果第一条指令的执行结果，能够直接传输给第二条指令的执行阶段，作为输入，那第二条指令，就不用再从寄存器里面，把数据再单独读出来一次，才来执行代码。

我们完全可以在第一条指令的执行阶段完成之后，直接将结果数据传输给到下一条指令的 ALU。然后，下一条指令不需要再插入两个 NOP 阶段，就可以继续正常走到执行阶段。dceadd35c334974d8270052b37d48c27.webp
这样的解决方案，就叫作操作数前推（Operand Forwarding），或者操作数旁路（Operand Bypassing）。

操作数前推，就是通过在硬件层面制造一条旁路，让一条指令的计算结果，可以直接传输给下一条指令，而不再需要“指令 1 写回寄存器，指令 2 再读取寄存器“这样多此一举的操作。这样直接传输带来的好处就是，后面的指令可以减少，甚至消除原本需要通过流水线停顿，才能解决的数据冒险问题。

操作数前推的解决方案不但可以单独使用，还可以和流水线冒泡一起使用。有的时候，虽然可以把操作数转发到下一条指令，但是下一条指令仍然需要停顿一个时钟周期。49f3a9b1ae2972ac5c6cfca7731bf12d.webp
流水线停顿就像游泳比赛的接力方式。下一名运动员，需要在前一个运动员游玩了全程之后，触碰到了游泳池壁才能出发。而操作数前推，就好像短跑接力赛。后一个运动员可以提前抢跑，而前一个运动员会多跑一段主动把交接棒传递给他。

填上空闲的 NOP

文章前面提到，无论是流水线停顿还是操作数前推，只要前面指令的特定阶段还没有执行完成，后面的指令就会被阻塞。但是这个“阻塞”很多时候是没有必要的。因为尽管代码生成的指令是顺序的，但是如果后面的指令不需要依赖前面指令的执行结果，完全可以不必等待前面的指令运算完成。

  1. a = b + c
  2. d = a * e
  3. x = y * z

在流水线里，后面的指令不依赖前面的指令，那就不用等待前面的指令执行，它完全可以先执行。

计算里面的 x ，不必等待 a 和 d 都计算完成。所以完全可以在 d 的计算等待 a 的计算的过程中，先把 x 的结果给算出来。37ba6c453e530660cecbbfcf56a3ecef.webp
这样的解决方案，在计算机组成里面，被称为乱序执行（Out-of-Order Execution，OoOE）。

实现乱序执行

153f8d5e4a4363399133e1d7d9052804.webp
1. 在取指令和指令译码的时候，乱序执行的 CPU 和其他使用流水线架构的 CPU 是一样的。它会一级一级顺序地进行取指令和指令译码的工作。

  1. 在指令译码完成之后，就不一样了。CPU 不会直接进行指令执行，而是进行一次指令分发，把指令发到一个叫作保留站（Reservation Stations）的地方。顾名思义，这个保留站，就像一个火车站一样。发送到车站的指令，就像是一列列的火车。

  2. 这些指令不会立刻执行，而要等待它们所依赖的数据，传递给它们之后才会执行。这就好像一列列的火车都要等到乘客来齐了才能出发。

  3. 一旦指令依赖的数据来齐了，指令就可以交到后面的功能单元（Function Unit，FU），其实就是 ALU，去执行了。我们有很多功能单元可以并行运行，但是不同的功能单元能够支持执行的指令并不相同。就和我们的铁轨一样，有些从上海北上，可以到北京和哈尔滨；有些是南下的，可以到广州和深圳。

  4. 指令执行的阶段完成之后，我们并不能立刻把结果写回到寄存器里面去，而是把结果再存放到一个叫作重排序缓冲区（Re-Order Buffer，ROB）的地方。

  5. 在重排序缓冲区里，我们的 CPU 会按照取指令的顺序，对指令的计算结果重新排序。只有排在前面的指令都已经完成了，才会提交指令，完成整个指令的运算结果。

  6. 实际的指令的计算结果数据，并不是直接写到内存或者高速缓存里，而是先写入存储缓冲区（Store Buffer），最终才会写入到高速缓存和内存里。

可以看到，在乱序执行的情况下，只有 CPU 内部指令的执行层面，可能是“乱序”的。只要我们能在指令的译码阶段正确地分析出指令之间的数据依赖关系，这个“乱序”就只会在互相没有影响的指令之间发生。

即便指令的执行过程中是乱序的，我们在最终指令的计算结果写入到寄存器和内存之前，依然会进行一次排序，以确保所有指令在外部看来仍然是有序完成的。

  1. a = b + c
  2. d = a * e
  3. x = y * z

乱序执行中，d 依赖于 a 的计算结果，不会在 a 的计算完成之前执行。但是 CPU 并不会闲着，因为 x = y * z 的指令同样会被分发到保留站里。因为 x 所依赖的 y 和 z 的数据是准备好的， 这里的乘法运算不会等待计算 d，而会先去计算 x 的值。

如果只有一个 FU 能够计算乘法，那么这个 FU 并不会因为 d 要等待 a 的计算结果，而被闲置，而是会先被拿去计算 x。在 x 计算完成之后，d 也等来了 a 的计算结果。这个时候，FU 就会去计算出 d 的结果。然后在重排序缓冲区里，把对应的计算结果的提交顺序，仍然设置成 a -> d -> x，而计算完成的顺序是 x -> a -> d。可见实际的计算顺序和呈现的结果顺序可能不同。

整个乱序执行技术，就好像在指令的执行阶段提供一个“线程池”。指令不再是顺序执行的，而是根据池里所拥有的资源，以及各个任务是否可以进行执行，进行动态调度。在执行完成之后，又重新把结果在一个队列里面，按照指令的分发顺序重新排序。即使内部是“乱序”的，但是在外部看起来，仍然是井井有条地顺序执行。

乱序执行，极大地提高了 CPU 的运行效率。核心原因是，现代 CPU 的运行速度比访问主内存的速度要快很多。如果完全采用顺序执行的方式，很多时间都会浪费在前面指令等待获取内存数据的时间里。CPU 不得不加入 NOP 操作进行空转。而现代 CPU 的流水线级数也已经相对比较深了，到达了 14 级。这也意味着，同一个时钟周期内并行执行的指令数是很多的。

在现代 Intel 的 CPU 的乱序执行的过程中，只有指令的执行阶段是乱序的，后面的内存访问和数据写回阶段都仍然是顺序的。这种保障内存数据访问顺序的模型，叫作强内存模型（Strong Memory Model）。

为什么要保证内存访问的顺序：保证数据不会因为乱序执行而出现前后覆盖的情况，保证数据与指令顺序一致。这里举一个例子： core1 执行的代码为：x = 1; flag = true; core2 执行的代码为：while(!flag); assert(x ==1); 如果core1先写入了 flag，那么程序就不正确了。

扩展阅读：强/弱内存模型，与并发编程有关。

截至到此，所有的流水线停顿操作都要从指令执行阶段开始。流水线的前两个阶段，也就是取指令（IF）和指令译码（ID）的阶段，是不需要停顿的。CPU 会在流水线里面直接去取下一条指令，然后进行译码。

取指令和指令译码不会需要遇到任何停顿，这是基于一个假设。这个假设就是，所有的指令代码都是顺序加载执行的。不过这个假设，在执行的代码中，一旦遇到 if…else 这样的条件分支，或者 for/while 循环，就会不成立。b439cebb2d85496ad6eef2f61071aefa.webp
jmp 后的那一条指令是否应该顺序加载执行，在流水线里面进行取指令的时候，我们没法知道。要等 jmp 指令执行完成，去更新了 PC 寄存器之后，我们才能知道，是否执行下一条指令，还是跳转到另外一个内存地址，去取别的指令。

这种为了确保能取到正确的指令，而不得不进行等待延迟的情况，就是接下来要介绍的控制冒险（Control Harzard）。这也是流水线设计里最后一种冒险。

控制冒险

在遇到了控制冒险之后，我们的 CPU 具体会怎么应对呢？除了流水线停顿，等待前面的 jmp 指令执行完成之后，再去取最新的指令，还有什么好办法吗？当然是有的。我们一起来看一看。

缩短分支延迟

回想一下我们的条件跳转指令，它其实进行了两种电路操作。

第一种，是进行条件比较。这个条件比较，需要的输入是，根据指令的 opcode，就能确认的条件码寄存器。

第二种，是进行实际的跳转，也就是把要跳转的地址信息写入到 PC 寄存器。无论是 opcode，还是对应的条件码寄存器，还是我们跳转的地址，都是在指令译码（ID）的阶段就能获得的。而对应的条件码比较的电路，只要是简单的逻辑门电路就可以了，并不需要一个完整而复杂的 ALU。

所以，可以将条件判断、地址跳转，都提前到指令译码阶段进行，而不需要放在指令执行阶段。对应的，我们也要在 CPU 里面设计对应的旁路，在指令译码阶段，就提供对应的判断比较的电路。

这种方式，本质上和前面数据冒险的操作数前推的解决方案类似，就是在硬件电路层面，把一些计算结果更早地反馈到流水线中。这样反馈变得更快了，后面的指令需要等待的时间就变短了。

不过只是改造硬件，并不能彻底解决问题。跳转指令的比较结果，仍然要在指令执行的时候才能知道。在流水线里，第一条指令进行指令译码的时钟周期里，我们其实就要去取下一条指令了。这个时候，我们其实还没有开始指令执行阶段，自然也就不知道比较的结果。

静态分支预测

这个时候，我们就引入了一个新的解决方案，叫作分支预测（Branch Prediction）技术，也就是说，让 CPU 来猜一猜，条件跳转后执行的指令，应该是哪一条。

最简单的分支预测技术，叫作“假装分支不发生”。顾名思义，自然就是仍然按照顺序，把指令往下执行。其实就是 CPU 预测，条件跳转一定不发生。这样的预测方法，其实也是一种静态预测技术。就好像猜硬币的时候，你一直猜正面，会有 50% 的正确率。

如果分支预测是正确的，自然赚到了。这个意味着，我们节省下来本来需要停顿下来等待的时间。如果分支预测失败了？就把后面已经取出指令已经执行的部分，给丢弃掉。这个丢弃的操作，在流水线里面，叫作 Zap 或者 Flush。CPU 不仅要执行后面的指令，对于这些已经在流水线里面执行到一半的指令，我们还需要做对应的清除操作。比如，清空已经使用的寄存器里面的数据等等，这些清除操作，也有一定的开销。

所以，CPU 需要提供对应的丢弃指令的功能，通过控制信号清除掉已经在流水线中执行的指令。只要对应的清除开销不要太大，我们就是划得来的。39d114b3e37fe7fbad98ef0322b876c3.webp

动态分支预测

ea82f279b48c10ad95027c91ed62ab5d.webp
已经发生的事情辅助预测未发生的情况。

循环嵌套方式与性能

  1. public class BranchPrediction {
  2.     public static void main(String args[]) {        
  3.         long start = System.currentTimeMillis();
  4.         for (int i = 0; i < 100; i++) {
  5.             for (int j = 0; j <1000; j ++) {
  6.                 for (int k = 0; k < 10000; k++) {
  7.                 }
  8.             }
  9.         }
  10.         long end = System.currentTimeMillis();
  11.         System.out.println("Time spent is " + (end - start));
  13.         start = System.currentTimeMillis();
  14.         for (int i = 0; i < 10000; i++) {
  15.             for (int j = 0; j <1000; j ++) {
  16.                 for (int k = 0; k < 100; k++) {
  17.                 }
  18.             }
  19.         }
  20.         end = System.currentTimeMillis();
  21.         System.out.println("Time spent is " + (end - start) + "ms");
  22.     }
  23. }
  25. //Time spent in first loop is 5ms
  26. //Time spent in second loop is 15ms

这个差异就来自我们上面说的分支预测。已知循环其实也是利用 cmp 和 jle 这样先比较后跳转的指令来实现的。

这里的代码，每一次循环都有一个 cmp 和 jle 指令。每一个 jle 就意味着，要比较条件码寄存器的状态，决定是顺序执行代码，还是要跳转到另外一个地址。也就是说，在每一次循环发生的时候，都会有一次“分支”。69c0cb32d5b7139e0f993855104e55a5.webp
分支预测策略最简单的一个方式，自然是“假定分支不发生”。对应到上面的循环代码，就是循环始终会进行下去。在这样的情况下，上面的第一段循环，也就是内层 k 循环 10000 次的代码。每隔 10000 次，才会发生一次预测上的错误。而这样的错误，在第二层 j 的循环发生的次数，是 1000 次。

最外层的 i 的循环是 100 次。每个外层循环一次里面，都会发生 1000 次最内层 k 的循环的预测错误，所以一共会发生 100 × 1000 = 10 万次预测错误。下面的代码同理。

同样空转次数相同的循环代码，第一段代码运行的时间要少得多了。因为第一段代码发生“分支预测”错误的情况比较少，更多的计算机指令，在流水线里顺序运行下去了，而不需要把运行到一半的指令丢弃掉，再去重新加载新的指令执行。

小结

缩短分支延迟，类似于操作数前推，改造我们的 CPU 功能，通过增加对应的电路的方式，来缩短分支带来的延迟。分支预测，静态：“假装分支不发生”，动态：一级分支预测（一比特饱和计数）方法，其实就是认为，预测结果和上一次的条件跳转是一致的，在此基础上还有二比特饱和计数，或者叫双模态预测器的方法。

这个方法虽然简单，但是却非常有效。在 SPEC 89 版本的测试当中，使用这样的饱和计数方法，预测的准确率能够高达 93.5%。Intel 的 CPU，一直到 Pentium 时代，在还没有使用 MMX 指令集的时候，用的就是这种分支预测方式。在上面的例子中也可以看出，预测方式对性能造成了很大影响。