第九章 指令流水线
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.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