Chapter 03 : Instruction-Level Parallelism (ILP)¶

约 8805 个字 62 行代码 24 张图片预计阅读时间 45 分钟

Abstract

在计组我们学习的流水线 CPU 仅仅只是考虑了整数指令的操作，且默认每次操作需要一个时钟周期，那对于浮点数的操作呢？浮点数操作所需要的时间远比整数操作时间大，那么当我们添加浮点数操作时，是该使用一个更慢的时钟？还是去各种优化浮点数模块呢？

Introduction¶

Multicycle FP Operation¶

浮点数流水线
- 允许对于一次操作更长的时延，例如，对于 EXE 模块用大于 1 个时钟周期的时间来完成操作
- 在整数流水线上的两个改变：
  - 重复使用 EXE 模块
  - 使用多样的浮点数函数单元（比如浮点数加法器，浮点数除法）

可以看到，EX 模块并没有使用流水线的方式执行：

直到前一条指令离开 EX 模块，不能发射（Issue）使用该功能单元的其他指令
如果有一条指令没法前进到 EX 模块，在这条指令之后整个流水线都会停顿

Latency & Ini/Repeat Interval¶

时延（Latency）：产生结果的指令和使用结果的指令之间需要的时钟周期数
初始化/重复间隔（Initiation/Repeat Interval）：发出给定类型的两个操作之间必须经过的时钟周期数

各个功能单元的时延和初始化/重复间隔如下：

一些解释：

对于我们学习过的整数 ALU，因为有 Forwarding 的存在，所以时延为 0

对于数据存储器来说，即 Load-Use Hazard 的情况，必须加一个停顿周期，所以时延为 1

当连续两个指令都是 Load 指令时，第二个 Load 指令必须等第一个 Load 指令完成才能执行，所以重复间隔为 1

特别需要注意的是：流水线的时延永远比执行模块到产生结果的时钟周期数要小 1 个时钟周期

Structural Hazard¶

在加入浮点数操作之后，就会造成一个新的问题，因为不同的浮点数操作并不完全是流水线式的，且需要的时钟周期也不同，这会导致有可能会出现在同一个时钟周期出现不止一次的寄存器写操作，这就造成了结构冒险（Structural Hazard）

解决方法——联锁检测（Interlock Detection）：
- 方法一：在译码阶段就记录写端口的使用情况，并在指令发射之前停顿一个周期
  - 移位寄存器记录何时已发射的指令将使用寄存器堆
  - 如果在译码阶段有指令需要使用寄存器堆，则停顿一个周期
- 方法二：当指令要进入 MEM/WB 模块时，停顿这个指令
  - 可以停顿正在发射或者已经发射的指令
  - 给最长时延单元最高的优先级
  - 更复杂情况是，在两个地方都需要停顿

WAW Hazard¶

不仅仅是结构冒险，由于指令并不是按照指令的既定顺序到达 WB 模块了，所以就会出现 WAW 冒险（Write After Write Hazard），即两个指令都要写入同一个寄存器，但是第二条指令在第一条指令之前到达了 WB 模块

解决方法：
- 方法一：延后 fld 指令的发射
- 方法二：fadd.d 的零写入控制

RAW Hazard¶

RAW 冒险（Read After Write Hazard）就是和我们的 Load-Use 冒险同理，只是因为加入了浮点数操作，所以会造成更多更复杂的情况

Hazard: Exceptions¶

由于不同浮点数操作需要的时钟周期不同，所以一系列指令的结束顺序很可能和发射顺序不同，这就会造成异常（Exception）

Hazard Detection in ID¶

检查结构冒险
- 确保当寄存器写端口被需要时是可用的
- 直到需要的功能单元不忙碌时再做（仅限除法）
检查 RAW 数据冒险
- 直到源寄存器在需要时可用再做——当它们不是已发射指令的待处理目标时
检查 WAW 冒险
- 检查任何 A1-A4，D，M1-M7 中的指令是否有和当前指令相同的目的寄存器
- 如果有，则停顿当前指令在 ID 阶段的发射

