3.1 引言

大约从 1985 年起，所有处理器都采用流水线，使指令的执行相互重叠，从而提高性能。指令之间这种潜在的重叠称为指令级并行性（instruction-level parallelism，ILP），因为这些指令可以并行求值。本章与附录 H 将讨论一系列技术：通过开发指令之间更多的并行性，扩展基本的流水线思想。

本章内容比附录 C 的基本流水线知识深入得多。如果你对附录 C 的概念还不够熟悉，建议先复习该附录，再进入本章。

本章首先考察数据冒险和控制冒险施加的限制，然后讨论如何增强编译器与处理器开发并行性的能力。前两节将介绍大量概念，本章后续内容以及下一章都建立在这些概念之上。

开发 ILP 大体有两种可以分开讨论的方法：（1）依靠硬件动态发现和开发并行性；（2）依靠软件技术，在编译时静态找出并行性。本章介绍这两种方法的核心概念，因为为其中一种方法开发的许多技术，也已用于主要依赖另一种方法的设计。采用动态硬件方法的处理器，包括近期所有 Intel、AMD 处理器以及许多 Arm 处理器，如今已主导桌面和服务器市场。同样的方法也已普遍用于平板电脑及大多数智能手机中的处理器。在物联网领域，功耗与成本约束比性能目标更重要，因此设计者开发的 ILP 程度较低。从 20 世纪 80 年代开始，人们曾多次尝试更激进的编译器方法，最近的一次是 1999 年推出的 Intel Itanium 系列。尽管投入了巨大的努力，这些方法只在领域专用体系结构，或具有大量数据级并行性、结构良好的科学应用中取得了成功（见第 7 章）。

本章还讨论 ILP 方法的局限，因为正是这些局限直接促成了向多核处理器的转变。在权衡 ILP 与线程级并行性（TLP）的使用时，理解这些局限仍然很重要。

本节讨论程序与处理器中哪些特征会限制可开发的指令间并行性，以及程序结构与硬件结构之间的关键映射关系。理解这种映射，才能判断某种程序属性是否真的会限制性能，以及会在什么情况下构成限制。

流水线处理器的 CPI（每条指令的时钟周期数），等于基础 CPI 与各种停顿的贡献之和：

理想流水线 CPI 衡量一种实现所能达到的最高性能。降低等号右侧的任意一项，就能降低流水线的总体 CPI；换一种说法，就是提高 IPC（每个时钟周期执行的指令数）。利用上式，可以按照某项技术降低总体 CPI 中的哪一部分，对各种技术加以描述。图 3.1 列出了本章与附录 H 将研究的技术，以及附录 C 入门内容涵盖的主题。本章将看到，我们用来降低理想流水线 CPI 的技术，也会使冒险处理变得更加重要。

图 3.1 附录 C、第 3 章与附录 H 研究的主要技术，以及各项技术影响的 CPI 公式分量。

什么是指令级并行性？

本章的所有技术都开发指令之间的并行性。一个基本块（basic block）内部可用的并行性很少。基本块是一段顺序代码，分支只能从入口进入，并且只能从出口离开。典型 RISC 程序中，动态执行的指令里，分支所占比例通常为 15%～25%，这意味着两个分支之间会执行 3～6 条指令。由于这些指令很可能相互依赖，基本块内部能够实现的重叠程度，往往还小于基本块的平均大小。要显著提高性能，就必须跨越多个基本块开发 ILP。

提高 ILP 最简单、也最常用的方法，是开发循环各次迭代之间的并行性。这种并行性通常称为循环级并行性。

下面是一个简单例子：循环将两个各含 1000 个元素的数组相加，而且完全可以并行执行。

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

虽然每次循环迭代内部几乎没有指令重叠的机会，但任意一次迭代都可以与其他任何迭代重叠。本章将介绍多种将这种循环级并行性转化为 ILP 的技术。其基本方法是展开循环：可以由编译器静态展开（下一节讨论），也可以由硬件动态展开（3.3～3.8 节讨论）。

开发循环级并行性的另一种重要方法，是在向量处理器与图形处理单元（GPU）中使用 SIMD；第 4 章将介绍这两类处理器。SIMD 指令通过并行处理少量到中等数量的数据项（通常为 2～16 个），开发数据级并行性。向量指令则同时利用并行执行单元与深流水线，并行处理大量数据项，从而开发数据级并行性。例如，上述代码用最简单的方式实现时，每次迭代需要 7 条指令：两次加载、一次加法、一次存储、两次地址更新和一次分支，总计 7000 条指令。在某种每条指令处理 4 个数据项的 SIMD 体系结构上，所需指令数可能只有四分之一。在某些向量处理器上，这段代码可能只需 4 条指令：两条向量指令从内存加载向量 x 与 y，一条向量指令将它们相加，另一条向量指令将结果向量写回。当然，这些指令会以流水线方式执行，延迟也相对较长，但这些延迟可以相互重叠。

