深入浅出计算机组成原理——原理篇：处理器（22-29）

全文内容主要来自对课程《深入浅出计算机组成原理》的学习笔记。

22 | 冒险和预测（一）

流水线设计需要解决的三大冒险：

• 结构冒险（Structural Hazard）；
• 数据冒险（Data Hazard）；
• 控制冒险（Control Hazard）

结构冒险

本质上是一个硬件层面的资源竞争问题。

CPU 在同一个时钟周期，同时运行两条指令的不同阶段。但是可能会用到同样的硬件电路。

如上图所示就是内存读取的结构冒险。因为内存只有一个地址译码器的作为地址输入，在一个时钟周期里面只能读取一条数据。

一个直观的方案：内存分成两部分（存放指令的程序内存和存放数据的数据内存），各有各的地址译码器。这称为哈佛架构（Harvard Architecture）。有弊端：没法动态分配内存了。

然而，现在都是冯·诺依曼体系结构，其参考上述，在 CPU 内部加了高速缓存部分，主要是为了缓解访问内存速度过慢于 CPU。但在这里把高速缓存分成了指令缓存（Instruction Cache）和数据缓存（Data Cache）两部分。CPU 并不会直接读取主内存。它会从主内存把指令和数据加载到高速缓存中，这样后续的访问都是访问高速缓存。解法的本质都是增加资源。

数据冒险

三大类：

• 先写后读（Read After Write，RAW）——数据依赖；
• 先读后写（Write After Read，WAR）——反依赖；
• 写后再写（Write After Write，WAW）——输出依赖。

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

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

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

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

冲突：

• 流水线架构的核心是在前一个指令还没有结束的时候，后面的指令就要开始执行。
• 但，对于同一个寄存器或者内存地址的操作，都有明确强制的顺序要求。

解法： 流水线停顿（Pipeline Stall），或者叫流水线冒泡（Pipeline Bubbling）。

在执行后面的操作步骤前面，插入一个 NOP 操作，也就是执行一个其实什么都不干的操作。

---

23 | 冒险和预测（二）

前面两种冒险的解决方案可以归纳为“加资源”和“加时间”。这里介绍一个更有效的方案：操作数前推。

NOP 操作和指令对齐

五级流水线：“取指令（IF）- 指令译码（ID）- 指令执行（EX）- 内存访问（MEM）- 数据写回（WB） ”。

但并不是所有的指令都需要完全的5级流水线，如上表，STORE 和 ADD/SUB 就分别不需要 WB 和 MEM 操作

但是我们并不能跳过对应的阶段直接执行下一阶段，否则容易出现结构冒险，例如 LOAD 指令和 ADD 先后执行的时候，WB 是在统一时钟周期，所以需要针对确实的阶段进行插入 NOP。

操作数前推

插入过多的 NOP 操作，带来的坏处就是浪费了CPU的资源。

add $t0, $s2,$s1
add $s2, $s1,$t0

上述2行 code 的流水线如下，后者依赖前者计算结果。为了流水线对齐和结构依赖，多了4个 NOP 的操作。

实际上，第二条指令未必要等待第一条指令写回完成。可将第一条指令的执行结果直接传输给第二条指令的执行阶段。如下图所示，就叫作操作数前推（Operand Forwarding），或者操作数旁路（Operand Bypassing）。

它的实现是 CPU 的硬件里面，再单独拉一根信号传输的线路出来，使得 ALU 的计算结果能够重新回到 ALU 的输入里。

---

24 | 冒险和预测（三）

填上空闲的 NOP

流水线停顿的时候，对应的电路闲着，可以先完成后面指令的执行阶段。

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

如上，后面的指令不依赖前面的，那就不用等，可以先执行。这就是乱序执行（Out-of-Order Execution，OoOE）

CPU 里的“线程池”

乱序执行的流水线不同于历史的5级流水线，如上图：

1. 取指令和指令译码没有变化；
2. 译码后，不直接执行，先分发到保留站（Reservation Stations）；
3. 这些指令等待依赖的数据，等到后才交到 ALU 执行；；
4. 结果也不直接写回寄存器，先存在重排缓冲区（Re-Order Buffer，ROB）；
5. CPU 按照取指令的顺序，对结果重新排序，从前往后依赖提交完成；
6. 结果数据也不直接写内存，先写入存储缓冲区(Store Buffer)后再写。

即使执行乱序，但最终结果会排序，确保写入内存和寄存器是有序的

---

25 | 冒险和预测（四）

所有的流水线停顿都从指令执行开始，但取指令和指令译码不需要任何停顿。当然，这有一个前提：所有的指令代码都是顺序加载执行的。

但是，遇到条件分支时就不成立：

要等 jmp 指令执行完成，去更新了 PC 寄存器之后，才能判断是否执行下一条指令，还是跳转到另外内存地址，去取别的指令。

上述提到的就是控制冒险。

分支预测

缩短分支延迟