Forwarding¶

因为数据冒险更为多样复杂了，Forwarding 的情况也变得更多了（EX/MEM, A4/MEM, M7/MEM, D/MEM, MEM/WB）

Out-of-Order Completion¶

指令结束的顺序不同的解决方法有：

直接忽略
将指令的结果写入缓冲器中，直到其他比当前指令先发射的指令完成
记录流水线当中执行的指令和它们的 PC
只有确认所有之前的指令完成时不会造成异常，才发射指令

ILP Exploitation¶

ILP 的实现重点是寻找依赖关系（Dependence），只要两个指令没有互相依赖就可以进行并行

有两类利用指令集并行的方法：

基于硬件的动态并行
基于软件（编译器）的静态（编译时）并行：仅限于领域特定的环境或者结构良好的且具备较大程度的数据级并行的科学应用中

如果两条指令是并行的话，意味着它们能够在同一个流水线中同时执行，且不会造成任何停顿（假设流水线有足够多的资源，不会造成结构冒险问题）

在设计 ILP 时，我们必须要考虑指令之间是否存在依赖关系。依赖关系一般分为数据依赖（Data Dependence）、名称依赖（Name Dependence）和控制依赖（Control Dependence）三种类型

Data Dependence¶

如果满足下列条件，那我们称指令 j 数据依赖于指令 i：

指令 i 的执行结果会被指令 j 用到
指令 j 数据依赖于指令 k，而指令 k 数据依赖于指令 i

第二个条件告诉我们：多条指令间可能存在一条依赖链，甚至这条链可以遍布于整个程序中

需要注意的是：单条指令间的依赖关系（比如 add x1, x1, x1）不视为存在依赖

Example

考虑以下 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
    bne      x1, x2, Loop   // branch x1 != x2

这段代码中的数据依赖包括：2-3 行的 f0、3-4 行的 f4 和 5-6 行的 x1

如果两条指令间存在数据依赖关系，则必须保留这两条指令的执行顺序，不得让它们同时执行，因为这可能蕴含着单个或多个数据冒险

Name Dependence¶

当两条指令使用相同的寄存器或内存位置（称为名称（Name）），但这两条指令之间没有关于该名称的数据流时，我们认为发生了名称依赖（Name Dependences）。有以下两类名称依赖（假设指令 j 的程序顺序在指令 i 后面）：

反依赖（Antidependence）：指令 j 向指令 i 读取的寄存器或内存位置上进行写操作
输出依赖（Output Dependence）：当指令 i 和 j 向同一个寄存器或内存位置上进行写操作

正如定义所言，由于具有名称依赖的两条指令之间不存在数据流，所以这种依赖不是真正的依赖，也就是说这样的指令可以并行执行或重新排序，只要改变这些指令使用的名称（寄存器或内存位置），让指令间不冲突就行了

对于寄存器而言，这种重命名操作更加容易（称为寄存器重命名（Register Renaming）），可以用编译器或由硬件动态处理

Data Hazards¶

当指令间存在名称或数据依赖时，如果这样的指令足够接近，能够被重叠执行的话，那么就可能会改变访问和依赖相关的操作数的顺序，此时冒险就发生了。为了避免冒险的发生，在并行时必须保留那些会影响到程序执行结果的程序顺序（Program Order），即按源程序顺序来执行指令的顺序

对于数据冒险（Data Hazard），我们根据指令的读写访问顺序，将其划分为以下几类（还是假设指令 j 的程序顺序在指令 i 的后面）：

RAW（Read after Write）：j 尝试在 i 写入某个源操作数之前读取它，这样 j 就会得到旧的数据。这是最常见的一类冒险，且对应真正的数据依赖
WAW（Write after Write）：j 尝试在 i 写入某个操作数之前向它写入，这样导致写操作的执行顺序错误，该操作数的最终结果是 i 写入的结果而非 j。该冒险对应输出依赖，且仅存在于允许在多个阶段写入数据的流水线，或者允许指令在前一条指令停顿时继续执行的情况下
WAR（Write after Read）：j 尝试在 i 读取某个目的操作数之前先向它写入，这样 i 就会错误地得到了新的数据。该冒险对应反依赖，在大多数静态发射的流水线中不会发生

