Chapter 6 Pipelining（2）

目录中英对照表

章节编号	英文标题	中文标题
6.1	Basic Concept of Pipelining	流水线的基本概念
6.2	Pipeline Organization	流水线的组织结构
6.3	Pipeline Issues	流水线中的问题
6.4	Data Dependencies	数据相关性
6.5	Memory Delays	内存延迟
6.6	Branch Delays	分支延迟
6.7	Resource Limitations	资源限制

序号	英文标题	中文标题
1	Making the Execution of Programs Faster	提高程序执行速度
2	What is Pipelining?	什么是流水线？
3	Car Assembly Line Example	汽车装配线示例
4	Pipelining a Processor	对处理器进行流水线处理
5	Pipeline Terminology	流水线术语
6	Pipeline Organization	流水线的组织结构

English	中文
Pipeline Issues	流水线问题
Data Dependency	数据依赖
- Operand Forwarding	操作数转发
- Extension of Operand Forwarding	操作数转发的扩展
- Software Handling of Dependencies	依赖关系的软件处理
Memory Delays	内存延迟
Resource Limitations	资源限制
Branch Delays	分支延迟

回忆

在流水线处理器中，F, D, C, M, W 代表了指令在执行过程中所经过的五个基本阶段。每个字母代表一个阶段，指令会依次经过这些阶段，完成从获取到最终写回的过程。

1. F - Fetch（取指阶段）

功能：从内存中获取指令。
操作：处理器从程序计数器（PC）指定的位置取出指令，指令被加载到指令寄存器（IR）中。之后，PC 会增加，指向下一条指令的地址。
解释：这一阶段的目的是将程序指令从内存中提取出来，送入流水线的下一个阶段。

2. D - Decode（译码阶段）

功能：解码指令并读取操作数。
操作：处理器解析指令，确定操作类型（如加法、存储等）。同时，读取所需的寄存器中的数据。
解释：在这一阶段，处理器确定该指令需要哪些寄存器和哪些操作，并准备好输入给算术逻辑单元（ALU）等组件。数据路径上的寄存器读取也发生在这一阶段。

3. C - Execute（执行阶段）

功能：执行指令指定的操作。
操作：在算术逻辑单元（ALU）或其他功能单元中执行操作。例如，如果是加法指令，ALU 将执行加法运算；如果是内存访问指令，ALU 将计算访问的地址。
解释：这一阶段是指令实际执行计算的过程，例如运算、地址计算等。

4. M - Memory Access（内存访问阶段）

功能：访问内存（如果需要）。
操作：如果指令需要从内存读取或写入数据（例如 Load 或 Store 指令），那么在这个阶段会发生内存操作。
解释：对于 Load 和 Store 指令，这一阶段涉及到访问内存。Load 指令会从内存中读取数据，Store 指令会将数据写入内存。

5. W - Write Back（写回阶段）

功能：将执行结果写回寄存器。
操作：在这一阶段，指令的结果（如算术运算结果或从内存加载的数据）将被写入寄存器。
解释：这是指令执行的最后一个阶段。计算结果或内存数据将被存储到寄存器中，以供后续的指令使用。

总结

每个字母代表流水线中的一个阶段，五个阶段依次进行。每个指令从 F 阶段开始，逐步通过 D, C, M, 最后到 W 阶段，最终完成执行。流水线处理器通过并行处理多条指令，提升处理效率。每个阶段同时处理不同指令的不同部分，从而在同一时刻多个指令的不同阶段可以并行进行，显著提高了处理器的吞吐量。

流水线工作原理简要总结：

F (Fetch)：取指令
D (Decode)：译码并准备操作数
C (Execute)：执行操作
M (Memory)：访问内存（如有必要）
W (Write)：将结果写回寄存器

流水线问题（Pipeline Issues）

1. 数据依赖（Data Dependency）

描述：考虑两条指令 $ I_j $ 和 $ I_{j+1} $，其中指令 $ I_j $ 的目的寄存器是指令 $ I_{j+1} $ 的源操作数寄存器。
问题：这种依赖关系可能导致数据不在预期时间内可用，导致流水线停顿或延迟。

2. 流水线停顿（Hazard）

