BLOG

利用 ILP 有两种在很大程度上可分离的方法：(1)一种依赖于硬件来帮助动态发现和利用并行性的方法，以及 (2)一种依赖于软件技术在编译时静态查找并行性的方法。使用动态、基于硬件的方法的处理器（包括所有最近的英特尔和许多 ARM 处理器）在台式机和服务器市场占主导地位。在个人移动设备市场中，平板电脑和高端手机中的处理器也使用了相同的方法。在物联网领域，功耗和成本限制是性能目标的主要因素，设计人员利用较低级别的指令级并行性。自 20 世纪 80 年代以来，已经多次尝试激进的基于编译器的方法，最近一次是在 1999 年推出的英特尔安腾系列中。尽管付出了巨大的努力，但此类方法仅在特定领域的特定环境或具有显著数据级并行性的结构良好的科学应用中取得了成功。

对于流水线处理器，CPI（每条指令周期数）的值是基本 CPI 和所有停顿贡献的总和：

Pipeline CPI = Ideal pipeline CPI + Structural stalls + Data hazard stalls + Control stalls

理想的管道 CPI 是衡量实施可达到的最大性能的指标。通过减少右侧的每个项，我们降低了整体管道 CPI，或者增加了 IPC（每个时钟的指令数）。前面的等式允许我们通过一种技术降低的整体 CPI 的哪个组成部分来表征各种技术。图 3.1 显示了我们在本章和附录 H 中研究的技术，以及附录 C 中介绍材料中涵盖的主题。在本章中，我们将看到，我们引入的降低理想管道 CPI 的技术可以增加处理危害的重要性。

本章中的所有技术都利用了指令之间的并行性。基本块（一个直线代码序列，除了入口之外没有分支，除了出口之外没有分支）中可用的并行度非常小。对于典型的 RISC 程序，平均动态分支频率通常在 15% 到 25% 之间，这意味着在一对分支之间执行三到六条指令。由于这些指令可能相互依赖，因此我们可以在基本块中利用的重叠量可能小于平均基本块大小。为了获得实质性的性能增强，我们必须在多个基本块中利用 ILP。

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

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

循环的每次迭代都可以与任何其他迭代重叠，尽管在每次循环迭代中，重叠的机会很少或根本没有。

我们将研究一些将这种循环级并行性转换为指令级并行性的技术。基本上，这些技术的工作原理是编译器静态展开循环（如下一节所示）或硬件动态展开循环（如第 3.5 节和第 3.6 节）。

利用循环级并行性的一种重要替代方法是在矢量处理器和图形处理单元 （GPU） 中使用 SIMD，这两者都在第 4 章中介绍。SIMD 指令通过对少量到中等数量的数据项（通常为 2 到 8 个）进行并行操作来利用数据级并行性。矢量指令通过使用并行执行单元和深层管道对多个数据项进行并行操作来利用数据级并行性。例如，前面的代码序列在简单形式下，每次迭代需要 7 条指令（2 条加载、1 条添加、1 条存储、2 条地址更新和 1 条分支），总共 7000 条指令，在某些 SIMD 体系结构中，每条指令处理 4 个数据项，执行的指令数量可能只有该指令的四分之一。在某些向量处理器上，此序列可能只需要四条指令：两条指令用于从内存中加载向量 x 和 y，一条指令用于添加两个向量，一条指令用于存储结果向量。当然，这些指令将是流水线式的，并且具有相对较长的延迟，但这些延迟可能会重叠。

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

数据依赖关系

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

• 指令 i 产生一个结果，该结果可由指令 j 使用。
• 指令 j 依赖于指令 k，指令 k 依赖于指令 i。

如果满足以下任一条件，则指令 j 依赖于指令 i：第二个条件只是说明如果两个指令之间存在第一种类型的依赖链，则一条指令依赖于另一个指令。这个依赖链可以像整个程序一样长。请注意，单个指令中的依赖关系（例如 add x1，x1，x1）不被视为依赖关系。

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

Loop: 
	fld f0,0(x1)    //f0=array element
	fadd.d f4,f0,f2 //add scalar in f2
	fsd f4,0(x1)    //store result
	addi x1,x1,"8   //decrement pointer 8 bytes
	bne x1,x2,Loop  //branch x16 ¼x2

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

和整数数据：

在前面的两个从属序列中，如箭头所示，每条指令都依赖于前一条指令。此处和以下示例中的箭头显示了为正确执行而必须保留的顺序。箭头指向的指令必须位于箭头指向的指令之前。

如果两条指令依赖于数据，则它们必须按顺序执行，不能同时执行或完全重叠。依赖性意味着两个指令之间将存在一个或多个数据危害链。（有关数据危害的简要描述，请参阅附录 C，我们将在几页中精确定义。同时执行指令将导致具有管道互锁（并且管道深度大于周期中指令之间的距离）的处理器检测到危险并停止，从而减少或消除重叠。在没有互锁的处理器中，依赖于编译器调度，编译器无法以以下方式调度依赖指令

它们完全重叠，因为程序将无法正确执行。指令序列中存在数据依赖关系反映了生成指令序列的源代码中的数据依赖关系。必须保留原始数据依赖关系的效果。

依赖关系是程序的一个属性。给定的依赖性是否会导致检测到实际危险，以及该危险是否实际导致失速是管道组织的属性。这种差异对于理解如何利用指令级并行性至关重要。

数据依赖性传达了三件事：（1） 危险的可能性，（2） 必须计算结果的顺序，以及 （3） 可以利用多少并行性的上限。这些限制在第 262 页的陷阱和附录 H 中进行了更详细的探讨。

由于数据依赖性会限制我们可以利用的指令级并行性的数量，因此本章的一个主要重点是克服这些限制。依赖可以通过两种不同的方式克服：（1）保持依赖性但避免危险，以及（2）通过转换代码来消除依赖性。调度代码是用于在不改变依赖关系的情况下避免危险的主要方法，这种调度可以由编译器和硬件完成。

数据值可以通过寄存器或存储器位置在指令之间流动。当数据流通过寄存器发生时，检测依赖关系很简单，因为寄存器名称在指令中是固定的，尽管当分支干预并且正确性问题迫使编译器或硬件保守时，它会变得更加复杂。

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

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

名称依赖关系

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

1. 当指令 j 写入指令 i 读取的寄存器或存储器位置时，指令 i 和指令 j 之间就会发生反依赖性。原文必须保留排序，以确保读取正确的值。在第 171 页的示例中，寄存器 x1 上的 fsd 和 addi 之间存在反依赖关系。
2. 当指令 i 和指令 j 写入相同的寄存器或存储器位置时，就会发生输出依赖性。必须保留指令之间的顺序，以确保最终写入的值与指令 j 相对应。

原来的反依赖性和输出依赖性都是名称依赖性，而不是真正的数据依赖性，因为指令之间没有传递任何值。由于名称依赖关系不是真正的依赖关系，因此如果更改了指令中使用的名称（寄存器号或内存位置），则名称依赖关系中涉及的指令可以同时执行或重新排序，以便指令不会发生冲突。

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

数据危害

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

附录 C 中非正式描述的数据危害可分为三种类型之一，具体取决于说明中读取和写入访问的顺序。按照惯例，危险由程序中的顺序命名，必须由管道保留。考虑两个指令 i 和 j，其中 i 在程序顺序的 j 之前。可能的数据危害是

• RAW（先写后读）——j 在我写入源之前尝试读取源，因此 j 错误地获取了旧值。这种危险是最常见的类型，对应于真正的数据依赖性。必须保留程序顺序，以确保 j 从 i 接收到值。
• WAW（write after write）— j 尝试在 i 写入操作数之前写入操作数。写入最终以错误的顺序执行，将 i 写入的值而不是 j 写入的值留在目标中。这种危险对应于输出依赖性。WAW 危险仅存在于写入多个管道阶段的管道中，或者即使前一条指令停滞也允许指令继续执行。
• WAR（读后写）— j 尝试在目的地被 i 读取之前写入目的地，因此 i 错误地获取了新值。这种危险源于反依赖性（或名称依赖性）。在大多数静态问题管道（甚至更深的管道或浮点管道）中不会发生 WAR 危险，因为所有读取都是早期的（在附录 C 的管道中的 ID 中），而所有写入都是延迟的（在附录 C 的管道中的 WB 中）。当某些指令在指令流水线的早期写入结果，而其他指令在流水线的后期读取源时，或者当指令被重新排序时，就会发生 WAR 危险，正如我们将在本章中看到的那样。