Control Dependence¶

控制依赖（Control Dependence）决定了指令 i 关于分支指令的顺序。除了程序的第一个基本块外，所有指令都和某些分支之间存在控制依赖，并且这些控制依赖必须被保留下来，以保留程序顺序。考虑以下代码块：

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

不难发现：S1 控制依赖于 p1，S2 控制依赖于 p2 而非 p1。

控制依赖带来以下约束：

关于某个分支控制依赖的指令不得被移动到分支之前，否则的话该指令就不被该分支所控制
不受某个分支控制依赖的指令不得被移动到分支之后，否则的话该指令就要被该分支所控制

事实上，我们不需要严格保留控制依赖，而只需要保留两个关键的性质：异常行为（Exception Behaviour）和数据流（Data Flow）

保留异常行为意味着任何对指令执行顺序作出的改动，不能改变程序如何产生异常的
- 更松弛的版本是：对指令执行的重新排序不得导致程序中出现新的异常
数据流是指令间产生结果或接受输入中的数据值的真实流动
- 分支让数据流变得动态，因为它们让数据源可以来自很多地方。通过保留控制，就能够阻止对数据流的非法变化

Static Scheduling¶

Pipeline Scheduling¶

流水线调度指的是编译器在编译时就重排指令的执行顺序，最后减少一些不必要的停顿

Example

对于以下 C 代码：

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

将其转化为 RISC-V 代码，且没有做过任何调度的结果如下所示：

Loop:
    fld     f0, 0(x1)
    fadd.d  f4, f0, f2
    fsd     f4, 0(x1)
    addi    x1, x1, -8
    bne     x1, x2, Loop

如果没有调度的话，执行一趟循环需要停顿 8 个时钟周期：

但如果我们将 addi 指令移到 fld 的下一条指令的位置上，就可以消除一个停顿：

Loop Unrolling¶

对于上面的例子，事实上真正对数组操作的指令只有三条（fld、fadd.d、fsd）；对于剩下的两个停顿，以及 addi 和 bne 指令，我们希望能够消除掉，因此我们有循环展开（Loop Unrolling）的方法，具体来说就是拷贝多份循环体，并调整循环终止相关的代码。此外，该方法还能提升调度，因为它消除了分支，所以能允许不同迭代下的指令被一起调度

Example

对于上面的例子，使用循环展开，拷贝 4 份循环体。这里假设 x1 - x2 的值是 32 的倍数，这也意味着迭代次数为 4 的倍数

在展开的时候，我们合并了 addi 指令，并删掉了不必要的重复的 bne 指令。结果如下所示：

如果没有调度的话，上述改变不会对性能带来多少提升（每趟循环 6.5 个时钟周期）；但是再加上调度的话，就能够显著提升性能了（每趟循环 3.5 个时钟周期），结果如下所示：

Dynamic Branch Prediction¶

在计组当中我们介绍过简单的分支预测器（Predictors）；但对于更深层的流水线以及多发射处理器，我们需要更精确的分支预测，相对于计组中的简单的静态预测，动态预测更为精确，下面就介绍提高动态预测精度的高级技术

Correlating Branch Predictors¶

我们可以通过观察其他分支的最近行为来提升预测的精度：

Example

考虑以下具有多分支的代码：

if (aa != 2)
    aa = 0;
if (bb != 2)
    bb = 0;
if (aa == bb) {
    // ...
}

对应的 RISC-V 代码为：

    addi x3, x1, -2
    bnez x3, L1         // branch b1
    add x1, x0, x0      // aa = 0
L1:
    addi x3, x2, 02
    bnez x3, L2         // branch b2
    add x2, x0, x0      // bb = 0
