这一节内容相对较为基础，或许写得有些冗长，但是是融入了初次接触体系结构优化必要的思想。

20.1 ILP 基本概念与简单认识

ILP 基本概念

在本章引言中，我们已经提到 ILP 实际上是一种利用指令间潜在并行性进行优化的技术。最简单的例子便是流水线技术，它将指令的执行分为较短的几个阶段，不同的指令在同一时刻可以处于不同的执行阶段，由此实现了指令级并行。

需要注意的一点是，在本节中我们不再默认 CPU 执行是按照之前所学的五阶段顺序流水线，而是希望我们的 CPU 能够并行执行所有指令，这对于理解关于本节中依赖于冒险的概念十分重要。

基本块（Basic Block）

请阅读以下代码：

for (int i =0; i <= 999; i++)
    x[i] = x[i] + y[i];

相信你能够十分轻松地将这一段代码转化为 RISC-V 汇编代码。让你的流水线 CPU 开始执行这些代码，你将会无助地发现，无需几条指令，你的代码便会陷入控制冒险中。这显然不是我们希望看到的，但是很遗憾，对于一般的 RISC 程序，平均需要分支预测的指令比例通常在 15% 到 25% 之间，也就是说，平均约 4-7 条指令便会遭遇一次控制冒险，这并不是一个好消息。为了更好地描述这一问题，我们引入一个新的概念称为基本块。程序中的基本块只有一个入口和一个出口，入口就是其中的第—条语句，出口就是其中的最后一条语句。对一个基本块来说，执行时只从其入口进入，从其出口退出。具体而言：

只有一个入口，表示程序中不会有其它任何地方能通过跳转类指令进入到此基本块中；
只有一个出口，表示程序只有最后一条指令能导致进入到其它基本块去执行。

所以，基本块的一个典型特点是：只要基本块中第一条指令被执行了，那么基本块内所有执行都会按照顺序仅执行一次。有了基本块的定义后，前述问题可被描述为五个字：基本块太小。并且由此控制冒险严重。不仅如此，基本块中的指令间数据冒险也常常十分严重，因此严重影响ILP所需的指令间潜在并行性。为了优化这一问题，我们不难想到以下三种途径：

为了降低控制冒险的损失，我们可以使用高级的分支预测技术；
面对冲突严重的情况，我们可以通过硬件动态调度进一步挖掘并行性；
同一基本块内冲突严重，我们可以通过静态调度，使得我们可以在不同的基本块的指令间实现ILP。

1 中涉及的内容在 Chapter08 中已经介绍，在 20.4 中我们会有更多的拓展。对于 2 和 3，我们也将在之后的章节中详细讲解。

事实上，基本块这一概念不仅在体系结构中会被不断强调，在编译原理、程序分析等领域也是很基本的概念，此处不再展开，只表明其重要性。

依赖（dependence）与冒险（hazard）

在之前的学习以及本节前述内容中我们知道，指令级并行的瓶颈主要在于两点：

前后指令使用了相同的寄存器，使得指令之间存在数据依赖或名字依赖关系；
存在大量跳转指令，使得我们必须执行完跳转指令后才能确定接下来执行的指令，因此指令间还存在控制依赖。这一方面跳转指令会拖慢流水线执行效率，还有分支预测错误的可能，另一方面还会使得基本块太小，使得后文介绍的动态调度的空间非常有限。

当然根据我们在流水线一章中学习的内容，结构冒险也是潜在的瓶颈之一，但在以上两个问题严重的情况下，结构冒险的问题便不再突出，毕竟同一时刻能同时执行的指令十分有限。突破上述瓶颈的方案将会在后续章节讲解，这一两小节将为后文的分析引入一些基本概念，由此我们可以认识到，怎样的指令之间并行性会受限。

数据依赖（data dependence）

我们首先来看这样一段代码，这段代码的功能是将内存地址从 0(x1) 开始到 0(x2) 结束的每个 64 位浮点数都加上 f2 寄存器中存储的值：

Loop: 
    fld    f0, 0(x1)      // 将内存中 64 位浮点数取入 f0 寄存器
    fadd.d f4, f0, f2     // 将取入的数值加上 f2 中的数值
    fsd    f4, 0(x1)      // 存入修改后的数值
    addi   x1, x1, -8     // 读写内存的地址-8
    bne    x1, x2, Loop   // 直到 x1 = x2 不再继续

