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

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

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

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

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

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

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

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

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

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

图9-1：MIPS五级指令流水线示意图

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

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

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

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

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

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

假设有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个周期是流水线的排空阶段

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

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

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

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

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

解决方法：

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

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

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

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

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

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

数据依赖的类型：

真数据依赖（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之间插入不相关的指令

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

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

控制冒险的解决方法：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

数据通路的主要部件： - 程序计数器（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结果 或 存储器数据 写回寄存器堆 ```

前递条件判断： 前递需要满足以下条件： 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

```

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