L2:
    sub x3, x1, x2      // x3 = aa - bb
    beqz x3, L3         // branch b3

我们称能够利用其他分支的行为来预测的预测器为相关预测器（Correlating Predictors) 或两级预测器（Two-level Predictors）。相关预测器会添加和最近分支的行为相关的信息，来决定如何预测给定的分支。一个 \((m,n)\) 预测器能够预测最近 \(m\) 个分支的行为，来选择 \(2^m\) 个分支预测器，每个都是对应单个分支的 \(n\) 位预测器。这类预测器能够在仅增加少量硬件的基础上，就能产生比 2 位预测器更高的预测率。相关预测器的结构大致如下所示：

\((m,n)\) 预测器的总位数为：

\[ \text{Total Bits} = 2^m \times n \times\text{Number of prediction entries selected by the branch address} \]

而硬件之所以简单，是因为关于最近 \(m\) 条分支的全局历史能够被一个 \(m\) 位移位寄存器记录下来，每一位表示对应分支是否被采用。然后分支预测缓冲器通过对分支地址的地位和 \(m\) 位全局历史的拼接来被索引。通过拼接（或简单的哈希函数）来结合局部和全局信息，我们能够位一个预测器表索引，得到比 2 位预测器更快的预测。而这种能够结合局部分支信息和全局分支历史的预测器也被称为合金预测器（Alloyed Predictors）或混合预测器（Hybrid Predictors）

Tournament Predictors¶

锦标赛预测器（Tournament Predictors）同样用到了多种预测器（全局 + 局部），但它通过一个选择器从这些预测器中选一个最好的来用（实际上是另一种合金预测器或混合预测器）。其大致结构如下所示：

全局预测器（Global Predictors）使用最近的分支历史来索引预测器
局部预测器（Local Predictors）使用分支地址作为索引

Tagged Hybrid Predictors¶

有一类表现更好的预测器，它参照了一种叫做 PPM（Prediction by Partial Matching，根据部分匹配预测）的类似分支预测算法的算法，使用了一系列用不同长度的历史索引的全局预测器——这类预测器称为带标签的混合预测器（Tagged Hybrid Predictors），其大致结构如下所示：

可以看到，它有 5 个预测表：\(P(0),P(1),\cdots,P(4)\)。它使用 PC 的哈希值和最近 \(i\) 条分支（被保存在移位寄存器里）来访问 \(P(i)\)。除了不同的历史长度外，另一个特点是在表 \(P(1),\cdots,P(4)\) 上使用标签。一般情况下 4-8 位的小标签就能取得最佳效果了。仅当标签和分支地址和全局分支历史的哈希值匹配时，才会用到 \(P(1),\cdots,P(4)\) 内的预测。\(P(0…n)\) 例的每个预测器可以是一个标准的 2 位预测器。在实际上，3 位计数器的效果会略微优于 2 位计数器

给定分支的预测来自于标签匹配的，且分支历史最长的预测器上。\(P(0)\) 总是能够匹配，因为它没有标签，因此如果其余表都没有匹配的话，那么它就提供默认的预测了。预测器里还会用到 2 位的使用字段（Use Field），用于表明预测是否在最近被用到过，因此它可能是更精确的。所有的使用字段会被周期性地复位，以清除旧的预测

Dynamic Scheduling¶

动态调度（Dynamic Scheduling）指的是硬件重排指令的执行，以减少停顿，同时维护了（即不会改变）数据流和异常行为。它的优点有：

可以让在某个流水线上被编译的代码在其他流水线上也能高效运行，消除了多份二进制文件以及重新编译的需求
能够处理在编译时没有被发现的依赖，比如内存引用或数据依赖分支，或者采用现代的动态链接或分派
能让处理器容忍无法预测的时延，比如对于高速缓存失效，可通过在等待失效解决时执行其他代码来实现这一点

