Chapter 03 : Instruction-Level Parallelism (ILP)¶

约 5322 个字 40 行代码 18 张图片预计阅读时间 27 分钟

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 代码，且没有做过任何调度的结果如下所示：

```asm
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

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¶

评论