计算机组成 -- 冒险

冒险

流水线架构的CPU，是主动进行的冒险选择，期望通过冒险带来更高的回报
- 对于各种冒险可能造成的问题，都准备好了应对方案
分类
- 结构冒险（Structural Hazard）
- 数据冒险（Data Hazard）
- 控制冒险（Control Hazard）

结构冒险

结构冒险，本质上是一个硬件层面的资源竞争问题
CPU在同一个时钟周期，同时在运行两条计算机指令的不同阶段，但这两个不同的阶段可能会用到同样的硬件电路

内存的数据访问

第1条指令执行到访存（MEM）阶段的时候，流水线的第4条指令，在执行取指令（Fetch）操作
访存和取指令，都是要进行内存数据的读取，而内存只有一个地址译码器，只能在一个时钟周期内读取一条数据
- 无法同时执行第1条指令的读取内存数据和第4条指令的读取指令代码

解决方案

解决方案：增加资源
哈佛架构
- 把内存分成两部分，它们有各自的地址译码器，这两部分分别是存放指令的程序内存和存放数据的数据内存
- 缺点：无法根据实际情况去动态调整
普林斯顿架构 – 冯.诺依曼体系架构
- 今天使用的CPU，仍然是冯.诺依曼体系架构，并没有把内存拆成程序内存和数据内存两部分
混合架构
- 现代CPU没有在内存层面进行对应的拆分，但在CPU内部的高速缓存部分进行了区分，分成了指令缓存和数据缓存
- 内存的访问速度远比CPU的速度慢，现代CPU并不会直接读取主内存
  - 会从主内存把指令和数据加载到高速缓存中，后续的访问都是访问高速缓存
- 指令缓存和数据缓存的拆分，使得CPU在进行数据访问和取指令的时候，不会再发生资源冲突的情况

数据冒险

结构冒险是硬件层面的问题，可以通过增加硬件资源的方式来解决；但还有很多冒险问题属于程序逻辑层面，最常见是数据冒险
数据冒险：同时在执行多个指令之间，有数据依赖的情况
依赖分类
- 先写后读（Read After Write，RAW）
- 先读后写（Write After Read，WAR）
- 写后再写（Write After Write，WAW）

依赖

写 -> 读

raw.c

int main() {
    int a = 1;
    int b = 2;
    a = a + 2;
    b = a + 3;
}

1 2	$ gcc -g -c raw.c $ objdump -d -M intel -S raw.o

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

内存地址12的机器码，把0x2添加到rbp-0x4对应的内存地址
内存地址16的机器码，从rbp-0x4这个内存地址里面读取，把值把写入到eax这个寄存器里面
必须保证：在内存地址16的指令读取rbp-0x4里面的值之前，内存地址12的指令写入到rbp-0x4的操作已经完成
写 -> 读的依赖关系，一般称为数据依赖，即Data Dependency
简单理解：先写入，才能读

读 -> 写

war.c

int main() {
  int a = 1;
  int b = 2;
  a = b + a;
  b = a + b;
}

1 2	$ gcc -g -c war.c $ objdump -d -M intel -S war.o

......
0000000000000000 <main>:
int main() {
   0:    55                   	push   rbp
   1:    48 89 e5             	mov    rbp,rsp
    int a = 1;
   4:    c7 45 fc 01 00 00 00 	mov    DWORD PTR [rbp-0x4],0x1
    int b = 2;
   b:    c7 45 f8 02 00 00 00 	mov    DWORD PTR [rbp-0x8],0x2
    a = b + a;
  12:    8b 45 f8             	mov    eax,DWORD PTR [rbp-0x8]
  15:    01 45 fc             	add    DWORD PTR [rbp-0x4],eax
    b = a + b;
  18:    8b 45 fc             	mov    eax,DWORD PTR [rbp-0x4]
  1b:    01 45 f8             	add    DWORD PTR [rbp-0x8],eax
}
  1e:    5d                   	pop    rbp
  1f:    c3                   	ret

内存地址15的指令，要把eax寄存器里面的值读出来，再加到rbp-0x4的内存地址
内存地址18的指令，要更新eax寄存器
如果内存地址18的eax的写入先完成，在内存地址为15的代码里面取出eax才发生，程序就会出错