简单流水线技术的一大限制是采用有序（In-Order）指令发射和执行，即指令按照程序顺序发射，如果有指令停顿了，后面的指令不得继续。因此，如果两条很接近的指令间存在依赖，那么就会导致冒险发生，因而产生停顿；如果有多个函数单元的话，那这些单元在停顿期间就处于空闲状态了。对于下面的指令序列：

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

前两条指令存在依赖关系，因而产生停顿。第三条指令和前两条没有依赖关系，但也不得不跟着一起停顿。所以我们希望在停顿发生时还能继续执行第三条指令。为了做到这一点，我们将发射过程分为两部分：检查任何的结构冒险，以及等待数据冒险的消失。因此我们仍然使用有序的指令发射，但我们希望当处理器的操作数空闲时就能执行指令，这样的流水线做的就是乱序执行（Out-of-Order Execution）

乱序执行会引入 WAR 和 WAW 冒险的可能，这在原来的流水线中是没有的，不过这两类冒险都可以用寄存器重命名来避免

乱序执行还会为处理异常带来麻烦。动态调度处理器会通过延后通知某条指令异常，直到处理器知道该指令是下一条要被执行的指令时，来保留异常行为。此外，动态调度处理器还会产生不精确（Imprecise）的异常：该“异常”产生时，观察处理器的状态，指令好像并没有按严格的程序顺序来执行——这不是真正的异常。发生这种“异常”的原因有：

流水线可能已经执行完程序后面的指令
流水线可能还没有执行程序前面的指令

为了实现乱序执行，我们将流水线的 ID（译码）阶段划分为两个子阶段：

发射（Issue）：对指令译码，检查结构冒险（顺序发射）
读取操作数（Read Operands）：等待，直到没有数据冒险，然后读取操作数（乱序执行）

我们需要区分指令何时开始执行，以及何时完成执行；而在这两个时间点之间，我们认为指令正在执行。并且我们假设处理器有多个函数单元，以实现多指令的同时执行。

有以下实现动态调度的技术：

记分板（Scoreboarding）：当有足够资源以及没有数据依赖的情况下，允许指令乱序执行的技术
托马苏洛算法（Tomasulo's Algorithm）：相比记分板更为精密的技术，它能够通过动态地为寄存器重命名来处理反依赖和输出依赖的问题；此外它还可以被扩展，用于处理推测

Scoreboarding¶

计分板技术通过和功能单元进行交互来动态地调度指令。它会跟踪每个指令的执行状态，并且在指令发射时检查结构冒险和数据冒险。计分板技术的主要组件有：

指令状态（Instruction Status）
功能单元状态（Functional Unit Status）
寄存器状态（Register Status）

Parts of Scoreboarding

Instruction StatusFunctional Unit StatusRegister Status

指令状态表示指令所处的状态，状态包括发射（Issue）、读取操作数（Read Operands）、执行（Execute）、写回（Write Back），同时略去了内存访问，因为乱序执行更多关注浮点数指令

功能单元状态表示功能单元的状态，包括忙碌（Busy）、操作类型（Op）、目标寄存器（Fi）、源寄存器（Fj, Fk）、使用的功能单元（Qj, Qk）、标志（Rj, Rk，表示 Fj, Fk 是否已经准备好被读取）

寄存器状态表示哪个功能单元将要写寄存器

Example

Tomasulo's Algorithm¶

在使用 Tomasulo 算法的动态调度处理器中，

RAW 冒险可通过在操作数空闲时就执行指令来避免
WAR 和 WAW 冒险可通过寄存器重命名（Register Renaming）来消除

其中寄存器重命名通过重命名所有的目标寄存器，包括等待先前指令读 / 写的寄存器来实现，这样的话乱序写操作就不会影响到任何依赖于操作数先前值的指令。如果有足够多可用的寄存器的话，编译器就会实现这种重命名

Example

我们有如下指令序列：

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

其中第 2、4 条指令和第 3、5 条指令之间存在反依赖（WAR 冒险），而第 2、5 条指令之间存在输出依赖（WAW 冒险）。这三个冒险都可以通过寄存器重命名（利用临时寄存器 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

