3.3 现代超标量处理器中的关键 ILP 概念

超标量处理器的理想 CPI 小于 1，通过硬件技术发现并开发 ILP。即使程序只经过适度优化，它们也能提供很高的性能，因此已成为服务器、桌面计算机、笔记本电脑和手机领域的主流选择。不过，它们的局限与设计复杂度，也促使芯片厂商将超标量思想与侧重数据级并行性的技术（见第 4 章的 SIMD）以及 TLP 技术（见第 5 章的多核）相结合。

采用 x86、Arm、RISC-V 等主流指令集体系结构（ISA）的处理器，必须忠实实现这些 ISA 的顺序语义。程序执行在功能上必须等价于在一个简单处理器上运行：该处理器按原始程序顺序执行指令，指令之间没有重叠。功能等价既涉及寄存器与内存位置中产生的值、引发的异常，也涉及这些值与异常变为可见的顺序。稍后将看到，许多超标量处理器虽然按照数据依赖决定的顺序执行指令，而非按照原始程序顺序执行，仍然能够保持功能等价。这类设计称为乱序（out-of-order，OOO）超标量处理器。由于多数现代超标量处理器都采用 OOO 流水线，许多人认为“超标量”与“乱序超标量”是同义词。本章后面也将介绍按程序规定顺序执行指令的低功耗、顺序超标量设计。

冗余代码消除、强度削弱和寄存器分配等基本编译器优化，对超标量处理器与标量处理器同样有益。不过，超标量处理器较少依赖循环展开等高级编译器技术，因为它们具有相应的硬件机制，能够在几十到几百条指令的窗口内实施类似优化。即使现有二进制程序没有为新处理器的流水线重新编译、重新优化，新一代超标量处理器也能使其获得性能提升。这个优点是超标量体系结构取得商业成功的关键因素之一。

更深的流水线与多发射

与前面讨论的简单流水线相比，超标量处理器通过改善 CPU 执行时间公式中的两个因素来提高性能。该公式为 $\text{CPU 时间}=\text{IC}\times\text{CPI}\times\text{CCT}$：

• 更深的流水线：附录 C 的简单处理器采用五级流水线。超标量处理器采用更深的流水线，当代设计通常为 10～20 级。流水线更深，便可以缩短时钟周期；目前时钟频率为 1～5 GHz。两个整数操作数相加之类的简单操作仍只占一个流水级，而乘法、浮点操作、指令或数据缓存访问等较长延迟的操作，会占用多个流水级，通常为 2～4 级。不过，多数流水线大约有一半流水级，用于实现发现 ILP 并进行动态调度所需的复杂控制逻辑。
• 多发射或宽发射：附录 C 的简单处理器每个时钟周期启动一条指令，因此最佳流水线 CPI 为 1。超标量处理器试图在每个周期启动多条指令，当代设计为每周期 2～16 条。每周期启动 4 条指令的处理器，最佳 CPI 为 1/4，或者说最佳 IPC 为 4。这类处理器包含多个加法器、乘法器等功能单元，以并行执行指令。

例如，假设一个超标量处理器的发射宽度为 4 条指令，流水线深度为 15 级。它能够重叠执行 60 条指令，需要很高的 ILP 才能相对于简单流水线显著提高性能。

接下来先回顾 3.1 节提出的 ILP 挑战如何塑造了超标量处理器的设计，再在后续各节详细解释每项技术。

控制依赖 → 分支预测与推测执行

典型程序每 4～7 条指令就有一条分支。由此产生的控制依赖，严重限制了可开发的 ILP。

考虑 3.1 节中给数组元素加上一个标量的循环：

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 时跳转

该循环单次迭代内部几乎没有并行性可供开发。要使不同迭代中的独立指令重叠执行，就必须迅速确定循环末尾 bne 的结果。本章后面将看到，15 级流水线的分支延迟通常为 5～10 个周期。控制循环结束的分支经常跳转，所以对于宽度为 4 条指令的流水线，每个分支延迟周期都意味着错失执行 4 条指令的机会，多发射与更深流水线带来的大部分性能收益因此被抵消。

编译器进行循环展开能够减少分支出现的频率，从而缓解这一问题。不过，合适的展开程度取决于处理器设计。宽度为 2、深度为 7 级的处理器，可能在循环展开 4 次后就表现良好；宽度为 4、深度为 15 级的处理器，却可能需要展开至 16 次，才能显露出足够的并行性。许多程序以二进制形式分发，很难针对每一种处理器流水线重新编译和优化。此外，循环展开对于条件语句（if-then-else）的分支并无帮助，而这类分支在循环内部也可能很常见。