最后一种依赖关系是控制依赖关系。控制依赖关系决定了指令 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 的数据依赖性，我们可以更改程序的结果。不太明显的事实是，如果我们忽略控制依赖性并将加载指令移动到分支之前，则加载指令可能会导致内存保护异常。请注意，没有任何数据依赖性阻止我们交换 beqz 和 ld;它只是控制依赖。为了允许我们对这些指令进行重新排序（并且仍然保留数据依赖性），我们希望在进行分支时忽略异常。在第 3.6 节中，我们将研究一种硬件技术，即推测，它使我们能够克服这个异常问题。附录 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 值，如果占用分支，则 or 应使用由 add 计算的 x1 值。通过保留 or 对分支的控制依赖性，我们可以防止对数据流进行非法更改。出于类似的原因，子指令不能移动到分支上方。推测有助于解决异常问题，它还将允许我们减少控制依赖的影响，同时仍然保持数据流，正如我们将在第 3.6 节中看到的那样。

有时，我们可以确定违反控制依赖关系不会影响异常行为或数据流。请考虑以下代码序列：

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

假设我们知道子指令 （x4） 的寄存器目标在标记为 skip 的指令之后未使用。（即将到来的指令是否使用值的属性称为活动。如果 x4 未使用，则在分支之前更改 x4 的值不会影响数据流，因为 x4 在跳过后将在代码区域中失效（而不是活动）。因此，如果 x4 已死，并且现有的子指令无法生成异常（处理器从中恢复相同进程的子指令除外），我们可以将子指令移到分支之前，因为数据流不会受到此更改的影响。

如果分支被占用，子指令将执行并且将无用，但不会影响程序结果。这种类型的代码调度也是一种投机形式，通常称为软件投机，因为编译器押注的是分支结果;在这种情况下，赌注是通常不会采取分支。附录 H 中讨论了更雄心勃勃的编译器推测机制，通常，当我们说推测或推测时，该机制是硬件机制还是软件机制会很清楚;不清楚时，最好说“硬件推测”或“软件推测”。

通过实施导致控制失速的控制危害检测来保持控制依赖性。控制失速可以通过各种硬件和软件技术来消除或减少，我们将在第 3.3 节中对此进行研究。

本节介绍如何使用简单的编译器技术来增强处理器利用 ILP 的能力。这些技术对于使用静态问题或静态调度的处理器至关重要。有了这种编译器技术，我们将很快检查使用静态发布处理器的设计和性能。附录 H 将研究更复杂的编译器和相关硬件方案，旨在使处理器能够利用更多的指令级并行性。

若要使管道保持完整，必须通过查找管道中可能重叠的不相关指令序列来利用指令之间的并行性。为了避免流水线停滞，依赖指令的执行必须与源指令的距离（以时钟周期为单位）相隔，该距离等于该源指令的流水线延迟。编译器执行此计划的能力取决于程序中可用的 ILP 量和管道中功能单元的延迟。图 3.2 显示了我们在本章中假设的 FP 单元延迟，除非明确说明不同的延迟。我们假设标准的五级整数流水线，因此分支有一个时钟周期的延迟。我们假设功能单元是完全流水线化或复制的（与流水线深度一样多），因此可以在每个时钟周期发出任何类型的操作，并且没有结构性危险。

在本节中，我们将了解编译器如何通过转换循环来增加可用 ILP 的数量。此示例既可以说明一种重要的技术，也可以激励附录 H 中描述的更强大的程序转换。我们将依赖于以下代码段，该代码段向向量添加标量：

for (i=999; i>=0; i=i+1 )
	x[i] = x[i] + s;

我们可以通过注意到每次迭代的主体是独立的来看到这个循环是并行的。我们在附录 H 中将这个概念形式化，并描述了我们如何在编译时测试循环迭代是否独立。首先，让我们看一下这个循环的性能，它展示了我们如何利用并行性来提高其在具有上述延迟的 RISC-V 流水线中的性能。

第一步是将前面的片段翻译成RISC-V汇编语言。

在下面的代码段中，x1 最初是数组中具有最高地址的元素的地址，f2 包含标量值 s。寄存器 x2 是预先计算的，因此 Regs[x2]+8 是最后一个要操作的元素的地址。

图 3.2 本章中使用的 FP 操作的延迟。最后一列是避免失速所需的干预时钟周期数。这些数字类似于我们在 FP 设备上看到的平均延迟。浮点加载到存储的延迟为 0，因为可以绕过加载的结果，而不会使存储停止。我们将继续假设整数加载延迟为 1，整数 ALU 操作延迟为 0（包括对分支的 ALU 操作）。

简单的 RISC-V 代码，未计划用于管道，如下所示：

Loop: fld f0,0(x1) //f0=array element
fadd.d f4,f0,f2 //add scalar in f2
fsd f4,0(x1) //store result
addi x1,x1,"8 //decrement pointer
//8 bytes (per DW)
bne x1,x2,Loop //branch x16 ¼x2

首先，让我们看看在RISC-V的简单流水线上调度这个循环时，它的运行情况如何，延迟如图3.2所示。

例子：显示RISC-V上的循环会是什么样子，包括计划的和未计划的，包括任何停滞或空闲的时钟周期。为浮点操作的延迟安排时间。

没有任何调度，循环将如下执行，需要九个周期

我们可以安排循环以只获得两个stall，并将时间减少到七个周期：

fadd.d后的 stalls 是供 fsd 使用的，重新定位 addi 可以防止 fld 后的 stall。

在前面的例子中，我们每七个时钟周期完成一个循环迭代并存储回一个数组元素，但操作数组元素的实际工作只需其中的三个时钟周期（load，add和store）。

剩下的四个时钟周期包括循环开销——addi和bne——以及两个stal。要消除这四个时钟周期，我们需要相对于开销指令的数量获得更多的操作。

增加与分支和开销指令相对的指令数量的一种简单方案是循环展开。展开只是多次复制循环体，调整循环终止代码。

循环展开也可以用于改进调度。因为它消除了分支，所以它允许来自不同迭代的指令一起调度。在这种情况下，我们可以通过在循环体内创建额外的独立指令来消除数据使用停滞。如果我们在展开循环时简单地复制指令，同一寄存器的结果使用可能会阻止我们有效地调度循环。因此，我们将希望为每次迭代使用不同的寄存器，增加所需的寄存器数量。

例子：我们的循环展开，以便循环体有四个副本，假设x1 - x2（即，数组的大小）最初是32的倍数，这意味着循环迭代的次数是4的倍数。消除任何明显冗余的计算，并且不要重用任何寄存器。

这是合并添加指令并丢弃在展开过程中复制的不必要的bne操作后的结果。请注意，现在必须设置x2，以便Regs[x2]+32是最后四个元素的起始地址。

我们已经消除了三个分支和三个x1的减量。加载和存储上的地址已经得到了补偿，以允许将x1上的addi指令合并。这种优化可能看起来微不足道，但事实并非如此；它需要符号替换和简化。符号替换和简化将重新排列表达式，以便允许常数折叠，允许像((i + 1) + 1)这样的表达式被重写为(i + (1 + 1))，然后简化为(i + 2)。

我们将在附录H中看到更一般形式的这些优化，消除依赖性计算。

没有调度，展开循环中的每个FP加载或操作后面都跟着一个依赖操作，因此会导致停滞。这个展开的循环将在26个时钟周期内运行——每个fld有1个停滞，每个fadd.d有2个，加上14个指令发出周期——或者每个元素有6.5个时钟周期，但是它可以被调度以显著提高性能。循环展开通常在编译过程的早期进行，以便优化器可以暴露和消除冗余计算。

在实际程序中，我们通常不知道循环的上限。假设它是n，我们想要展开循环，使得主体有k个副本。我们不是生成一个展开的循环，而是生成一对连续的循环。第一个执行(nmod k)次，并且主体是原始循环。第二个是由一个外部循环包围的展开的主体，该外部循环迭代(n/k)次。(正如我们将在第4章中看到的，这种技术类似于一种称为条带采矿的技术，用于向量处理器的编译器。)对于n的大值，大部分执行时间将在展开的循环主体中花费。

