第六章利用流水线提高性能 作业参考答案
参考答案 : P.373 中 ALU 操作时间为 200ps a. ALU 操作时间缩短 25% 不能加快流水线指令速度 因为流水线的速度最终由时钟周期的宽度决定, 而它不会缩短时钟周期 b. 如果 ALU 操作时间延长 25%, 那么,ALU 时间将变为 250ps, 这样,ALU 操作将变成瓶颈, 使得流水线的时钟周期为 250ps, 其效率降低 (250-200)/250=20%
参考答案 : a. 一个程序核心模块共 10 6 条指令, 每条指令花 100ps 完成, 则在非流水线处理器上执行的时间为 :100 x10 6 =100us. b. 若在一个 20 级流水线的处理器上执行, 理想情况下, 每个时钟周期为 :100/20=5ps, 所以, 程序执行时间为 5 x10 6 =5us. 快了 100/5=20 倍 c. 流水线并不是理想的, 流水线段之间数据的传递会产生额外的开销 一方面, 这种开销使得一条指令的执行时间被延长, 即影响 Instruction latency 另一方面, 这种开销也拉长了每个流水段的执行时间, 即影响 Instruction throughput
参考答案 : 有三个 RAW 数据冒险, 其中一个是 load-use 数据冒险, 需要 阻塞 一个时钟
参考答案 : 有四个 RAW 数据冒险 (1) 第一条 add 指令和第二条 sub 指令之间 (2) 第一条 add 指令和第三条 lw 指令之间 (3) 第一条 add 指令和第四条 add 指令之间 (4) 第三条 lw 指令和第四条 add 指令之间其中,(1) (2) 和 (3) 是关于寄存器 $3 的数据冒险, 可以通过 转发 解决 (4) 是关于寄存器 $6 的数据冒险, 是 load-use 数据冒险, 不能通过 转发 解决, 将发生一次 阻塞
参考答案 : 图 6.36 是一个带 冒险 检测和 转发 处理的五阶段流水线数据通路 第五个时钟结束时, 各条指令的执行情况如下 : 第一条指令在 WB 阶段, 寄存器 $2 正被写入第二条指令在 MEM 阶段,sub 指令是 NOOP 操作第三条指令在 EXE 阶段,ALU 正在执行 add 操作第四条指令在 ID/REG 阶段, 寄存器 $6 和 $1 正被读出第五条指令在 IF 阶段, 指令正被读出
ID/EX.MemRead and (ID/EX.RegisterRt=IF/ID.RegisterRs or ID/EX.RegisterRt=IF/ID.RegisterRt) C1 P.416 图 6.36 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
参考答案 : 第 6.17 题中的 指令序列为 : 第五个时钟中, 各条指令的执行情况如下 : 指令 1 在 WB 阶段, 控制信息等在 MEM/WB.Reg 中指令 2 在 MEM 阶段, 控制信息等在 EX/MEM.Reg 中指令 3 在 EXE 阶段, 控制信息等在 ID/EX.Reg 中指令 4 在 ID/REG 阶段, 指令在 IF/ID.Reg 中指令 5 在 IF 阶段, 指令正被读出 转发 检测条件为 : 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 根据以上 转发 检测条件, 得到比较结果为 : C1: EX/MEM.RegWrite=1(sub 指令 ) EX/MEM. RegisterRd($4) 0 EX/MEM. RegisterRd ($4) ID/EX. RegisterRs($3) EX/MEM. RegisterRd($4) ID/EX. RegisterRt($5) C2: MEM/WB.RegWrite=1 (add 指令 ) and MEM/WB. RegisterRd ($2) 0 MEM/WB. RegisterRd($2) ID/EX. RegisterRs($3) MEM/WB. RegisterRd($2) ID/EX. RegisterRt($7) 由此可知 :C1 和 C2 都不满足 转发 条件, 所以不需要转发
参考答案 : 第 6.17 题中的 指令序列为 : 第五个时钟中, 各条指令的执行情况如下 : 指令 1 在 WB 阶段, 控制信息等在 MEM/WB.Reg 中指令 2 在 MEM 阶段, 控制信息等在 EX/MEM.Reg 中指令 3 在 EXE 阶段, 控制信息等在 ID/EX.Reg 中指令 4 在 ID/REG 阶段, 指令在 IF/ID.Reg 中 指令 5 在 IF 阶段, 指令正被读出 Hazard ( 冒险 ) 检测条件为 : ID/EX.MemRead and ID/EX.RegisterRt=IF/ID.RegisterRs or ID/EX.RegisterRt=IF/ID.RegisterRt) 根据以上 冒险阻塞 检测条件, 得到比较结果为 : ID/EX.MemRead=0(add 指令 ) ID/EX. RegisterRt($5) IF/ID. RegisterRs ($6) ID/EX. RegisterRt($5) IF/ID. RegisterRt($1) 说明 : 因为当前在 EXE 阶段的指令为 add, 所以目的地址应该为 Rd 而不是 Rt 所以, ID/EX. RegisterRt 为寄存器 $5 而不是 $3! 由此可知 : 不满足 冒险 条件, 所以不需要阻塞
参考答案 : a. 因为 lw 指令和 add 指令之间存在一个 load- use 数据冒险 ( 满足图 6.36 中数据冒险检测条件 ), 所以每个 lw 指令和 add 指令之间要有一次流水线阻塞 而 add 指令和 lw 指令之间的数据冒险满足图 6.36 中的 转发 检测条件, 故可通过数据转发解决冒险 即 : 实际的 CPI 为 1.5 b. 如果没有转发, 则在每条 lw 指令和 add 指令之间将会有两个阻塞, 这样每条指令相当于都要有三个时钟才能完成 即 :CPI 为 3
使用 转发 的情况 : Time (clock cycles) I n s t r. O r d e r add r1,r2,r3 lw r4,0(r1) add r6,r4,r7 lw r8,0(r6) IF ID/RF EX MEM WB ALU Im Reg Dm Reg ALU Im Reg Dm Reg stall Im Reg bubble bubble bubble Im Reg Dm Reg ALU Im Reg ALU Dm 使用 转发 时, 只有 lw 指令后需要一次阻塞!
不使用 转发 的情况 : Time (clock cycles) I n s t r. O r d e r add r1,r2,r3 stall stall lw r4,0(r1) stall stall add r6,r4,r7 IF ID/RF EX MEM WB ALU Im Reg Dm Reg Im bubble bubble bubble bubble Im bubble bubble bubble bubble Im Reg Dm Reg ALU Im bubble bubble bubble Im bubble bubble Im Reg 通过寄存器写口 / 读口分别安排在前半 / 后半周期, 在不使用 转发 时使得每条指令之间只要阻塞两次就可解决!
参考答案 : 从后面的图中可以看出 : 若采用 转发 技术, 则执行这段代码需要 8 个时钟周期若不采用 转发 技术, 则执行这段代码需要 11 个时钟周期
I n s t r. O r d e r lw $4,100($2) sub $6,$4,$3 add $2,$3,$5 Time (clock cycles) IF ID/RF EX MEM WB ALU Im Reg Dm Reg ALU Im Reg Dm Reg Im Reg Dm Reg ALU 寄存器 $4 在第四时钟周期结束时才有值, 但 sub 指令在第四周期开始就要用, 所以必须使 sub 指令延迟一个周期执行!
使用转发时的情况 : I n s t r. lw $4,100($2) Time (clock cycles) IF ID/RF EX MEM WB ALU Im Reg Dm Reg Sub->nop Im Reg bubble bubble bubble O r d e r sub $6,$4,$3 add $2,$3,$5 ALU Im Reg Dm Reg Im Reg Dm Reg ALU 在 EX 阶段内, 通过 冒险 检测, 发现有一个数据冒险存在, 在 EX 阶段结束前进行阻塞, 做 : 1) 使 sub 指令控制信号冲刷为 0,Sub 操作变为 nop 2) 使 IF/ID 流水段中的 Sub 指令不被 add 指令冲掉, 下个周期继续对 sub 指令译码 3) 使当前 PC 不变, 下个周期继续取 add 指令
不使用转发时的情况 : I n s t r. add r1,r2,r3 stall stall Time (clock cycles) IF ID/RF EX MEM WB ALU Im Reg Dm Reg Im bubble bubble bubble bubble Im bubble bubble bubble bubble O r d e r lw r4,0(r1) stall stall add r6,r4,r7 Im Reg Dm Reg ALU Im bubble bubble bubble Im bubble bubble Im Reg 通过寄存器写口 / 读口分别安排在前半 / 后半周期, 在不使用 转发 时使得每条指令之间只要阻塞两次就可解决!
参考答案 : 图 6.36 中 转发 检测条件和控制信号为 : 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 ForwardA (ForwardB) = 01 当 c2=1 时 10 当 c1=1 时 由此可见, 图 6.36 中 转发 单元的输入和输出为 :
参考答案 : 各类指令所用功能部件的时间为 存储器操作变为两个时钟周期后, 其单周期数据通路的时钟周期不变, 为 600ps 而多周期数据通路中, 各类指令的时钟周期变为 : load:7;store:6;alu:5;beq:4;jump:4 以 SPECINT2000 混合指令比例计算,CPI=0.25x7+0.10x6+0.52x5+0.11x4+0.02x4 = 5.47 存储器操作变为两个时钟周期后, 多周期数据通路的时钟周期为 100ps, 故一条指令的执行时间为 100x5.47=547ps 比较结果 : 多周期比单周期快!
参考答案 : 存储器操作变为两个时钟周期后, 其流水线包含了以下 7 个阶段 : instruction1 instruction2 instruction3 instruction4 当第一条指令为 lw 指令时,instruction1-4 的执行情况由咖啡色 ( 不能转发 ) 和红色 ( 可转发 ) 表示 instruction1 需要 2 个 stall ; instruction2 需要 1 个 stall ; 后续指令 3 可以通过 转发 解决 ( 后续指令 4 不是数据冒险 ) 当第一条指令为 ALU 指令时,instruction1-4 的执行情况由兰色表示 说明后续所有的数据冒险都可以通过 转发 解决 ( 后续指令 4 不是数据冒险 )
参考答案 : 根据 P425 中的例子, 已知 : 各主要功能单元的操作时间为 : 存储单元 :200ps ( 被分成 100ps 的两个阶段 ) ALU 和加法器 :100ps 寄存器堆 ( 读 / 写 ):50ps 假设 MUX 控制单元 PC 扩展器和传输线路都没有延迟, 指令组成为 : 25% 取数 10% 存数 52%ALU 11% 分支 2% 跳转则下面实现方式中, 哪个更快? 快多少? (1) 单周期方式 : 每条指令在一个固定长度的时钟周期内完成 (2) 流水线方式 : 取指 1 取指 2 取数/ 译码 执行 存取 1 存取 2 写回七个阶段
对于单周期方式 : 时钟周期将由最长指令来决定, 应该是 load 指令, 为 600ps 所以,N 条指令的执行时间为 600N(ps) 对于流水线方式 : 存储器操作变为两个时钟周期后, 其流水线包含了 7 个阶段. 对于 beq, 若预测正确, 则为 1 个周期, 若预测错误, 则为 3 个周期 ( 与原五段流水线相比, 多一个取指周期, 多阻塞了 1 个周期 ), 故 CPI=1/4x3+3/4x1=1.5 对于 load, 随后第一条则为 3 个 ( 阻塞 2 个 ) 周期 ; 随后第二条则为 2 个 ( 阻塞 1 个 ) 周期, 以后的指令都不需要阻塞, 故 CPI=1/2x3+1/2x1/4x2+3/8x1=2.125 对于 ALU 指令, 随后的数据相关指令都可通过转发解决, 故 CPI=1 对于 Store 指令, 不会发生数据冒险, 故 CPI=1 对于 Jump 指令, 总要等到译码结束才能确定转移地址, 故 CPI=3 平均 CPI 为 :2.125x25%+1x10%+1x52%+1.5x11%+3x2%=1.38 所以, N 条指令的执行时间为 1.38x100xN=138N(ps) 流水线比单周期快 600/138=4.38 倍
参考答案 : 根据 6.6.2 节中所指出的, 将分支比较操作提前到 ID 阶段, 会导致来不及通过转发来解决数据冒险 ( 即 : 若不提前的话, 本可以通过转发解决的 ) 当分支指令依赖于仍在流水段中的结果时, 便来不及通过转发来解决 例如, 以下的例子中, 如果分支比较不提前, 则 add 指令 EXE 阶段执行的结果 ( 在 EX/MEM 流水段寄存器 ) 可以转发给 beq 指令的 EXE 阶段进行比较 ( 红线 ), 但如果 beq 指令在 ID 阶段比较的话, 就来不及转发了 ( 兰线 ) lw $1, 100 ($2) add $1, $1, 8 beq $1, $3, 10 ALU Im Reg Dm Reg ALU Im Reg Dm Reg 在给出的例子中, 第一条指令和第二条指令中还有一个 load-use 数据冒险, 也不能通过转发来消除 所以, 该例中 1-2 之间的 阻塞 和 2-3 之间的 转发 都不可通过转发来消除!
参考答案 : 预测准确率 = 预测正确次数 / 总预测时间 *100% a. B1: R-3, W-0; B2: R-0, W-4; B3: R-3, W-3; B4: R-4, W-1; B5: R-5, W-2;60% b. B1: R-0, W-3; B2: R-4, W-0; B3: R-3, W-3; B4: R-1, W-4; B5: R-2, W-5;40% c. B1: R-3, W-0; B2: R-3, W-1; B3: R-1, W-5; B4: R-3, W-2; B5: R-3, W-4;52% d. B1: R-3, W-0; B2: R-3, W-1; B3: R-3, W-3; B4: R-4, W-1; B5: R-5, W-2;72%
参考答案 : 要使得上述代码段的性能最差, 则只要让代码段中出现 load-use 冒险最多 lw $2, 100($6) add $4, $2, $3 lw $3, 200($7) add $6, $3, $7 sub $8, $4, $6 lw $7, 300($8) beq $7, $8, Loop 这样做有什么问题吗?
参考答案 : 从给定的图可以看出,beq 指令是在 ID 段确定是否转移, 并计算转移地址的 当判断要转移 (taken) 时,ID 段会产生一个 Flush 信号, 使得下一条已被取出的指令 (lw) 被清 0, 并控制将转移地址送 PC, 流水线被阻塞一个时钟后, 从转移地址处开始执行 故不会同时发生 Flush 和 Stall 假定 beq 指令的分支判断和转移地址计算没有提前, 还是在 MEM 阶段时, 则在 MEM 阶段会产生一个 Flush 信号, 此时, 在 ID 阶段同时检测到 load-use 冲突, 并引起一次 stall 因此, 这种情况下,Flush 和 Stall 会同时发生
Figure6.45 on P.461 题意 : 图中 冲突 检测和 分支判断 是否可能同时分别要求进行 阻塞 和 冲刷?
带静态分支预测处理的数据通路 IF.Flush=Br. and Eq. 40# 指令 beq $1,$3, 7 的 ID 阶段 转移目标地址 (72)->PC 控制转移目标地址 ->PC 将 IF/ID 中指令字清 0, 变为 nop 指令
Beq 前面的指令还在流水线中继续执行, 没有任何影响 使指令转到 72 处执行上条错取指令变成了 bubble BACK
带 转发 和 阻塞 检测的流水线数据通路 使控制信号清 0, 阻塞随后指令! 1 ID/EX.MemRead and (ID/EX.RegisterRt=IF/ID.RegisterRs or ID/EX.RegisterRt=IF/ID.RegisterRt) 2 3 使 写使能 信号为 0, 使 PC 和 IF/ID 不变!
Zero 同时检测到 Flush 和 Stall 时, 会产生矛盾, 此时, 必须保证 Flush 的优先级更高! 可以将两个检测电路合在一起, 并加上并行判优电路
循环中, 有 2 个 load-use 冒险和一个控制冒险 (3 次阻塞 ), 所以共有 5 次阻塞, 因而每次循环共需 8+5=13 个周期 这样对吗? 不采用任何预测时, 如是! 采用静态预测 ( 初始预测转移 ) 时, 怎样? 最后 1 次循环需 8+5=13 个周期, 前面各次预测都能成功, 故只需 8+2=10 个周期 不预测时, 优化调度指令顺序后, 消除了 load-use 参考答案 : 优化调度后的代码段为 : 冒险, 有一个控制冒险 (3 次阻塞 ), 因而每次循环共需 8+3=11 个周期 总的操作次数为 400/4=100 次, 循环次数为 100/2=50 次, 所以优化后的程序用 11x50=550 个周期原程序为 13x50=650 个周期所以, 性能提高了 650/550=1.18 倍采用简单静态预测 ( 初始预测转移 ) 时, 性能如何? 最后 1 次需 8+3=11 个周期, 前面各次只需 8 个周期优化后的程序用 11x1+8x49=403 个周期原程序为 13x1+10x49=503 个周期性能各提高了 650/503=1.29,550/403=1.36 优化后提高了 503/403=1.25 倍
参考答案 : 题目给出的一次循环展开代码中循环体有三条指令 (lw,sub 和 sw), 已知循环次数是 2 的倍数, 将循环体展开三次后, 循环结束条件的判断要作相应的调整, 以保证展开后的代码能得到正确的结果 展开为 3 次后, 操作次数可能的情况为 3 6 9 12 15 18, 故对于 4 6 8 10 12 14 16 18 的操作次数来说, 有以下三种可能 : 1) 操作次数是 4 10 16, 按 3 的倍数循环的对应次数为 3 9 15, 少了 1 次 2) 操作次数是 6 12 18, 正好既是 3 的倍数, 又是 2 的倍数, 不多不少 3) 操作次数是 8 14 20, 按 3 的倍数循环的对应次数为 6 12 18, 少了 2 次 所以, 需要在代码中加入操作次数调整部分
循环展开 3 次的代码段如右所示 在循环的开始, 判断是否剩下的循环次数小于 3, 是的话, 转到 leftover 进行结束前处理 ; 否则, 进入循环在循环中, 判断循环次数是否正好是 3 的倍数, 是的话, 则直接跳转到结束 (finish 处 ) 在结束前处理中, 先补充操作一次, 然后判断是否结束, 是的话, 跳转到结束 (finish 处 ); 否则, 再补充操作一次 右边代码段的性能分析如下 : 1) 控制冒险 : 循环内有两条分支指令 bgt bne; 循环外有一条 jump 指令 (1 次阻塞 ) 和一条分支指令 2)load-use 冒险 :1 次或 2 次总操作次数为 400/4=100, 则循环次数为 100/3=33 次, 补充 1 次操作总的周期数为 (12+3+3)x33+1+4+2+3+4=608 比前面两种代码的性能分别提高了 650/608=1.07 倍 550/608=0.90 倍 周期数计算是在无预测的情况下进行的 假定采用简单静态预测方法, 则结果应该不同!
采用静态预测 ( 初始预测转移 ) 时, 性能分析如下 : 总操作次数为 400/4=100, 循环次数为 100/3=33 次, 补充 1 次操作 1) 控制冒险 : bgt 只在最后 1 次转移, 第一次和最后一次预测错误 ; bne 指令每次都发生转移, 无预测错误 ; beq 指令发生转移, 无预测错误 ; jump 指令发生一次阻塞 2)load-use 冒险 :1 次或 2 次总的周期数为 : (12+3)x1+12x32+1+4+2+3+1=410 采用静态预测后, 性能提高了 608/410=1.48 倍 比前面两种代码的性能分别提高了 503/410=1.22 倍 403/410=0.98 倍本题说明了是否优化调度 循环展开次数如何选择 是否采用预测等方面对程序性能的影响 你的结论是什么? 优化调度能消除循环内大量 load-use 冒险, 性能约提高 20%; 循环展开次数选择不当会影响性能, 降低 2%-10%; 采用预测会大大提高性能, 约提高 30%-59%
参考答案 : 将代码段中的循环展开四次, 放在一个 2 发射 MIPS 流水线中执行时, 可以按以下方式进行调度 ALU 或 Branch lw 或 sw Loop: addi $20, $10, 0 lw $2, 0($10) lw $5, 4($10) sub $4, $2, $3 lw $7, 8($10) sub $6, $5, $3 lw $9, 12($10) sub $8, $7, $3 sw $4, 0($10) sub $11, $9, $3 sw $6, 4($10) 用重命名机制避免了寄存器 $10 在最后两行中的名字依赖关系 name Dependence( 或反依赖关系 antidependence, 不是真实依赖 ) 用 $20 替换了 $10 这种超标量方式下, 其性能又如何呢? addi $10, $10, 16 sw $8, 8($20) bne $10, $30, loop sw $11, 12($20)