超标量处理器利用动态分支预测与推测执行，减轻控制依赖的影响。其硬件结构保存最近分支执行的历史，据此预测分支是否跳转（方向预测），以及分支跳转后的下一条指令是什么（目标预测）。对于上面的简单循环，只需几次迭代和简单的历史记录结构，就足以高度确信该分支几乎总会跳转，而且其目标在整个程序执行过程中保持不变。面对包含数千条分支的程序，就需要更大、更复杂的预测结构来保存历史，并捕捉嵌套循环、直接或间接函数调用以及条件语句中可预测的行为模式；即使这些模式在执行过程中变化，也要能够捕捉。此外，深流水线与宽发射还要求处理器同时处理多条已预测、但仍在途的分支。

分支预测与取指令并行进行。每个时钟周期，硬件都必须确定下一周期访问指令时使用的程序计数器（PC）。第一次预测只能以当前 PC 为输入，此时甚至还不知道它是否指向分支，更不知道分支类型。因此，处理器通常采用多级方案，随着指令译码过程中逐步获得更多信息，不断修正预测。

在一条已预测分支之后取到的指令，会以推测方式执行，直到该分支本身执行、验证方向与目标预测为止。如果其中任一预测有误，就用恢复机制撤销错误预测分支之后推测取入并执行的所有指令。恢复完成后，从正确的 PC 继续执行。

超标量处理器要获得良好性能，分支预测就必须高度准确。假设我们的四发射处理器具有 10 周期分支延迟，对上面含 5 条指令的循环，预测准确率为 95%。每发生一次错误预测，处理器就会连续 10 个周期取入错误指令；对于四发射设计，这相当于损失执行 40 条指令的机会。要使 40 条指令在宽发射、深流水线中，以其他依赖允许的最快速度执行，处理器必须连续正确预测 7 条分支，其概率为 $(0.95)^7=69.8\%$。连续执行 200 条指令而不发生错误预测的概率为 $(0.95)^{39}=13.5\%$。即使忽略其他所有性能挑战，95% 的预测准确率仍会限制任意超标量处理器的持续性能，并限制流水线可采用的宽度与深度。

名依赖 → 寄存器重命名

分支预测使硬件能够进行循环展开，超标量处理器因而可以重叠执行多次迭代中的指令。对于我们的循环，关键是使不同迭代的加载指令 fld 重叠执行，因为这些指令有相当大的延迟，尤其是在部分加载发生 L1 缓存未命中时。然而，所有加载指令之间，都存在关于寄存器 f0 的名依赖（WAW）。图 3.3 展示了两次迭代之间的全部名依赖，即 WAW 与 WAR；它们使跨迭代的有效指令重叠无法实现。

图 3.3 展开循环的两次迭代中，指令之间的全部名依赖。名依赖可以是输出依赖（WAW），也可以是反依赖（WAR）。图中 1st iteration、2nd iteration 分别表示第 1 次和第 2 次迭代；绿色实线为输出依赖，红色虚线为反依赖；指令与寄存器标识符保持原样。

如 3.2 节所示，编译器将循环展开 4 次时，会为每次迭代使用不同的一组整数寄存器，以消除名依赖。¹ 寄存器重命名试图用硬件完成同样的工作，但有两项主要区别。第一，硬件不能假定 ISA 定义的其他寄存器可供使用。尽管我们的示例代码只用了 f0、f2、f4 和 f6，其他所有浮点与整数寄存器都可能保存了程序前后部分需要使用的数据。第二，我们可能需要比 ISA 定义的数量更多的寄存器。

为了适应宽而深的流水线，将循环展开 10 次就需要 40 个浮点寄存器，每次迭代 4 个，超过了 RISC-V 定义的 32 个。¹

硬件寄存器重命名通过实现数百个对软件透明的物理寄存器来应对这些挑战，并动态分配它们以消除名依赖。硬件维护指令引用的体系结构寄存器与实际实现的物理寄存器之间的映射。指令发射时，利用这一映射确定哪些物理寄存器保存输入操作数，并更新映射，指出哪个物理寄存器将保存输出操作数。如 3.4 节所讨论，其中一个难点是确定物理寄存器中的值何时不再需要，从而使该寄存器能被后续指令复用。²

数据依赖 → 利用动态调度实现乱序执行

分支预测对控制依赖进行推测，寄存器重命名消除经由寄存器的名依赖；在此基础上，超标量处理器通过动态调度，按数据依赖决定的顺序执行已取入的指令，这也称为数据流顺序。硬件实现两项功能。第一，跟踪所有待执行指令的输入操作数（物理寄存器）是否可用。当所有输入操作数都可用时，该指令就已就绪，可以执行。在我们的循环中，当 f4 与 x1 的值可用时，fsd 就已就绪。第二，根据指令年龄、指令关键程度等标准，从就绪指令中选择一部分，交给可用的功能单元执行。