在 Tomasulo 算法中，寄存器重命名由保留站（Reservation Station），它作为正在等待发射且和函数单元相关的指令的缓冲区。当操作数可用时，保留站获取并缓存该操作数，消除了从寄存器中获取操作数的需要。此外，正在等待的指令会指定为自己提供输入的保留站。在指令发射时，用于正在等待的操作数的寄存器标识符被重命名为保留站的名称，从而实现寄存器重命名

保留站的使用带来的重要性质有：

冒险检测和执行控制是被分配好的：在每个函数单元内，保留站保存的信息用于确定指令何时在该单元开始执行
执行结果会从缓存它们的保留站中直接传到函数单元，而无需经过寄存器。这种旁路（Bypassing）操作通过一根公共数据总线（Common Data Bus, CDB）来实现，它允许为所有单元同时加载正在等待的操作数

基于 Tomasulo 算法的处理器的基本结构如下：

其中：

指令队列（Instruction Queue）获取指令，如果没有结构冒险就发射指令
地址单元（Address Unit）在基寄存器可用时，计算有效地址，然后将其放在加载/存储缓冲区内
- 对于加载，当内存单元可用时，加载会立马执行；对于存储，在值被送到内存单元前，会一直等待执行
加载缓冲区（Store Buffers）和存储缓冲区（Load Buffers）分别保留了来自或前往内存的数据或地址
保留站（Reservation Stations）保存了一个被发射的，且正等待在函数单元内被执行的指令
- 如果该指令的操作数值已经被计算出来的话，那么该值也会被一起保存；否则保留站会保存那些提供操作数值的保留站的名称
- 有一个标签字段，为流水线控制所用
所有来自函数单元和内存的结果会被送到公共数据总线（Common Data Bus, CDB）上，该总线除了不经过加载缓冲区外，会经过其他所有部件

在上述处理器中，一条指令会经过以下三步：

发射（Issue）：
- 从指令队列（FIFO 顺序，以维持正确的数据流）的队首中获取下一条指令
- 如果该指令匹配到的保留站是空的，那么将该指令及其操作数（如果当前已在寄存器内的话）发射到该保留站内
- 如果没有空的保留站，那么就存在结构冒险，指令发射停止，直到某个保留站空间被释放
- 如果操作数不在寄存器内，那么追踪会产生操作数值的那个函数单元
- 这一步会进行寄存器重命名（寄存器的名称将会被丢掉），消除了 WAR 和 WAW 冒险
执行（Execute）：
- 如果一个或多个操作数不可用的话，那么监控公共数据总线，等待操作数被计算出来
- 当某个操作数可用时，它将会被放到任何等待它的保留站内
- 当某个操作的所有操作数都可用时，该操作就会在对应的函数单元内被执行
- 通过延时到所有操作数都可用时再执行指令，RAW 冒险得以避免
- 有时多条指令可能在相同的时钟周期下准备就绪，且要用同一个函数单元，此时该单元不得不从中做出选择，比如浮点数单元是随机挑选的，而加载 - 存储单元则更加复杂
- 加载和存储需要两步执行过程：
  - 当基寄存器可用时，计算有效地址，然后将其放在加载或存储缓冲区内
  - 对于加载，当内存单元可用时，加载会立马执行；对于存储，在值被送到内存单元前，会一直等待执行
- 为了保留异常行为，直到在程序顺序中先于指令的分支完成执行后，才允许后面的指令被执行
- 如果处理器记录了异常的发生，但没有发起异常，那么该指令会被执行而不停顿，直到它进入“写入结果”阶段
写入结果（Write Result）：
- 当结果可用时，将其写入 CDB 中，然后再写到寄存器以及任何等待该结果的保留站中）
- 存储操作一直缓存在存储缓冲区内，直到值被存储，且存储地址可用，此时结果被写入空余的内存单元上

每个保留站有 7 个字段：