在前面的例子中，展开改善了这个循环的性能，通过消除开销指令，尽管它大大增加了代码大小。

当它被调度为前述的管道时，展开的循环将如何执行？

例子：在图3.2中的延迟已经安排进流水线之后，显示前面例子中的展开的循环。

展开循环的执行时间已经降低到总共14个时钟周期，或者每个元素3.5个时钟周期，与展开或调度之前的每个元素8个周期以及展开但未调度时的6.5个周期相比。

在展开的循环上进行调度的收益甚至大于原始循环。这种增加是因为展开循环暴露出更多可以调度以最小化停顿的计算；前面的代码没有停顿。以这种方式调度循环需要认识到加载和存储是独立的，可以互换。

在本章和附录 H 中，我们将介绍各种硬件和软件技术，这些技术使我们能够利用指令级并行性来充分利用处理器中功能单元的潜力。大多数这些技术的关键是知道何时以及如何更改指令之间的顺序。在我们的例子中，我们做了许多这样的改变，这对我们人类来说显然是允许的。在实践中，此过程必须由编译器或硬件以有条不紊的方式执行。为了获得最终的展开代码，我们必须做出以下决策和转换：

• 通过发现循环迭代是独立的（循环维护代码除外），确定展开循环是否有用。
• 使用不同的寄存器可以避免不必要的约束，这些约束会因使用相同的寄存器进行不同的计算（例如，名称依赖性）而强制执行。
• 消除额外的测试和分支指令，并调整循环终止和迭代代码。
• 通过观察不同迭代中的加载和存储是独立的，确定展开循环中的加载和存储可以互换。此转换需要分析内存地址，并发现它们不引用相同的地址。
• 计划代码，保留生成与原始代码相同的结果所需的任何依赖项。

所有这些转换的关键要求是了解一条指令如何依赖于另一条指令，以及如何在给定依赖关系的情况下更改或重新排序指令。

三种不同的效果限制了循环展开的收益：（1） 每次展开时摊销的开销量减少，（2） 代码大小限制，以及 （3） 编译器限制。让我们先考虑循环开销的问题。当我们展开循环四次时，它在指令之间产生了足够的并行性，可以安排循环，没有失速周期。事实上，在 14 个时钟周期中，只有 2 个周期是环路开销：addi 和 bne，前者保持索引值，后者终止环路。如果循环展开 8 次，则开销从每个元素的 1/2 周期减少到 1/4。

展开的第二个限制是导致代码大小的增长。对于较大的循环，代码大小增长可能是一个问题，特别是当它导致指令缓存未命中率增加时。

另一个通常比代码大小更重要的因素是寄存器的潜在不足，这是由激进的展开和调度造成的。这种由大型代码段中的指令调度产生的次要效应称为寄存器压力。之所以出现这种情况，是因为计划代码以增加 ILP 会导致实时值的数量增加。在激进的指令调度之后，可能无法将所有实时值分配给寄存器。转换后的代码虽然理论上速度更快，但可能会失去部分或全部优势，因为它会导致寄存器短缺。如果不展开，激进的调度会受到分支的充分限制，因此寄存器压力很少成为问题。但是，展开和主动调度的组合可能会导致此问题。在需要暴露更多独立指令序列的多问题处理器中，这个问题变得尤为具有挑战性，这些指令序列的执行可能会重叠。一般来说，使用复杂的高级转换，其潜在的改进在详细的代码生成之前很难衡量，这导致了现代编译器的复杂性显着增加。

循环展开是一种简单但有用的方法，用于增加可以有效调度的直线代码片段的大小。这种转换在各种处理器中都很有用，从我们目前研究过的简单流水线到本章后面探讨的多问题超标量和 VLIW。

由于需要通过分支危险和停顿来执行控制依赖，分支会损害流水线性能。循环展开是一种减少分支危险的方法；我们还可以通过预测分支的行为来减少分支的性能损失。在附录C中，我们研究了依赖于编译时信息或单个分支的动态行为的简单分支预测器。随着更深的流水线和每个时钟的问题数量的增加，更准确的分支预测的重要性也在增加。在这个部分，我们将研究提高动态预测准确性的技术。本节大量使用了C.2节中介绍的简单的2位预测器，理解该预测器的操作对于读者来说至关重要，以便进行下一步。

附录 C 中的 2 位预测器方案仅使用单个分支的近期行为来预测该分支的未来行为。如果我们同时查看其他分支的近期行为，而不仅仅是我们试图预测的分支，则有可能提高预测准确性。考虑来自 eqntott 基准测试的一个小代码片段，它是早期 SPEC 基准测试套件的成员，它显示了特别糟糕的分支预测行为：

以下是我们通常会为早期 SPEC 基准测试套件的这段代码生成的 RISC-V 代码，这些代码表现出特别糟糕的分支预测行为： 假设 aa 和 bb 被分配给寄存器 x1 和 x2：

让我们将这些分支标记为b1、b2和b3。关键的观察是，分支b3的行为与分支b1和b2的行为相关。显然，如果分支b1和b2都没有被取（即，如果条件都评估为真，并且aa和bb都被赋值为0），那么b3将会被取，因为aa和bb显然是相等的。一个只使用单个分支的行为来预测该分支结果的预测器，永远无法捕捉到这种行为。

那些使用其他分支行为来做出预测的分支预测器被称为关联预测器或二级预测器。现有的关联预测器添加了最近分支行为的信息，以决定如何预测给定的分支。例如，一个(1,2)预测器使用最后一个分支的行为，从一对2位分支预测器中选择，以预测特定的分支。在一般情况下，一个(m,n)预测器使用最后m个分支的行为，从2^m个分支预测器中选择，每一个都是一个n位的单一分支预测器。这种类型的关联分支预测器的吸引力在于，它可以比2位方案产生更高的预测率，而只需要微不足道的额外硬件。

硬件的简单性来自于一个简单的观察：最近m个分支的全局历史可以在一个m位的移位寄存器中记录，其中每一位记录了分支是被取还是没有被取。然后，可以使用来自分支地址的低阶位与m位全局历史的连接来索引分支预测缓冲区。例如，在一个有64个总条目的(2,2)缓冲区中，分支（字地址）的4个低阶地址位和代表最近执行的两个分支行为的2个全局位形成一个6位索引，可以用来索引64个计数器。通过将本地和全局信息通过连接（或一个简单的哈希函数）组合在一起，我们可以用结果索引预测表，并得到一个预测，就像我们很快就要为标准的2位预测器做的那样。

与标准的 2 位方案相比，相关分支预测器的工作效果好多少？为了公平地比较它们，我们必须比较使用相同数量状态位的预测变量。（m，n） 预测变量中的位数为

2^m * n * Number of prediction entries selected by the branch address

没有全局历史记录的 2 位预测变量只是一个 （0,2） 预测变量。

具有 4K 条目的 （0,2） 分支预测器中有多少位？（2,2） 个预测变量中有多少个条目具有相同的位数？

2^0 * 2 * 4K = 8K bits

预测缓冲区中总共有 8K 位的 （2,2） 预测器中有多少个分支选择的条目？我们知道

2^2 * 2 * Number of prediction entries selected by the branch = 8K

因此，分支选择的预测条目数 1K

关联分支预测变量的主要动机来自以下观察结果：仅使用局部信息的标准 2 位预测变量在一些重要分支上失败。添加全球历史可能有助于纠正这种情况。锦标赛预测器通过使用多个预测器（通常是全局预测器和局部预测器）并使用选择器在它们之间进行选择，将这种洞察力提升到一个新的水平，如图 3.5 所示

图 3.3 2位预测变量的比较。首先是 4096 位的非相关预测变量，然后是具有无限条目的非相关 2 位预测变量，以及具有 2 位全局历史记录和总共 1024 个条目的 2 位预测变量。尽管这些数据是针对旧版本的 SPEC，但较新的 SPEC 基准测试的数据在准确性方面会显示出类似的差异。

如图 3.5 所示。全局预测变量使用最新的分支历史记录来索引预测变量，而本地预测变量使用分支的地址作为索引。锦标赛预测变量是混合或合金预测变量的另一种形式。

