L21

Size: px

Start display at page:

Download "L21"

烈汪
5 years ago
Views:

1 Lecture 25: Pipeline Hazard

2 流水线冒险的处理主要内容流水线冒险的几种类型数据冒险的现象和对策数据冒险的种类 - 相关的数据是结果 : 可以通过转发解决 - 相关的数据是 DM 读出的内容 : 随后的指令需被阻塞一个时钟数据冒险和转发 - 转发检测 / 转发控制数据冒险和阻塞 - 阻塞检测 / 阻塞控制控制冒险的现象和对策静态分支预测技术动态分支预测技术缩短分支延迟技术流水线中对异常和中断的处理访问缺失对流水线的影响

3 总结 : 流水线的三种冲突 / 冒险 (Hazard) 情况 Hazards: 指流水线遇到无法正确执行后续指令或执行了不该执行的指令 Structural hazards (hardware resource conflicts): 现象 : 同一个部件同时被不同指令所使用 - 一个部件每条指令只能使用 1 次, 且只能在特定周期使用 - 设置多个部件, 以避免冲突如指令存储器 IM 和数据存储器 DM 分开 Data hazards (data dependencies): 现象 : 后面指令用到前面指令结果时, 前面指令结果还没产生 - 采用转发 (Forwarding/Bypassing) 技术 - Load-use 冒险需要一次阻塞 (stall) - 编译程序优化指令顺序 Control (Branch) hazards (changes in program flow): 现象 : 转移或异常改变执行流程, 顺序执行指令在目标地址产生前已被取出 - 采用静态或动态分支预测 - 编译程序优化指令顺序 ( 实行分支延迟 ) SKIP

4 Structural Hazard( 结构冒险 ) 现象 Time (clock cycles) Load Instr 1 Instr 2 Mem Reg Mem Reg Mem Reg Mem Reg Mem Reg Mem Reg Instr 3 Instr 4 Mem Reg Mem Reg Mem Reg Mem Reg 如果只有一个存储器, 则在 Load 指令取数据同时又取指令的话, 则发生冲突! 如果不对寄存器堆的写口和读口独立设置的话, 则发生冲突! 结构冒险也称为硬件资源冲突 : 同一个执行部件被多条指令使用

5 Structural Hazard 的解决方法为了避免结构冒险, 规定流水线数据通路中功能部件的设置原则为 : 每个部件在特定的阶段被用!( 如 : 总在第三阶段被用!) 将 Instruction Memory (Im) 和 Data Memory (Dm) 分开将寄存器读口寄存器读口和写口写口独立开来 Time (clock cycles) I n s t r. O r d e r Load Instr 1 Instr 2 Instr 3 Instr 4 Im Reg Dm Reg Im Reg Dm Im Reg BACK Reg Dm Reg

6 Data Hazard 现象举例说明 : 以下指令序列中, 寄存器 r1 会发生数据冒险 add r1,r2,r3 sub r4, r1,r3 and r6, r1,r7 or r8, r1,r9 xor r10, r1,r11 想一下, 哪条指令的 r1 是老的值? 哪条是新的值? 读 r1 时,add 指令正在执行加法 (EXE), 老值! 读 r1 时,add 指令正在传递加法结果 (MEM), 老值! 读 r1 时,add 指令正在写加法结果到 r1(wb), 老值! 读 r1 时,add 指令已经把加法结果写到 r1, 新值补充 : 三类数据冒险现象画出流水线图能很清楚理解! RAW: 写后读 ( 基本流水线中经常发生, 如上例 ) WAR: 读后写 ( 基本流水线中不会发生, 多个功能部件时会发生 ) WAW: 写后写 ( 基本流水线中不会发生, 多个功能部件时会发生 ) 本讲介绍基本流水线, 所以仅考虑 RAW 冒险

7 Data Hazard on r1 Time (clock cycles) IF ID/RF EX MEM WB I n s t r. O r d e r add r1,r2,r3 sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9 xor r10,r1,r11 Im Reg Dm Reg 最后一条指令的 r1 才是新的值! 如何解决这个问题?

8 I n s t r. O r d e r 方案 1: 在硬件上采取措施, 使相关指令延迟执行硬件上通过阻塞 (stall) 方式阻止后续指令执行, 延迟到有新值以后! 这种做法称为流水线阻塞, 也称为气泡 Bubble Time (clock cycles) IF ID/RF EX MEM WB add r1,r2,r3 stall stall stall sub r4,r1,r3 Im bubble bubble bubble bubble Im bubble bubble bubble bubble Im bubble bubble bubble bubble and r6,r1,r7 Im Reg Dm 缺点 : 控制相当复杂, 需要改数据通路!

9 方案 2: 软件上插入无关指令最差的做法 : 由编译器插入三条 NOP 指令, 浪费三条指令的空间和时间 I n s t r. O r d e r Time (clock cycles) add r1,r2,r3 nop nop nop sub r4,r1,r3 IF ID/RF EX MEM WB Im Reg Dm Reg and r6,r1,r7 Im Reg Dm

10 方案 3: 利用 DataPath 中的中间数据仔细观察后发现 : 流水段寄存器中已有需要的值 r1! 在哪个流水段 R 中? I n s t r. O r d e r Time (clock cycles) IF ID/RF EX MEM WB add r1,r2,r3 sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9 xor r10,r1,r11 Im Reg Dm Reg 1. 把数据从流水段寄存器中直接取到的输入端 2. 寄存器写 / 读口分别在前 / 后半周期, 使写入被直接读出 BACK 称为转发 (Forwading) 或旁路 (Bypassing)