Op：在源操作数 \(S_1\) 和 \(S_2\) 上的操作
\(Q_j, Q_k\)：产生对应源操作数的保留站。值为 0 表示源操作数已经在 \(V_j\) 或 \(V_k\) 上可用
\(V_j, V_k\)：源操作数的值。注意对每个操作数而言，Q 字段或 V 字段中只有一个是有效的。对于加载，\(V_k\) 字段用于保留偏移字段
A：保留加载或存储的内存地址计算信息。最开始指令的立即数字段会存在这里；经过地址计算后，有效地址会存在这里
Busy：表明保留站以及对应的函数单元是否被占据

寄存器堆有一个字段 \(Q_i\)，表示保留站的数量，这些保留站包括了结果需要存储到寄存器内的操作

加载和存储缓冲区有一个字段 A，保留了有效地址的结果

Tomasulo 算法的具体步骤如下所示：

Example

执行以下指令序列时：

fld     f6, 32(x2)
fld     f2, 44(x3)
fmul.d  f0, f2, f4
fsub.d  f8, f2, f6
fdiv.d  f0, f0, f6
fadd.d  f6, f8, f2

当第一条指令完成写入结果阶段后的信息表格如下：

根据指令状态表可以看到第一条指令完成写入后，第二条指令并未写入，即 \(f_2\) 没有准备好，那么对应需要 \(f_2\) 的 fmul, fsub, fadd 就都不能开始执行，从而导致 \(f_0\) 也没有准备好，进而导致 fdiv 也不能开始执行。

如果访问不同的地址的话，那么加载和存储就可以放心地被乱序执行，但如果访问相同地址的话，以下情况中的其中一种就会发生：

在程序顺序中，若加载在存储的前面，交换两者就会发生 WAR 冒险
在程序顺序中，若存储在加载的前面，交换两者就会发生 RAW 冒险
交换两个访问相同地址的存储指令会发生 WAW 冒险

为了检测这样的冒险，处理器必须计算和先前内存指令相关的数据内存地址。对于加载而言，先计算它的有效地址，如果发现和存储缓冲区中的任何一项匹配上的话，那就不要将这条加载指令送到加载缓冲区里，直到那条冲突的存储指令执行完毕。对存储的处理也是类似的，除了它要同时检查加载和存储缓冲区里的内容

Tomasulo 算法的两大优势是：

冒险检测单元的分布，该优势来自于分布的保留站和 CDB 的使用。如果多条指令等待相同的结果，且每条指令的其他操作数均以准备就绪，那么通过 CDB 对结果的广播，指令得以同时释放
消除因 WAW 和 WAR 冒险导致的停顿，该优势通过保留站重命名寄存器，以及在保留站存储可用操作数来实现的

Hardware Speculation¶

当我们想要更大程度的 ILP 时，维持控制依赖将成为增长的负担，对于多发射处理器更加如此，因此我们将会使用硬件推测（Hardware Speculation）技术

硬件推测的三个关键思想为：

动态分支预测，用于选择需要执行的指令
推测，允许控制依赖前的指令得以执行
动态调度，处理对不同基本块的调度

硬件推测遵循预测的数据值流来选择何时执行指令。这种执行程序的方法称为数据流执行（Data execution）：当操作数可用时，运算立即执行

当指令不再是推测指令时，才允许该指令更新寄存器堆或内存，我们称这个步骤为指令提交（Instruction Commit）

实现推测背后的关键思想是允许指令乱序执行，但强迫它们按顺序提交，以阻止任何不可更改的行为。所以在使用推测技术时，需要将完成执行的过程和指令提交分开来；并且需要额外的硬件缓冲区来保留已执行完毕的，但未提交的指令结果。这种缓冲区称为重排缓冲区（Reorder Buffer, ROB），它和保留站一样提供了额外的寄存器。由于 ROB 和存储缓冲区类似，所以之后就将存储缓冲区并到 ROB 里面了

下图展示了实现推测技术后的，并采用托马苏洛算法的处理器的结构：

