【梳理】计算机组成与设计 第4章 处理器 第4节 指令级并行（内附文档高清截图）

配套教材：
Computer Organization and Design: The Hardware / Software Interface (5th Edition)
建议先修课程：数字逻辑电路、C / C++、汇编语言。
这是专业必修课《计算机组成原理》的复习指引。建议将本复习指导与博客中的《简明操作系统原理》配合复习。
在本文的最后附有复习指导的高清截图。需要掌握的概念在文档截图中以蓝色标识，并用可读性更好的字体显示 Linux 命令和代码。代码部分语法高亮。
计算机组成原理不是语言课，本复习指导对用到的编程语言的语法的讲解也不会很细致。如果不知道代码中的一些关键字、指令或函数的具体用法，你应该自行查找相关资料。

---

第四节 指令级并行

36、这里只对相应内容简单介绍。如果想要详细学习，请参阅《计算机架构：量化方法》。
指令级并行（instruction-level parallelism，ILP）指的是在一个周期内同时执行多条指令。常用的方法有两种：一种是增长流水线，其利弊已经在前面作了简单分析。另一种是增加硬件单元的数量，即多发射（multiple issue）。
指令发射，指的是指令从译码阶段进入执行阶段。

37、多发射分为静态多发射（static multiple issue）和动态多发射（dynamic multiple issue）两种。
静态多发射高度依赖编译器，由编译器在编译时，进行相关性分析和静态分支预测，以静态完成指令打包或冒险处理。
指令打包，指的是将同时发射的多条指令合并到一个长指令中。将一个周期内发射的多个指令看成一条多个操作的长指令，称为一个发射包（issue packet）。静态多发射最初被称为超长指令字（VLIW，Very Long Instruction Word），采用这种技术的处理器被称为VLIW处理器。不过，在同一个周期内发射的指令类型是受限制的（例如，只能是一条ALU指令/分支指令、一条Load/Store指令），以降低解码和指令发射的实现难度。
IA-64（其为RISC）采用这种方法，Intel称其为EPIC（Explicitly Parallel Instruction Computer，显式并行指令计算机）。
冒险处理，指的是减少或消除数据冒险和控制冒险。
做法1：完全由编译器通过代码调度和插入nop指令来消除所有冒险，无需硬件实现冒险检测和流水线阻塞。
做法2：由编译器通过静态分支预测和代码调度来消除同时发射指令间内部依赖，由硬件检测数据冒险并进行流水线阻塞。
即：保证打包指令内部不会出现冒险。
动态多发射处理器由硬件在执行时动态完成指令打包或冒险处理，通常被称为超标量（Superscalar）处理器。针对VLIW处理器的编译结果与机器结构密切相关，在结构有差异（即使指令集相同）的机器上要重新针对编译。而对于超标量处理器，编译器仅进行指令顺序调整，但不进行指令打包，由硬件根据机器的结构来决定一个周期发射哪几条指令。因此，编译后的代码能够被不同结构的机器正确执行。

38、推测（speculation）基于预测（prediction）的思想，是实现指令打包和冒险处理的基础。前面我们讲过，通过分支预测可以推测分支结果。当分支条件成立的概率不大时，先执行紧随分支指令之后的指令。另一个推测的例子就是假设跟在load指令之前的store指令的地址肯定与这个load指令的不同。于是在需要时，这个load指令可以在store之前执行。
既然是推测，就意味着有时候是错的。任何推测机制都必须实现对推测正确性的检测，并在推测错误后回滚（rollback / unroll）已经根据推测结果执行的指令。
编译器可以通过推测机制来调整指令的执行顺序。
软件与硬件在推测错误后的恢复机制是不同的。编译器一般通过插入额外指令来检查推测结果是否正确，并提供负责恢复的指令。而CPU进行该过程时，先缓存推测结果。如推测正确，则将结果直接写入寄存器或内存；反之，清空缓存并重新按正确的顺序执行。
推测机制可能会引发原先没有的异常。编译器针对此种情况的方案是：忽略它们，除非该指令确实会被执行并发生异常。在基于硬件的推测中，异常也被暂时存入缓冲区，直到该指令确实会被执行时，才产生异常，并进入正常的异常处理程序。

39、以下是一个基于MIPS的静态双发射数据通路。

该通路一次读出2条符合要求的指令：一条为计算，一条为存取（没有配对指令时，填充空指令）。可以看出，多了两个ALU，一个用于执行各种算术逻辑操作，另一个则专门计算新的PC值。带符号扩展单元、寄存器堆的读写端口和内存访问端口的数量也翻倍了。
双发射有时可能会引发相对更多的性能损失。例如：如果在load指令后的一条指令需要用到读取的数据，那么这条指令与load指令之间会自动空出一个周期的延迟，称为使用延迟（use latency）。假设紧随其后的下一对指令都需要用到刚才读取的数据，那么这两条指令就要一起停顿一个周期。显然，如果CPU只有单发射，这两条指令之间不用延迟，只需要排在前面的那条指令与load之间隔开1个周期即可。也就是说，执行同样的这段指令，执行到这一处时，在双发射CPU上要比单发射CPU上多了1周期的延迟，使得实际性能的提升幅度减小。为了避免这种情形，在编译器和硬件调度方面都要下更多的功夫。