学过流水线数据冒险的我们我们不难发现，假如上述代码在简单的顺序执行流水线 CPU 上运行，

fld    f0, 0(x1)
fadd.d f4, f0, f2

这一代码片段中存在一个关于寄存器 f0 的数据冒险——因为加法指令的源操作数中用到了上一条指令的目的寄存器，于是这两条指令间便有了数据流动，即 fld 指令得到的结果通过 f0 寄存器流动到 fadd.d 指令。由此我们便引入第一种指令依赖关系——数据依赖。我们称指令 \(j\) 数据依赖于指令 \(i\) （我们称指令 \(j\) 为依赖方，指令 \(i\) 为被依赖方），如果

指令 \(j\) 需要指令 \(i\) 产生的结果作为其源操作数；
指令 \(j\) 数据依赖于指令 \(k\) ，指令 \(k\) 数据依赖于指令 \(i\) 。

事实上我们已经十分熟悉上面这种递归式的定义，1 中的描述说明了数据依赖产生的 base case，2 中的描述表明数据依赖可以形成一个“数据依赖链”，这个链条的长度甚至可以贯穿整个程序。

从数据流动的角度来看上述定义也是很清晰的，当指令 \(i\) 有数据流动到指令 \(k\) ，指令 \(k\) 又有数据流动到指令 \(j\) 时，我们可以将数据流动类比为河流，这种流动具有传递性，因此只要在同一数据依赖链上，两条指令间便有数据依赖关系。

定义数据依赖后有一个很显然的意义，即存在数据依赖的两条指令之间必须（即使两条指令在数据依赖链条中距离较远也必须如此，可以思考其中原因）依照源程序规定的执行顺序执行，否则无法确保依赖方源操作数的准确性，因此我们的动态调度、静态调度技术需要检测出这种依赖，并保证顺序执行。

还有一点需要强调的是，我们在定义的第一条中并没有限制数据依赖必须是使用了相同寄存器，实际上访问同样的内存地址也是符合定义的。但是这增大了检测依赖的难度，因为同一个内存地址可以有不同表达方式，例如可以表示为 0(x1)，也可以表示为 -12(x2)，这便增大了检测难度。在后续章节中我们会详细讲解现在的技术如何解决这一较为复杂的问题。

名字依赖（name dependence）

我们继续阅读上述代码，可以观察到以下两个代码块：

代码块 1：

fadd.d f4, f0, f2
fsd    f4, 0(x1)

代码块 2：

fsd    f4, 0(x1)
addi   x1, x1, -8

在代码块 1 中，f4 寄存器同时是两条指令的目的寄存器，在代码块 2 中，x1 寄存器在作为第一条指令的源操作数的同时是第二条指令的目的寄存器。像这样两条指令都使用了相同的寄存器或内存地址，但两条指令间没有数据流动的依赖，称为名字依赖。这里的名字实际上就是寄存器或是内存地址的另称。

事实上，在两个代码块中我们已经将名字依赖分为更具体的两种类型：

假定在一个程序中，指令 \(i\) 出现在指令 \(j\) 之前，则有以下两种名字依赖类型：

**反依赖（antidependence）**指指令 \(j\) 写入了指令 \(i\) 源操作数所在的寄存器或内存地址；
**输出依赖（output dependence）**指指令 \(i\) 和指令 \(j\) 写入了同一寄存器或内存地址。

显然，代码块 1 中出现了输出依赖，代码块 2 中出现了反依赖。学过顺序执行流水线的我们或许会疑惑，因为名字依赖不存在指令间数据流动，因此并不会引起流水线暂停或引发前递。但是为什么我们仍然需要考察这两种依赖呢？我们回顾 20.1 节开头所提及的，我们现在希望所有的指令都并行执行，那么很有可能指令 \(i\) 是一条需要较多周期执行的指令（如乘除法），指令 \(j\) 则需要较少周期即可（如加减法），假如此时存在输出依赖，那么很可能指令 \(i\) 写入目的寄存器/内存地址的时间比指令 \(j\) 晚，于是便会导致目的寄存器/内存地址的值与期望不一致。

对于反依赖，我们描述一种可能的情形，指令 \(i\) 可能因为与之前的指令存在结构冒险或数据冒险被迫暂停，而此时指令 \(j\) 直接开始执行，就有可能导致指令 \(i\) 读入被指令 \(j\) 改写后的数据，发生错误。