动态调度会使指令乱序执行。在示例循环中，第一次迭代的加载 fld 可能发生缓存未命中，依赖它的加法 fadd.d 与存储 fsd 可能几十个周期都无法就绪。不过，addi 对该加载没有数据依赖，所以可以执行；这又使第二次迭代的加载能够执行。如果第二次加载缓存命中，那么第二次迭代的所有浮点指令，很可能比第一次迭代的对应指令更早完成。

动态调度受到操作数跟踪硬件容量的限制，这些结构通常能跟踪几十到一百条指令。当指令执行延迟可以静态确定时，编译器的静态调度效果很好；动态调度则能应对可变的执行延迟。这一点对于从多级缓存读取数据的加载指令尤其重要，因为它们的延迟可能从 2 个周期到 100 个周期不等。硬件会动态绕过缓存未命中的加载进行调度，执行后面任何独立的指令。这项优化是现代超标量处理器的一项关键性能优势。

内存依赖 → 推测性内存消歧

动态调度还必须遵守经由内存位置形成的依赖。考虑示例循环的以下版本：目标数组与输入数组不同，而且遍历两个数组的顺序也不同。

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

高性能的关键是尽早执行不同迭代的加载，因为其他浮点指令都对加载存在数据依赖，而加载访问缓存时可能具有很高的延迟。若硬件要把第 $i+1$ 次迭代的加载调度到第 $i$ 次迭代的存储之前，就必须先检查它们是否访问不同的内存地址。这种检查不一定能静态完成，因为 x1 与 x3 的值可能在编译时未知，编译器无法确定输入和输出数组是互不相交，还是有重叠。此外，存储的内存地址也不一定立即可用。只有影响 x3 值的所有先前指令都执行完，并且存储指令被分配给地址生成单元、算出有效地址 x3+40 后，才能进行检查。这种约束可能推迟下一条加载的执行，限制硬件可开发的 ILP。即使加载与存储的有效地址已知，硬件也可能无法安全地改变它们的顺序，因为这可能违反多处理器系统的存储一致性约束（见第 5 章）。

超标量处理器用推测性内存消歧（speculative memory disambiguation）应对内存依赖的不确定性。正如跟踪分支历史可以围绕控制依赖进行推测，硬件也会跟踪加载与存储指令的近期历史，学习哪些加载很可能依赖尚未算出地址的较早存储。对于不太可能存在依赖的加载，硬件会推测性地将其重排到较早的存储之前。当所有较早存储的地址都已确定，硬件就能验证这次重排是否正确。如果不正确，就必须重新执行加载及所有依赖它的指令，从错误推测中恢复。

推测恢复与精确异常 → 重排序缓冲区

超标量处理器上的程序执行，在功能上必须等价于一个指令之间完全不重叠的简单处理器。简单处理器只有在指令的全部依赖都已解决后才执行该指令，因此不需要预测分支结果，也不需要预测加载、存储指令的顺序。要保持功能等价，超标量处理器需要一种恢复机制，撤销分支错误预测，或加载与存储之间的依赖错误预测之后，错误执行的全部指令。该机制必须确保，错误执行的指令既不影响程序的数据流，即不更新寄存器或内存值，也不影响控制流，即不更新 PC。

这种等价要求也涵盖程序执行中触发的任何异常，例如加载指令的缺页异常，或浮点指令的算术溢出。在简单处理器中，异常发生并将控制权交给操作系统时，出错指令之前的所有指令均已完成，而出错指令之后的所有指令，都没有修改处理器状态（寄存器或内存位置），也没有触发异常。这一属性称为精确异常。超标量处理器一律预测指令不会引发异常，这通常是非常准确的预测。不过，在处理器确认某条可能引发异常的指令实际上不会引发异常之前，该指令之后的所有指令都必须视为推测执行的指令。

高级超标量处理器有两项属性，使精确异常更难实现。第一，它们会重排指令。在示例循环的第一次迭代中，存储指令触发缺页异常时，后续迭代中的若干加载和浮点指令可能已经执行，甚至可能各自触发了异常。第二，它们既对控制依赖，也对内存依赖进行推测。如果分支预测有误，在发现错误并恢复之前，部分已错误地全部或部分执行的指令，可能引发异常。如果推测性内存消歧有误，部分加载可能返回错误数据，进一步导致错误计算与错误异常。