定义：任何导致流水线停顿的情况都被称为“hazard”。
- 三种类型的hazard：
1. 数据hazard（Data Hazard）
  - 描述：指令的源操作数或目的操作数在流水线中的预期时间内不可用，导致需要延迟操作，流水线因此停顿。
  - 举例：如果指令 $ I_j $ 的目的寄存器是 $ I_{j+1} $ 的源操作数，那么 $ I_{j+1} $ 就需要等待 $ I_j $ 完成。
2. 指令（控制）hazard（Instruction/Control Hazard）
  - 描述：指令的可用性延迟导致流水线停顿。
  - 举例：例如，分支指令的执行可能会导致无法提前确定下一个要执行的指令，从而需要暂停流水线，等待控制信息。
3. 结构hazard（Structural Hazard）
  - 描述：两条指令同时要求使用相同的硬件资源时发生的情况。
  - 举例：如果两条指令同时需要访问同一内存或处理器寄存器，但硬件资源不足，则会导致结构性冲突。

精华：

数据依赖、控制依赖和结构冲突是流水线中的主要hazard，它们可能导致流水线停顿或延迟。
数据hazard与操作数的可用性有关，控制hazard与指令的可执行性有关，结构hazard涉及硬件资源的竞争。

数据依赖（Data Dependency）

1. 示例：

指令：
- Add R2, R3, #100
  将 R3 与立即数 100 相加，并将结果存储到 R2 中。
- Subtract R9, R2, #30
  将 R2 与立即数 30 相减，并将结果存储到 R9 中。
数据依赖：
- Add 指令的目的寄存器 R2 是 Subtract 指令的源操作数。
- 因此，Add 指令的结果必须在 Subtract 指令执行之前可用，存在数据依赖。
非流水线数据通路：
- 在非流水线的执行路径中，R2 的值在 Add 完成后才会更新，因此 Subtract 可以在 Add 完成之后使用 R2 中的新值。

2. 流水线中的停顿（Stalling the Pipeline）

流水线执行：
- 在流水线执行中，Add 指令的结果仍未更新到 R2，当 Subtract 指令进入解码阶段时，R2 中仍然保存的是旧值。
- 因此，必须在解码阶段暂停 Subtract 指令 3 个周期，直到新的 R2 值可用。
结果：
- 在第 6 个周期，R2 中的新值会变得可用，Substract 可以继续执行。

3. 停顿流水线的细节

控制电路的作用：
- 控制电路必须在 Subtract 指令解码阶段（第 3 个周期）识别到数据依赖。
阶段间缓冲区（Interstage Buffers）：
- 缓冲区携带源寄存器和目的寄存器的标识符。
- 在第 3 个周期，控制电路会将 Compute 阶段的目标寄存器与 Decode 阶段的源寄存器进行比较。
识别依赖：
- 如果 R2 匹配，Substract 指令会被保留在 Decode 阶段，而 Add 指令会继续执行。

精华：

数据依赖会导致流水线停顿，必须通过控制电路识别依赖并适当延迟相关指令的执行。
流水线停顿：当一个指令的源操作数来自于前一个尚未完成的指令时，流水线会暂停一段时间，直到源操作数可用。

操作数转发（Operand Forwarding）

1. 操作数转发的作用

目的：
- 操作数转发通过将依赖关系中的数据直接传递给需要的指令，从而避免了流水线停顿的惩罚。
示例：
- 在前述指令序列中，R2 的新值在第 3 个周期结束时变得可用。
- 通过操作数转发，将该新值在第 4 个周期传递给 Subtract 指令，而无需等待流水线停顿。

2. 硬件实现细节

引入多路复用器（Multiplexers）：
- 在 ALU 输入之前引入多路复用器（MUX），使得寄存器 RZ 中的内容（即转发的值）可以直接作为输入传递给 ALU。
控制电路的工作：
- 控制电路在第 4 个周期识别到数据依赖（即在 Subtract 指令处于计算阶段时），并在 Compare 阶段对比 Add 指令在 Memory 阶段的目标寄存器与 Subtract 指令在 Compute 阶段的源寄存器。
流水线缓冲区的作用：
- 各阶段间的缓冲区仍然保存寄存器标识符，以便在不同阶段进行比较和判断。
多路复用器控制：
- 根据比较结果设置多路复用器的控制信号，从而将 Add 指令的结果转发给 Subtract 指令。

精华：

操作数转发通过将计算结果直接传递给依赖该数据的指令，从而避免了流水线的停顿，提高了指令执行的效率。
硬件实现包括使用多路复用器（MUX）和控制电路来识别并解决数据依赖问题。