锦标赛预测器可以在中等大小（8K–32K 位）下实现更高的准确性，并且还可以有效地使用非常多的预测位。现有的锦标赛预测器使用每个分支的 2 位饱和计数器，根据哪个预测器（局部、全局甚至某些时变组合）在最近的预测中最有效，在两个不同的预测器中进行选择。与简单的 2 位预测器一样，饱和计数器在更改首选预测器的标识之前需要两次错误预测。

锦标赛预测器的优势在于它能够为特定分支选择正确的预测器，这对于整数基准尤为重要。

图 3.5 锦标赛预测器使用分支地址为一组 2 位选择计数器编制索引，这些计数器在本地和全局预测器之间进行选择。在本例中，选择器表的索引是当前分支地址。这两个表也是 2 位预测变量，分别按全局历史记录和分支地址进行索引。选择器的作用类似于 2 位预测器，当连续发生两个错误预测时，更改分支地址的首选预测器。用于索引选择器表和本地预测器表的分支地址的位数等于用于索引全局预测表的全局分支历史记录的长度。请注意，错误预测有点棘手，因为我们需要同时更改选择器表和全局或局部预测器。

对于SPEC整数基准测试，典型的锦标赛预测器将有近40%的时间选择全局预测器，而对于SPEC FP基准测试，选择全局预测器的时间不到15%。除了开创锦标赛预测器的 Alpha 处理器外，还有几款 AMD 处理器使用了锦标赛式预测器。

图 3.6 以 SPEC89 为基准，查看了三种不同预测器（本地 2 位预测器、相关预测器和锦标赛预测器）在不同位数下的性能。局部预测变量首先达到其极限。相关预测变量显示出显著的改进，而锦标赛预测变量产生的性能略好。对于较新版本的 SPEC，结果将相似，但直到预测变量大小稍大时才会达到渐近行为。

局部预测变量由两级预测变量组成。顶层是一个本地历史记录表，由 1024 个 10 位条目组成;每个 10 位条目对应于该条目的最新 10 个分支结果。也就是说，如果分支连续被占用 10 次或更多次，则本地历史记录表中的条目将全部为 1。如果交替获取和取消获取分支，则历史记录条目由交替的 0 和 1 组成。此 10 位历史记录允许发现和预测多达 10 个分支的模式。从本地历史记录表中选择的条目用于索引由 3 位饱和计数器组成的 1K 条目表，这些计数器提供本地预测。这种组合总共使用 29K 位，可在分支预测时需要比具有相同预测精度的单级表更少的位。

图 3.6 SPEC89 上三个不同预测变量的错误预测率与预测变量大小（以千比特为单位）的关系。预测变量是局部 2 位预测变量、在图形中每个点使用全局和局部信息时结构最佳的相关预测变量，以及锦标赛预测变量。尽管这些数据适用于较旧版本的 SPEC，但较新的 SPEC 基准的数据显示出类似的行为，可能在预测变量大小稍大时收敛到渐近极限。

截至 2017 年，性能最好的分支预测方案涉及组合多个预测变量，这些预测变量跟踪预测是否可能与当前分支相关联。一类重要的预测变量松散地基于一种称为 PPM（部分匹配预测）的统计压缩算法。PPM（参见Jimenez和Lin，2001）就像分支预测算法一样，试图根据历史预测未来的行为。这类分支预测变量，我们称之为标记的混合预测变量（参见 Seznec 和 Michaud，2006 年），采用一系列具有不同长度历史索引的全局预测变量。

例如，如图 3.7 所示，一个五分量标记的混合预测变量有五个预测表：P（0）、P（1）、. .P（4），其中 P（i） 使用

图 3.7 一个五分量标记的混合预测器有五个独立的预测表，由分支地址的哈希值和图中标记为“h”的长度为 0-4 的最近分支历史记录段进行索引。哈希可以像 gshare 中的 exclusive-OR 一样简单。每个预测变量都是一个 2 位（也可能是 3 位）预测变量。标记通常为 4–8 位。所选的预测1是具有最长历史记录的预测，其中标记也匹配。

例如，如图3.7所示，一个五组件标记混合预测器有五个预测表：P(0)，P(1)，... P(4)，其中，P(i)通过PC的哈希值和最近i个分支的历史（在移位寄存器h中保留，就像在gshare中一样）进行访问。使用多个历史长度来索引不同的预测器是第一个关键区别。第二个关键区别是在表P(1)到P(4)中使用标签。标签可以很短，因为不需要100％的匹配：一个小标签的4-8位似乎可以获得大部分的优势。只有当标签与分支地址和全局分支历史的哈希值匹配时，才使用来自P(1)，... P(4)的预测。P(0...n)中的每个预测器都可以是标准的2位预测器。实际上，一个3位计数器，需要三次错误预测才能改变预测，比2位计数器的结果略好一些。

对于给定的分支，预测是具有最长分支历史并且也有匹配标签的预测器。P(0)始终匹配，因为它不使用标签，并且如果P(1)到P(n)都不匹配，它将成为默认预测。此预测器的标记混合版本还在每个历史索引预测器中包含一个2位使用字段。使用字段指示预测是否最近被使用，因此可能更准确；使用字段可以在所有条目中定期重置，以便清除旧的预测。在实现这种风格的预测器时，涉及到更多的细节，特别是如何处理错误预测。由于预测器的数量，用于索引的确切历史，以及每个预测器的大小都是可变的，因此寻找最佳预测器的搜索空间也非常大。

标记混合预测器（有时称为TAGE—TAgged GEometic—预测器）和早期的基于PPM的预测器一直是最近几年的国际分支预测大赛的赢家。这些预测器在适度的内存（32-64 KiB）下，表现优于gshare和比赛预测器，此外，这类预测器似乎能够有效地使用较大的预测缓存来提供更好的预测准确性。

对于较大的预测器来说，另一个问题是如何初始化预测器。它可以随机初始化，这样，将需要一定量的执行时间来填充预测器，使其预测变得有用。一些预测器（包括许多最近的预测器）包含一个有效位，表示预测器中的条目是否已被设置或处于“未使用状态”。在后一种情况下，我们可以使用某种方法来初始化那个预测条目，而不是使用随机预测。例如，一些指令集包含一个位，该位表示是否预期相关的分支将被执行。在动态分支预测之前的日子里，这些提示位就是预测；在最近的处理器中，那个提示位可以用来设置初始预测。我们也可以根据分支的方向来设置初始预测：前行分支被初始化为未执行，而后行分支，可能是循环分支，被初始化为已执行。对于运行时间较短，预测器较大的程序，这种初始设置可以对预测性能产生可测量的影响。

图3.8显示，混合标记预测器明显优于gshare，尤其是对于像SPECint和服务器应用这样的不容易预测的程序。在这个图中，性能是以每千条指令的错误预测次数来衡量的；假设分支频率为20％-25％，对于多媒体基准，gshare的错误预测率（每个分支）为2.7％-3.4％，而混合标记预测器的误预测率为 1.8%–2.2%，误报率大约减少三分之一。与 gshare 相比，标记混合预测变量的实现更复杂，并且由于需要检查多个标记并选择预测结果，因此速度可能略慢。尽管如此，对于深度流水线处理器来说，分支错误预测会受到很大惩罚，因此准确性的提高超过了这些缺点。因此，许多高端处理器的设计人员选择在其最新实现中包含标记的混合预测器。

图 3.8 标记混合与 gshare 的误预测率（以每 1000 条指令的误预测来衡量）的比较。两个预测器使用相同的总位数，尽管标记混合将部分存储用于标记，而 gshare 不包含标记。基准测试包括来自 SPECfp 和 SPECint 的跟踪，这是一系列多媒体和服务器基准测试。后两者的行为更像 SPECint。

如上一章所述，在 2008 年（使用 Nehalem 微架构的酷睿 i7 920）和 2016 年（使用 Skylake 微架构的酷睿 i7 6700）之间，有六代英特尔酷睿 i7 处理器。由于深度流水线和每个时钟的多个问题相结合，i7 可同时运行许多指令（最多 256 条，通常至少 30 条）。这使得分支预测变得至关重要，这也是英特尔一直在不断改进的领域。也许是因为分支预测器的性能关键性，英特尔倾向于对其分支预测器的细节高度保密。