当然，细心的你可能会发现，我们先前并没有对两条指令源操作数中使用同一寄存器/内存地址定义依赖关系，因为这种情况无论顺序或乱序执行都不会出现上述冲突情况。

但是，名字依赖实际上都可以通过重命名的方式消除，例如我们将代码块1改为：

fadd.d f5, f0, f2
fsd    f4, 0(x1)

即我们只需在编译时刻将 fadd.d 的目的寄存器 f4 改为其他未使用的寄存器（如 f5）即可避免名字依赖的出现。当然修改 fsd 的目的寄存器也是可行的，这两种修改都需要检查其他与 f4、f5 相关的指令是否受到影响，当然实际上好的编译器会帮我们做好这些事情，于是名字依赖便可以在寄存充足的情况下被消除。

数据冒险（data hazard）

大家不难发现，我们在前文中多次提及数据依赖与数据冒险这两个词，我们十分有必要首先说明这两个词的区别，以免产生混淆，同时分析二者的联系：

数据依赖是程序本身的性质，当我们看见一个程序，便可以根据上一节中给出的定义判断存在什么数据依赖。而数据冒险是指两条指令位置足够靠近，使得两条指令并行会导致数据依赖中的寄存器/内存地址访问时机不符合预期，这是与流水线的执行策略有关的，例如采用之前学习的五阶段顺序执行流水线进行调度，输入程序可以存在名字依赖，但不会因此产生流水线数据冒险；
由1可以看出，数据依赖是产生数据冒险的原因，因此我们的优化方向一方面可以减少数据依赖的出现，相关技术（重命名）在上一节中已有初步介绍，另一方面则是在数据依赖存在的情况下通过调度技术修改流水线执行策略，尽可能减少数据冒险的出现，我们将在之后章节讲解此类技术。

我们可以根据前文中数据依赖的类型对数据冒险同样进行分类，考虑依次出现的两条指令 \(i\) 和 \(j\) ：

**RAW（read after write，写后读）**出现在存在数据依赖时，指令 \(i\) 还未写入目的寄存器/内存地址时指令 \(j\) 就读取了存在依赖的值，这种情况会导致指令 \(j\) 读取了错误的数据，可以通过前递（forwarding）或暂停（stall）解决或避免；
**WAW（write after write，写后写）**出现在存在输出依赖时，两条指令写回目的寄存器/内存地址的顺序发生了变化从而导致错误，可能的情形已在上一节提及，并且这可以直接通过重命名的方式将输出依赖解除，从而解除这一数据冒险；
**WAR（write after read，读后写）**出现在存在反依赖时，指令 \(j\) 写回与指令 \(i\) 间有依赖的寄存器/内存地址比指令 \(i\) 读入的时间早，则指令 \(i\) 读入了被修改过的数据，产生了错误。产生这一情形的原因已在上一节提及，并且这可以直接通过重命名的方式将输出依赖解除，从而解除这一数据冒险。

注意，RAR（read after read，读后读）没有对应的数据依赖且不会产生冒险，因此不构成一种数据冒险类型，理由已在之前说明。可以看到，在描述数据冒险时我们的定义描述的是执行错误的后果，这与数据依赖基于程序中指令本就存在的依赖关系的定义是有很大区别的。

控制依赖（control dependence）与分支冒险（branch hazard）

TODO: 图 20-1. 依赖与冒险的总结图

在这一节的最后，我们来完成一个简单的练习以巩固所学的知识：

练习 20.1.1

阅读以下汇编代码并回答问题，假定代码将运行在无前递（forwarding）机制的顺序执行流水线 CPU 上，跳转指令在 ID 阶段判断执行，每条指令的理想执行时间均为 1 个流水线周期：

    ld   t0, -8(x1)
    addi t1, x0, 0
    beqz t0, L2
L1:
    ld   t2, 0(x1)
    add  t1, t1, t2
    sd   t1, 0(x1)
    addi x1, x1, 8
    addi t0, t0, -1
    bnez t0, L1
L2:
    ...

请描述上述代码的功能，并写出上述代码中所有的基本块；
请写出上述代码中所有出现的数据依赖与数据冒险类型，并计算执行上述代码所需的最小周期数；
请分析 2 中数据依赖/数据冒险能否解决，并根据你的解决方法，计算出解决数据冒险后执行上述代码所需的最小周期数。

计算机系统——从小白学起