计算机组织中流水线中的依赖性和数据冲突

在本节中，我们将学习流水线处理器中的依赖关系，具体描述如下：

流水线处理器中的依赖

流水线处理器通常有三种类型的依赖，具体描述如下：

1. 结构依赖
2. 数据依赖
3. 控制依赖

由于这些依赖关系，流水线中会引入停顿。停顿可以描述为流水线中没有新输入的周期。换句话说，当后续指令依赖于先前指令的输出时，就会发生停顿。

结构依赖

结构依赖通常是由于流水线中的资源冲突引起的。资源冲突可以描述为流水线中包含ALU（算术逻辑单元）、内存或寄存器等资源的情况。在资源冲突中，一个以上的指令试图访问同一资源。

示例

上表包含四条指令 I₁、I₂、I₃ 和 I₄，以及五个周期 1、2、3、4、5。在周期 4 中，存在资源冲突，因为 I₁ 和 I₄ 试图访问同一资源。在本例中，该资源是内存。解决此问题的方法是，在所需资源可用之前，让指令等待。由于这种等待，流水线中会引入停顿，如下所示：

结构依赖的解决方案

借助硬件机制，我们可以最大程度地减少流水线中的结构依赖停顿。该机制称为 **重命名**。

重命名： 在此机制中，内存被分成两个独立的模块，称为数据内存（DM）和代码内存（CM）。在此，所有指令都通过 CM 获取，而指令所需的所有操作数都由 DM 获取。

控制依赖（分支冲突）

当传输控制指令时，就会发生控制依赖。这些指令可以是 JMP、CALL、BRANCH 等。在许多指令体系结构中，当处理器想将新指令添加到流水线时，它不知道这些新指令的目标地址。由于这一缺点，不必要的指令会被插入流水线。

例如

为此，我们将假设一个程序并按以下顺序处理指令：

100: I1
101: I2
102: I3
.
.
250: BI1

预期输出描述如下：

I1 → I2 → BI1  

注意：在 ID 阶段之后，处理器就能知道 JMP 指令的目标地址。

输出序列描述如下：

I1 → I2 → I3 → BI1 

因此，上面的例子表明预期输出和输出序列不相等。这表明流水线未正确实现。

我们可以通过在获得分支指令的目标地址之前停止取指令来纠正这个问题。为此，我们将实现一个延迟槽，直到获得目标地址，如下表所示：

输出序列描述如下：

I1 → I2 → Delay (Stall) → BI1

在上面的例子中，我们可以看到延迟槽没有执行任何操作。这就是为什么输出序列和预期输出不相等的原因。但由于这个槽，流水线中会引入停顿。

控制依赖的解决方案

在控制依赖中，我们可以通过一种称为 **分支预测** 的方法来消除流水线中的停顿。对哪个分支将被采取的预测在分支预测的第 1 个阶段完成。分支预测包含 0 **分支惩罚**。

分支惩罚： 分支惩罚可以描述为在流水线中的分支操作期间引入的停顿数量。

数据依赖（数据冲突）

为此，我们将假设一条 ADD 指令 S 和三个寄存器，具体描述如下：

指令 S2 将依赖于指令 S1，如下所示：

上述条件称为 **伯恩斯坦条件**。在此条件下，有三种情况，具体描述如下：

流动（数据）依赖： 假设此依赖项包含 O(S1) ? I(S2)，S1 → S2。在这种情况下，当 S2 读取某些内容时，S1 才会写入。

反依赖： 假设此依赖项包含 I(S1) ? O(S2)，S1 → S2。在这种情况下，在 S2 覆盖 S1 之前，S1 会读取一些内容。

输出依赖： 假设此依赖项包含 O(S1) ? O(S2)，S1 → S2。在这种情况下，S1 和 S2 都会写入同一个内存位置。

例如： 在这里，我们将假设我们有两条指令 I₁ 和 I₂，如下所示：

I1: ADD R1, R2, R3
I2: SUB R4, R1, R2