即使对于像2008年推出的Core i7 920这样的旧处理器，他们也只发布了有限的信息。在此部分，我们简要描述已知的信息，并将Core i7 920的预测器性能与最新的Core i7 6700中的预测器进行比较。

Core i7 920使用了一个两级预测器，它有一个较小的第一级预测器，设计用来满足每个时钟周期预测一个分支的周期约束，以及一个较大的第二级预测器作为备用。每个预测器结合了三种不同的预测器：（1）简单的2位预测器，这是在附录C中介绍的（并用在前面的锦标赛预测器中）；（2）一个全局历史预测器，就像我们刚刚看到的那样；和（3）一个循环退出预测器。循环退出预测器使用一个计数器来预测取得分支的确切数量（这是循环迭代的数量）对于被检测为循环分支的分支。对于每个分支，最佳预测是通过跟踪每个预测的准确性从三个预测器中选择的，就像一个锦标赛预测器。此外，除了这个多级主预测器，一个单独的单元预测间接分支的目标地址，并且也使用了一个栈来预测返回地址。

尽管对最新的i7处理器中的预测器了解的还更少，但有充分的理由相信英特尔正在使用一个带标签的混合预测器。这种预测器的一个优点是它结合了早期i7中所有三个第二级预测器的功能。带有不同历史长度的带标签混合预测器包含了循环退出预测器以及本地和全局历史预测器。一个单独的返回地址预测器仍然在使用。

就像其他情况一样，推测导致评估预测器时面临一些挑战，因为一个错误预测的分支很容易导致另一个分支被获取并错误预测。为了简化问题，我们查看误预测的数量占成功完成的分支数量（那些不是由于错误推测造成的）的百分比。图3.9显示了这些数据对于SPECPUint2006基准。这些基准比SPEC89或SPEC2000大得多，结果是即使有更强大的预测器组合，误预测率也高于图3.6中的误预测率。因为分支误预测导致推测无效，它对浪费的工作有所贡献，我们将在本章后面看到。

一个简单的静态调度管道会获取一个指令并发出它，除非管道中已有的指令与获取的指令之间存在无法通过旁路或转发隐藏的数据依赖性。(转发逻辑减少了有效的管道延迟，使得某些依赖性不会导致危险。) 如果存在无法隐藏的数据依赖性，那么危险检测硬件就会从使用结果的指令开始阻塞管道。在依赖性被清除前，不会获取或发出新的指令。

在这一部分，我们探讨动态调度，这是一种硬件重排指令执行顺序以减少阻塞同时保持数据流和异常行为的技术。动态调度提供了几个优点。首先，它允许用一个管道编译的代码在不同的管道上有效运行，消除了需要有多个二进制文件并为不同的微架构重新编译的需要。在今天的计算环境中，大部分软件都来自第三方，并以二进制形式分发，这个优点显得非常重要。其次，它能处理一些在编译时未知的依赖性；例如，它们可能涉及到内存引用或数据依赖分支，或者它们可能源于使用动态链接或调度的现代编程环境。第三，也许最重要的是，它允许处理器容忍不可预测的延迟，例如缓存未命中，通过执行其他代码来等待未命中解决。在第3.6节中，我们探讨了硬件推测，这是一种具有额外性能优势的技术，它建立在动态调度之上。正如我们将看到的，动态调度的优点是以显著增加硬件复杂性的代价获得的。

虽然动态调度处理器不能改变数据流，但它试图在存在依赖性时避免停滞。相比之下，编译器的静态管道调度(在第3.2节中讨论)试图通过分离依赖指令以减少阻塞，使它们不会导致危险。当然，编译器的管道调度也可以用于预计运行在有动态调度管道的处理器上的代码。

图 3.9 Intel Core i7 920 和 6700 上整数SPECCPU2006基准测试的错误预测率。误预测率计算为被错误预测的已完成分支与所有已完成分支的比率。这可能会在一定程度上低估错误预测率，因为如果一个分支被错误预测并导致另一个错误预测的分支（不应该被执行），它将被计为只有一个错误预测。

动态调度：理念

简单流水线技术的一个主要局限性是它们使用按顺序发出和执行指令：指令是按程序顺序发出的，如果指令在流水线中停滞不前，则以后的指令无法继续。因此，如果管道中两个间隔很近的指令之间存在依赖关系，则会导致危险，并导致停滞。如果有多个功能单元，这些单元可能会处于闲置状态。如果指令 j 依赖于一个长时间运行的指令 i，该指令当前正在管道中执行，那么 j 之后的所有指令都必须停止，直到 i 完成并且 j 可以执行。例如，请考虑以下代码：

fdiv.d f0,f2,f4
fadd.d f10,f0,f8
fsub.d f12,f8,f14

fsub.d 指令无法执行，因为 fadd.d 对 fdiv.d 的依赖导致管道停止;然而，fsub.d 并不依赖于管道中的任何内容。这种危险会造成性能限制，可以通过不要求指令按程序顺序执行来消除。

在经典的五阶段流水线中，可以在指令解码 （ID） 期间检查结构和数据危害：当指令可以在没有危害的情况下执行时，它会从 ID 发出，并认识到所有数据危害都已解决。

为了允许我们开始执行前面示例中的 fsub.d，我们必须将问题过程分为两部分：检查任何结构性危险和等待数据危险不存在。因此，我们仍然使用按顺序发出的指令（即按程序顺序发出的指令），但我们希望指令在其数据操作数可用时立即开始执行。这样的管道执行无序执行，这意味着无序完成。

无序执行引入了 WAR 和 WAW 危险的可能性，这在五阶段整数管道及其对有序浮点管道的逻辑扩展中不存在。请考虑以下 RISC-V 浮点代码序列：

fdiv.d f0,f2,f4
fmul.d f6,f0,f8
fadd.d f0,f10,f14

fmul.d 和 fadd.d（对于寄存器 f0）之间存在反依赖性，如果管道在 fmul.d（正在等待 fdiv.d）之前执行 fadd.d，它将违反反依赖性，从而产生 WAR 危险。同样，为了避免违反输出依赖关系，例如在 fdiv.d 完成之前 fadd.d 写入 f0，必须处理 WAW 危险。正如我们将看到的，使用寄存器重命名可以避免这两种危险。

无序完成也会在处理异常时造成重大复杂性。具有无序完成的动态调度必须保留异常行为，因为如果程序以严格的程序顺序执行，则实际上确实会出现那些异常。动态调度的处理器通过延迟关联异常的通知来保留异常行为，直到处理器知道该指令应该是下一个完成的指令。

尽管必须保留异常行为，但动态计划的处理器可能会生成不精确的异常。如果引发异常时的处理器状态看起来与指令按严格程序顺序顺序执行的指令不完全相同，则异常是不精确的。由于两种可能性，可能会发生不精确的异常：

1. 管道可能已经完成了程序顺序晚于导致异常的指令的指令。
2. 管道可能尚未完成某些指令，这些指令在程序顺序上早于导致异常的指令。

不精确的异常使得在发生异常后很难重新开始执行。我们将在第 3.6 节中讨论一种解决方案，该解决方案在处理器的上下文中提供精确的异常，而不是在本节中讨论这些问题。对于浮点异常，已使用其他解决方案，如附录 J 中所述。

为了允许无序执行，我们基本上将简单的五阶段管道的 ID 管道阶段拆分为两个阶段：

1. 问题 - 解码指令，检查结构性危险。
2. 读取操作数 - 等到没有数据危险，然后读取操作数。

指令提取阶段先于发出阶段，可以提取到指令寄存器或待处理指令队列中;然后从寄存器或队列发出指令。执行阶段遵循读取操作数阶段，就像在五阶段管道中一样。执行可能需要多个周期，具体取决于操作。

我们区分指令何时开始执行和何时完成执行;在两次之间，指令正在执行中。我们的流水线允许同时执行多个指令;如果没有此功能，动态调度的主要优势就会丧失。同时执行多个指令需要多个功能单元和/或流水线功能单元。由于这两种功能（流水线功能单元和多个功能单元）在流水线控制方面本质上是等效的，因此我们将假设处理器具有多个功能单元。

在动态调度的流水线中，所有指令都按顺序通过发出阶段（按顺序发出）;但是，它们可以停滞或绕过每个