ROB 里的每一项包含了 4 个字段：

指令类型：表明该指令是分支指令（无目标结果），存储指令（目标为内存地址），还是寄存器操作（ALU 运算和加载指令，目标为寄存器）
目标字段：提供指令结果应该被写入的寄存器编号（ALU 运算和加载指令）或内存地址（存储指令）
值字段：保留指令结果的值，直到指令提交
准备字段：表明指令是否执行完毕，此时值已经准备好了

发射：
- 从指令队列获取指令
- 若存在一个空的保留站以及一个空的 ROB 项，则发射该指令
- 如果操作数在寄存器或 ROB 上可用的话，那么将操作数也送到保留站内
- 更新控制项，表明缓冲区在使用了
- 为结果分配的 ROB 的项数也要送到保留站内，这样的话当结果被放在 CDB 上时，可以用这个数字来为该结果打标签
- 如果保留站或 ROB 满了，那么停止发射指令，直到有空余项为止
执行：
- 如果一个或多个操作数不可用的话，那么监控 CDB，等待操作数被计算出来
- 当某个操作的所有操作数都可用时，那就执行该操作
- 这一阶段可能需要多个时钟周期
写入结果：
- 当结果可用时，将其（以及 ROB 标签）写入 CDB，然后从 CDB 写到 ROB 以及其他等待该结果的保留站内
- 对于存储指令，如果存储值可用，那么将其写入到 ROB 项的值字段内；若不可用，那么监控 CDB 直到该值被广播
提交（Commit）：有以下三种情况
- 正常提交（当指令到达 ROB 头，且对应值在缓冲区内时）：处理器用指令执行结果更新寄存器，并移除 ROB 内的指令
- 提交存储指令：和前一种情况类似，只是更新的东西变成了内存而非寄存器
- 错误预测的分支指令（即推测错误）：清除 ROB 里的内容，重新开始分支指令后的正确指令

Example

假设浮点数函数单元的时延为：

加法：2 个时钟周期
乘法：6 个时钟周期
除法：12 个时钟周期

对于以下指令序列：

fld     f6, 32(x2)
fld     f2, 44(x3)
fmul.d  f0, f2, f4
fsub.d  f8, f2, f6
fdiv.d  f0, f0, f6
fadd.d  f6, f8, f2

当 fmul.d 指令准备提交时的状态表如下：

直到指令提交前，都不会向寄存器和内存写入数据，所以当发现分支预测错误时，处理器能够轻松地撤回推测行为（或恢复）：清空缓冲区，获取其他指令。在推测处理器中，性能对分支预测更加敏感，因为错误预测的影响会更大，因此处理分支的各方面，包括预测精度、误预测检测的时延和误预测恢复时间都相当重要

处理器仅在准备提交时才会识别并处理异常。如果推测指令发起异常，那么该异常会被记录到 ROB 里。如果发生了分支误预测且指令还没被执行，那么异常就会随 ROB 里的其他内容被清除掉。但如果指令已经进入到 ROB 头，那饿我们知道该指令不再是可推测的，且异常真的发生了，此时应尽快处理异常

推测处理器的具体运行步骤如下图所示：

Chapter 03 : Instruction-Level Parallelism (ILP)¶

Introduction¶

Multicycle FP Operation¶

Latency & Ini/Repeat Interval¶

Structural Hazard¶

WAW Hazard¶

RAW Hazard¶

Hazard: Exceptions¶

Hazard Detection in ID¶

Forwarding¶

Out-of-Order Completion¶

ILP Exploitation¶

Data Dependence¶

Name Dependence¶

Data Hazards¶

Control Dependence¶

Static Scheduling¶

Pipeline Scheduling¶

Loop Unrolling¶

Dynamic Branch Prediction¶

Correlating Branch Predictors¶

Tournament Predictors¶

Tagged Hybrid Predictors¶

Dynamic Scheduling¶

Scoreboarding¶

Tomasulo's Algorithm¶

Hardware Speculation¶

评论