数据依赖与冒险

要确定程序有多少并行性，以及如何开发这些并行性，关键在于判断一条指令如何依赖另一条指令。具体而言，要开发 ILP，就必须确定哪些指令可以并行执行。若两条指令相互独立，那么只要流水线有足够资源、不存在结构冒险，它们就能在任意深度的流水线中同时执行，而不引起停顿。若两条指令存在依赖，它们就不能并行，而必须按顺序执行，不过通常仍可以部分重叠。两种情况下，关键都是确定一条指令是否依赖另一条指令。

数据依赖

依赖分为三类：数据依赖（也称真数据依赖）、名依赖与控制依赖。若满足以下任一条件，指令 $j$ 就对前面的指令 $i$ 存在数据依赖：

• 指令 $i$ 产生一个可能被指令 $j$ 使用的结果。
• 指令 $j$ 对指令 $k$ 存在数据依赖，而指令 $k$ 对指令 $i$ 存在数据依赖。

第二个条件只是说，如果指令 $j$ 经由第一类依赖组成的链条，间接依赖指令 $i$，两者也存在数据依赖。这条依赖链可以长到贯穿整个程序。注意，单条指令内部的依赖，例如 add x1,x1,x1，不计作这里所说的依赖。

例如，考虑下面的 RISC-V 代码。它把寄存器 f2 中的标量加到内存中的一个向量上；该向量从地址 0(x1) 开始，最后一个元素位于地址 0(x2)。

Loop: fld    f0,0(x1)     // f0 = 数组元素
      fadd.d f4,f0,f2     // 加上 f2 中的标量
      fsd    f4,0(x1)     // 存储结果
      addi   x1,x1,-8     // 指针减去 8 字节
      bne    x1,x2,Loop   // x1 ≠ x2 时跳转

该指令序列中的数据依赖既涉及浮点（FP）数据：

Loop: fld    f0,0(x1)     // f0 = 数组元素
             │
             └─→ fadd.d f4,f0,f2  // 加上 f2 中的标量
                       │
                       └─→ fsd f4,0(x1)  // 存储结果

也涉及整数数据：

addi x1,x1,-8     // 指针减去 8 字节（每个双字）
     │
     └─→ bne x1,x2,Loop  // x1 ≠ x2 时跳转

上面两个存在依赖的序列中，箭头都表明每条指令依赖前一条指令。此处及后续例子的箭头表示，为正确执行而必须保留的顺序：箭尾所在指令必须先于箭头指向的指令。

若两条指令存在数据依赖，就必须按顺序执行，不能同时执行或完全重叠。依赖意味着，两条指令之间存在由一个或多个数据冒险组成的链条。（附录 C 对数据冒险作了简要说明，稍后我们会给出精确定义。）若同时执行这两条指令，具有流水线互锁的处理器就会检测到冒险并停顿，前提是流水线深度大于两条指令之间以周期数计的距离；这会减少甚至完全消除重叠。对于没有互锁、依靠编译器调度的处理器，编译器不能把有依赖的指令调度成完全重叠，否则程序就无法正确执行。指令序列中的数据依赖，反映了生成这些指令的源代码中存在的数据依赖。原始数据依赖的作用必须得到保留。

依赖是程序的属性。 某种依赖是否真的会使处理器检测到冒险，以及冒险是否真的会导致停顿，则是流水线组成的属性。理解这种区别，是理解如何开发 ILP 的关键。

数据依赖传达三方面信息：（1）存在冒险的可能性；（2）计算结果必须遵循的顺序；（3）可开发并行性的上限。本章末尾的一个陷阱条目将讨论这些限制，附录 H 会作更详细的探讨。

由于数据依赖会限制可开发的 ILP，本章的一项重点就是如何克服这些限制。可以采用两种方式：（1）保留依赖，但避免冒险；（2）通过变换代码消除依赖。在不改变依赖的前提下避免冒险，主要依靠代码调度；编译器和硬件都可以进行这种调度。