指令获取阶段在发出阶段之前，可以将指令获取到指令寄存器，或者放入待处理指令的队列中；然后从寄存器或队列中发出指令。执行阶段紧接着读取操作数阶段，就像五阶段流水线一样。执行可能需要多个周期，取决于操作。

我们区分一条指令开始执行和完成执行的时间；在这两个时间之间，指令正在执行。我们的流水线允许多条指令同时执行；如果没有这种能力，动态调度的主要优势就会丧失。一次有多条指令执行需要多个功能单元、流水线功能单元，或者两者都有。因为这两种能力——流水线功能单元和多个功能单元——对于流水线控制来说基本上是等效的，我们将假设处理器有多个功能单元。

在动态调度的流水线中，所有指令按顺序通过发出阶段（按顺序发出）；然而，它们可以在第二阶段（读取操作数）中被阻塞或者跳过彼此，因此可以乱序进入执行。

记分牌是一种技术，当有足够的资源和没有数据依赖性时，允许指令乱序执行；它是以 CDC 6600 记分牌命名的，该记分牌开发了这种能力。在这里，我们将重点研究一种更复杂的技术，称为 Tomasulo 的算法。主要的区别在于，Tomasulo 的算法通过动态重命名寄存器有效地处理反依赖性和输出依赖性。此外，Tomasulo 的算法可以扩展以处理推测，这是一种通过预测分支的结果，预执行预测目标地址的指令，并在预测错误时采取纠正措施来减少控制依赖性影响的技术。虽然使用记分牌可能足以支持更简单的处理器，但更复杂、性能更高的处理器会使用推测。

使用 Tomasulo 方法的动态调度

IBM 360/91的浮点单元使用了一个复杂的方案，允许乱序执行。这个方案是由Robert Tomasulo发明的，它能够跟踪指令的操作数何时可用，以最小化RAW危险，并在硬件中引入寄存器重命名，以最小化WAW和WAR危险。尽管在最近的处理器中有许多这种方案的变体，但它们都依赖于两个关键原则：动态确定何时准备执行指令，以及重命名寄存器以避免不必要的危险。IBM的目标是从指令集和为整个360计算机系列设计的编译器中得到高性能的浮点性能，而不是从为高端处理器专门设计的编译器中得到。360架构只有四个双精度浮点寄存器，这限制了编译器调度的有效性；这是采用Tomasulo方法的另一个动机。此外，IBM 360/91有长时间的内存访问和长时间的浮点延迟，Tomasulo的算法就是为了克服这些问题而设计的。

在本节的最后，我们将看到Tomasulo的算法也可以支持循环多次迭代的重叠执行。

我们将解释这个算法，它主要关注浮点单元和负载-存储单元，在RISC-V指令集的背景下。RISC-V和360之间的主要区别是后者架构中存在寄存器-内存指令。因为Tomasulo的算法使用了一个负载功能单元，所以不需要做大的改变就可以添加寄存器-内存寻址模式。IBM 360/91也有流水线功能单元，而不是多个功能单元，但我们描述的算法好像有多个功能单元一样。这也是一个简单的概念扩展，可以把这些功能单元也流水线化。

通过只在操作数可用时执行指令，可以避免RAW危险，这正是更简单的记分牌方法提供的。WAR和WAW危险，这些危险源于名称依赖，通过寄存器重命名被消除。寄存器重命名通过重命名所有目标寄存器，包括那些有一个挂起的读或写的早期指令，使得乱序写不会影响任何依赖于操作数的早期值的指令。如果ISA中有足够的寄存器，编译器通常可以实现这样的重命名。原来的360/91只有四个浮点寄存器，Tomasulo的算法就是为了克服这个缺陷而创建的。虽然现代处理器有32-64个浮点和整数寄存器，但最近实现中可用的重命名寄存器的数量是几百个。

为了更好地理解寄存器重命名如何消除WAR和WAW危险，请考虑以下包含潜在WAR和WAW危险的示例代码序列。

fdiv.d f0,f2,f4
fadd.d f6,f0,f8
fsd f6,0(x1)
fsub.d f8,f10,f14
fmul.d f6,f10,f8

存在两个反向依赖：一个在fadd.d和fsub.d之间，另一个在fsd和fmul.d之间。还有一个输出依赖在fadd.d和fmul.d之间，导致三种可能的危险：WAR危险在fadd.d对f8的使用和其被fsub.d的使用上，以及一个WAW危险，因为fadd.d可能比fmul.d结束得晚。还有三个真正的数据依赖：在fdiv.d和fadd.d之间，fsub.d和fmul.d之间，以及fadd.d和fsd之间。

这三个名称依赖都可以通过寄存器重命名来消除。为了简单起见，假设存在两个临时寄存器，S和T。使用S和T，序列可以在没有任何依赖的情况下被重写。

fdiv.d f0,f2,f4
fadd.d S,f0,f8
fsd S,0(x1)
fsub.d T,f10,f14
fmul.d f6,f10,T

此外，任何后续使用f8的地方都必须用寄存器T来替换。在此例中，重命名过程可以由编译器静态完成。查找代码后面的任何使用f8的地方需要复杂的编译器分析或硬件支持，因为在前面的代码段和f8的后续使用之间可能存在干扰分支。正如我们将看到的，Tomasulo的算法可以处理跨分支的重命名。

在Tomasulo的方案中，寄存器重命名是由预留站提供的，预留站缓冲等待发出的指令的操作数，并与功能单元关联。基本的想法是，一旦操作数可用，预留站就会获取并缓冲该操作数，从而不需要从寄存器中获取操作数。此外，待处理的指令指定将提供其输入的预留站。最后，当连续对寄存器的写入在执行中重叠时，只有最后一个实际用于更新寄存器。随着指令的发出，待处理操作数的寄存器指定符被重命名为提供寄存器重命名的预留站的名称。

由于预留站可能比实际寄存器更多，这种技术甚至可以消除由名称依赖性引起的风险，而这是编译器无法消除的。当我们探讨Tomasulo方案的组件时，我们将回到寄存器重命名的主题，看看重命名是如何发生的，以及它是如何消除WAR和WAW冒险的。

使用预留站，而不是集中寄存器文件，导致了另外两个重要的属性。首先，危险检测和执行控制是分布式的：每个功能单元的预留站中的信息决定了指令可以在该单元开始执行的时间。其次，结果直接从预留站传递到功能单元，而不是通过寄存器。这种绕过是通过一个公共结果总线完成的，该总线允许等待操作数的所有单元同时加载（在360/91上，这被称为公共数据总线，或CDB）。在每个时钟发出多条指令并且有多个执行单元的流水线中，将需要多个结果总线。

图3.10显示了基于Tomasulo的处理器的基本结构，包括浮点单元和加载/存储单元；没有显示任何执行控制表。每个预留站都持有一个已发出并等待在功能单元执行的指令。如果该指令的操作数值已经被计算出来，那么它们也存储在该条目中；否则，预留站条目将保留将提供操作数值的预留站的名称。

加载缓冲区和存储缓冲区保存来自内存的数据或地址，并且几乎完全像预留站一样，因此我们只有在必要时才区分它们。浮点寄存器通过一对总线连接到功能单元，通过单个总线连接到存储缓冲区。

所有来自功能单元和内存的结果都发送到公共数据总线上，该总线到处都有，除了加载缓冲区。所有预留站都有标签字段，由流水线控制使用。

在我们描述预留站和算法的细节之前，让我们看看指令经历的步骤。只有三个步骤，尽管现在每个步骤都可以花费任意数量的时钟周期：

1. 发出——从指令队列的头部获取下一条指令，该队列按FIFO顺序维护以确保正确的数据流。如果有一个匹配的预留站是空的，就向该站发出带有操作数值的指令（如果它们当前在寄存器中）。如果没有空的预留站，那么就有一个结构性危险，指令发出暂停，直到站点或缓冲区被释放。如果操作数不在寄存器中，跟踪将生成操作数的功能单元。这一步重命名寄存器，消除WAR和WAW风险。（在动态调度的处理器中，这个阶段有时被称为调度。）