超标量处理器使用重排序缓冲区（reorder buffer，ROB）从错误推测中恢复。ROB 是一种先进先出（FIFO）结构，临时保存指令结果，并且只允许这些结果按原始程序顺序，对程序的数据流和控制流产生永久影响。指令按照程序顺序获得 ROB 条目。指令乱序完成执行时，更新自身 ROB 条目，标记执行中检测到的潜在异常。每个时钟周期，硬件检查 ROB 中最老的指令，等待它们执行完成后，才允许结果永久影响寄存器和内存位置：丢弃物理寄存器中的较旧值，允许存储覆盖内存位置，并释放 ROB 条目。如果最老的指令是一条分支，而此前流水线对它的结果预测错误，就通过释放其后所有指令的 ROB 条目及其他临时缓冲区，例如为结果分配的物理寄存器，来撤销这些后续指令。撤销所有这些指令，能确保错误的分支推测不影响程序的数据流与控制流。随后从分支执行时算出的正确目标地址恢复执行。如果最老的指令是一条被错误重排到较早存储之前的加载，则撤销该加载本身及其后的所有指令，并从该加载指令的地址恢复执行。这种顺序确保内存依赖的错误推测不会影响程序的数据流与控制流。

ROB 提供的推测恢复也支持精确异常。如果 ROB 中最老的指令被标记为会产生缺页、算术溢出等异常，就撤销它本身以及后面的全部指令，再从操作系统相应异常处理程序的 PC 开始执行。硬件还会更新寄存器，帮助操作系统识别引发异常的指令与异常类型。只有当指令到达 ROB 头部时，才向操作系统报告异常，因此无论错误推测还是指令重排，都不会影响异常的报告顺序。

超标量处理器概览

图 3.4 概括了现代超标量处理器如何将多发射、深流水线与推测及动态调度技术结合起来。这样的处理器在整个流水线中，可以同时保有几十到几百条尚未完成的指令，包括多条已预测的分支，以及多条发生缓存未命中的加载、存储指令。处理器流水线由三部分组成，每部分都以流水线方式每周期处理多条指令。

处理器前端每周期取入并译码多条指令。它按顺序、以推测方式工作：利用分支预测确定每周期的 PC，但不重排指令。每条指令译码后，对寄存器操作数重命名，为结果分配一个 ROB 条目，再将指令发射到动态调度硬件结构中。如果没有空闲物理寄存器、ROB 条目或调度条目，前端就停止取入新指令，直到资源可用。我们用指令束（instruction bundle）表示同一个时钟周期内并行发射的一组指令。在多数超标量处理器中，同一指令束中的指令也会并行取入和译码。

执行引擎利用动态调度，以数据依赖所允许的速度，每周期推测性地、乱序处理多条指令。当一条指令的所有输入操作数都就绪，且有适当的功能单元可用时，就将它派发（dispatch）去执行。执行完成后，包括异常在内的指令结果会暂存在 ROB 条目中。硬件同时通知调度逻辑，因为部分依赖该指令的指令此时可能已经就绪。注意，同一指令束中的指令，很可能在不同的周期派发，也在不同的周期完成。硬件会重新排序并重叠执行来自多个指令束的指令。

图 3.4 现代超标量乱序处理器流水线的高层概览。前端、执行引擎和后端都每周期处理多条指令。图中的若干硬件模块，例如缓存或某些功能单元，可能占据多个流水级。

图中文字对照：PC 为程序计数器；Instruction Cache 为指令缓存；Branch Predictors 为分支预测器；Instruction Decoding 为指令译码；Register Renaming 为寄存器重命名；Dynamic Scheduling 为动态调度；Reorder Buffer 为重排序缓冲区；Physical Registers 为物理寄存器；FUs 为功能单元；Load/Store Queue 为加载／存储队列；Data Cache 为数据缓存；In-order Commit 为顺序提交。Front-end 为前端（顺序、推测）；Execution Engine 为执行引擎（乱序、推测）；Back-end 为后端（顺序、非推测）。处理步骤 Fetch、Issue、Dispatch、Complete、Commit 依次为取指、发射、派发、完成、提交。

处理器后端利用 ROB，按程序顺序更新处理器状态、寄存器和内存位置，并从错误推测或异常中恢复。只有当指令成为 ROB 中最老的指令后，它才能提交（commit，也称退役，retirement），结果才会对体系结构可见。如果最老的指令引发异常或错误预测，就利用 ROB 撤销出错指令之后的指令：释放它们分配的物理寄存器和 ROB 条目，再从正确 PC 恢复执行。被撤销的指令中，有些可能已经执行完成，另一些则可能还在等待操作数。

了解现代乱序处理器的整体工作方式后，后续各节将深入考察其流水线中关键硬件结构的实现。3.8 节还会进一步讨论：每个流水级都要每周期处理多条指令，同时不违反任何依赖，这是复杂度的主要来源之一。