同样要保证对于eax的先读后写的操作顺序

读 -> 写的依赖关系，一般称为反依赖，即Anti Dependency
简单理解：前一个读操作取出来的数据用于其它运算，后一个写操作就不能先执行完成

写 -> 写

waw.c

int main() {
  int a = 1;
  a = 2;
}

1 2	$ gcc -g -c waw.c $ objdump -d -M intel -S waw.o

......
0000000000000000 <main>:
int main() {
   0:    55                   	push   rbp
   1:    48 89 e5             	mov    rbp,rsp
    int a = 1;
   4:    c7 45 fc 01 00 00 00 	mov    DWORD PTR [rbp-0x4],0x1
    a = 2;
   b:    c7 45 fc 02 00 00 00 	mov    DWORD PTR [rbp-0x4],0x2
}
  12:    5d                   	pop    rbp
  13:    c3                   	ret

内存地址4的指令和内存地址b的指令，都是将对应的数据写入到rbp-0x4 的内存地址里面
必须保证：内存地址4的指令的写入，在内存地址b的指令的写入之前完成
写 -> 写的依赖关系，一般称为输出依赖，即Output Dependency
简单理解：覆盖写

解决方案 – 流水线停顿

除了读 -> 读，对于同一个寄存器或者内存地址的操作，都有明确强制的顺序要求
解决数据冒险的简单方案：流水线停顿（Pipeline Stall）、别称：流水线冒泡（Pipeline Bubbling）

这是一种以牺牲CPU性能为代价的方案，在最坏的情况下，流水线架构的CPU会退化成单指令周期的CPU！！

在进行指令译码的时候，会拿到对应指令所需要访问的寄存器和内存地址

此时能判断这个指令是否会触发数据冒险，如果会触发数据冒险，可以决定让整个流水线停顿一个或多个周期

时钟信号会不停地在0和1之间自动切换，并没有办法真的停顿下来

在实践过程中，并不是让流水线停下来，而是在执行后面的操作步骤前插入一个NOP（No Option）操作
好像在一个水管里面，进了一个空气泡，因此也叫流水线冒泡

操作数前推

流水线对齐

五级流水线

取指令（IF） -> 指令译码（ID） -> 指令执行（EX） -> 内存访问（MEM） -> 数据写回（WB）

MIPS指令

在MIPS的体系结构下，不同类型的指令，会在流水线的不同阶段进行不同的操作
LOAD：从内存里读取数据到寄存器

需要经历5个完整的流水线

STORE：从寄存器往内存里写入数据

不需要有写回寄存器的操作，即没有数据写回（WB）的流水线阶段

ADD、SUB

加减法指令，所有操作都在寄存器完成，没有实际的内存访问（MEM）操作

有些指令没有对应的流水线阶段，但不能跳过对应的阶段直接执行下一阶段
如果先后执行一条LOAD指令和一条ADD指令，LOAD指令的WB阶段和ADD指令的WB阶段，在同一个时钟周期发生

相当于触发了一个结构冒险事件，产生了资源竞争

在实践中，各个指令不需要的阶段，不会直接跳过，而是会运行一次NOP操作

操作数前推

通过NOP操作进行对齐，在流水线里，就不会遇到资源竞争产生的结构冒险问题

NOP操作，即流水线停顿插入的对应操作

插入过多的NOP操作，意味着CPU空转增多

1
2
3

// s1 s2 t0都是寄存器
add $t0, $s2,$s1 // s1 + s2 -> t0
add $s2, $s1,$t0 // s1 + t0 -> s2

后一条add指令，依赖寄存器t0的值，而t0里面的值，又来自于前一条add指令的计算结果

因此后一条add指令，需要等待前一条add指令的数据写回（WB）阶段完成之后才能执行

这是一个数据冒险：数据依赖类型（写 -> 读），上面的方案是通过流水线停顿来解决这个问题
要在第二条指令的译码阶段之后，插入对应的NOP指令，直到前一条指令的数据写回完成之后，才能继续执行
这虽然解决了数据冒险的问题，但也浪费了两个时钟周期