图 3.10 使用 Tomasulo 算法的 RISC-V 浮点单元的基本结构。指令从指令单元发送到指令队列中，从该队列中以先进先出 （FIFO） 顺序发出指令。预留站包括操作和实际操作数，以及用于检测和解决危险的信息。负载缓冲器具有三个功能：（1） 保留有效地址的分量，直到计算完成，（2） 跟踪等待内存的未完成负载，以及 （3） 保存等待 CDB 的已完成负载的结果。同样，存储缓冲区具有三个功能：（1） 保留有效地址的组件，直到计算出来，（2） 保留等待数据存储值的未完成存储的目标内存地址，以及 （3） 保留要存储的地址和值，直到内存单元可用。FP 单元或负载单元的所有结果都放在 CDB 上，CDB 将进入 FP 寄存器文件以及预留站和存储缓冲区。FP 加法器实现加法和减法，FP 乘法器进行乘法和除法。

1. 执行——如果一个或多个操作数尚未准备好，那么在等待它被计算的过程中，监视公共数据总线。当操作数变得可用时，它会被放入等待它的任何预留站。当所有的操作数都准备好了，该操作就可以在相应的功能单元上执行。通过延迟指令执行直到操作数可用，可以避免RAW风险。（一些动态调度的处理器称这一步为“发行”，但我们使用的是“执行”这个词，这个词是在第一台动态调度的处理器CDC 6600中使用的。）

请注意，对于同一功能单元，可能有多个指令在同一时钟周期内变得准备就绪。虽然独立的功能单元可以在同一时钟周期内开始执行不同的指令，但如果有多于一个的指令准备好了一个功能单元，那么该单元将必须在它们之间进行选择。对于浮点预留站，这个选择可能是任意的；然而，加载和存储带来了额外的复杂性。

加载和存储需要一个两步执行过程。第一步是当基本寄存器可用时，计算有效地址，然后将有效地址放入加载或存储缓冲区。加载缓冲区中的加载一旦内存单元可用就开始执行。存储缓冲区中的存储等待被存储的值准备就绪后才发送到内存单元。通过有效地址计算，按照程序顺序维护加载和存储，这将有助于防止通过内存产生风险。

为了保留异常行为，不允许任何指令在程序顺序中在其前面的分支完成之前开始执行。

这个限制保证了在执行过程中引起异常的指令真的会被执行。在使用分支预测的处理器（如所有动态调度处理器所做的），这意味着处理器必须在允许分支后的指令开始执行之前知道分支预测是正确的。如果处理器记录了异常的发生，但并没有真正引发它，那么一个指令可以开始执行，但不会在进入写 结果之前停滞。

推测提供了一种更灵活、更完整的方法来处理异常，所以我们将推迟进行这种改进，并在后面展示推测如何处理这个问题。

1. 写入结果——当结果可用时，将其写入CDB，然后从那里写入寄存器和等待此结果的任何预约站（包括存储缓冲器）。存储被缓存在存储缓冲器中，直到要存储的值和存储地址都可用；然后，只要存储器单元空闲，就将结果写入。

检测和消除冒险的数据结构附加到预约站，寄存器文件，以及负载和存储缓冲器，不同的对象附有稍微不同的信息。这些标签本质上是用于重命名的扩展虚拟寄存器集的名称。在我们的例子中，标签字段是一个4位数量，表示五个预约站之一或五个负载缓冲器之一。这种组合产生了相当于10个寄存器（5个预约站+ 5个负载缓冲器）可以被指定为结果寄存器（与360架构包含的四个双精度寄存器相反）。在具有更多实际寄存器的处理器中，我们希望重命名提供更大的虚拟寄存器集，通常数百个。标签字段描述了哪个预约站包含将产生源操作数所需结果的指令。

一旦指令已发出并等待源操作数，它将通过将写入寄存器的指令已分配的预约站编号来引用操作数。未使用的值，如零，表示操作数已在寄存器中可用。由于预约站比实际寄存器编号更多，因此通过使用预约站编号重命名结果来消除WAW和WAR冒险。尽管在托马苏洛的方案中，预约站被用作扩展的虚拟寄存器，但其他方法可能使用具有额外寄存器的寄存器集，或者像重排序缓冲区那样的结构，我们将在第3.6节中看到。

在托马苏洛的方案中，以及我们看过的支持推测的后续方法中，结果在总线（CDB）上广播，预约站监视这个总线。公共结果总线和预约站从总线检索结果的组合实现了在静态调度的管道中使用的转发和绕过机制。然而，这样做时，动态调度的方案，如托马苏洛的算法，引入了源和结果之间的一个周期的延迟，因为结果和其使用的匹配不能在写结果阶段结束时完成，而是在执行阶段结束时完成一个更简单的管道。因此，在动态调度的管道中，生成指令和消费指令之间的有效延迟至少比生成结果的功能单位的延迟长一个周期。

重要的是要记住，托马苏洛方案中的标签指的是将产生结果的缓冲器或单元；当指令发出到预约站时，寄存器名称被丢弃。（这是托马苏洛的方案和记分板之间的一个关键区别：在记分板中，操作数保留在寄存器中，只有在生成指令完成并且消费指令准备执行后才被读取。）

每个预约站有七个字段：

• Op - 对源操作数 S1 和 S2 执行的操作。
• Qj， Qk - 将生成相应源操作数的预留站;值为零表示源操作数已在 Vj 或 Vk 中可用，或者是不必要的。
• Vj， Vk - 源操作数的值。请注意，每个操作数只有一个 V 字段或 Q 字段有效。对于荷载，Vk 字段用于保存偏移字段。
• A - 用于保存加载或存储的内存地址计算信息。最初，指令的直接字段存储在此处;地址计算完成后，有效地址存储在这里。
• Busy - 表示此预订工作站及其随附的功能单元已被占用。

寄存器文件有一个字段 Qi：

• Qi - 包含应将其结果存储到此寄存器的操作的预订站的数量。如果 Qi 的值是空的（或 0），则当前没有活动的指令在计算结果以存储到此寄存器，这意味着该值就是寄存器的内容。

加载和存储缓冲区各有一个字段，A，一旦执行的第一步完成，它就会持有有效地址的结果。

在下一节中，我们将首先考虑一些显示这些机制如何工作的示例，然后研究详细的算法。

在我们详细研究 Tomasulo 的算法之前，让我们考虑几个有助于说明该算法如何工作的示例。

例子：显示以下代码序列的信息表在仅完成第一次加载并写入其结果时的特征：

图 3.11 在三个表格中显示了结果。附加到名称 Add、Mult 和 Load 后面的数字代表该预订站的标记 - Add1 是第一个添加单元的结果的标记。此外，我们还提供了一个指令状态表。包含此表只是为了帮助您理解算法;它实际上不是硬件的一部分。相反，预留站会保留已发出的每个操作的状态。

与早期和更简单的方案相比，Tomasulo的方案具有两个主要优势：（1）危害检测逻辑的分布，以及（2）消除WAW和WAR危害的失速。

第一个优势来自分布式预订站和 CDB 的使用。如果多条指令正在等待一个结果，并且每条指令已经有其另一个操作数，则可以通过在 CDB 上广播结果来同时释放指令。如果使用集中式寄存器文件，则当寄存器总线可用时，单元必须从寄存器中读取其结果。

第二个优点是消除 WAW 和 WAR 危险，这是通过使用保留站重命名寄存器以及在操作数可用时立即将其存储到保留站的过程来实现的。

例如，图 3.11 中的代码序列同时发出 fdiv.d 和 fadd.d，即使存在涉及 f6 的 WAR 危险。危险是以两种方式之一消除。首先，如果为 fdiv.d 提供值的指令已经完成，那么 Vk 将存储结果，允许 fdiv.d 独立于 fadd.d 执行（如图所示）。另一方面，如果 fld 尚未完成，则 Qk 将指向 Load1 预订站，并且 fdiv.d 指令将独立于 fadd.d。因此，无论哪种情况，fadd.d 都可以发出并开始执行。对 fdiv.d 结果的任何使用都将指向预订站，允许 fadd.d 完成并将其值存储到寄存器中，而不会影响 fdiv.d。