可以将条件判断、地址跳转，都提前到指令译码阶段进行。CPU 里面设计对应的旁路，在指令译码阶段，就提供对应的判断比较的电路，节省等待时间。
但并不能彻底解决问题，跳转指令的比较结果，仍然要在指令执行的时候才能知道。

分支预测

让 CPU 预测下一跳执行指令，无非 2 选 1，最朴素的就是假装分支不发生，即静态预测技术。统计学角度，约50%正确率。

动态分支预测

上面一种属实太随机，实际上可以根据之前条件跳转的比较结果来预测。

类似于天气预报，如果始终选择跟上次状态一样，便是一级分支预测（One Level Branch Prediction），或者叫 1 比特饱和计数（1-bit saturating counter）。

进一步提升，我们引入一个状态机（State Machine）如下图，4 个状态，所以需要 2 个比特来记录。这样这整个策略，就可以叫作 2 比特饱和计数，或者叫双模态预测器（Bimodal Predictor）。

循环嵌套的改变会影响性能

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");
    }
}

如上述2种嵌套循环代码，性能差异很大，主要是因为：

1. 每次循环需要 cmp 和 jle 指令，后者就需要分支预测；
2. 最内层只有最后一次会预测错（跳到外层），故外层循环次数越多，整体预测错的越多。

---

26 | Superscalar 和 VLIW

程序的 CPU 执行时间 = 指令数 × CPI × Clock Cycle Time

CPI 的倒数，即 IPC（Instruction Per Clock），也就是一个时钟周期里面能够执行的指令数，代表了 CPU 的吞吐率。

最佳情况下，IPC 也只能到 1

即一个时钟周期也只能执行完取一条指令，但有办法突破。

多发射与超标量

乱序执行的时候，你会看到，其实指令的执行阶段，是由很多个功能单元（FU）并行（Parallel）进行的。

取指令（IF）和指令译码（ID）部分并不是并行进行的。如何实现并行？

其实只要我们把取指令和指令译码，也一样通过增加硬件的方式。一次性从内存里面取出多条指令，然后分发给多个并行的指令译码器，进行译码，然后对应交给不同的功能单元去处理。

这种 CPU 设计，我们叫作多发射（Mulitple Issue）和超标量（Superscalar）。

如此，流水线就会有所变化，

Intel 失败的超长指令字

乱序执行和超标量在硬件层面实现都很复杂，因为要解决依赖冲突问题，所以需要考虑放到软件里面做。

通过编译器来优化指令数，一个 CPU 设计叫作超长指令字设计（Very Long Instruction Word，VLIW）。即 IA-64 架构的安腾（Itanium）处理器，使用显式并发指令运算（Explicitly Parallel Instruction Computer）。

在超长指令字架构里，将检测指令的前后依赖关系由 CPU 硬件电路转到了编译器。

让编译器把没有依赖关系的代码位置进行交换。然后，再把多条连续的指令打包成一个指令包，安腾是3.

其失败的重要原因——向前兼容：

1. 与x86指令集不同，x86的程序全部要重新编译；
2. 想要提升并行度，需要增加指令包里的指令数量，就需要重新编译。

在 Intel 的 x86 的 CPU 里，从 Pentium 时代，第一次开始引入超标量技术，整个 CPU 的性能上了一个台阶。依赖于在硬件层面，能够检测到对应的指令的先后依赖关系，解决“冒险”问题。所以，它也使得 CPU 的电路变得更复杂了。

---

27 | SIMD：加速矩阵乘法

超线程

2002 年底，Intel 在的 3.06GHz 主频的 Pentium 4 CPU 上，第一次引入了超线程（Hyper-Threading）技术。

朴素思想：找一些没有依赖完全独立的指令来并行运算。不同的程序貌似天然符合该要求。

看上去没有什么技术，但实际上我们并没有真正地做到指令的并行运行：

在同一时间点上，一个物理的 CPU 核心只会运行一个线程的指令。

超线程的 CPU，其实是把一个物理层面 CPU 核心，“伪装”成两个逻辑层面的 CPU 核心。硬件上增加很多电路，使得一个 CPU 维护两个不同线程的指令的状态信息。其中会有双份的 PC 寄存器、指令寄存器乃至条件码寄存器，不过指令译码器还是 ALU等其他组件没有双份。超线程技术一般也被叫作同时多线程（Simultaneous Multi-Threading，简称 SMT）技术。

SIMD

SIMD，中文叫作单指令多数据流（Single Instruction Multiple Data）。

>>> import numpy as np
>>> import timeit
>>> a = list(range(1000))
>>> b = np.array(range(1000))
>>> timeit.timeit("[i + 1 for i in a]", setup="from __main__ import a", number=1000000)
32.82800309999993
>>> timeit.timeit("np.add(1, b)", setup="from __main__ import np, b", number=1000000)
0.9787889999997788
>>>

上述两种计算法，性能差30多倍，主要因为：
NumPy 直接用到了 SIMD 指令，能够并行进行向量的操作。

SIMD 在获取数据和执行指令的时候，都做到了并行。且在从内存里面读取数据的时候，SIMD 是一次性读取多个数据。