第二条指令的执行，未必需要等待第一条指令写回完成才能进行
如果能够把第一条指令的执行结果作为输入直接传输到第二条指令的执行阶段

那第二条指令就不用再从寄存器里面，把数据再单独读取出来才能执行代码
可以在第一条指令的执行（EX）阶段完成之后，直接将结果数据传输到下一条指令的ALU
- 这样，下一条指令不再需要再插入两个NOP阶段，就可以正常走到执行阶段

上面的方案就是操作数前推（Operand Forwarding）、操作数旁路（Operand Bypassing）

Forwarding：逻辑含义，第一条指令的执行结果作为输入直接转发给第二条指令的ALU
Bypassing：硬件含义，为了实现Forwarding，在CPU的硬件层面，需要单独拉出一根信号传输的线路
- 使得ALU的计算结果能够重新回到ALU的输入
- 越过了写入寄存器，再从寄存器读出来的过程，可以节省两个时钟周期

操作数前推的解决方案可以和流水线停顿一起使用

虽然可以把操作数转发到下一条指令，但下一条指令仍然需要停顿一个时钟周期

先执行一条LOAD指令，再执行ADD指令

LOAD指令在访存阶段才能把数据读取出来，下一条指令的执行阶段，需要等上一阶段的访存阶段完成之后，才能进行

操作数前推并不能减少所有冒泡，只能去掉其中一部分，仍然需要通过插入一些NOP来解决数据冒险问题

乱序执行

结构冒险

限制来源：在同一时钟周期内，不同的指令的不同流水线阶段，要访问相同的硬件资源
解决方案：_增加资源_

数据冒险

限制来源：数据之间的各种依赖
解决方案：_流水线停顿、操作数前推_

即便综合运用这三个技术，仍然会遇到不得不停下整个流水线，等待前面的指令完成的情况

填补空闲的NOP

无论是流水线停顿，还是操作数前推，只要前面指令的特定阶段还没有执行完成，后面的指令就会被阻塞
虽然代码生成的指令是顺序的，如果后面的指令不需要依赖前面指令的执行结果，完全可以不必等待前面的指令执行完成

这样的解决方案，在计算机组成里面，被称为乱序执行（Out-of-Order Execution，OoOE）

1
2
3

a = b + c
d = a * e
x = y * z

实现过程

取指令和指令译码阶段，乱序执行的CPU和使用流水线架构的CPU是一样的，会一级一级顺序进行
指令译码完成后，CPU不会直接进行指令执行，而是进行一次指令分发

指令分发：把指令分发到保留站（Reservation Stations，RS）
- 类比：保留站 -> 火车站，指令 -> 火车
这些指令不会立即执行，而是等待它们所依赖的数据，传递给它们之后才会执行
- 类比：数据 -> 乘客，火车需要等乘客

一旦指令依赖的数据到齐了，指令就可以交到后面的功能单元（Function Unit，FU，本质是ALU）去执行了

很多功能单元是可以并行运行的，但不同的功能单元能够支持执行的指令是不相同的

指令执行阶段完成后，我们并不能立即把结果写回到寄存器里面，而是把结果先存放到重排序缓冲区（ReOrder Buffer，ROB）
在重排序缓冲区里，我们的CPU会按照取指令的顺序，对指令的计算结果重新排序

只有排在前面的指令都已经完成了，才会提交指令，完成整个指令的运算结果

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

最终才会写入内存和高速缓存

在乱序执行的情况下，只有CPU内部指令的执行层面，可能是乱序的

只要能在指令译码阶段正确地分析出指令之间的数据依赖关系，『乱序』就只会在相互没有影响的指令之间发生
- 相互没有影响 ≈ 不破坏数据依赖
即便指令的执行过程是乱序的，在指令的计算结果最终写入到寄存器和内存之前，依然会进行一次排序
- 以确保所有指令在外部看来仍然是有序完成的

回到样例

1
2
3

a = b + c
d = a * e
x = y * z