操作数转发扩展（Extension of Operand Forwarding）

1. 扩展操作数转发

操作数转发不仅限于 R2，还可以扩展到其他寄存器的结果，例如寄存器 RY。
这样可以处理像下面这样涉及数据依赖的指令序列：
- Add R2, R3, #100
  将 R3 和立即数 100 相加，结果存入 R2。
- Or R4, R5, R6
  将 R5 和 R6 进行按位或运算，结果存入 R4。
- Subtract R9, R2, #30
  将 R2 和立即数 30 相减，结果存入 R9。
数据依赖：
- 上述指令序列中的 Subtract 指令依赖于 Add 指令的结果（即 R2 的值），因此需要进行操作数转发。

2. 硬件实现细节

转发到需要的地方：
- 在第 5 个周期，操作数转发将 Add 指令的结果传递给 Subtract 指令，以便 Subtract 能够在没有停顿的情况下继续执行。
执行过程：
- 当 Subtract 在周期 5 中进行时，控制电路将识别到对 R2 的依赖，并通过转发机制将 Add 的结果提供给 Subtract，避免了流水线停顿。

精华：

操作数转发扩展：通过扩展转发机制，不仅解决了 R2 的依赖问题，还可以应用于其他寄存器，进一步提高流水线的效率。
这种扩展可以在多个阶段同时处理不同指令的依赖关系，从而减少停顿时间，提高处理速度。

软件处理依赖（Software Handling of Dependencies）

1. 编译器生成与分析指令

编译器可以生成并分析指令序列，以识别数据依赖关系。
数据依赖通常通过寄存器之间的关系显现出来，编译器可以通过识别这些依赖来优化指令顺序。

2. 插入 NOP 指令

为了处理数据依赖，编译器可以在存在依赖关系的指令之间插入 NOP（无操作） 指令。
NOP 指令 作为延迟指令，确保在依赖的指令中使用的新值能够在寄存器中可用，从而避免数据冲突。
影响：
- 插入的 NOP 指令会增加总的执行时间，因为这些指令不会做任何实际工作，只是为了保证数据依赖得到满足。

3. 优化策略

编译器可以通过 指令重排 来优化程序：
- 如果存在数据依赖，编译器可以将一些不依赖于当前数据的指令移动到 NOP 指令的位置，以减少不必要的等待时间。
- 这样，尽管有依赖，程序的整体执行效率会有所提高。

总结：

软件处理依赖：通过编译器插入 NOP 指令来处理数据依赖，尽管这样会增加执行时间，但可以确保正确执行。
优化方法：编译器通过调整指令顺序，避免不必要的等待，提升程序执行效率。

内存延迟（Memory Delays）

1. 内存延迟可能导致流水线停顿

内存访问延迟：当流水线中的指令需要访问内存时，内存延迟可能会导致流水线停顿。
缓存的作用：
- 缓存（Cache）能够存储来自主内存的指令和数据，并且访问速度比主内存快。
- 在缓存命中时，内存访问时间通常是 1 个周期。

2. 缓存未命中导致的延迟

如果发生 缓存未命中（cache miss），则需要访问速度较慢的主内存，这会导致较长的延迟。
在流水线中，如果一个指令的内存访问存在延迟，后续的指令也会受到影响，导致它们被延迟执行。

3. 即使缓存命中，Load 指令仍可能导致短暂的延迟

即使是 缓存命中，Load 指令也可能由于数据依赖关系导致短暂的延迟。
- 数据依赖：Load 指令从内存加载数据，并将其存入寄存器。如果后续指令依赖于这个数据，它们需要等待加载的结果。
- 1 周期停顿：为了确保正确的值被转发到需要它的指令，可能需要插入 1 个周期的停顿。

4. 优化策略

填充延迟：为了优化流水线的效率，可以在延迟周期期间插入其他有用的指令，这样可以减少由于延迟造成的空闲周期。

总结：

内存延迟：缓存未命中或数据依赖会导致流水线停顿，影响处理速度。
优化方法：可以使用缓存来减少访问延迟，并通过插入有用的指令来填充延迟周期，从而提高流水线的效率。

资源限制（Resource Limitations）

1. 资源争用

两条指令可能需要在同一个时钟周期访问相同的硬件资源。
这种情况下，需要暂停一条指令，以便另一条指令可以使用该资源。
通过增加硬件资源，可以避免这种资源争用和停顿。

