====== 第九章 指令流水线 ======

===== 9.1 流水线技术概述 =====

==== 9.1.1 流水线的基本概念 ====

流水线（Pipeline）技术是将一个复杂的操作分解为若干个子操作，每个子操作由专门的硬件完成，多个操作的不同子操作在时间上重叠执行，从而提高系统吞吐率的技术。

**流水线的基本原理**：
类似于工厂中的装配线，将一个复杂任务分解为若干个顺序执行的子任务，每个子任务由专门的部件完成。当流水线填满后，每隔一个时间间隔就有一个任务完成，理想情况下吞吐率提高了n倍（n为流水线级数）。

**流水线的时空图**：
流水线的执行过程可以用时空图表示，横轴表示时间，纵轴表示流水线的各段。通过时空图可以直观地看到各个任务在流水线上的流动过程。

==== 9.1.2 流水线的分类 ====

根据流水线处理的对象和级别，可以将流水线分为以下几类：

**部件级流水线（操作流水线）**：
将复杂的运算操作（如浮点运算）分解为多个子操作，如求阶差、对阶、尾数运算、规格化等。典型的例子是浮点运算流水线。

**处理器级流水线（指令流水线）**：
将指令的执行过程分解为多个阶段，如取指、译码、执行、访存、写回等。这是现代CPU中最常见的流水线形式。

**系统级流水线（宏流水线）**：
由多个处理器串联组成，每个处理器完成整个任务的一部分。例如，在图像处理中，一个处理器负责读取数据，一个负责处理，一个负责输出。

==== 9.1.3 流水线的性能指标 ====

**吞吐率（Throughput）**：
单位时间内流水线能完成的任务数。是衡量流水线性能的主要指标。
- 最大吞吐率：流水线达到稳定状态后的吞吐率，理想情况下等于1/Δt（Δt为时钟周期）
- 实际吞吐率：考虑装入和排空时间后的平均吞吐率

**加速比（Speedup）**：
顺序执行时间与流水线执行时间的比值。
```
S = 顺序执行时间 / 流水线执行时间
```
理想情况下，n级流水线的加速比为n。

**效率（Efficiency）**：
流水线的设备利用率，即实际使用时间与总时间的比值。
```
E = 加速比 / 流水线级数 = S / n
```
理想情况下，效率为100%。