数据值既可以通过寄存器，也可以通过内存位置，在指令之间传递。当数据流经寄存器时，检测依赖比较直接，因为寄存器名称固定在指令编码中；不过，中间若夹有分支，问题就会更复杂，而且为确保正确性，编译器或硬件必须采取保守做法。当加载指令使用了先前存储指令产生的数据值时，就会形成经由内存位置传递的依赖。这类依赖更难检测，因为两个看起来不同的地址，可能指向同一个位置。例如，100(x4) 与 20(x6) 可能是同一个内存地址。此外，同一条加载或存储指令每次执行时，其有效地址可能不同；因此，100(x6) 与 20(x4) 有时相同、有时不同，这进一步增加了依赖检测的难度。

本章将研究用于检测涉及内存位置的数据依赖的硬件，但也会看到这些技术本身的局限。编译器对这类依赖的检测技术，对于发现循环级并行性至关重要。

名依赖

第二类依赖是名依赖（name dependence）。当两条指令使用同一个寄存器或内存位置，也就是同一个“名称”，但与该名称有关的数据并未在它们之间传递时，就存在名依赖。设指令 $i$ 在程序顺序中先于指令 $j$，两者之间可能存在两种名依赖：

1. 若指令 $j$ 写入的寄存器或内存位置被指令 $i$ 读取，$i$ 与 $j$ 之间就存在反依赖（antidependence）。必须保留原始顺序，确保 $i$ 读到正确的值。在前面的例子中，fsd 与 addi 之间存在关于寄存器 x1 的反依赖。

2. 若指令 $i$ 与指令 $j$ 写入同一个寄存器或内存位置，就存在输出依赖（output dependence）。必须保留它们之间的顺序，确保最后写入的值来自指令 $j$。

反依赖和输出依赖都属于名依赖，而不是真数据依赖，因为这两条指令之间并没有传递任何值。既然名依赖不是真依赖，只要改变指令所使用的名称，即寄存器编号或内存位置，使它们不再冲突，相关指令就可以同时执行或重新排序。对寄存器操作数进行这种重命名比较容易，这称为寄存器重命名。寄存器重命名既可以由编译器静态完成，也可以由硬件动态完成。

数据冒险

在讨论分支引起的依赖之前，先看看依赖与流水线数据冒险之间的关系。如果两条指令存在名依赖或数据依赖，并且它们的执行重叠到足以改变相关寄存器操作数或内存位置的访问顺序，就会发生冒险。由于存在依赖，我们必须保留所谓的程序顺序：即按照原始源程序，一次执行一条指令时所遵循的顺序。软件与硬件技术的共同目标，是仅在程序顺序会影响程序结果时才保留它，从而开发并行性。检测并避免冒险，可以确保保留必要的程序顺序。

根据指令中读、写访问的顺序，数据冒险可分为三类。按照惯例，冒险以流水线必须保留的程序顺序来命名。考虑两条指令 $i$ 与 $j$，其中 $i$ 在程序顺序中先于 $j$。可能的数据冒险如下：

• RAW（read after write，写后读）：$j$ 试图在前面的指令 $i$ 写入源操作数之前读取它，因此错误地读到了旧值。这是最常见的冒险，对应真数据依赖。必须保留程序顺序，确保 $j$ 得到 $i$ 产生的值。
• WAW（write after write，写后写）：$j$ 试图在 $i$ 写入某个操作数之前写入它。最终写入操作按错误的顺序完成，使目标寄存器或内存位置中留下的是 $i$ 写入的值，而非 $j$ 写入的值。这种冒险对应输出依赖。只有在多个流水级都可能执行写入，或者允许指令在前面的指令停顿时继续推进的流水线中，才会发生 WAW 冒险。

• WAR（write after read，读后写）：$j$ 试图在 $i$ 读取某个目标位置之前写入它，因此 $i$ 错误地读到了新值。这种冒险源于反依赖。多数静态发射流水线中，即使是更深的流水线或浮点流水线，也不会发生 WAR 冒险，因为所有读取都在较早阶段完成（附录 C 的流水线中为 ID），所有写入都在较晚阶段完成（附录 C 中为 WB）。若某些指令在流水线前部写入结果，而另一些指令在后部才读取源操作数，就可能发生 WAR 冒险；指令重新排序时也可能发生，本章将讨论这种情况。

注意，RAR（read after read，读后读）并不是冒险。

控制依赖

最后一类依赖是控制依赖。控制依赖确定指令 $i$ 相对于某条分支指令的顺序，使 $i$ 按正确的程序顺序执行，而且只在应该执行时才执行。除程序第一个基本块中的指令外，每条指令都对一组分支存在控制依赖；一般来说，要保留正确的程序顺序，就必须保留这些控制依赖。最简单的控制依赖例子之一，是 if 语句中 then 部分的语句对分支的依赖。例如：

