计算机体系结构基础知识介绍之指令级并行性：概念和挑战_体系结构 名称依赖 反依赖 输出依赖

一、相关概念

自 1985 年以来，所有处理器都使用流水线来重叠指令的执行并提高性能。 指令之间的这种潜在重叠称为指令级并行性（ILP）。 

具体来说：流水线和指令级并行是两个相关的概念。

流水线是一种将每条指令分解为多个阶段，并让不同阶段的操作重叠进行的一种技术，可以提高指令的执行效率和吞吐率。指令级并行是指在一个时钟周期内，可以同时执行多条指令的一种技术，可以提高处理器的性能和利用率。

流水线和指令级并行之间的关系是，流水线是实现指令级并行的一种基本方法，但是流水线也会受到一些因素的限制，如指令之间的相关性、结构冲突、控制冲突等。为了克服这些限制，需要采用一些技术，如指令调度、寄存器换名、分支预测、动态调度等。

利用 ILP 有两种基本上可分离的方法：(1) 依赖硬件来帮助动态发现和利用并行性的方法；(2) 依赖软件技术在编译时静态发现并行性的方法。

使用动态、基于硬件的方法的处理器（包括所有最新的英特尔和许多 ARM 处理器）在桌面和服务器市场占据主导地位。 在个人移动设备市场，平板电脑和高端手机的处理器也采用相同的方法。 

增加 ILP 的最简单且最常见的方法是利用循环迭代之间的并行性。 这种类型的并行性通常称为循环级并行性。 下面是一个简单的循环示例，它将两个 1000 元素的数组相加并且完全并行：

循环的每次迭代都可以与任何其他迭代重叠，尽管在每次循环迭代内，重叠的机会很少。 

我们将研究多种将这种循环级并行性转换为指令级并行性的技术。 基本上，此类技术的工作原理是由编译器静态展开循环或由硬件动态展开循环。

二、相关挑战

2.1 数据依赖性和危险

确定一条指令如何依赖另一条指令对于确定程序中存在多少并行性以及如何利用该并行性至关重要。 特别是，为了利用指令级并行性，我们必须确定哪些指令可以并行执行。 如果两条指令是并行的，它们可以在任意深度的管道中同时执行，而不会导致任何停顿，假设管道有足够的资源（因此不存在结构危险）。 如果两条指令是相关的，则它们不是并行的，必须按顺序执行，尽管它们通常可能部分重叠。 这两种情况的关键是确定一条指令是否依赖于另一条指令。

2.1.1 数据依赖

依赖关系分为三种不同类型：数据依赖关系（也称为真正的数据依赖关系）、名称依赖关系和控制依赖关系。 如果以下任一条件成立，则指令 j 与指令 i 数据相关：

■ 指令i 产生可由指令j 使用的结果。
■ 指令j 数据依赖于指令k，指令k 数据依赖于指令i。

第二个条件简单地表明，如果两条指令之间存在第一类型的依赖链，则一条指令依赖于另一条指令。 这个依赖链可以和整个程序一样长。 注意，单个指令内的依赖关系（例如 add x1,x1,x1）不被视为依赖关系。

例如，考虑以下 RISC-V 代码序列，该序列将内存中的值向量（从 0(x1) 开始，到最后一个元素 0(x2) 结束）增加寄存器 f2 中的标量。

 此代码序列中的数据依赖性涉及浮点数据：

 和整数数据：

 可以通过两种不同的方式克服依赖性：（1）保持依赖性但避免危险，（2）通过转换代码消除依赖性。代码调度是在不改变依赖关系的情况下避免危险的主要方法，这种调度既可以由编译器完成，也可以由硬件完成。

流经内存位置的依赖关系更难以检测，因为两个地址可能引用同一位置但看起来不同：例如，100(x4) 和 20(x6) 可能是相同的内存地址。 此外，加载或存储的有效地址可能会从指令的一次执行到另一次执行而改变（因此 20(x4) 和 20(x4) 可能不同），从而使依赖性检测进一步复杂化。

2.1.2 名称依赖

第二种类型的依赖是名称依赖。 当两条指令使用相同的寄存器或内存位置（称为名称）时，就会发生名称依赖，但与该名称关联的指令之间没有数据流。 按程序顺序位于指令 j 之前的指令 i 之间存在两种类型的名称相关性： 

1. 当指令 j 写入指令 i 读取的寄存器或内存位置时，指令 i 和指令 j 之间会出现反依赖性。 必须保留原始顺序以确保读取正确的值。
2. 当指令 i 和指令 j 写入相同的寄存器或内存位置时，会出现输出相关性。 必须保留指令之间的顺序，以确保最终写入的值对应于指令 j。