**图9-1：MIPS五级指令流水线示意图**
{{https://upload.wikimedia.org/wikipedia/commons/thumb/2/27/Pipeline_MIPS.png/800px-Pipeline_MIPS.png?direct|MIPS五级流水线|500}}

===== 9.2 指令流水线的工作原理 =====

==== 9.2.1 指令流水线的基本阶段 ====

经典的MIPS五级指令流水线包括以下阶段：

**IF段（Instruction Fetch，取指）**：
- 根据PC中的地址从指令存储器读取指令
- PC值增加，指向下一条指令
- 将取出的指令送入IR

**ID段（Instruction Decode，译码/读寄存器）**：
- 对指令进行译码，确定操作类型
- 从寄存器堆读取源操作数
- 对于分支指令，计算目标地址并进行分支预测

**EX段（Execute，执行/计算地址）**：
- ALU执行算术或逻辑运算
- 计算存储器有效地址
- 比较操作数，确定分支是否成立

**MEM段（Memory Access，访存）**：
- 对于Load指令，从数据存储器读取数据
- 对于Store指令，将数据写入数据存储器
- 其他指令在此段空闲

**WB段（Write Back，写回）**：
- 将结果写回寄存器堆
- 结果可能来自ALU（ALU指令）或存储器（Load指令）

==== 9.2.2 指令流水线的时空图 ====

假设有5条指令连续执行，时空图如下：

```
时钟周期：  1    2    3    4    5    6    7    8    9
指令1      IF   ID   EX   MEM  WB
指令2           IF   ID   EX   MEM  WB
指令3                IF   ID   EX   MEM  WB
指令4                     IF   ID   EX   MEM  WB
指令5                          IF   ID   EX   MEM  WB
```

从时空图可以看出：
- 第1-4个周期是流水线的装入阶段
- 第5个周期开始流水线满载，每个周期完成一条指令
- 第9个周期是流水线的排空阶段

==== 9.2.3 流水线寄存器的作用 ====

为了保证各段能够独立工作并在正确的时钟沿传递数据，需要在流水段之间设置流水线寄存器（也称为流水线锁存器或流水线缓冲器）。

流水线寄存器的作用：
- **数据缓冲**：保存前一阶段产生的结果，供下一阶段使用
- **隔离阶段**：使各阶段可以独立操作，互不干扰
- **同步控制**：在时钟边沿同步传递数据

流水线寄存器的开销：
- **时间开销**：寄存器本身的传输延迟（建立时间和传播延迟）
- **空间开销**：需要额外的寄存器硬件
- **时钟周期限制**：时钟周期必须大于最慢流水段的执行时间加上寄存器延迟

===== 9.3 流水线冒险及其处理 =====

==== 9.3.1 结构冒险 ====

**定义**：结构冒险是由于硬件资源冲突引起的，多条指令需要使用同一硬件资源。

**常见原因**：
- 存储器冲突：取指和数据访问同时使用存储器
- 功能部件冲突：多条指令需要使用同一个ALU
- 寄存器端口冲突：同时读写的寄存器端口不足

**解决方法**：

**资源重复**：
- 使用哈佛结构，分离指令存储器和数据存储器
- 增加功能部件的数量
- 增加寄存器堆的读写端口

**流水线停顿（插入气泡）**：
当资源冲突时，让后面的指令等待一个周期。

【例题】分析以下代码在单端口存储器中的结构冒险：
```
LOAD R1, 0(R2)    ;需要从存储器读取数据
ADD  R3, R4, R5   ;需要取指令
```

分析：
- 时钟周期3：LOAD指令进入MEM段，需要访问数据存储器
- 同时ADD指令进入IF段，需要访问指令存储器
- 如果指令和数据共享同一个存储器，就会发生结构冒险

解决：
- 使用双端口存储器
- 或者在MEM段停顿ADD指令一个周期（插入气泡）

==== 9.3.2 数据冒险 ====

**定义**：数据冒险是由于指令之间存在数据依赖关系，后续指令需要使用前面指令产生的结果，但结果还未准备好。

**数据依赖的类型**：

**真数据依赖（RAW，Read After Write）**：
后续指令读取前面指令写入的位置。
```
ADD R1, R2, R3    ;写入R1
SUB R4, R1, R5    ;读取R1（RAW依赖）
```

**反依赖（WAR，Write After Read）**：
后续指令写入前面指令读取的位置。
```
ADD R2, R3, R4    ;读取R4
SUB R4, R5, R6    ;写入R4（WAR依赖）
```

**输出依赖（WAW，Write After Write）**：
两条指令写入同一位置。
```
ADD R1, R2, R3    ;写入R1
SUB R1, R4, R5    ;写入R1（WAW依赖）
```

在简单的五级流水线中，只有RAW依赖会导致数据冒险，WAR和WAW冒险只在乱序执行时出现。

**数据冒险的类型**：

**RAW冒险的三种情况**：

EX到1st冒险：前一条指令在EX段产生结果，下一条指令在EX段需要使用
```
ADD R1, R2, R3    ;EX段产生结果
SUB R4, R1, R5    ;下一条指令EX段需要R1
```

MEM到1st冒险：前一条指令在MEM段产生结果，下一条指令在EX段需要使用
```
LOAD R1, 0(R2)    ;MEM段读取数据
ADD R4, R1, R5    ;下一条指令EX段需要R1
```

MEM到2nd冒险：前一条指令在MEM段产生结果，隔一条指令在EX段需要使用
```
LOAD R1, 0(R2)    ;MEM段读取数据
ADD R3, R4, R5    ;不相关指令
ADD R6, R1, R7    ;隔一条指令EX段需要R1
```

**数据冒险的解决方法**：

**数据前递（Forwarding/Bypassing）**：
将ALU计算结果或存储器读取的数据直接传送给需要它的指令，而不等待写回寄存器堆。

前递路径：
- EX/MEM寄存器 → ALU输入（EX到1st）
- MEM/WB寄存器 → ALU输入（MEM到1st、MEM到2nd）

**停顿（Stall）**：
当无法使用前递解决冒险时，需要停顿流水线等待数据就绪。

最典型的需要停顿的情况是Load-Use冒险：
```
LOAD R1, 0(R2)    ;MEM段才能读取数据
ADD R4, R1, R5    ;下一条指令EX段需要R1
```

由于Load指令的数据在MEM段末才可用，而ADD指令在EX段初就需要数据，即使使用前递也需要停顿一个周期。

【例题】分析以下代码的数据冒险及解决方法：
```
ADD R1, R2, R3
SUB R4, R1, R5
AND R6, R1, R7
OR R8, R1, R9
```

解：
1. SUB指令与ADD指令：RAW依赖（R1），EX到1st冒险，可以通过前递解决
2. AND指令与ADD指令：RAW依赖（R1），MEM到1st冒险，可以通过前递解决
3. OR指令与ADD指令：RAW依赖（R1），MEM到2nd冒险，可以通过前递解决

不需要停顿。

【例题】分析以下代码的数据冒险及解决方法：
```
LOAD R1, 0(R2)
ADD R4, R1, R5
SUB R6, R7, R8
```

解：
ADD指令与LOAD指令之间存在RAW依赖（R1），这是Load-Use冒险。
- LOAD指令在MEM段读取数据
- ADD指令在EX段需要数据
即使使用前递，数据也需要从MEM段传递到EX段，存在时间差。

解决方案：
- 停顿一个周期：在ADD指令的ID段插入一个气泡
- 编译器调度：在LOAD和ADD之间插入不相关的指令

==== 9.3.3 控制冒险 ====

**定义**：控制冒险是由于分支指令和跳转指令改变了程序执行的顺序，导致流水线中预取的指令无效。

**分支指令的影响**：
在条件分支指令中，条件判断在EX段完成，而后续指令已经取入流水线。如果分支成立，这些预取的指令需要被取消。

**控制冒险的解决方法**：

**冻结流水线（Flush）**：
在分支指令的结果确定之前，暂停取指，或者取指后如果分支成立则取消已取指令。

**预测不分支（Predict Not Taken）**：
假设分支条件不成立，继续按顺序取指。
- 如果预测正确：没有延迟
- 如果预测错误：取消已取指令，重新从分支目标取指，延迟2-3个周期

**预测分支（Predict Taken）**：
假设分支条件成立，从分支目标地址取指。
- 需要提前知道分支目标地址（ID段计算）
- 如果预测正确：没有延迟（或1个周期延迟）
- 如果预测错误：取消已取指令，重新取指

**延迟分支（Delayed Branch）**：
在分支指令后安排一条必定执行的指令（延迟槽），无论分支是否成立，这条指令都会执行。
```
BEQ R1, R2, LABEL
ADD R3, R4, R5    ;延迟槽指令，无论分支是否成立都会执行
```
编译器的任务是在延迟槽中放入有用的指令。

**动态分支预测**：
使用分支预测器预测分支的结果。
- 一位预测器：根据上一次执行结果预测
- 两位预测器：有四种状态（强不取、弱不取、弱取、强取），减少预测翻转
- 分支目标缓冲器（BTB）：缓存分支指令的地址和目标地址，以及历史信息

===== 9.4 高级流水线技术 =====

==== 9.4.1 超标量流水线 ====

**基本概念**：
超标量处理器是指每个时钟周期可以发射和执行多条指令的处理器。与之相对的是标量处理器，每个周期最多发射一条指令。

**超标量处理器的特点**：
- 有多条独立的执行流水线
- 需要多个功能部件（ALU、浮点单元、访存单元等）
- 需要动态调度技术处理数据冒险
- 能够开发指令级并行性（ILP）

**发射策略**：
- **顺序发射顺序执行**：简单但效率低
- **顺序发射乱序执行**：发射顺序保持程序顺序，但执行和完成可以乱序
- **乱序发射乱序执行**：最高效但最复杂

**动态调度技术**：
使用保留站（Reservation Station）和重排序缓冲区（ROB）实现乱序执行：
- 指令发射时进入保留站等待操作数
- 操作数就绪后立即执行（乱序执行）
- 结果写入重排序缓冲区
- 按程序顺序提交结果（精确中断）

==== 9.4.2 超长指令字（VLIW） ====

**基本概念**：
VLIW处理器将多条独立的指令打包成一个超长指令字，同时发射和执行。

**VLIW与超标量的区别**：
- 超标量：硬件负责找出可以并行执行的指令
- VLIW：编译器负责找出可以并行执行的指令，打包成VLIW

**VLIW的优点**：
- 硬件简单，不需要复杂的调度逻辑
- 功耗低，适合嵌入式系统

**VLIW的缺点**：
- 代码兼容性差，不同宽度的VLIW处理器需要重新编译
- 存在代码膨胀问题
- 当无法填满VLIW时，需要插入NOP，降低效率

==== 9.4.3 多线程技术 =====

**细粒度多线程（Fine-Grained Multithreading）**：
每个时钟周期切换线程，隐藏长延迟操作的影响。
- 优点：可以隐藏流水线延迟
- 缺点：单个线程的执行速度下降

**粗粒度多线程（Coarse-Grained Multithreading）**：
只在发生长延迟事件（如Cache不命中）时切换线程。
- 优点：单个线程执行效率较高
- 缺点：不能隐藏短延迟操作

**同时多线程（SMT，Simultaneous Multithreading）**：
在一个周期内从多个线程中各取指令，混合发射。
- 超线程技术（Hyper-Threading）就是SMT的实现
- 可以充分利用超标量处理器的资源

===== 9.5 流水线处理器设计实例 =====

==== 9.5.1 简单流水线数据通路设计 ====

**数据通路的主要部件**：
- 程序计数器（PC）
- 指令存储器
- 寄存器堆
- ALU
- 数据存储器
- 流水线寄存器（IF/ID, ID/EX, EX/MEM, MEM/WB）

**各段数据通路**：

**IF段**：
```
PC → 指令存储器 → 指令
     ↓
    PC+4 → PC（分支时不适用）
```

**ID段**：
```
指令 → 译码 → 控制信号
    → 寄存器地址 → 寄存器堆 → 数据1、数据2
    → 立即数扩展
```

**EX段**：
```
ALU根据ALUOp执行运算
数据源：寄存器数据、立即数、PC+4（分支计算）
```

**MEM段**：
```
数据存储器访问（Load/Store）
分支判断：如果分支成立，更新PC
```

**WB段**：
```
结果选择：ALU结果 或 存储器数据
写回寄存器堆
```

==== 9.5.2 前递单元设计 ====

**前递条件判断**：
前递需要满足以下条件：
1. 前一条指令的目标寄存器与后一条指令的源寄存器相同
2. 前一条指令确实要写入寄存器（不是Store或分支）
3. 目标寄存器不是R0（如果R0恒为0）

**前递路径控制**：
```
if (EX/MEM.RegWrite && EX/MEM.Rd != 0 && EX/MEM.Rd == ID/EX.Rs)
    ForwardA = 10    ;从EX/MEM前递到ALU输入A

if (EX/MEM.RegWrite && EX/MEM.Rd != 0 && EX/MEM.Rd == ID/EX.Rt)
    ForwardB = 10    ;从EX/MEM前递到ALU输入B

if (MEM/WB.RegWrite && MEM/WB.Rd != 0 && MEM/WB.Rd == ID/EX.Rs)
    ForwardA = 01    ;从MEM/WB前递到ALU输入A

if (MEM/WB.RegWrite && MEM/WB.Rd != 0 && MEM/WB.Rd == ID/EX.Rt)
    ForwardB = 01    ;从MEM/WB前递到ALU输入B
```

==== 9.5.3 冒险检测单元设计 ====

**Load-Use冒险检测**：
```
if (ID/EX.MemRead && 
    ((ID/EX.Rt == IF/ID.Rs) || (ID/EX.Rt == IF/ID.Rt)))
    // 检测到Load-Use冒险
    Stall = 1
    // 停顿IF和ID段，插入气泡到EX段
```

**分支冒险处理**：
```
// 分支在MEM段判断
if (分支条件成立)
    Flush IF/ID, ID/EX    ;取消已取的错误指令
    PC = 分支目标地址
```

===== 9.6 流水线性能分析 =====

==== 9.6.1 CPI计算 ====

**理想CPI**：
在理想的流水线中，CPI（每条指令的时钟周期数）为1。

**实际CPI**：
```
实际CPI = 理想CPI + 停顿周期数/指令数
```

**各种因素对CPI的影响**：
- Load-Use冒险：增加0.5-1个周期（取决于停顿策略）
- 分支预测错误：增加2-3个周期（取决于流水线深度）
- Cache不命中：增加10-100个周期（取决于存储器层次）

==== 9.6.2 流水线性能公式 ====

**程序执行时间**：
```
执行时间 = 指令数 × CPI × 时钟周期
```

**流水线加速比**：
```
加速比 = 顺序执行时间 / 流水线执行时间
       = (指令数 × 顺序CPI × 时钟周期) / (指令数 × 流水线CPI × 时钟周期')
```

假设顺序CPI等于流水线级数k，时钟周期相同：
```
加速比 ≈ k / 流水线CPI
```

【例题】某流水线处理器执行一个程序，程序包含1000条指令。已知：
- Load指令占20%，其中50%会引起Load-Use停顿
- 分支指令占15%，预测准确率90%
- 分支预测错误惩罚为2个周期
- Load-Use停顿为1个周期

计算实际CPI。

解：
基础CPI = 1
Load-Use停顿贡献 = 0.20 × 0.50 × 1 = 0.10
分支预测错误贡献 = 0.15 × 0.10 × 2 = 0.03

实际CPI = 1 + 0.10 + 0.03 = 1.13

==== 9.6.3 提高流水线性能的方法 ====

**减少数据冒险**：
- 优化编译器，在Load和Use之间插入不相关指令
- 使用更多的寄存器，减少数据依赖
- 改进前递路径设计

**减少控制冒险**：
- 改进分支预测算法
- 使用延迟分支技术
- 减少分支指令（使用条件移动指令代替短分支）

**减少结构冒险**：
- 资源复制
- 分离的指令和数据存储器（哈佛结构）

**增加流水线深度**：
- 更深的流水线可以缩短时钟周期
- 但会增加冒险的惩罚，收益递减

===== 9.7 本章重点总结 =====

**核心概念**：
- 流水线通过时间重叠提高指令执行效率
- 指令流水线将指令执行分为IF、ID、EX、MEM、WB五个阶段
- 流水线冒险包括结构冒险、数据冒险和控制冒险

**流水线性能**：
- 理想吞吐率：每个周期完成一条指令
- 实际CPI = 1 + 停顿造成的额外周期
- 加速比 = 顺序执行时间 / 流水线执行时间

**数据冒险处理**：
- RAW依赖是主要问题
- 前递（Forwarding）可以解决大部分数据冒险
- Load-Use冒险需要停顿一个周期

**控制冒险处理**：
- 预测不分支/预测分支
- 延迟分支
- 动态分支预测（BTB、两位预测器）

**高级技术**：
- 超标量：每周期发射多条指令
- VLIW：编译器打包并行指令
- 多线程：通过线程切换隐藏延迟

**设计要点**：
- 流水线寄存器用于段间数据传递和同步
- 前递单元检测数据依赖并控制数据通路
- 冒险检测单元控制流水线停顿

**重要计算**：
- CPI = 1 + Σ(停顿频率 × 停顿周期)
- 加速比与流水线级数和CPI有关
- 流水线效率 = 实际吞吐率 / 最大吞吐率

**学习建议**：
- 熟练掌握流水线时空图的画法
- 能够识别各种类型的数据冒险
- 理解前递路径的设计原理
- 会计算各种情况下的CPI