第三章 高级流水线与指令级并行 石教英
内容提要及与各节的关系 (1) 流水线技术就是指令重叠执行技术, 达到加快运算速度的目的 由于存在三种流水线竞争 : 结构竞争 数据竞争 控制竞争, 导致流水线性能降低, 不能运作在理想的重叠状态, 需要插入停顿周期, 从而使流水线性能降低 --3.1 流水线技术基础
内容提要及与各节的关系 (2) 指令之间可重叠执行性称为指令级并行性 (Instruction Parallelism-ILP) 因此进一步研究和开发指令之间的并行性, 等于拓宽指令重叠执行的可能性, 从而能进一步提高流水线的性能 --3.2 指令级并行概念与技术
内容提要及与各节的关系 (3) 本章研究 : 针对流水线竞争的动态调度与预测技术 --3.3 流水线动态调度与预测 进一步开发指令级并行性的高级流水线技术 --3.4 进一步开发指令级并行处理的高级流水线技术
3.1 流水线技术基础 3.1.1 什么是流水线 (pipeline)(1) 流水线是实现多条指令重叠执行的技术, 是加快 CPU 执行速度的关键技术 术语 : 流水级 (pipe stage): 流水线由多个流水级组成, 通常一条指令由 n 级流水级完成 每个流水级完成指令的部分任务 吞吐量 (throughput): 单位时间内流出流水线的指令数
什么是流水线 (2) 机器周期 (machine cycle): 不同流水线完成指令功能不等, 所需时间有长有短, 因此设计流水线的关键是合理划分指令功能, 使每一流水级完成指令功能的时间大致相等 机器周期由最长流水级的时间决定, 通常等于时钟周期
什么是流水线 (3) 理想流水线的加速因子 (Speedup) 非流水线机器指令的平均执行时间 =-------------------------------- 流水线机器指令的平均执行时间 非流水线机器指令的平均执行时间 = --------------------------------- 非流水线机器指令的平均执行时间 / 流水级数 = 流水级数
3.1.2 DLX 指令的非流水线实现 (1) 本书的教学样机称为 DLX, 是一 RISC 体系结构计算机 DLX 指令的非流水线实现分五步 ( 即 5 个时钟周期 ) 完成 : 1 取指令周期 (IF) IR Mem[PC] NPC PC + 4 2 译码 / 读寄存器周期 (ID) A Reg[IR 6..10] B Reg[IR11..15] Imm ( (IR16)16## IR16..31)
DLX 指令的非流水线实现 (2) 3 执行 / 有效地址计算 (EX) Load/Store ALUoutput A+Imm R-R ALU ALUoutput A func B R-I ALU ALUoutput A op Imm Branch ALUoutput NPC + Imm; Cond A op 0
DLX 指令的非流水线实现 (3) 4 存储器访问/ 转移完成 (MEM) Load/Store: LMD Mem[ALUoutput] Mem[ALUoutput] B Branch if (Cond) then PC ALUoutput else PC NPC
DLX 指令的非流水线实现 (4) 5 写回周期 (WB) R-R ALU Regs[IR16..20] ALUoutput R-I ALU Regs[IR11..15] ALUoutput Load Regs[IR11..15] LMD
3.1.3 DLX 的基本流水线 (1) DLX 简单流水线的实现示意图 (Fig3.2; 表 4-2,p136) 指令序流水时钟数列 1 2 3 4 5 6 7 8 9 指令 i IF ID EX MEM W B 指令 i +1 IF ID EX MEM W B 指令 i +2 IF ID EX MEM W B 指令 i +3 IF ID EX MEM W B 指令 i +4 IF ID EX MEM W B
序执行序列DLX 流水线节拍与 CPU 相关硬件的时间关系图 时钟周期 CC3 CC5 CC6 CC7 CC8 CC9 程CC1 CC2 CC4 IM Reg DM Reg ALU IM Reg ALU DM Reg IM Reg ALU DM Reg IM Reg ALU DM Reg IM Reg ALU DM Reg
由图 3.3 可以看出实现流水线后, 对硬件 的要求更高了, 并需作相应的改变, 主要 有以下 2 点 : IM,DM 必须分开, 或由一双端口存储器代替 IM 和 DM; IM,DM 的带宽要提高 5 倍,( 对 DLX 的 5 级流水线而言 ) 另外, 可以发现 Branch 指令将要推迟三个节拍.
ADD 存储器DLX 流水化 CPU 中数据通路的实现图 (Fig3.4; 图 4-8, p139) 4 0? PC 数据MUX IF/ID ID/EX EX/MEM MEM/WB 转移发生 IR IR6..10 IR11..15 MEM/ WB IR 寄存器32 MUX MUX ALU 数据存储器MUX 16 Sign extend
图 3.4 中注意 : 在两个相邻节拍间增加一暂存器, 用来保留指令的状态 ( 及数据 ), 共有 IF/ID,ID/EX, EX/MEM, MEM/WB 四个.
DlX 流水线的形式化描述 (Fig.3.5, P136)
3.1.4 流水线的主要障碍 -- 流水线竞争 (pipeline hazard) 定义 : 流水线竞争是流水线中造成下一条指令不能在指令时钟周期被执行的情况.
流水线竞争 (2) 流水线竞争分三类 : 结构竞争 (structure hazard)---- 由硬件资源冲突引起 数据竞争 (data hazard)---- 下一条指令药用到上一条指令的结果. 控制竞争 (control hazard)---- 由转移指令或其他改变 PC 指令引起. 流水线竞争的后果 ---- 造成流水线停顿 几个周期, 从而降低流水线效率.
3.1.5 流水线竞争举例及其解决方法 1. 结构竞争单口存储器造成存储器访问冲突, 造成流水线停顿实例.
结构竞争 (Fig3.6; 表 4-4,p143) 指令序 流水时钟数 列 1 2 3 4 5 6 7 8 9 10 Load 指令 IF ID EX MEM WB 指令 i +1 IF ID EX MEM WB 指令 i +2 IF ID EX MEM WB 指令 i +3 stall IF ID EX MEM WB 指令 i +4 IF ID EX MEM WB 指令 i +5 IF ID EX MEM
时钟周期 CC1 CC2 CC3 CC4 CC5 CC6 CC7 CC8 Load Mem ALU Reg Mem Reg 指令 1 Mem Reg ALU Mem Reg 指令 2 Mem ALU Reg Me Reg Stall 气泡气泡气泡气泡气泡 指令 3 Mem Reg ALU Mem
结构竞争造成停顿 改进方法 : 增加硬件的拷贝数 使硬件流水化
2. 数据竞争 [ 例 ] ADD R1, R2, R3 SUB R4, R5, R1 AND R6, R1, R7 OR R8, R1, R9 XOR R10, R1, R11 后四条指令都用 ADD 的结果 R1 作为源操作数.
数据相关性引起数据竞争 (Fig3.9; 图 4-10) 程序执行序列时钟周期 ADD R1,R2,R3 CC1 CC2 CC3 CC4 CC5 CC6 IM ALU Reg DM Reg SUB R4,R1,R5 IM Reg ALU DM Reg AND R6,R1,R7 ALU IM Reg DM OR R8,R1,R9 IM Reg ALU XOR R10,R1,R11 IM Reg
数据竞争解决说明 : SUB 和 ADD 必须分别停顿 2 个和 1 个 Cycle 才能得到所需的 R1 的值, Or 由于 Reg. 是在 Cycle 前沿写入, 在 Cycle 中间读出, 正好解决.
数据竞争的分类 : RAW(Read after write) WAW(Write after write) LW R1, 0(R2) ADD R1, R2, R3 若先写, 则造成 WAW. WAR(Write after read) SW 0(R1), R2 ADD R2, R3, R4 若先写, 则造成 WAR. DLX 不会发生此 WAW,WAR Wb 在最后一拍 Read(ID) 总是早于 WB
解决数据竞争的方法之一 : 把结果提前 (Forwarding), 可由硬件实现 (Fig3.10; 图 4-12, p148)
时钟周期程序执行序列把结果提前的可能性 : ADD R1,R2,R3 CC1 CC2 CC3 CC4 CC5 CC6 IM Reg DM Reg ALU SUB R4,R1,R5 IM Reg ALU DM Reg AND R6,R1,R7 IM Reg DM ALU OR R8,R1,R9 IM Reg ALU XOR R10,R1,R11 IM Reg
数据存储器ALU 提前硬件示意图 ( 彩线为提前线路 ) ID/EX EX/MEM MEM/WB 0? MUX MUX
不能用 提前 方法解决数据竞争的例子 LW R1,0(R2) R1 最早等到第四拍 MEM 结束, 才能得到.( 即才能从 Data Memory 读入, 存入暂存器 ) SUB R4,R1,R5 SUB 所用的 R1 最迟在第三拍 EX 开始是要准备好, 与 LW 相差一拍 AND R6,R1,R7 OR R8,R1,R9 同 SUB, 可用 提前 方法解决 同 SUB, 可用 提前 方法解决
时钟周期 程序执行序列LW R1,0(R2) CC1 CC2 CC3 CC4 IM Reg DM Reg ALU CC5 SUB R4,R1,R5 IM Reg ALU DM AND R6,R1,R7 IM Reg ALU OR R8,R1,R9 IM Reg
Load Delay: 不能用 提前 方法解决 解决方法 : 需要一种称为 Pipeline interlock 的硬件, 来检测储存在此类竞争, 使 Pipeline 停顿下来, 一直到竞争消失 ( 或可用 提前 硬件解决这一竞争 Compiler Scheduling, 或称 Pipeline Scheduling, instruction Scheduling
编译器调度 : 由编译器重新按排指令 执行顺序, 来避免停顿周期 例 : LW R1, B LW R2, C ADD R3, R1, R2 SW A, R3 由于存在 Load Delay, ADD 必须推迟一拍
A=B+C 的流水过程 LW R1, B LW R2, C ADD R3,R1,R2 SW A, R3 IF ID EX MEM WB IF ID EX MEM WB IF ID Stall EX MEM WB IF stall ID EX MEM WB
编译器调度指令顺序, 避免停顿 [ 例 ] a = b+c ; d = e-f LW Rb, b LW Rc, c ADD Ra,Rb,Rc SW a, Ra LW Re, e LW Rf, f SUB Rd,Re,Rf SW d, Rd LW Rb, b LW Rc, c LW Re, e ADD Ra,Rb,Rc LW Rf, f SW a, Ra SUB Rd,Re,Rf SW d, Rd
要采用 interlock 或 forwarding 来避免数据竞争的前提是要能检测出在流水线中存在数据竞争 这里要解决两个问题 : 1. 如何监测数据竞争 ( 分别对应需 interlock 或 forwarding 的数据竞争 ) 2. 检测到需 interlock 或 forwarding 后, 做什么?
* 分析需 Interlock 的情况 ( 相对简单 : 只 在 Load Delay 时发生 ) 如何检测 Load Delay? LD ADD SUB IF ID EX MEM WB ID/EX IF ID Stall EX MEM WB IF/ID IF Stall ID EX MEM WB 只要对 LD 指令 ( 在 ID 后, 才知道指令的 opcode 及 其操作数 operands) 比较其紧跟其后的指令的 opcode 及其 operands, 是否直接相关
Load 引起数据竞争的检测 ID/EX 级流水寄存器的代码段 (ID/EX.IR 0..5 ) IF/ID 级流水寄存器的代码段 (IF/ID.IR 0..5 ) 相应流水寄存器操作属域段匹配检测 Load r-r ALU 操作 ID/EX.IR 11..15 =IF/ID.IR 6..10 Load r-r ALU 操作 ID/EX.IR 11..15 =IF/ID.IR 11..15 Load Load, Store, ALU 立即数或转移 ID/EX.IR 11..15 =IF/ID.IR 6..10
如何实现内锁一旦检测到 Load Delay 情况, 只需 把下一条指令的 ID/EX 暂存器的操作码寄存器内容置 0, 使 ADD R0, R0, R0, 成为条空操作. 使 IF/ID 中被停顿指令的操作码寄存器的内容延长保留一拍.
* 分析需使用 Forwarding 硬件的情况 Fig.3.19, p160 和 Fig.3.20, p161; 表 4.9, P155 和图 4.19, p156.
含源指令的锁存器 源指令的操作 含目标指令的锁存器 目标指令的操作 ( 后继指令 ) 旁路电路的输入端 比较检测 ( 相等则直接送结果 EX/MEM R-R ALU ID/EX ALU,LD,ST,Branch ALU 上端 EX/MEM.IR 16..20 =ID/EX.IR.6..10 EX/MEM R-R ALU ID/EX R-R ALU ALU 下端 EX/MEM.IR 16..20 =ID/EX.IR 11.15 MEM/WB R-R ALU ID/EX ALU,LD,ST,Branch ALU 上端 MEM/WB.IR 16..20 =ID/EX.IR 6..10 MEM/WB R-R ALU ID/EX R-R ALU ALU 下端 MEM/WB.IR 16..20 =ID/EX.IR 11..15 EX/MEM R-I ALU ID/EX ALU,LD,ST,Branch ALU 上端 EX/MEM.IR 11..15 =ID/EX.IR 6..10 EX/MEM R-I ALU ID/EX R-R ALU ALU 下端 EX/MEM/.IR 11..15 =ID/EX.IR 11..15 MEM/WB R-I ALU ID/EX ALU,LD,ST,Branch ALU 上端 MEM/WB.IR 11..15 =ID/EX.IR 6..10 MEM/WB R-I ALU ID/EX R-R ALU ALU 下端 MEM/WB.IR 11..15 =ID/EX.IR 11..15 MEM/WB Load ID/EX ALU,LD,ST,Branch ALU 上端 MEM/WB.IR 11..15 =ID/EX.IR 6..10 MEM/WB Load ID/EX R-R ALU ALU 下端 MEM/WB.IR 11..15 =ID/EX.IR 11..15 对应 forwarding path 参见 ( 图 4-19,p156)
3. 控制竞争造成停顿实例 指令序列 流水时钟数 1 2 3 4 5 6 7 8 9 转移指令 IF ID EX MEM WB 指令 i +1 IF Stall Stall IF ID EX MEM WB 指令 i +2 IF ID EX MEM 指令 i +3 IF ID EX 指令 i +4 IF ID 指令 i +5 IF 转移指令造成的三个停顿周期
控制竞争造成停顿的原因 : 转移地址在第三拍 EX 中计算 ; 转移条件比较在第四拍 MEM 中进行 所以要等到第四拍结束才能知道转移成功与否 参见 ( 图 4-8,p139)
解决控制竞争造成停顿的方法 (1) 通过提前计算转移的目的地址和提前比较转移条件, 可使转移指令造成的停顿周期由 3 个减少到 1 个
数据存储转移计算提前后的流水线 4 ADD MUX IF/ID ADD 0? ID/EX EX/MEM MEM/WB PC IR6..10 IR11..15 寄IR 存MEM/ 器数器据存MUX 储MUX 器ALU 16 Sign extend 32
解决控制竞争造成停顿的方法 (2) 预测每一个转移都不成功, 即在下一拍立即取转移指令的下一条指令
预测成功, 即实际为不转移, 则无停顿 转移不成功指令 IF ID EX MEM WB 指令 i +1 IF ID EX MEM WB 指令 i +2 IF ID EX MEM WB 指令 i +3 IF ID EX MEM WB 指令 i +4 IF ID EX MEM WB
预测失败, 即实际为转移, 则停顿一个周期 转移成功指令 IF ID EX MEM WB 指令 i +1 IF idle idle idle Idle 目标指令 IF ID EX MEM WB 目标指令 +1 IF ID EX MEM WB 目标指令 +2 IF ID EX MEM WB
解决控制竞争造成停顿的方法 (3) 预测每一个转移都成功, 但必须等算出转移目标地址, 才能取转移目的指令 这一方法对 DLX 机器无效, 因为在 DLX 机器中, 转移地址计算和转移条件比较 ( 即知道转移能否成功 ) 是同时获得的, 因而无利可图 但对其他机器可能有利
解决控制竞争造成停顿的方法 (4) 延时转移 (delayed branch) 方法 从开始处理转移指令到明确转移是否发生之间存在一段转移延时时间, 称为转移延时槽 (branch-delay-slot) 在 DLX 机器中这一由转移指令造成的延时时间为一个时钟周期, 即允许利用 branch-delay-slot 执行一条指令 Delayed branch 方法就是由编译器挑选合适的, 有用的指令填入延时槽中执行, 即合理利用这一延时时间, 而不浪费
三种转移延时槽调度方法 ( 由编译完成 ) ADD R1,R2,R3 if R2=0 then 延时槽 SUB R4,R5,R6 ADD R1,R2,R3 if R2=0 then 延时槽 ADD R1,R2,R3 if R2=0 then 延时槽 SUB R4,R5,R6 ADD R1,R2,R3 if R2=0 then ADD R1,R2,R3 if R2=0 then if R2=0 then SUB R4,R5,R6 ADD R1,R2,R3 SUB R4,R5,R6 (a) 取自转移前 (b) 取自转移目标 (c) 取自转移后
3.1.6 带有停顿周期的流水线性能计算 speedup from pipelining Average instruction time unpipelined =-------------------------------------------------- Average instruction time pipelined CPIunpipelined Clock Cycle unpipelined = ------------------------------------------------- CPIpipelined Clock Cycle pipelined CPIunpipelined Clock Cycle unpipelined = ------------------------------------------------- CPIpipelined Clock Cycle pipelined
可以有两种观点来看待流水线性能的提高 由于缩短了 CPI(Clock cycle per instruction) 由于缩短了 Clock cycle time. 传统上, 采用比较 CPI 方法来计算流水线的加速因子, 我们研究 CPIpipelined =Ideal CPI+Pipeline stall clock cycles per instruction = 1 + Pipeline stall clock cycles per instruction
假设流水线机器每一周期内完成的工作 量均是均衡的, 即设备因为实现流水线 而延长流水级的时间, 则 Clock Cycleunpipelined = Clock Cycle pipelined 则含有停顿周期的流水线的加速因子为 : speedup CPIunpipelined =-------------------------------------------------- 1 + Pipelined stall cycles per instruction Pipeline depth =-------------------------------------------------- 1 + Pipelined stall cycles per instruction
试回忆比较理想流水线的加速因子 试从缩短 Clock cycle time 角度推导加 速因子, 应可得到同一公式.