11 硬件上的改动以支持转发技术加 MUX, 使流水段寄存器值返送输入端假定流水段寄存器能读出新写入的值 ( 否则, 需要更多的转发数据 ) Ex Mem ID/EX EX/MEM MEM/WB M u x M u x Zero? add r3, r2, r1 Sub r5, r3, r4 Data Memory lw r3, 100(r1) Or r6, r2, r1 Sub r5, r3, r4 add r3, r2, r1 Or r6, r2, r1 如果指令序列为 : lw r3, 100(r1) Or r6, r3, r1 Sub r5, r3, r4 能用转发技术解决第 1 2 两条指令间的数据冒险吗? 请看后面的幻灯片! Sub r5, r3, r4

12 复习 : Load 指令引起的延迟现象 Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Clock I0: Load Ifetch Reg/Dec Exec Mem Wr Plus 1 Ifetch Reg/Dec Exec Mem Wr Plus 2 Ifetch Reg/Dec Exec Mem Wr Plus 3 Ifetch Reg/Dec Exec Mem Wr 若不采用转发, 则在何时才能用使用 Load 指令的结果? Plus 4 Ifetch Reg/Dec Exec Mem Wr Load 指令最早在哪个流水线寄存器中开始有后续指令需要的值? 实际上, 在第四周期结束时, 数据在流水段寄存器中已经有值采用数据转发技术可以使 load 指令后面第二条指令得到所需的值但不能解决 load 指令和随后的第一条指令间的数据冒险, 要延迟执行一条指令! 这种 load 指令和随后指令间的数据冒险, 称为装入 - 使用数据冒险 (load- use Data Hazard)

13 Forwarding 技术使 Load-use 冒险只需延迟一个周期 I n s t r. O r d e r Time (clock cycles) IF ID/RF EX MEM WB lw r1, 0(r2) sub r7,r1,r3 and r6,r1,r7 or r8,r1,r9 Im Reg Dm Reg 采用转发后仅第二条指令 SUB r7,r1,r3 不能按时执行! 需要阻塞一个周期发生装入 - 使用数据冒险时, 需要对 load 后的指令阻塞一个时钟周期!

14 方案 1: 硬件阻止指令执行来解决 load-use 用硬件阻塞一个周期 ( 指令被重复执行一次 ) I n s t r. O r d e r Time (clock cycles) lw r1, 0(r2) stall sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9 IF ID/RF EX MEM WB Im bubble bubble bubble bubble Im Reg Dm Reg

15 方案 2: 软件上插入 NOP 指令来解决 load-use 用软件插入一条 NOP 指令!( 有些处理器不支持硬件阻塞处理 ) 例如 :MIPS 1 处理器没有硬件阻塞处理, 而由编译器 ( 或汇编程序员 ) 来处理 I n s t r. O r d e r Time (clock cycles) lw r1, 0(r2) nop sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9 IF ID/RF EX MEM WB Im Reg Dm Reg

16 方案 3: 编译器进行指令顺序调整来解决 load-use 以下源程序可生成两种不同的代码, 优化的代码可避免 Load 阻塞 a = b + c; d = e f; 假定 a, b, c, d,e, f 在内存 Slow code: lw $2, b lw $3, c add $1, $2, $3 sw a, $1 lw $5, e lw $6, f sub $4, $5, $6 sw d, $4 调整后 Fast code: lw $2, b lw $3, c lw $5, e add $1, $2, $3 lw $6, f sw a, $1 sub $4, $5, $6 sw d, $4 编译器的优化很重要!

17 编译器优化以避免阻塞的情况调查 : scheduled unscheduled gcc spice tex 14% 25% 31% 42% 54% 65% 0% 20% 40% 60% 80% % loads stalling pipeline 由此可见, 优化调度后 load 阻塞现象大约降低了 1/2~1/3

18 数据冒险的解决方法方法 1: 硬件阻塞 (stall) 方法 2: 软件插入 NOP 指令方法 3: 编译优化 : 调整指令顺序, 能解决所有数据冒险吗? 方法 4: 合理实现寄存器堆的读 / 写操作, 能解决所有数据冒险吗? 前半时钟周期写, 后半时钟周期读, 若同一个时钟内前面指令写入的数据正好是后面指令所读数据, 则不会发生数据冒险方法 5: 转发 (Forwarding 或 Bypassing 旁路 ) 技术, 能解决所有数据冒险吗? - 若相关数据是结果, 则如何? 可通过转发解决 - 若相关数据是上条指令 DM 读出内容, 则如何? 不能通过转发解决, 随后指令需被阻塞一个时钟或加 NOP 指令称为 Load-use 数据冒险! 实现转发和阻塞要修改数据通路 : (1) 检测何时需要转发, 并控制实现转发 (2) 检测何时需要阻塞, 并控制实现阻塞 BACK

19 RAW( 写后读 ) 数据冒险的转发条件 ID/EX EX/MEM MEM/WB M u x M u x Ex Zero? C1 Mem ori r3, r2, 100 sub r5, r3, r4 Data Memory C3 lw r3, 100(r1) or r6, r2, r1 sub r5, r3, r4 C2 add r3, r2, r1 or r6, r2, r1 sub r5, r3, r4 后面指令需用输出结果 C1: 目寄是后一条指令的源寄 C2: 目寄是后第二条指令的源寄 ( 例如 :R-Type 后跟 R- / lw / sw / beq 等 ) 后面指令需用从 DM 读出的结果 C3: 目寄是后第二条指令的源寄 ( 例如 :load 指令后跟 R-Type / beq 等 ) 用流水段寄存器来表示转发条件 (C3 以后考虑 ) C1(a): EX/MEM. RegisterRd=ID/EX. RegisterRs C1(b): EX/MEM. RegisterRd=ID/EX. RegisterRt C2(a): MEM/WB. RegisterRd=ID/EX. RegisterRs C2(b): MEM/WB. RegisterRd=ID/EX. RegisterRt 这里的 RegisterRd 是指目的寄存器实际上是 R-type 的 Rd 或 I-Type 的 rt