正是 SIMD 技术的出现，使得我们在 Pentium 时代的个人 PC，开始有了多媒体运算的能力。

---

28 | 异常和中断

异常

这里不是指 Exception 这种“软件异常”，而是和硬件、系统相关的“硬件异常”。

比如，除以 0，溢出，CPU 运行程序时收到键盘输入信号等。计算机会为每一种可能会发生的异常，分配一个异常代码（Exception Number）。

这些异常代码里，I/O 发出的信号的异常代码，是由操作系统来分配的，也就是由软件来设定的。而像加法溢出这样的异常代码，则是由 CPU 预先分配好的，也就是由硬件来分配的。

内存中有一个异常表（Exception Table），也叫作中断向量表（Interrupt Vector Table），存放的是不同的异常代码对应的异常处理程序（Exception Handler）所在的地址。

异常的分类

• 中断（Interrupt）：程序员执行时被打断，一般来自 I/O 设备。
• 陷阱（Trap）：程序员“故意“主动触发的异常，类似断点。
• 故障（Fault）：陷阱是我们开发程序的时候刻意触发的异常，而故障通常不是。
• 中止（Abort）：CPU 遇到故障无法恢复时需要终止。

类型	原因	示例	触发时机	处理后操作
中断	I/O设备信号	用户键盘输入	异步	下一条指令
陷阱	程序刻意触发	程序进行系统调用	同步	下一条指令
故障	程序执行出错	程序加载的缺页错误	同步	当前指令
终止	故障无法恢复	ECC内存校验失败	同步	退出程序

• 异步：中断异常的信号来自系统外部，而不是在程序自己执行的过程中；
• 同步：在程序执行的过程中发生的。

处理流程：保存现场、异常代码查询、异常处理程序调用“

异常的处理

切换到异常处理程序，像两个不同的独立进程之间在 CPU 层面的切换，所以这个过程我们称之为上下文切换（Context Switch）。

难点：

1. 异常情况往往发生在程序正常执行的预期之外；
2. 像陷阱类，涉及程序指令在用户态和内核态之间的切换；
3. 像故障类，在异常处理程序执行完成之后。

---

29 | CISC和RISC指令集

CPU 的指令集可分：

• 复杂指令集（Complex Instruction Set Computing，简称 CISC），机器码是固定长度;
• 精简指令集（Reduced Instruction Set Computing，简称 RISC），机器码是可变长度。

CISC VS RISC

CISC 的挑战：

• 在硬件层，支持更多的复杂指令，电路更复杂，设计更困难，散热和功耗更高。
• 在软件层，因为指令更多，编译器的优化更困难。

最早只有 CISC，70年代末，大卫·帕特森（David Patterson）发现在 CPU 运行的程序里，80% 的时间都是在使用 20% 的简单指令。于是提出了 RISC。

• CISC 的架构，通过优化指令数，来减少 CPU 的执行时间。
• RISC 的架构，在优化 CPI，指令简单，需要的时钟周期就比较少。

微指令架构

指令集的向前兼容性，即历史程序是否废弃，是 Intel 想要放弃 x86 重点要考虑的问题。

x86 下的 64 位的指令集 x86-64，并不是 Intel 发明的，而是 AMD 发明的。

Intel 在微指令架构的 CPU 里面，译码器会把一条机器码，“翻译”成好几条“微指令”，使之变成了固定长度的 RISC 风格的了。

如上，指令译码器变复杂，性能又有浪费。但因为“二八现象”的存在，对于这种有着很强局部性的问题，常见的解决方案就是使用缓存。
于是，Intel 加了一层 L0 Cache 来保存 CISC 翻译成 RISC 的微指令。不仅优化了性能，因为译码器的晶体管开关动作变少了，还减少了功耗。

由于 Intel 本身在 CPU 层面做的大量优化，比如乱序执行、分支预测等。故 x86 的 CPU 始终在功耗上还是要远远超过 RISC 架构的 ARM，所以最终在智能手机崛起替代 PC 的时代，落在了 ARM 后面。

ARM 和 RISC-V

ARM 能够在移动端战胜 Intel，并不是因为 RISC 架构。

CISC 和 RISC 的分界已经没有那么明显了。Intel 和 AMD 的 CPU 也都是采用译码成 RISC 风格的微指令来运行。而 ARM 的芯片，一条指令同样需要多个时钟周期，有乱序执行和多发射。

核心差异是：

• 功耗优先的设计
  一个 4 核的 Intel i7 的 CPU，设计的功率就是 130W。而 ARM A8 的单个核心的 CPU，设计功率只有 2W。
• 低价。
  ARM 只是进行 CPU 设计，然后产权授权出去。尽管出货量远大于 Intel，但是收入和利润却比不上 Intel。

图灵奖的得主大卫·帕特森教授从伯克利退休之后，成了 RISC-V 国际开源实验室的负责人，开始推动 RISC-V 这个开源 CPU 的开发。

---