图 3.11 当所有指令都已发出，但只有第一个加载指令完成并将其结果写入 CDB 时，显示的预留站和寄存器标签。第二个负载已完成有效地址计算，但正在等待内存单元。我们使用数组 Regs[ ] 来指代寄存器文件，使用数组 Mem[ ] 来指代内存。请记住，操作数在任何时候都由 Q 字段或 V 字段指定。请注意，在 WB 阶段存在 WAR 危险的 fadd.d 指令已经发出，并且可以在 fdiv.d 启动之前完成。

我们很快就会看到一个消除 WAW 危害的例子。但是，让我们首先看看我们前面的示例如何继续执行。在此示例以及本章后面的示例中，假设以下延迟：load 为 1 个时钟周期，add 为 2 个时钟周期，multiply 为 6 个时钟周期，divide 为 12 个时钟周期。

例子：使用与上一个示例（第 201 页）相同的代码段，显示当 fmul.d 准备好写入其结果时状态表的样子。

结果如图 3.12 中的三个表所示。 请注意，fadd.d 已完成，因为 fdiv.d 的操作数已被复制，从而克服了 WAR 危险。 请注意，即使 f6 的负载是 fdiv.d，添加到 f6 中的操作也可以在不触发 WAW 危险的情况下执行

图 3.12 乘法和除法是唯一未完成的指令。

图 3.13 指定了每条指令必须经过的检查和步骤。如前所述，加载和存储经过一个功能单元进行有效的地址计算，然后再进行独立的加载或存储缓冲区。加载需要第二个执行步骤来访问内存，然后转到写入结果，将内存中的值发送到寄存器文件和/或任何等待的预订站。存储在写入结果阶段完成其执行，该阶段将结果写入内存。请注意，所有写入都发生在 Write Result 中，无论目标是寄存器还是内存。此限制简化了 Tomasulo 的算法，并且对于第 3.6 节中的推测的扩展至关重要。

要了解通过动态重命名寄存器来消除 WAW 和 WAR 危害的全部功能，我们必须查看一个循环。考虑以下简单的序列，用于将数组的元素乘以 f2 中的标量：

如果我们预测分支被占用，则使用预留站将允许同时执行此循环的多个执行。这种优势是在不更改代码的情况下获得的，实际上，循环由硬件使用通过重命名获得的预订站作为附加寄存器动态展开。

假设我们已经在循环的两次连续迭代中发出了所有指令，但没有一个浮点加载/存储或操作完成。图 3.14 显示了此时的预留站、寄存器状态表以及加载和存储缓冲区。（整数 ALU 运算被忽略，并假定该分支被预测为已采用。一旦系统达到此状态，就可以在接近 1.0 的 CPI 下维持循环的两个副本，前提是乘法可以在四个时钟周期内完成。由于延迟为 6 个周期，因此需要处理额外的迭代才能达到稳定状态。这需要更多的预订站来保存正在执行的指令。正如我们将在本章后面看到的那样，当使用多个问题指令进行扩展时，Tomasulo 的方法可以在每个时钟上维持多个指令。

加载和存储可以安全地无序完成，前提是它们访问不同的地址。如果负载和存储访问同一地址，则会发生以下两种情况之一：

• load按程序顺序在store之前，互换它们会导致 WAR 危险。
• store位于程序顺序load之前，互换它们会导致 RAW 危险。

图 3.13 算法中的步骤以及每个步骤所需的内容。对于发出指令，rd 是目标，rs 和 rt 是源寄存器编号，imm 是符号扩展的即时字段，r 是指令分配到的保留站或缓冲区。RS 是预订站数据结构。FP 单元或负载单元返回的值称为 result。RegisterStat 是寄存器状态数据结构（不是寄存器文件，即 Regs[]）。发出指令时，目标寄存器的 Qi 字段设置为发出指令的缓冲站或预留站的编号。如果操作数在寄存器中可用，则它们存储在 V 字段中。否则，将 Q 字段设置为指示将生成所需值作为源操作数的值的预留站。指令在预订站等待，直到其两个操作数都可用，在 Q 字段中用零表示。当发出此指令或此指令所依赖的指令完成并执行回写时，Q 字段设置为零。当指令完成执行并且 CDB 可用时，它可以进行回写。所有值为 Qj 或 Qk 的缓冲区、寄存器和预留站都从 CDB 更新其值，并标记 Q 字段以指示已接收值。因此，CDB 可以在单个时钟周期内将其结果广播到多个目的地，如果等待指令有其操作数，它们都可以在下一个时钟周期开始执行。 加载在执行过程中会经历两个步骤，存储在写入结果期间的性能略有不同，它们可能必须等待值存储。请记住，为了保留异常行为，如果程序顺序较早的分支尚未完成，则不应允许执行指令。由于在问题阶段之后不会保留程序顺序的概念，因此，如果管道中已有挂起的分支，则通常通过防止任何指令离开问题步骤来实现此限制。在第 3.6 节中，我们将看到推测支持如何消除此限制。

图 3.14 循环的两次活动迭代，尚未完成任何指令。乘数预留站中的条目表明未完成的负载是源。商店预订站指示乘法目标位置是要存储的值的来源。

同样，将两个存储交换到同一地址会导致 WAW 风险。

因此，要确定某个时间是否可以执行加载，处理器可以检查是否有任何未完成的存储在程序顺序上先于加载并共享同一数据内存地址。同样，存储必须等待，直到在程序顺序上早于它并共享相同数据内存地址的所有未执行的加载或存储都完成。我们在第3.9节中考虑一种消除这种限制的方法。

为了检测这种风险，处理器必须已经计算出与任何早期内存操作相关的数据内存地址。一种简单但不一定最优的方法来保证处理器具有所有这些地址是按程序顺序执行有效地址计算。（我们实际上只需要保持存储和其他内存引用之间的相对顺序，也就是说，加载可以自由地重新排序。）

让我们首先考虑加载的情况。如果我们按程序顺序执行有效地址计算，那么当加载完成有效地址计算时，我们可以通过检查所有活动存储缓冲区的A字段来检查是否存在地址冲突。如果加载地址与存储缓冲区中任何活动条目的地址匹配，那么这个加载指令不会被发送到加载缓冲区，直到冲突的存储完成。（一些实现直接将值从待处理的存储绕过到加载，减少了这种 RAW 风险的延迟。）

存储的操作方式类似，只不过处理器必须检查加载缓冲区和存储缓冲区中的冲突，因为冲突的存储不能相对于加载或存储进行重新排序。

动态调度的流水线可以提供非常高的性能，只要精确预测分支，我们在上一节中解决了这个问题。这种方法的主要缺点是 Tomasulo 方案的复杂性，它需要大量的硬件。特别是，每个预约站都必须包含一个关联缓冲区，该缓冲区必须以高速运行，以及复杂的控制逻辑。性能也可能受到单一 CDB 的限制。尽管可以添加额外的 CDB，但每个 CDB 必须与每个预约站进行交互，并且关联标签匹配硬件必须在每个站点为每个 CDB 复制。在1990年代，只有高端处理器能够利用动态调度（及其对推测的扩展）；然而，近年来，即使是为 PMD 设计的处理器也在使用这些技术，并且为高端桌面和小型服务器设计的处理器有数百个缓冲区来支持动态调度。

在 Tomasulo 的方案中，结合了两种不同的技术：将架构寄存器重命名为更大的寄存器集，以及从寄存器文件中缓冲源操作数。源操作数缓冲解决了当操作数在寄存器中可用时产生的 WAR 风险。如我们稍后将看到，也可能通过将寄存器重命名结合结果缓冲，直到没有对寄存器早期版本的未完成引用，来消除 WAR 风险。当我们讨论硬件推测时，将使用这种方法。

Tomasulo 的方案在 360/91 之后多年未被使用，但在1990年代开始被多发行处理器广泛采用，原因有几个：

1. 尽管 Tomasulo 的算法是在有缓存之前设计的，但缓存的存在，以及其固有的不可预测的延迟，已成为动态调度的主要动机之一。乱序执行允许处理器在等待缓存未命中的完成时继续执行指令，从而隐藏全部或部分的缓存未命中的惩罚。
2. 随着处理器在发布能力上变得更加激进，设计师们开始关心难以调度的代码（如大多数非数值代码）的性能，像寄存器重命名、动态调度和推测这样的技术变得更加重要。
3. 它可以在不需要编译器针对特定流水线结构定位代码的情况下实现高性能，这是在塑料包装大众软件时代的一项宝贵属性。