2. 例子：取指阶段与存储阶段

假设 取指阶段（Fetch）和 内存阶段（Memory）都需要访问缓存（cache）：
- 取指阶段：在每个周期都需要访问缓存来获取指令。
- 内存阶段：当有 Load 或 Store 指令需要访问缓存时，会发生资源争用。
- 为了避免这种争用，需要在一个周期内停顿，直到资源可用。

3. 解决方案：分离指令缓存与数据缓存

为了解决资源争用问题，可以使用 指令缓存 和 数据缓存：
- 指令缓存（I-Cache）用于存储指令。
- 数据缓存（D-Cache）用于存储数据。
- 这样，取指阶段 和 内存阶段 可以同时进行而不发生停顿，因为它们分别访问不同的缓存。

精华：

资源限制：多个指令争用相同的硬件资源时，可能导致流水线停顿。
解决方法：通过增加硬件资源（如分离的指令缓存和数据缓存）来避免资源争用，从而减少停顿。

分支延迟（Branch Delays）

1. 理想的流水线（Ideal Pipelining）

在理想的流水线中，每个新指令的获取（Fetch）应该与前一条指令的解码（Decode）阶段重叠进行。

2. 分支指令的影响

分支指令（Branch instructions）会改变程序的执行顺序，因此必须处理这些指令来确定：
- 是否跳转（Whether to branch）
- 跳转的位置（Where to branch）

3. 分支延迟的影响

分支结果的确定延迟：分支指令需要一些时间来决定是否跳转以及跳转到哪里。
- 如果分支结果的确定存在延迟，会导致总执行时间的增加。

总结：

分支延迟：分支指令的处理延迟会增加流水线的执行时间，影响整体性能。
解决方法：减少分支指令的延迟，例如通过预测分支结果或延迟处理等技术来提高流水线效率。

无条件分支（Unconditional Branches）

1. 分支指令的影响

假设有一系列指令：$ I_j $**, **$ I_{j+1} $**, **$ I_{j+2} $**，其中 **$ I_j $** 是一个无条件分支指令，它的目标是 **$ I_k $。
在 第5章 中，计算阶段（Compute）根据偏移量和更新后的程序计数器（PC）计算目标地址。

2. 流水线中的情况

在流水线中，$ I_j $** 指令的目标地址 **$ I_k $** 在 **$ I_j $ 的 第4周期时已知。
然而，指令 $ I_{j+1} $** 和 **$ I_{j+2} $ 分别在 第2周期 和 第3周期 已经被取指（fetch）了。

3. 处理无条件分支

$ I_j $** 指令的目标 **$ I_k $** 应该紧跟 **$ I_j $** 执行。因此，必须丢弃已经获取的 **$ I_{j+1} $** 和 **$ I_{j+2} $，并且会产生 两个周期的分支惩罚。

总结：

无条件分支延迟：无条件分支指令的目标在分支发生后才被确定，因此流水线必须丢弃已经获取的指令 $ I_{j+1} $** 和 **$ I_{j+2} $，并产生额外的周期惩罚。

减少分支惩罚（Reducing the Branch Penalty）

1. 提早计算分支目标地址

需要在流水线中更早地计算分支目标地址。
将目标地址的计算和程序计数器（PC）的更新移至解码阶段（Decode），而不是计算阶段（Compute）。
为了实现这一点，在解码阶段增加一个专门用于分支的第二个加法器。

2. 减少分支惩罚

在上述优化后，$ I_j+1 $ 指令会在 第2周期 被取指。
只有一条指令（$ I_{j+1} $）需要丢弃。
这样，分支惩罚减少为 一个周期。

总结：

通过在解码阶段计算分支目标地址，可以减少分支指令的惩罚周期，将惩罚从两个周期减少为一个周期。

条件分支（Conditional Branches）

1. 条件分支指令的考虑

以条件分支指令为例：
- Branch_if_[R5] = [R6] LOOP
- 该指令不仅需要计算目标地址，还需要进行条件比较。

2. 目标地址和条件比较

在之前的计算阶段（Chapter 5），是通过ALU来执行比较操作的。
现在，目标地址将在解码阶段（Decode）计算。

3. 减少分支惩罚

为了保持一个周期的惩罚，引入一个专门用于分支的比较器，该比较器位于解码阶段（Decode）。

总结：