20 指令的回写 (Write Back) 阶段 Clk Ifetch Reg/Dec Exec Mem Wr RegWr=1 ExtOp Op Branch PC 1 0 PC+4 AIUnit I IF/ID: PC+4 Imm Rs Ra Rb Rt RFile Rt Rw Di Rd ID/Ex Register 0 1 PC+4 Imm busa busb Exec Unit Ex/Mem Register Zero Data Mem RA Do WA Di Mem/Wr Register 1 Mux 0 Rd 还是 Rt 取决于是 R- 型指令, 还是 I- 型指令! 若是 beq 指令会怎样? RegDst beq r3, r2, 100 sub r5, r3, r2 Src MemWr MemtoReg=1/0 因为 beq 指令没有写结果, 不用进行转发!

21 转发条件的进一步完善以下两种情况下, 根据前面的转发条件转发会发生错误指令的结果不写入目的寄存器 Rd 时 beq r3, r2, 100 sub r5, r3, r2 - 例如,Beq 指令只对 rs 和 rt 相减, 不写结果到目的寄存器 - 即 :EX / MEM 或 MEM / WB 流水段寄存器的 RegWrite 信号为 0 Rd 等于 $0 时 - 例如, 指令 sll $0, $1, 2 的转发结果为 (R[$1]<<2), 但实际上应该是 0 因此, 修改转发条件为 : C1(a): EX/MEM.RegWrite and EX/MEM. RegisterRd 0 and EX/MEM. RegisterRd=ID/EX. RegisterRs C1(b): EX/MEM.RegWrite and EX/MEM. RegisterRd 0 and EX/MEM. RegisterRd=ID/EX. RegisterRt C2(a): MEM/WB.RegWrite and MEM/WB. RegisterRd 0 and MEM/WB. RegisterRd=ID/EX. RegisterRs C2(b): MEM/WB.RegWrite and MEM/WB. RegisterRd 0 and MEM/WB. RegisterRd=ID/EX. RegisterRt

22 转发路径和转发条件 ID/EX EX/MEM MEM/WB 加 MUX, 使流水段寄存器值返送输入端 M u x M u x Ex Zero? Mem C1(a) Data Memory C1(b) C3 C2(a) C2(b) C1 反映本条指令和随后指令间的相关关系 C2 反映本条指令和随后第二条指令间的相关关系 C1(a) 和 C1(b) 可以合并为一个条件 C1, 并把转发线合一起后同时送 A 口和 B 口即 :C1=C1(a) or C1(b), 同样 :C2=C2(a) or C2(b), 转发线合起来实际上红线和兰线可以合并, 而且在原数据通路中是合并在一起的记得吗? 由一个二路选择器 ( 控制端为 MemtoReg) 合并输出到寄存器堆! 所以不需另外有一个检测条件 C3! C1 和 C2 分别反映哪两条指令的关系呢?