40、以下是一段MIPS汇编指令：
Loop:
lw $t0, 0($t0,0(s1) # $t0=array element
addu $t0,$t0,t0,$s2 # add scalar in $s2
sw $t0, 0($t0,0(s1) # store result
addi $s1,$s1,s1,–4 # decrement pointer
bne $s1,$s1,zero,Loop # branch $s1!=0
由于前三条指令和后两条指令都具有相关性，并且双发射同时执行的指令类型有限制（一条ALU或分支指令，一条存取指令），最终只能这样子安排指令的执行：

实际IPC仅为1.25，而非理论上的最高值2。注意：计算IPC时，不计nop的影响。

41、循环展开（loop unrolling），指的是将循环中的一系列语句去掉控制循环的指令，并根据循环次数复制若干份副本。这循环展开可以将每两轮循环之间的指令重叠起来执行，提升IPC。
针对上面的例子进行循环展开。我们把这段指令复制三个副本，与原来的指令加起来一共4份。

编译器额外使用了一些寄存器，这称为寄存器重命名（register renaming），可以消除名称依赖（name dependence）——实际上这并不是数据依赖。不过这个技巧并不是总带来正面效果的，有时候它会带来额外的流水线冲突或者使得编译器无法更灵活地调整代码顺序。
经过循环展开后，IPC提升到了1.75，代价是更大的代码占用空间和寄存器占用数量。

42、采用动态多发射的处理器，一般称为超标量处理器（superscalars）。这种处理器在程序运行期间决定哪些指令可以并行。当然，动态多发射处理器仍然需要编译器配合：编译器负责调整指令的顺序，以减少依赖性。代码的正确执行由硬件来保障。
多数超标量处理器都结合动态流水线调度（Dynamic pipeline scheduling）技术：通过指令相关性检测和动态分支预测等手段，投机性地不按指令顺序执行。发生流水线阻塞时，可以到后面找指令来执行。
一个采用动态流水线调度技术的CPU的流水线中的硬件单元可以分为如下三种：取指令与解码单元、功能单元和提交单元（commit unit）。第一个单元取指令并解码，将指令发送至相应的功能单元。每个功能单元都有缓冲区，称为保留站（reservation station，也称执行缓冲区），暂存操作数和操作。当功能单元准备就绪后，开始计算结果。得到结果后，送至保留站等待提交单元提交。当时机适宜后，提交单元正式将数据写入目标寄存器或内存。提交单元的缓冲区常被称为重排序缓冲区（reorder buffer，ROB），被用于将调整了执行顺序的指令重新按原有顺序排列，称为有序提交（in-order commit）。

保留站和重排序缓冲为寄存器重命名提供了实现机制。当指令发射后，它会被复制到正确的功能单元的保留站，寄存器堆和重排序缓冲中的可用操作数也会一并被复制进去。这些缓冲会一直保留到所有需要的操作数和功能单元都可用，缓冲内容在之后会被新的数据覆写。如果寄存器堆和重排序缓冲中读取不到数据，意味着需要的数据应当来自功能单元的执行结果。当相应的功能单元给出结果后，这个结果会不经过寄存器，直接写入保留站。动态流水线调度使得指令的执行顺序与取指令的顺序不同，这种执行方式也称为乱序执行（out-of-order execution，OoOE）。虽然取指令和提交是按顺序执行的，但中间的过程可以灵活调整执行顺序，提升性能。

43、动态流水线调度常与基于硬件的推测结合，包括基于硬件的分支预测。在指令提交前，常常就得以知晓哪些预测是错误的，并令这些错误执行不提交。动态调度的流水线还可以对将要读取的内存地址预测，将存取指令重排，通过拒绝因为预测错误而执行的指令被提交来减少性能损失。

44、前端主要包括取指令、解码和分支预测；后端则由保留站、乱序执行及其控制单元、提交单元构成。前端和后端之间还有指令控制器用来把前端解码出来的操作分发指令给执行单元。

45、编译器可以依据数据依赖关系来调度代码，为什么还要超标量处理器来动态调度？原因主要有三：
（1）并不是所有停顿都可以事先发现。例如缓存缺失（将在第5章学习）无法被编译器提前预知，因为程序开始执行之前，缓存的使用情况显然是不唯一的。动态调度在运行期发现这类阻塞后，可以提前执行无关指令。
（2）当CPU采用动态分支预测时，编译器无法提前得知指令的最终执行顺序，需要根据执行的实际情况进行预测。
（3）发射宽度和流水线延迟在同一指令集的不同CPU上亦可不同，流水线的结构也会影响循环展开的深度和寄存器重命名的效果。于是最佳的指令顺序也会改变。通过动态调度使得处理器细节被屏蔽起来，软件发行商无需针对同一指令集的不同处理器发行相应的编译器，并且以前的代码也可在新的处理器上运行，无需重新编译。

46、现代处理器虽然普遍达到三发射、四发射，但只有很少程序实际运行时能够在每周期执行超过两条指令。
首先，流水线内的主要性能瓶颈是无法被消除的指令间依赖。有些依赖是无法消除的，也有一些是编译器和硬件无法判定为依赖的。为了保证指令执行的正确性，只好保守地调整。例如：使用指针的方法，尤其是可能导致别名的指针用法，可能会产生更多的潜在依赖。相比之下，对长数组的循环遍历一般就没有依赖。有的分支比较复杂，预测并不好做。
其次就是内存访问的异常或者内存方面的系统调用，这些停顿也有无法消除的。

47、大量事实告诉我们，具有乱序执行和激进的推测机制的复杂CPU在能耗比上往往比顺序执行的简单CPU更差。所以近年来的CPU开始降低流水线级数，并在推测机制上针对能效优化。

48、提交单元负责将结果写回寄存器堆或内存，不过有的CPU会在执行时率先更新寄存器堆。一些CPU会用额外的寄存器实现寄存器重命名，并且寄存器原有的内容仍会被保存，直到得以确定推测结果是否正确。

49、动态流水线可以分为三种执行模式：按序发射按序完成、按序发射无序完成和无序发射无序完成。
最保守的方案是顺序完成（顺序提交），好处有：
(1) 简化异常检测和异常处理。
(2) 能在被推测指令完成前得知推测结果的正确性。
按序发射，指的是执行单元有空，上一条已发射就执行；无序发射，指的是执行单元一有空就执行。按序提交，指的是写回单元有空，可在上一条已经写回后写回，或与上一条同时写回；无序提交，指的是写回单元一有空就写回。
无序发射的超标量CPU中，译码后的指令被存放在一个叫做指令窗口的缓冲器中，等待发射。当所需功能部件可用、且无冲突或无相关性阻碍指令执行时，就从指令窗口发射，与取指和译码的顺序无关。在无序发射和无需完成中，无关指令可以先行发射和先行完成。

50、微架构（microarchitecture），是指一个处理器的内部设计与结构，包括功能单元、缓存、寄存器堆、指令发射、流水线控制和互连（interconnect）等。

51、回忆之前进行DGEMM的代码：
void dgemm(int n, double *A, double *B, double C) {
for (int i = 0; i < n; i += 4)
for (int j = 0; j < n; ++j) {
__m256d c0 = _mm256_load_pd(C + i + j * n); / c0 = C[i][j] /
for (int k = 0; k < n; ++k)
c0 = _mm256_add_pd(c0, / c0 += A[i][k]*B[k][j] /
_mm256_mul_pd(_mm256_load_pd(A + i + k * n),
_mm256_broadcast_sd(B + k + j * n)));
_mm256_store_pd(C + i + j * n, c0); / C[i][j] = c0 */
}
}
这段代码产生的汇编指令如下：

1. vmovapd (%r11),%ymm0 ; Load 4 elements of C into %ymm0
2. mov %rbx,%rcx ; register %rcx = %rbx
3. xor %eax,%eax ; register %eax = 0
4. vbroadcastsd (%rax,%r8,1),%ymm1 ; Make 4 copies of B element
5. add $0x8,%rax ; register %rax = %rax + 8
6. vmulpd (%rcx),%ymm1,%ymm1 ; Parallel mul %ymm1,4 A elements
7. add %r9,%rcx ; register %rcx = %rcx + %r9
8. cmp %r10,%rax ; compare %r10 to %rax
9. vaddpd %ymm1,%ymm0,%ymm0 ; Parallel add %ymm1, %ymm0
10. jne 50 <dgemm+0x50> ; jump if not %r10 != %rax
11. add $0x1,%esi ; register % esi = % esi + 1
12. vmovapd %ymm0,(%r11) ; Store %ymm0 into 4 C elements
    现在有一个启用循环展开优化的版本：
    #include <intrin.h>
    #define UNROLL (4)

void dgemm(int n, double* A, double* B, double* C) {
for (int i = 0; i < n; i += UNROLL * 4)
for (int j = 0; j < n; ++j) {
__m256d c[4];
for (int x = 0; x < UNROLL; ++x)
c[x] = _mm256_load_pd(C + i + x * 4 + j * n);
for (int k = 0; k < n; ++k) {
__m256d b = _mm256_broadcast_sd(B + k + j * n);
for (int x = 0; x < UNROLL; ++x)
c[x] = _mm256_add_pd(
c[x], _mm256_mul_pd(
_mm256_load_pd(A + n * k + x * 4 + i), b));
}
for (int x = 0; x < UNROLL; ++x)
_mm256_store_pd(C + i + x * 4 + j * n, c[x]);
}
}
这段代码产生的汇编指令如下：
1 vmovapd (%r11),%ymm4 ; Load 4 elements of C into %ymm4
2 mov %rbx,%rax ; register %rax = %rbx
3 xor %ecx,%ecx ; register %ecx = 0
4 vmovapd 0x20(%r11),%ymm3 ; Load 4 elements of C into %ymm3
5 vmovapd 0x40(%r11),%ymm2 ; Load 4 elements of C into %ymm2
6 vmovapd 0x60(%r11),%ymm1 ; Load 4 elements of C into %ymm1
7 vbroadcastsd (%rcx,%r9,1),%ymm0 ; Make 4 copies of B element
8 add $0x8,%rcx ; register %rcx = %rcx + 8
9 vmulpd (%rax),%ymm0,%ymm5 ; Parallel mul %ymm1,4 A elements
10 vaddpd %ymm5,%ymm4,%ymm4 ; Parallel add %ymm5, %ymm4
11 vmulpd 0x20(%rax),%ymm0,%ymm5 ; Parallel mul %ymm1,4 A elements
12 vaddpd %ymm5,%ymm3,%ymm3 ; Parallel add %ymm5, %ymm3
13 vmulpd 0x40(%rax),%ymm0,%ymm5 ; Parallel mul %ymm1,4 A elements
14 vmulpd 0x60(%rax),%ymm0,%ymm0 ; Parallel mul %ymm1,4 A elements
15 add %r8,%rax ; register %rax = %rax + %r8
16 cmp %r10,%rcx ; compare %r8 to %rax
17 vaddpd %ymm5,%ymm2,%ymm2 ; Parallel add %ymm5, %ymm2
18 vaddpd %ymm0,%ymm1,%ymm1 ; Parallel add %ymm0, %ymm1
19 jne 68 <dgemm+0x68> ; jump if not %r8 != %rax
20 add $0x1,%esi ; register % esi = % esi + 1
21 vmovapd %ymm4,(%r11) ; Store %ymm4 into 4 C elements
22 vmovapd %ymm3,0x20(%r11) ; Store %ymm3 into 4 C elements
23 vmovapd %ymm2,0x40(%r11) ; Store %ymm2 into 4 C elements
24 vmovapd %ymm1,0x60(%r11) ; Store %ymm1 into 4 C elements
测试条件：Sandy Bridge Core i7，矩阵大小：32×32。
编译条件：循环展开版本为-O3，且展开深度为4。
测试结果：
Freq (GHz) 2.6 3.3 2.6 3.3 2.6 3.3
Version Unoptimized Unoptimized AVX AVX AVX, DLP, ILP AVX, DLP, ILP
GFLOPS 1.7 2.1 6.4 8.1 14.6 18.6
注：3.3 GHz为Turbo开启的频率，2.6 GHz为Turbo关闭的频率。

52、实现流水线设计并不容易。本复习指导的配套教材《计算机组成与设计：硬件 / 软件接口》的两位作者（David A. Patterson，John L. Hennessy）写过另一本更为深入的体系结构书《计算机架构：量化方法》。该书的第一版（现在已经更新到第11版）出版时，讲解流水线的内容中有一个bug，即使经过了100人的复查，并且在18所大学的课上使用过，也未能将其发现，直到有人尝试按照书本的内容去实现这样的一个CPU。使用Verilog来实现Core i7的流水线至少需要几千行。

53、不适当的指令集设计会对流水线产生不利影响。
变化的指令长度和运行时间会导致流水线阶段的不平衡，严重影响流水线冲突的探测。直到1980年的DEC VAX 8500开始，这个问题才通过引入微操作和微流水线（micropipeline）机制成功解决。这两个机制也是Intel Core i7一直使用到如今的机制。当然，指令与微指令之间的翻译和一致性保持还是需要一定的开销。
复杂的寻址模式会带来一系列问题。需要更新寄存器的寻址模式可能使流水线冲突的检测变得困难。一些需要多次内存访问的寻址模式则给流水线控制带来了极大压力，导致很难保持流水线的充分负载。
DEC Alpha和DEC NVAX是一对很好的例子。Alpha采用了新的ISA，使得其性能达到NVAX的两倍以上。另一个例子是MIPS M/2000和DEC VAX 8700。虽然M/2000在SPEC基准测试中执行了更多的指令数，但是VAX 8700运行SPEC项目时平均执行的周期数达到了M/2000的2.7倍，导致最终MIPS M/2000的速度更快。