d依赖于a的计算结果，不会在a的计算完成之前执行
x = y * z的指令同样会被分发到保留站，x所依赖的y和z的数据是准备好的，这里的乘法运算不会等待d的计算结果
如果只有一个FU能够计算乘法，那么这个FU并不会因为d要等待a的计算结果而被限制，会先被拿来计算x
x计算完成后，d也等来了a的计算结果，此时，唯一的乘法FU会去计算d的结果
在重排序缓冲区里，把对应的计算结果的提交顺序，仍然设置为a->d->x，但实际计算完成的顺序是x->a->d
整个过程中，计算乘法的FU没有被闲置，意味着CPU的吞吐率最大化

小结

整个乱序执行技术，类似于在指令的执行阶段提供了一个线程池，FU就是线程

指令不再是顺序执行的，而是根据线程池所拥有的资源，各个任务是否可以进行执行，进行动态调度
在执行完成之后，又重新把结果放在一个队列里面，按照指令的分发顺序重新排序
即使内部是『乱序』的，但外部看来，仍然是顺序执行的

乱序执行，极大地提高了CPU的运行效率

核心原因：CPU的运行速度比访问主内存的速度快很多
如果采用顺序执行的方式，很多时间会被浪费在前面指令等待获取内存数据
- 为此，CPU不得不加入NOP操作进行空转
乱序执行充分利用了较深流水线带来的并发性，可以充分利用CPU的性能

控制冒险

在结构冒险和数据冒险中，所有的流水线停顿都要从指令执行（EX）阶段开始

流水线的前两个阶段，即取指令（IF）和指令译码（ID），是不需要停顿的
基于一个基本假设：所有的指令代码都是顺序加载执行的
- 不成立的情况：在执行的代码中，遇到if/else条件分支，或者for/while循环

jne指令发生的时候，CPU可能会跳转去执行其它指令

jne后的那一条指令是否应该顺序加载执行，在流水线里进行取指令的时候，是无法知道的
要等到jne指令执行完成，更新了PC寄存器后，才能知道是否执行下一条指令，还是跳转到另一个内存地址，去取别的指令

为了确保能取到正确的指令，不得不进行等待延迟的情况，这就是控制冒险

缩短分支延迟

条件跳转指令实际上进行了两种电路操作：条件比较 + 实际跳转
条件跳转

根据指令的opcode，就能确认对应的条件码寄存器

实际跳转

把要跳转的地址写入到PC寄存器

无论是指令的opcode，还是对应的条件码寄存器，还是跳转的地址，都是在指令译码阶段就能获得的

对应的条件码比较电路，只需要简单的逻辑门电路即可，并不需要一个完整而复杂的ALU
可以将条件判断、地址跳转，都提前到指令译码阶段进行，而不需要放在指令执行阶段
在CPU里面设计对应的旁路，在指令译码阶段，就提供对应的判断比较的电路

这种方式，本质上和前面数据冒险的操作数前推的解决方案类似，就是在硬件电路层面，把一些计算结果更早地反馈到流水线中

这样反馈会变得更快，后面的指令需要等待的时间就会变短

只是改造硬件，并不能彻底解决问题

跳转指令的比较结果，仍然要在指令执行完成后才能知道
在流水线里，第一条指令进行指令译码的时钟周期里，其实就要取下一条指令了
- 但由于第一条指令还没开始指令执行阶段，此时并不知道比较的结果，自然也就无法准确知道要取哪一条指令了

分支预测

静态预测

CPU预测：条件跳转一定不发生
如果预测成功，可以节省本来需要停顿下来等待的时间
如果预测失败，需要丢弃后面已经取出指令且已经执行的部分

这个丢弃的操作，在流水线里面叫作Zap或者Flush
CPU不仅要执行后面的指令，对于已经在流水线里面执行到一半的指令，还需要做对应的清除操作
- 例如清空已经使用的寄存器里面的数据，而这些清除操作，有一定的开销

动态预测

一级分支预测（One Level Branch Prediction）、1比特饱和计数（1-bit saturating counter）

用1Bit，记录当前分支的比较情况，直接用当前分支的比较情况来预测下一次分支的比较情况

状态机（State Machine）

如果状态机总共有4个状态，需要2个比特来记录对应的状态，这样的策略叫作2比特饱和计数或者双模态预测器

循环嵌套

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("Time spent is " + (end - start));

        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("Time spent is " + (end - start) + "ms");
    }
}