23 转发路径和转发条件 ForwardA (ForwardB) = 01 当 c2=1 时 10 当 c1=1 时转发检测部件中缺何条件? C1 C2 C1: EX/MEM.RegWrite and EX/MEM. RegisterRd 0 and (EX/MEM. RegisterRd=ID/EX. RegisterRs or EX/MEM. RegisterRd=ID/EX. RegisterRt C2: MEM/WB.RegWrite and MEM/WB. RegisterRd 0 and (MEM/WB. RegisterRd=ID/EX. RegisterRs or MEM/WB. RegisterRd=ID/EX. RegisterRt

24 带转发的流水线数据通路 ForwardA (ForwardB) = 01 当 c2=1 时 10 当 c1=1 时 ForwardA ForwardB C1: EX/MEM.RegWrite and EX/MEM. RegisterRd 0 and (EX/MEM. RegisterRd=ID/EX. RegisterRs or EX/MEM. RegisterRd=ID/EX. RegisterRt C2: MEM/WB.RegWrite and MEM/WB. RegisterRd 0 and (MEM/WB. RegisterRd=ID/EX. RegisterRs or MEM/WB. RegisterRd=ID/EX. RegisterRt

25 更加复杂的数据冒险问题考察以下指令序列, 采用前述转发条件会发生什么情况? add $1, $1, $2 add $1, $1, $3 add $1, $1, $4 本条指令 ForwardA (ForwardB) = 01 当 c2=1 时 10 当 c1=1 时对于左边的指令序列,C1 和 C2 的值各是什么? C1=C2=1, 使得 Forward 信号取值不确定! 可能会使转发到第 3 条指令的操作数是第 1 条指令结果, 而不是第 2 条指令的结果! 怎样改写转发检测条件 : 改 C1 还是改 C2? 应该让 C1=1,C2=0! 需要改写转发条件 C2 为 : MEM/WB.RegWrite and MEM/WB.RegisterRd 0 and (EX/MEM.RegisterRd ID/EX.RegisterRs or EX/MEM.RegisterRd ID/EX.RegisterRt) and (MEM/WB.RegisterRd=ID/EX.RegisterRs or MEM/WB.RegisterRd=ID/EX.RegisterRt) 上述公式相当于加了一个条件限制 : 如果本条指令源操作数和上条指令的目的寄存器一样, 则不转发上上条指令的结果, 而转发上条指令的结果 ( 即 : 此时的 C1=1 而 C2=0) 至此, 解决了 RAW 数据冒险的转发处理 BACK

26 I n s t r. O r d e r Load-use Data Hazard( 硬件阻塞方式 ) Time (clock cycles) IF ID/RF EX MEM WB lw r1, 0(r2) sub r4,r1,r3 sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9 检测点阻塞点 Im Reg bubble bubble bubble Im Reg Dm Reg 需解决以下问题 : (1) 判断什么条件下需要阻塞 ID/EX.MemRead and (ID/EX.RegisterRt=IF/ID.RegisterRs or ID/EX.RegisterRt=IF/ID.RegisterRt) (2) 如何修改数据通路来实现阻塞前面指令为 Load 并且前面指令的目的寄存器等于当前刚取出指令的源寄存器

27 Load-use Data Hazard( 硬件阻塞方式 ) I n s t r. 阻塞前的情况 : lw r1, 0(r2) sub r4,r1,r3 检测点 Time (clock cycles) IF ID EX MEM WB O r d e r and r6,r1,r7 or r8,r1,r9 阻塞点 Im Reg Dm Reg 检测阻塞过程中 : 1) sub 指令在 IF/ID 段寄存器中, 并正被译码 / 取数, 控制信号和 Rs/Rt 的值将被写到 ID/EX 段寄存器 2) and 指令地址在 PC 中, 正被取出, 取出的指令将被写到 IF/ID 段寄存器中在阻塞点, 必须将上述两条指令的执行结果清除, 并延迟一个周期执行这两条指令延迟一个周期执行后面的指令, 相当于把阻塞点前面一个周期的状态再保持一个周期 lw 指令还是继续正常执行下去想想看, 如何做到继续保持状态?

28 I n s t r. O r d e r Load-use Data Hazard( 硬件阻塞方式 ) 阻塞后的情况 : lw r1, 0(r2) sub r4,r1,r3 sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9 检测点 Time (clock cycles) IF ID/RF EX MEM WB 阻塞点 Im Reg bubble bubble bubble Im Reg Dm Reg 在阻塞点, 必须将上述两条指令的执行结果清除, 并延迟一个周期执行这两条指令 1 将 ID/EX 段寄存器中所有控制信号清 0 2 IF/ID 寄存器中的信息不变,sub 指令重新译码执行 3 PC 中的值不变,and 指令重新被取出执行

29 带转发和阻塞检测的流水线数据通路写使能信号为 0, 使 PC 2 和 IF/ID 不变 3 使控制信号 1 清 0, 阻塞随后指令! 0 ID/EX.MemRead and (ID/EX.RegisterRt=IF/ID.RegisterRs or ID/EX.RegisterRt=IF/ID.RegisterRt) 至此, 数据冒险的处理全部完成! BACK

30 转移分支指令 (Branch) 引起的延迟现象 ( 复习 ) Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 Cycle 10 Cycle 11 Clk 12: Beq Ifetch Reg/Dec Exec Mem Wr (target is 1000) 16: R-type Ifetch Reg/Dec Exec Mem Wr 20: R-type Ifetch Reg/Dec Exec Mem Wr 24: R-type Ifetch Reg/Dec Exec Mem Wr 1000: Target of Br Ifetch Reg/Dec Exec Mem Wr 虽然 Beq 指令在第四周期取出, 但 : 目标地址在第七周期才被送到 PC 的输入端第八周期才能取出目标地址处的指令执行结果 : 在取目标指令之前, 已有三条指令被取出, 取错了三条指令! 这种现象称为控制冒险 (Control Hazard ) ( 注 : 也称为分支冒险或转移冒险 (Branch Hazard) ) BACK

31 Control Hazard 的解决方法方法 1: 硬件上阻塞 (stall) 分支指令后三条指令的执行使后面三条指令清 0 或其操作信号清 0, 以插入三条 NOP 指令方法 2: 软件上插入三条 NOP 指令 ( 以上两种方法的效率太低, 需结合分支预测进行 ) 方法 3: 分支预测 (Predict) 简单 ( 静态 ) 预测 : - 总是预测条件不满足 (not taken), 即 : 继续执行分支指令的后续指令可加启发式规则 : 在特定情况下总是预测满足 (taken), 其他情况总是预测不满足如 : 循环顶 ( 底 ) 部分支总是预测为不满足 ( 满足 ) 能达 65%-85% 的预测准确率动态预测 : - 根据程序执行的历史情况, 进行动态预测调整, 能达 90% 的预测准确率注 : 采用分支预测方式时, 流水线控制必须确保错误预测指令的执行结果不能生效, 而且要能从正确的分支地址处重新启动流水线工作方法 4: 延迟分支 (Delayed branch)( 通过编译程序优化指令顺序!) 把分支指令前面与分支指令无关的指令调到分支指令后面执行, 也称延迟转移另一种控制冒险 : 异常或中断控制冒险的处理

32 简单 ( 静态 ) 分支预测方法基本做法总预测条件不满足 (not taken), 即 : 继续执行分支指令的后续指令可加启发式规则 : 在特定情况下总是预测满足 (taken), 其他情况总是预测不满足预测失败时, 需把流水线中三条错误预测指令三条错误预测指令丢弃掉 - 将三条丢弃指令的控制信号值设置为 0, 使其后续过程中执行 nop 操作 ( 注 : 涉及到当时在 IF ID 和 EX 三个阶段的指令 ) 性能如果转移概率是 50%, 则预测正确率仅有 50% 预测错误的代价预测错误的代价与何时能确定是否转移有关越早确定代价越少可以把是否转移的确定工作提前, 而不要等到 MEM 阶段才确定那最早可以提前到哪个阶段呢? SKIP

33 复习 : Control Hazard 现象 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 Cycle 10 Cycle 11 Clk 12: Beq Ifetch Reg/Dec Exec Mem Wr (target is 1000) 16: R-type Ifetch Reg/Dec Exec Mem Wr 20: R-type Ifetch Reg/Dec Exec Mem Wr 24: R-type Ifetch Reg/Dec Exec Mem Wr 1000: Target of Br Ifetch Reg/Dec Exec Mem Wr 虽然 Beq 指令在第四周期取出, 但 : 是否转移在 Mem 阶段确定, 目标地址在第七周期才被送到 PC 输入端第八周期才取出目标地址处的指令执行结果 : 在取目标指令之前, 已有三条指令被取出, 取错了三条指令! 发生转移时, 要在流水线中清除 Beq 后面的三条指令, 分别在 EXE ID IF 段中延迟损失时间片 C: 发生转移时, 给流水线带来的延迟损失这里 C=3 BACK

34 简单 ( 静态 ) 分支预测方法缩短分支延迟, 减少错误预测代价可以通过调整转移地址计算和分支条件判断操作到 ID 阶段来缩短延迟 - 将转移地址生成从 MEM 阶段移到 ID 阶段, 可以吗? 为什么? ( 是可能的 :IF/ID 流水段寄存器中已经有 PC 的值和立即数 ) - 将判 0 操作从 EX 阶段移到 ID 阶段, 可以吗? 为什么? ( 用逻辑运算 ( 如, 先按位异或, 再结果各位相或 ) 来直接比较 Rs 和 Rt 的值 ) ( 简单判断用逻辑运算, 复杂判断可以用专门指令生成条件码 ) ( 许多条件判断都很简单 ) 预测错误的检测和处理 ( 称为冲刷冲洗冲洗 -- Flush) 当 Branch=1 并且 Zero=1 时, 发生转移 (taken) 增加控制信号 :IF.Flush=Branch and Zero, 取值为 1 时, 说明预测失败预测失败 ( 条件满足 ) 时, 完成以下两件事 ( 延迟损失时间片 C=1 时 ): 1 将转移目标地址 ->PC 2 清除 IF 段中取出的指令, 即 : 将 IF/ID 中的指令字清 0, 转变为 nop 指令原来要清除三条指令, 调整后只需要清除一条指令, 因而只延迟一个时钟周期, 每次预测错误减少了两个周期的代价!

35 带静态分支预测处理的数据通路 IF.Flush=Branch and Zero 40# 指令 beq $1,$3, 7 的 ID 阶段转移目标地址 (72)->PC sub $3, $5, $1 add $1, $5, $2 beq $1, $3, 7 控制转移目标地址 ->PC 将 IF/ID 中指令字清 0, 变为 nop 指令若 $1 或 $3 和前面指令数据相关, 会怎么样? 上上条指令的 EXE 段结果可转发回来进行判断上条指令的 EXE 段结果来不及转发回来, 引起 1 次阻塞! BACK

36 动态分支预测方法简单的静态分支预测方法的预测成功率不高, 应考虑动态预测动态预测基本思想 : 利用最近转移发生的情况, 来预测下一次可能发生的转移预测后, 在实际发生时验证并调整预测转移发生的历史情况记录在 BHT 中 - 分支历史记录表 BHT(Branch History Table) - 分支目标缓冲 BTB(Branch Target Buffer) 每个表项由分支指令地址低位作索引, 故在 IF 阶段就可以取到预测位 - 低位地址相同的分支指令共享一个表项, 所以, 可能取的是其他分支指令的预测位会不会有问题? - 由于仅用于预测, 所以不影响执行结果现在几乎所有的处理器都采用动态预测 (dynamic predictor)

37 分支历史记录表 BHT 分支指令地址 =? 分支历史记录表 BHT 分支指令地址预测位转移目标转移目标地址 1 查找转移取顺序取查找时发现都不相等, 则未命中未命中说明什么? 说明以前没有执行过该分支指令加入新项命中与否 4 修正 2 预测控制控制逻辑 3 选择实际执行情况命中时 : 根据预测位, 选择转移取还是顺序取未命中时 : 加入新项, 并填入指令地址和转移目标地址初始化预测位指令预取器指令执行

38 动态预测基本方法采用一位预测位 : 总是按上次实际发生的情况来预测下次 1 表示最近一次发生过转移 (taken), ),0 表示未发生 (not taken) 预测时, 若为 1, 则预测下次 taken, 若为 0, 则预测下次 not taken 实际执行时, 若预测错, 则该位取反, 否则, 该位不变可用一个简单的预测状态图预测状态图表示缺点 : 当连续两次的分支情况发生改变时, 预测错误 - 例如, 循环迭代分支时, 第一次和最后一次会发生预测错误, 因为循环的第一次和最后一次都会改变分支情况, 而在循环中间的各次总是会发生分支, 按上次的实际情况预测时, 都不会错采用二位预测位用 2 位组合四种情况来表示预测和实际转移情况按照预测状态图预测状态图进行预测和调整在连续两次分支发生不同时, 只会有一次预测错误采用比较多的是二位预测位, 也有采用二位以上预测位如 :Pentium 4 的 BTB2 采用 4 位预测位 BACK

39 一位预测状态图发生正确不发生错误不发生预测发生预测不发生 1 0 发生错误正确 Loop: g = g +A[i]; i = i+ j; if (i!= h) go to Loop: Assuming variables g, h, i, j ~ $1, $2, $3, $4 and base address of array is in $5 指令预取时, 按照预测读取相应分支的指令预测发生时, 选择转移取预测不发生时, 选择顺序取指令执行时, 按实际执行结果修改预测位对照状态转换图来进行修改例如 : 对于一个循环分支若初始状态为 0( 再次循环时为 0), 则第一次和最后一次都错若初始状态为 1, 则只有最后一次会错即 : 只要本次和上次的发生情况不同, 就会出现一次预测错误 Loop: add $7, $3, $3 ; i*2 add $7, $7, $7 ; i*4 add $7, $7, $5 lw $6, 0($7) ; $6=A[i] add $1, $1, $6 ; g= g+a[i] add $3, $3, $4 bne $3, $2, Loop

40 举例 : 双重循环的一位动态预测 into sum (int N) { int i, j, sum=0; for (i=0; i < N; i++) for (j=0; j <N; j++) sum=sum+1; return sum; } Loop-i: beq $t1,$a0, exit-i # 若 ( i=n) 则跳出外循环 add $t2, $zero, $zero #j=0 Loop-j: beq $t2, $a0, exit-j # 若 (j=n) 则跳出内循环 addi $t2, $t2, 1 # j=j+1 addi $t0, $t0, 1 #sum=sum+1 j Loop-j exit-j: addi $t1, $t1, 1 # i=i +1 j Loop-i exit-i: 外循环中的分支指令共执行 N+1 次, 内循环中的分支指令共执行 N (N+1) 次 N=10, 分别 90.9% 和 82.7% N=100, 分别 99% 和 98% 预测位初始为 0, 外循环只有最后一次预测错误 ; 跳出内循环时预测位变为 1, 再进入内循环时, 第一次总是预测错误, 并且任何一次循环的最后一次总是预测错误, 因此, 总共有 1+2 (N 1) 次预测错误 N 越大准确率越高! BACK

41 两位预测状态图发生正确不发生错误预测发生预测发生发生正确发生错误不发生错误不发生正确预测不发生预测不发生发生错误不发生正确 Loop: add $7, $3, $3 ; i*2 add $7, $7, $7 ; i*4 add $7, $7, $5 lw $6, 0($7) ; $6=A[i] add $1, $1, $6 ; g= g+a[i] add $3, $3, $4 bne $3, $2, Loop 预测发生时, 选择转移取预测不发生时, 选择顺序取基本思想 : 只有两次预测错误才改变预测方向 11 状态时预测发生 ( 强转移 ), 实际不发生时, 转到状态 10( 弱转移 ), 下次仍预测为发生, 如果再次预测错误 ( 实际不发生 ), 才使下次预测调整为不发生 00 好处 : 连续两次发生不同的分支情况时, 会预测正确例如, 对于循环分支的预测 ( 假定预测初始位为 11) - 第一次 : 初始态为 11( 再次循环时状态为 10), 预测发生, 实际也发生, 正确 - 中间 : 状态为 11, 预测发生, 实际也发生, 正确 - 最后一次 : 状态为 11, 预测发生, 但实际不发生, 错

42 举例 : 双重循环的两位动态预测 into sum (int N) { int i, j, sum=0; for (i=0; i < N; i++) for (j=0; j <N; j++) sum=sum+1; return sum; } Loop-i: beq $t1,$a0, exit-i # 若 ( i=n) 则跳出外循环 add $t2, $zero, $zero #j=0 Loop-j: beq $t2, $a0, exit-j # 若 (j=n) 则跳出内循环 addi $t2, $t2, 1 # j=j+1 addi $t0, $t0, 1 #sum=sum+1 j Loop-j exit-j: addi $t1, $t1, 1 # i=i +1 j Loop-i exit-i: 外循环中的分支指令共执行 N+1 次, 内循环中的分支指令共执行 N (N+1) 次 N=10, 分别 90.9% 和 90.9% N=100, 分别 99% 和 99% 预测位初始为 00, 外循环只有最后一次预测错误 ; 跳出内循环时预测位变为 01, 再进入内循环时, 第一次预测正确, 只有最后一次预测错误, 因此, 总共有 N 次预测错误 N 越大准确率越高! BACK

43 分支延迟时间片的调度属于静态调度技术, 由编译程序重排指令顺序来实现基本思想 : 把分支指令前面的与分支指令无关的指令调到分支指令后面执行, 以填充延迟时间片 ( 也称分支延迟槽 Branch Delay slot), 不够时用 nop 操作填充举例 : 如何对以下程序段进行分支延迟调度? ( 假定时间片为 2) lw $1, 0($2) lw $3, 0($2) add $6, $4, $2 beq $3, $5, 2 add $3, $3,$2 sw $1, 0($2) 调度后若分支条件判断和目标地址计算提前到 ID 阶段, 则分支延迟时间片减少为 1 lw $3, 0($2) add $6, $4, $2 beq $3, $5, 2 lw $1, 0($2) nop add $3, $3,$2 sw $1, 0($2) lw $3, 0($2) add $6, $4, $2 beq $3, $5, 2 lw $1, 0($2) add $3, $3,$2 sw $1, 0($2) 调度后可能带来其他问题 : 产生新的 load-use 数据冒险调度后, 降低了分支延迟损失 BACK

44 另一种控制冒险 : 异常和中断异常和中断会改变程序的执行流程某条指令发现异常时, 后面多条指令已被取到流水线中正在执行例如指令发现溢出时, 已经到 EX 阶段结束了, 此时, 它后面已有两条指令进入流水线了流水线数据通路如何处理异常? ( 举例说明 ) 假设指令 add r1,r2,r3 产生了溢出 ( 记住 :MIPS 异常处理程序的首地址为 0x ) 处理思路 : 清除 add 指令以及后面的所有已在流水线中的指令关中断 ( 将中断允许触发器清 0) 保存 PC 或 PC+4( 断点 ) 到 EPC 0x 送 PC( 从 0x 处开始取指令 )

45 异常的处理异常 ( 溢出 ) 在第一条指令的 EXE 阶段被检出 Time (clock cycles) I IF ID/RF EX MEM WB n add r1,r2,r3 Im Reg s t r. sub r4,r2,r3 Im Reg O r d e r and r6,r1,r4 问题 : 会发生将溢出结果写到寄存器 r1 中去的情况吗? 阻塞点 Im bubble bubble bubble bubble bubble bubble bubble bubble bubble bubble 不会!EX.Flush 使 EXE 段指令的控制信号清 0( 主要保证 RegWr 清 0), 避异常处理 : 免了在 WB 阶段写寄存器 r1 的情况 IF.Flush 使 IF 段指令在 IF/ID 寄存器中清为 0, 变成 nop 指令 ID.Flush 与数据冒险阻塞检测信号相或 (or) 后, 使 ID 段指令的控制信号清 0 EX.Flush 使 EX 段指令的控制信号清 0 关中断, 并将断点 ( 可能是 PC 可能是 PC+4) 保存到 EPC 中将 0x 作为 PC 的一个输入, 并控制 PC 输入端的多路选择器 Im Reg Dm

46 带异常处理的流水线数据通路 Overflow H

47 流水线方式下的异常处理的难点问题流水线中同时有 5 条指令, 到底是哪一条发生异常? 根据异常发生的流水段可确定是哪条指令, 因为各类异常发生的流水段不同溢出在 EXE 段检出无效指令在 ID 段检出除数为 0 在 ID 段段检出无效指令地址在 IF 段检出无效数据地址在 Load/Store 指令的 EXE 段检出外部中断与特定指令无关, 如何确定处理点? 可在 IF 段或 WB 段中进行中断查询, 需要保证当前 WB 段的指令能正确完成, 并在有中断发生时, 确保下个时钟开始执行中断服务程序检测到异常时, 指令已经取出多条, 当前 PC 的值已不是断点, 怎么办? 指令地址存放在流水段 R, 可把这个地址送到 EPC 保存, 以实现精确中断 ( 非精确中断不能提供准确的断点, 而由操作系统来确定哪条指令发生了异常 ) 一个时钟周期内可能有多个异常, 该先处理哪个? 异常 : 检出异常后, 存到专门寄存器中 ( 前面指令优先级高?) 中断 : 在中断查询程序或中断优先级排队电路中按顺序查询系统中只有一个 EPC, 多个中断发生时, 一个 EPC 不够放多个断点, 怎么办? 总是把优先级最高的送到 EPC 中在异常处理过程中, 又发生了新的异常或中断, 怎么办? 利用中断屏蔽和中断嵌套机制来处理后面三个问题在第九章中详细介绍!

48 复习 :Cache 的操作过程如果被访问的信息不在 cache 中, 称为失效 (miss) 硬件如何进行缺失处理? 缺失处理如果被访问的信息在 cache 中, 称为命中 (hit)

49 Cache 缺失处理会引起流水线阻塞 ( 停顿 ) 在使用 Cache 的系统中, 数据通路中的 IM 和 DM 分别是 Code Cache 和 Data Cache CPU 执行指令过程中, 取指令或取数据时, 如果发生缺失, 则指令执行被阻塞 Cache 缺失的检测 ( 如何进行的? 记得吗?) Cache 中有相应的检测线路 ( 地址高位与 Cache 标志比较 ) 阻塞处理过程冻结所有临时寄存器和程序员可见寄存器的内容 ( 即 : 使整个计算机阻塞 ) 由一个单独的控制器处理 Cache 缺失, 其过程 ( 假定是指令缺失 ) 还记得吗?: - 把发生缺失的指令地址 (PC- 4) 所在的主存块首址送到主存 - 启动一次主存块读操作, 并等待主存完成一个主存块 (Cache 行 ) 的读操作 - 把读出的一个主存块写到 Cache 对应表项的数据区 ( 若对应表项全满的话, 还要考虑淘汰掉一个已在 Cache 中的主存块 ) - 把地址高位部分 ( 标记 ) 写到 Cache 的 tag 字段, 并置有效位 - 重新执行指令的第一步 : 取指令若是读数据缺失, 其处理过程和指令缺失类似 - 从主存读出数据后, 从取数那一步开始重新执行就可以了若是写数据缺失, 则要考虑用哪种写策略解决一致性问题比数据相关或分支指令引起的流水线阻塞简单 : 只要保持所有寄存器不变与中断引起的阻塞处理不同 : 不需要程序切换

50 TLB 缺失和缺页也会引起流水线阻塞 TLB 缺失处理当 TLB 中没有一项的虚页号与要找的虚页号相等时, 发生 TLB miss TLB miss 说明可能发生以下两种情况之一 : - 页在内存中 : 只要把主存中的页表项装载到 TLB 中 - 页不在内存中 ( 缺页 ):OS 从磁盘调入一页, 并更新主存页表和 TLB 缺页 (page fault) 处理当主存页表的页表项中 valid 位为 0 时, 发生 page fault Page fault 是一种故障异常, 按以下过程处理 (MIPS 异常处理 ) - 在 Cause 寄存器置相应位为 1 - 发生缺页的指令地址 (PC- 4) 送 EPC - 0x ( 异常查询程序入口 ) 送 PC 执行 OS 的异常查询程序, 取出 Cause 寄存器中相应的位分析, 得知发生了缺页, 转到缺页处理程序执行 page fault 一定要在发生缺失的存储器操作时钟周期内捕获到, 并在下个时钟转到异常处理, 否则, 会发生错误 - 例 :lw $1, 0($1), 若没有及时捕获异常而使 $1 改变, 则再重新执行该指令时, 所读的内存单元地址被改变, 发生严重错误! 处理 Cache 缺失和缺页的不同之处在哪里? 哪种要进行程序切换?

51 ( 缺页 ) 异常处理时要考虑的一些细节缺页异常结束后, 回到哪里继续执行? 指令缺页 : 重新执行发生缺页的指令数据缺页 : - 简单指令 ( 仅一次访存 ): 强迫指令结束, 重新执行缺页指令 - 复杂指令 ( 多次访存 ): 可能会发生多次缺页, 指令被中止在中间某个阶段, 缺页处理后, 从中间阶段继续执行 ; 因而, 需要能够保存和恢复中间机器状态异常发生后, 又发生新的异常, 怎么办? 在发现异常转到异常处理程序中, 若在保存正在运行进程的状态时又发生新的异常, 则因为要处理新的异常, 会把原来进程的状态和保存的返回断点破坏掉, 所以, 应该有一种机制来禁止响应新的异常处理通过中断 / 异常允许状态位 ( 或中断 / 异常允许触发器 ) 来实现中断 / 异常允许状态位置 1, 则开中断 ( 允许异常 ), 清 0 则关中断 ( 禁止异常 ) 也可由 OS 通过管态指令来设置该位的状态

52 三种处理器实现方式的比较单周期多周期多周期流水线三种方式比较假设各主要功能单元的操作时间为 : 存储单元 :200ps 和加法器 :100ps 寄存器堆 ( 读 / 写 ):50ps 假设 MUX 控制单元控制单元 PC 扩展器和传输线路都没有延迟, 指令组成为 : 25% 取数 10% 存数 52% 11% 分支 2% 跳转则下面实现方式中, 哪个更快? 快多少? (1) 单周期方式 : 每条指令在一个固定长度的时钟周期内完成 (2) 多周期方式 : 每类指令时钟数 : 取数 -5, 存数 -4,-4, 分支 -3, 跳转 -3 (3) 流水线方式 : 每条指令分取指令取数取数 / 译码执行执行存储器存取存储器存取写回五阶段 ( 假定没有结构冒险, 数据冒险采用转发处理, 分支延迟槽为 1, 预测准确率为 75%; 不考虑异常中断和访问缺失引起的流水线冒险 )

53 三种处理器实现方式的比较解 :CPU 执行时间 = 指令条数 x CPI x 时钟周期长度三种方式的指令条数都一样, 所以只要比较 CPI 和时钟周期长度即可各指令类型要求的时间长度为 :

54 三种处理器实现方式的比较对于单周期方式 : 时钟周期将由最长指令来决定, 应该是 load 指令, 为 600ps 所以,N 条指令的执行时间为 600N(ps) 对于多周期方式 : 时钟周期将取功能部件最长所需时间, 应该是存取操作, 为 200ps 根据各类指令的频度, 计算平均时钟周期数为 : CPU 时钟周期 =5x25%+4x10%+4x52%+3x11%+3x2%=4.12 所以, N 条指令的执行时间为 4.12x200xN=824N(ps) 对于流水线方式 : Load 指令 : 当发生 Load-use 依赖时, 执行时间为 2 个时钟, 否则 1 个时钟, 故平均执行时间为 1.5 个时钟 ; Store 指令 :1 个时钟 ; Branch 指令 : 预测成功时,1 个时钟, 预测错误时,2 个时钟, 所以 : 平均约为 :.75x1+.25x2=1.25 个 ; Jump 指令 :2 个时钟 ( 总要等到译码阶段结束才能得到转移地址 ) 平均 CPI 为 :1.5x25%+1x10%+1x52%+1.25x11%+2x2%=1.17 所以, N 条指令的执行时间为 1.17x200xN=234N(ps)

55 流水线冒险对程序性能的影响结构冒险对浮点运算的性能影响较大, 因为浮点运算单元不能有效被流水化, 可能造成运算单元的资源冲突控制冒险更多出现在整数运算程序中, 因为分支指令对应于循环或选择结构, 大多由整数运算结果决定分支数据冒险在整数运算程序和浮点运算程序中都一样浮点程序中的数据冒险容易通过编译器优化调度来解决 - 分支指令少 - 数据访问模式较规则整数程序的数据冒险不容易通过编译优化调度解决 - 分支指令多 - 数据访问模式不规则 - 过多使用指针

56 小结流水线冒险的几种类型 : 资源冲突数据相关数据相关控制相关 ( 改变指令流的执行方向 ) 数据冒险的现象和对策数据冒险的种类 - 相关的数据是结果, 可以通过转发解决 - 相关的数据是 DM 读出的内容, 随后的指令需被阻塞一个时钟数据冒险和转发 - 转发检测 / 转发控制数据冒险和阻塞 - 阻塞检测 / 阻塞控制控制冒险的现象和对策静态分支预测技术缩短分支延迟技术动态分支预测技术异常和中断是一种特殊的控制冒险访存缺失 (Cache 缺失 TLB 缺失缺页缺页 ) 会引起流水线阻塞

<4D F736F F F696E74202D20B5DAC1F9D5C220D7F7D2B5B2CEBFBCB4F0B0B8>

<4D F736F F F696E74202D20B5DAC1F9D5C220D7F7D2B5B2CEBFBCB4F0B0B8> 第六章利用流水线提高性能作业参考答案参考答案 : P.373 中 ALU 操作时间为 200ps a. ALU 操作时间缩短 25% 不能加快流水线指令速度因为流水线的速度最终由时钟周期的宽度决定, 而它不会缩短时钟周期 b. 如果 ALU 操作时间延长 25%, 那么,ALU 时间将变为 250ps, 这样,ALU 操作将变成瓶颈, 使得流水线的时钟周期为 250ps, 其效率降低 (250-200)/250=20%