对于条件分支指令，我们通过在解码阶段增加比较器来同时计算目标地址和进行条件判断，从而避免增加额外的惩罚周期。

分支延迟槽（The Branch Delay Slot）

1. 分支决策和目标地址

假设分支决策和目标地址在流水线的解码阶段（Decode）中都已确定。
无论分支是否执行，分支指令后面的指令始终会被取指。
如果分支被执行（跳转），紧随其后的指令会被丢弃，并产生惩罚周期；但如果条件分支未执行，则不丢弃。

2. 分支延迟槽

紧跟分支指令后的指令位置被称为分支延迟槽（Branch Delay Slot）。

3. 延迟分支（Delayed Branching）

为了优化延迟槽的使用，可以将分支指令延迟槽中的指令执行完毕，而不是条件丢弃。
编译器可以将数据依赖允许的情况下，调整指令顺序，将有用的指令移动到延迟槽。
这种方法称为延迟分支，通过重新排序指令来避免不必要的延迟。

4. 延迟槽优化

如果在延迟槽中放置的是有用的指令，分支惩罚为 零周期。
如果无法避免延迟槽的空白，则插入一个显式的NOP指令，以在延迟槽中消耗一个周期的惩罚。

总结：

分支延迟槽是为了利用分支指令后面紧跟的指令空间，通过重排序或填充有效指令来避免额外的惩罚周期。

Quiz

Quiz (1) ：

问题：

______ 是一种情况，管道因某些原因被暂停，因为要操作的数据被延迟。或者：______ 是任何情况下，在管道中，指令的源操作数或目标操作数在预期时间不可用。

选项：

A. 控制危害（control hazard）
B. 数据危害（data hazard）
C. 结构危害（structural hazard）
D. 指令危害（instruction hazard）

正确答案：

B. 数据危害（data hazard）

解释：

数据危害（Data Hazard）是指指令的源操作数或目标操作数在预期的时间点不可用，导致管道被暂停。

Quiz (2) ：

问题：

关于管道中的数据依赖，以下哪项不正确？

选项：

A. 操作数转发可以处理所有数据依赖，而无需暂停管道。
B. 编译器可以通过分析指令来检测数据依赖并进行处理。
C. 编译器在有依赖的指令之间插入显式的NOP指令。
D. 即使有缓存命中和操作数转发，“Load R2, (R3)”和“Subtract R9, R2, #30”之间的数据依赖仍会导致一个周期的停顿。

正确答案：

A. 操作数转发可以处理所有数据依赖，而无需暂停管道。

解释：

A项不正确，因为操作数转发虽然可以缓解数据依赖问题，但并不能处理所有的情况，某些情况下（例如缓存未命中或存在复杂的依赖关系）仍可能需要暂停管道。
B项正确，编译器可以通过分析指令来检测数据依赖并采取相应的措施。
C项正确，编译器可以在有数据依赖的指令之间插入显式的NOP（无操作）指令来避免冲突。
D项正确，即使在缓存命中和操作数转发的情况下，某些数据依赖仍然可能导致管道停顿，像在加载和减法操作之间的数据依赖。

Quiz (3) ：

问题 1：

识别下述指令序列中的所有数据依赖关系。对于每个依赖关系，指出涉及的两条指令以及造成依赖的寄存器。

指令序列：

Load R1, 4(R2)
Sub R4, R1, R5
And R6, R1, R7
Or R8, R3, R4

数据依赖关系：

Sub 指令依赖于 Load 指令，因为 Sub 指令需要使用 Load 指令将值存储到 R1 寄存器中的数据。
And 指令依赖于 Load 指令，因为 And 指令也需要使用 Load 指令将值存储到 R1 寄存器中的数据。
Or 指令依赖于 Sub 指令，因为 Or 指令需要使用 Sub 指令将结果存储到 R4 寄存器中的数据。

问题 2：

假设管道不使用操作数转发。假设管道停顿只由数据危险（Data Hazards）引起。绘制图表表示每个时钟周期中的指令流。

没有操作数转发时，管道停顿图示：

问题 3：

假设管道使用操作数转发。管道硬件与图 2 类似，但增加了从第 3 阶段和第 4 阶段的输出到第 3 阶段输入的独立转发路径。绘制图表表示在每个时钟周期中，指令流通过管道的情况。通过箭头标示操作数转发。

使用操作数转发时，管道流动图示：