由于名称依赖不是真正的依赖，因此如果指令中使用的名称（寄存器号或内存位置）发生更改，则涉及名称依赖的指令可以同时执行或重新排序，从而使指令不会发生冲突。

对于寄存器操作数来说，这种重命名可以更容易地完成，称为寄存器重命名。 寄存器重命名可以由编译器静态完成，也可以由硬件动态完成。 在描述分支产生的依赖之前，我们先来看看依赖和管道数据危险之间的关系。

2.1.3 数据危害

只要指令之间存在名称或数据依赖关系，并且它们足够接近，执行期间的重叠会改变对依赖关系中涉及的操作数的访问顺序，就会存在危险。 由于依赖性，我们必须保留所谓的程序顺序，即如果按原始源程序确定的一次顺序执行指令的执行顺序。 我们的软件和硬件技术的目标是通过仅在影响程序结果的情况下保留程序顺序来利用并行性。 检测和避免危险可确保保留必要的程序顺序。

数据危险可以分为三种类型，具体取决于指令中读写访问的顺序。按照惯例，危险是按程序中必须由管道保存的顺序命名的。考虑两条指令 i 和 j，其中 i 按程序顺序位于 j 之前。可能的数据危险是：
■ RAW（写入后读取）—j 尝试在写入源之前读取源，因此 j 错误地获取旧值。 这种危险是最常见的类型，对应于真正的数据依赖性。 必须保留程序顺序以确保 j 接收来自 i 的值。
■ WAW（写后写）—j 尝试在 i 写入操作数之前写入该操作数。 写入最终以错误的顺序执行，将 i 写入的值而不是 j 写入的值留在目标中。 这种危险对应于输出依赖性。 WAW 危险仅存在于在多个管道阶段写入或允许指令继续执行（即使前一条指令已停止）的管道中。
■ WAR（读后写）—j 尝试在 i 读取目标之前写入目标， 所以我错误地得到了新值。 这种危险是由反依赖性（或名称依赖性）引起的。 当某些指令在指令管道中早期写入结果而其他指令在管道中后期读取源时，或者当指令被重新排序时，就会发生 WAR 危险。

2.1.4 控制依赖

最后一种依赖是控制依赖。 控制依赖性确定指令 i 相对于分支指令的顺序，以便指令 i 仅在应该执行时才以正确的程序顺序执行。 除了程序的第一个基本块中的指令之外，每条指令都依赖于某些分支集，并且一般来说，必须保留这些控制依赖性以保持程序顺序。 例如，在代码段中

S1 控制依赖于 p1，S2 控制依赖于 p2，但不依赖于 p1。 一般来说，控制依赖性会施加两个约束： 
1. 控制依赖于分支的指令不能移到分支之前，从而使其执行不再受分支控制。 例如，我们不能从 if 语句的 then 部分取出指令并将其移到 if 语句之前。
2. 不依赖于分支的控制的指令不能移动到分支之后，从而使其执行由分支控制。 例如，我们不能将 if 语句之前的语句移到 then 部分。

简单来说，控制依赖性表示一条指令是否执行取决于另一条指令的结果。例如，如果一条指令是一个条件分支，那么它就控制了分支目标的执行。控制依赖性反映了程序的控制流结构，对于理解程序的语义和进行优化有重要作用。

当处理器保留严格的程序顺序时，它们确保控制依赖性也被保留。 然而，如果我们能够在不影响程序正确性的情况下这样做，我们可能愿意执行不应该执行的指令，从而违反控制依赖性。 因此，控制依赖性不是必须保留的关键属性。 相反，对程序正确性至关重要的两个属性是异常行为和数据流。

 保留异常行为意味着指令执行顺序的任何更改都不得改变程序中引发异常的方式。 通常，这被宽松地表示指令执行的重新排序不得在程序中引起任何新的异常。 考虑以下代码序列：

在这种情况下，很容易看出，如果我们不维护涉及x2的数据依赖性，我们可以改变程序的结果。 不太明显的是，如果我们忽略控制依赖性并将加载指令移到分支之前，则加载指令可能会导致内存保护异常。 

通过维护数据依赖性和控制依赖性而保留的第二个属性是数据流。 数据流是产生结果的指令和使用结果的指令之间数据值的实际流动。 分支使数据流变得动态，因为它们允许给定指令的数据源来自多个点。 换句话说，仅仅维护数据依赖性是不够的，因为一条指令可能依赖于多个前驱指令的数据。