if p1 {
    S1;
}
if p2 {
    S2;
}

S1 对 p1 存在控制依赖，S2 对 p2 存在控制依赖，但不依赖 p1。一般而言，控制依赖施加两项约束：

1. 对某条分支存在控制依赖的指令，不能移到该分支之前，使其执行不再受该分支控制。例如，不能把 if 语句 then 部分的一条指令移到 if 语句之前。
2. 对某条分支不存在控制依赖的指令，不能移到该分支之后，使其执行受到该分支控制。例如，不能把 if 之前的一条语句移入 then 部分。

严格保持程序顺序的处理器，也会保持控制依赖。不过，只要不影响程序的正确性，我们可能愿意执行本不该执行的指令，从而违反控制依赖。

因此，必须保留的关键属性并不是控制依赖本身。真正决定程序正确性的两项属性，是异常行为与数据流；通常，通过保持数据依赖与控制依赖，就能保留这两项属性。

保持异常行为，意味着无论如何改变指令执行顺序，都不能改变程序触发异常的方式。这个要求常被放宽为：指令执行顺序的改变，不得使程序产生新的异常。下面的简单例子说明，保持控制依赖与数据依赖如何避免这类问题。

add x2,x3,x4
beq x2,x0,L1
ld  x1,0(x2)
L1:

容易看出，若不保持涉及 x2 的数据依赖，就会改变程序结果。较不明显的是，如果忽略控制依赖，把加载指令移到分支之前，加载指令就可能引发内存保护异常。注意，没有数据依赖阻止我们交换 beq 与 ld，限制只来自控制依赖。要在保留数据依赖的同时重新安排这两条指令，我们希望能够在分支跳转时直接忽略这个异常。3.3 节将介绍一种称为推测执行（speculation）的硬件技术，它使我们能够克服控制依赖造成的限制，包括这里的异常问题。附录 H 则介绍支持推测执行的软件技术。

保持数据依赖与控制依赖所保留的第二项属性是数据流。数据流是数据值在产生结果的指令与使用结果的指令之间的实际流动。分支使数据流具有动态性，因为某条指令的数据来源可能位于多个位置。换言之，仅仅保持数据依赖并不够，因为一条指令可能对不止一条先前指令存在数据依赖。究竟由哪条先前指令向它提供数据值，取决于程序顺序；保持控制依赖，就能确保这一顺序。

例如，考虑以下代码片段：

add x1,x2,x3
beq x4,x0,L
sub x1,x5,x6
L:  …
or  x7,x1,x8

这里，or 使用的 x1 值取决于分支是否跳转。仅有数据依赖不足以保证正确性。or 对 add 和 sub 都存在数据依赖，但只保持这种先后顺序，还不足以保证正确执行。

指令实际执行时还必须保留数据流：若分支不跳转，or 应使用 sub 计算的 x1 值；若分支跳转，则应使用 add 计算的 x1 值。保持 or 对分支的控制依赖，就能防止数据流发生不合法的改变。同理，不能把 sub 移到分支之前。3.3 节将看到，帮助处理异常问题的推测执行，也能在保留数据流的同时减轻控制依赖的影响。

有时，我们能够确定，违反控制依赖既不会影响异常行为，也不会影响数据流。考虑下面的代码：

      add x1,x2,x3
      beq x12,x0,skip
      sub x4,x5,x6
      add x5,x4,x9
skip: or  x7,x8,x9

假设我们知道，在标记为 skip 的指令之后，sub 的目标寄存器 x4 不会再被使用。（某个值是否会被后续指令使用，这种属性称为活跃性，liveness。）若 x4 不再被使用，那么在分支之前改变它的值，就不会影响数据流，因为在 skip 之后的代码区域里，x4 是死的（dead），而不是活跃的（live）。因此，如果 x4 是死的，而且现有的 sub 指令不会产生异常——处理器处理后会继续恢复同一进程执行的异常除外——就可以把 sub 移到分支之前，因为这一改动不会影响数据流。

如果分支跳转，sub 虽然会执行，却不会起作用；但它也不会影响程序结果。这种代码调度也是推测执行的一种，通常称为软件推测执行，因为编译器是在对分支结果下注；这里押的是分支通常不跳转。附录 H 讨论更激进的编译器推测执行机制。通常，上下文足以说明“推测执行”是由硬件还是软件实现；若不够清楚，我们会明确写出“硬件推测执行”或“软件推测执行”。

通过检测控制冒险并引入控制停顿，可以保持控制依赖。多种软件与硬件技术能够消除或减少控制停顿，我们将分别在 3.2 节和 3.4 节讨论。