当上述指令 I₁、I₂ 在流水线处理器中执行时，就会发生数据依赖。这表明在 I₁ 写入数据之前，I₂ 试图读取它。结果，指令 I₂ 错误地获取了 I₁ 的旧值，具体描述如下表：

在这里，我们将使用 **操作数转发** 来最大程度地减少数据依赖中的停顿。

操作数转发： 在此转发中，我们将使用阶段之间的接口寄存器。这些寄存器用于包含中间输出。借助中间寄存器，依赖指令可以直接访问新值。

为了解释这一点，我们将使用相同的示例：

I1: ADD R1, R2, R3
I2: SUB R4, R1, R2

数据冲突

由于数据依赖，会发生数据冲突。如果通过显示数据依赖的指令在流水线的不同阶段修改数据，在这种情况下，会发生数据冲突。当指令读/写其他指令使用的寄存器时，在这种情况下，会发生指令冲突。由于数据冲突，流水线会产生延迟。数据冲突主要有三种类型：

1. RAW
2. WAR
3. WAW

为了理解这些冲突，我们将假设我们有两条指令 I1 和 I2，使得 I2 跟随 I1。冲突描述如下：

RAW

RAW 冲突可以称为 **“写后读”**。它也称为流动/真实数据依赖。如果后续指令尝试在先前指令写入之前读取操作数，在这种情况下，会发生 RAW 冲突。检测 RAW 冲突的条件是当 O_n 和 I_n+1 都有至少一个共同的操作数。

例如

I1: add R1, R2, R3
I2: sub R5, R1, R4

存在 RAW 冲突，因为减法指令读取了加法的输出。指令“add R1, R2, R3”和“sub R5, R1, R4”的冲突描述如下：

RAW 冲突非常普遍。

WAR

WAR 冲突可以称为“读后写”。它也称为反数据依赖。如果后续指令尝试在先前指令读取之前写入操作数，在这种情况下，会发生 WAR 冲突。检测 WAR 冲突的条件是当 I_n 和 O_n+1 都有至少一个共同的操作数。

例如

依赖关系描述如下：

add R1, R2, R3
sub R2, R5, R4

这里，加法指令会产生 WAR 冲突，因为减法指令写入了 R2，而 R2 是加法指令读取的。在合理的（有序）流水线中，WAR 冲突非常罕见或不可能。指令“add R1, R2, R3”和“sub R2, R5, R4”的冲突描述如下：

当指令尝试进入流水线的写回阶段时，此时，程序中包含的所有先前指令都已通过寄存器的读阶段并读取了它们的输入值。现在，写入指令可以毫无问题地写入其目标寄存器。与 WAW 相比，WAR 指令的问题较少，因为在 WAR 中，在流水线的写回阶段之前，会发生寄存器的读阶段。

WAW

WAW 冲突可以称为 **“写后写”**。它也称为输出数据依赖。如果后续指令尝试在先前指令写入之前写入操作数，在这种情况下，会发生 WAW 冲突。检测 WAW 冲突的条件是当 O_n 和 O_n+1 都有至少一个共同的操作数。

例如

依赖关系描述如下：

add R1, R2, R3
sub R1, R2, R4

这里，加法指令会产生 WAW 冲突，因为减法指令写入了同一个寄存器。指令“add R1, R2, R3”和“sub R1, R2, R4”的冲突描述如下：

在流水线的写回阶段，指令的输出寄存器将被写入。WAW 冲突的指令在程序中出现的顺序，这些指令将按相同的顺序进入流水线的写回阶段。这些指令的结果将按正确的顺序写入寄存器。与原始程序相比，处理器提高了性能，因为它允许指令以不同的顺序执行。

WAR 和 WAW 的影响

WAR 和 WAW 冲突的发生是因为处理器具有有限数量的寄存器。因此，这些冲突也称为名称依赖。

如果处理器包含无限数量的寄存器，它将使用不同的寄存器来生成每条指令的输出。在这种情况下，不会发生 WAR 和 WAW 冲突。

如果处理器使用相同的流水线处理所有指令，并按照指令在程序中出现的顺序执行它们，那么 WAR 和 WAW 冲突就不会导致延迟。这一切都是因为指令流经流水线的过程。