如何进行指令调度使其执行延迟时间最短？进行指令调度所获得的加速比是多少
答案:2 悬赏:0 手机版
解决时间 2021-02-15 03:07
- 提问者网友：星軌
- 2021-02-14 17:21
如何进行指令调度使其执行延迟时间最短？进行指令调度所获得的加速比是多少
最佳答案
- 五星知识达人网友：神鬼未生
- 2021-02-14 18:06
4.3 根据需要下面的循环并进行指令调度，直到没有任何延迟。指令的延迟如表4.4。
LOOP: L.D F0,0(R1)
MUL.D F0,F0,F2
L.D F4,0(R2)
ADD.D F0,F0,F4
S.D F0,0(R2)
DSUBI R1,R1,#8
DSUBI R2,R2,#8
BNEZ R1,LOOP
解:将循环两次，进行指令调度，即可以消除延迟，代码如下:
LOOP: L.D F0，0(R1)
L.D F10，-8(R1)
MUL.D F0，F0，F2
MUL.D F10，F10，F2
L.D F4，0(R2)
L.D F14，-8(R2)
ADD.D F0，F0，F4
ADD.D F10，F10，F14
DSUBI R1，R1，16
S.D 0(R2)，F0
DSUBI R2，R2，16
BNEZ R1，LOOP
S.D 8(R2)，F10
4.4 假设有一条长流水线，仅仅对条件转移指令使用分支目标缓冲。假设分支预测错误的开销为4个时钟周期，缓冲不命中的开销为3个时钟周期。假设:命中率为90%，预测精度为90%，分支频率为15%，没有分支的基本CPI为1。
(1) 求程序执行的CPI。
(2) 相对于采用固定的2个时钟周期延迟的分支处理，哪种方法程序执行速度更快?
解:(1)程序执行的CPI = 没有分支的基本CPI(1) + 分支带来的额外开销
分支带来的额外开销是指在分支指令中，缓冲命中但预测错误带来的开销与缓冲没有命中带来的开销之和。
分支带来的额外开销= 15% * (90%命中×10%预测错误×4 + 10%没命中×3)= 0.099
所以，程序执行的CPI = 1 + 0.099 = 1.099
(2)采用固定的2 个时钟周期延迟的分支处理CPI = 1 + 15%×2 = 1.3
由(1)(2)可知分支目标缓冲方法执行速度快。
4.5 假设分支目标缓冲的命中率为90%，程序中无条件转移指令的比例为5%，没有无条件转移指令的程序CPI值为1。假设分支目标缓冲中包含分支目标指令，允许无条件转移指令进入分支目标缓冲，则程序的CPI值为多少?
解:设每条无条件转移指令的延迟为x，则有:
1+5%×x=1.1
x=2
当分支目标缓冲命中时，无条件转移指令的延迟为0。
所以 程序的CPI = 1 + 2 × 5% ×(1 -90%) =1.01
4.6 下面的一段MIPS汇编程序是计算高斯消去法中的关键一步，用于完成下面公式的计算:
Y = a X + Y
其浮点指令延迟如表4.3所示，整数指令均为1个时钟周期完成，浮点和整数部件均采用流水。整数操作之间以及与其它所有浮点操作之间的延迟为0，转移指令的延迟为0。X中的最后一个元素存放在存储器中的地址为DONE。
FOO: L.D F2,0(R1)
MUT.D F4,F2,F0
L.D F6,0(R2)
ADD.D F6,F4,F6
S.D F6,0[R2]
DADDIU R1,R1,#8
DADDIU R2,R2,#8
DSUBIU R3,R1,#DONE
BNEZ R3, FOO
(1) 对于标准的MIPS单流水线，上述循环计算一个Y值需要多少时间?其中有多少空转周期?
(2) 对于标准的MIPS单流水线，将上述循环顺序4次，不进行任何指令调度，计算一个Y值平均需要多少时间?加速比是多少?其加速是如何获得的?
(3) 对于标准的MIPS单流水线，将上述循环顺序4次，优化和调度指令，使循环处理时间达到最优，计算一个Y值平均需要多少时间?加速比是多少?
(1) 对于采用如图4.8前瞻执行机制的MIPS处理器(只有一个整数部件)。当循环第二次执行到
BNEZ R3,FOO
时，写出前面所有指令的状态，包括指令使用的保留站、指令起始节拍、执行节拍和写结果节拍，并写出处理器当前的状态。
(2) 对于2路超标量的MIPS流水线，设有两个指令流出部件，可以流出任意组合的指令，系统中的功能部件数量不受限制。将上述循环4次，优化和调度指令，使循环处理时间达到最优。计算一个Y值平均需要多少时间?加速比是多少?
(3) 对于如图4.13结构的超长指令字MIPS处理器，将上述循环4次，优化和调度指令，使循环处理时间达到最优。计算一个Y值平均需要多少时间?加速比是多少?
解:(1)
L.D F2, 0(R1) 1
Stall
MUT.D F4, F2, F0 2
L.D F6, 0(R2) 3
Stall
Stall
ADD.D F6, F4, F6 4
Stall
Stall
S.D F6, 0[R2] 5
DADDIU R1, R1, #8 6
DADDIU R2, R2, #8 7
DSUBIU R3, R1, #DONE 8
BNEZ R3, FOO 9
所以，共有14 个时钟周期，其中有5 个空转周期。
(2)循环顺序4 次，不进行任何指令调度，则指令1~5 及其间的stall 都是必要的，只是指令6~9 只需执行一次，因此，共有 10 × 4 + 4 = 44 个时钟周期，计算出4 个Y 值，所以计算一个Y 值需要11 个时钟周期，加速比为:14/11 = 1.27 。加速主要是来自减少控制开销，即减少对R1、R2 的整数操作以及比较、分支指令而来的。
(3)循环顺序4 次，优化和调度指令，如下:
L.D F2, 0(R1)
L.D F8, 8(R1)
L.D F14, 16(R1)
L.D F20, 24(R1)
MUT.D F4, F2, F0
MUT.D F10, F8, F0
MUT.D F16, F14, F0
MUT.D F22, F20, F0
L.D F6, 0(R2)
L.D F12, 8(R2)
L.D F18, 16(R2)
L.D F24, 24(R2)
ADD.D F6, F4, F6
ADD.D F12, F10, F12
ADD.D F18, F16, F18
ADD.D F24, F22, F24
S.D F6, 0[R2]
S.D F12, 8[R2]
S.D F18, 16[R2]
S.D F24, 24[R2]
DADDIU R1, R1, #32
DADDIU R2, R2, #32
DSUBIU R3, R1, #DONE
BNEZ R3, FOO
共用了24 个时钟周期，则计算一个Y 值平均需要 24/4 = 6 个时钟周期，
加速比:14/6 = 2.33
(4)
指令 指令执行时钟
流出 执行 写结果 确认
L.D F2, 0(R1) 1 2 3 4
MUL.D F4, F2, F0 2 4 5 6
L.D F6, 0(R2) 3 4 6 7
ADD.D F6, F4, F6 4 8 9 10
S.D F6, 0(R2) 5 11 12 13
DADDIU R1, R1, #8 6 7 8
DADDIU R2, R2, #8 7 8 9
DSUBIU R3,R1,#DONE 8 9 10
BNEZ R3, FOO 9 10
L.D F2, 0(R1) 10 11 13 14
MUL.D F4, F2, F0 11 13 14 15
L.D F6, 0(R2) 12 13 15 16
ADD.D F6, F4, F6 13 17 18 19
S.D F6, 0(R2) 14 20 21 22
DADDIU R1, R1, #8 15 16 17
DADDIU R2, R2, #8 16 17 18
DSUBIU R3,R1,#DONE 17 18 19
BNEZ R3, FOO 18
名称 保留站
Busy Op Vj Vk Qj Qk Dest A
Add1 yes ADD.D Regs[F4] Regs[F6 ]
Add2 no
Add3 no
Mult1 yes
Mult2 no
项号 ROB
Busy 指令 状态 目的 Value
1 yes ADD.D F6, F4, F6 执行 F6 Regs[F4]+Regs[F6]
2 yes S.D F6, 0(R2) 流出 Mem[0+Regs[R2]] #2
字段 浮点寄存器状态
F0 F2 F4 F6 F8 F10 … F30
ROB项编号 1
Busy yes …
(5)
整数指令 浮点指令 时钟周期数
L.D F2, 0(R1) 1
L.D F8, 8(R1) 2
L.D F14, 16(R1) MUT.D F4, F2, F0 3
L.D F20, 24(R1) MUT.D F10, F8, F0 4
L.D F6, 0(R2) MUT.D F16, F14, F0 5
L.D F12, 8(R2) MUT.D F22, F20, F0 6
L.D F18, 16(R2) ADD.D F6, F4, F6 7
L.D F24, 24(R2) ADD.D F12, F10, F12 8
DADDIU R1, R1, #32 ADD.D F18, F16, F18 9
S.D F6, 0(R2) ADD.D F24, F22, F24 10
S.D F12, 8(R2) 11
S.D F18,16(R2) 12
S.D F24, 24(R2) 13
DADDIU R2, R2, #32 14
DSUBIU R3, R1, #DONE 15
BNEZ R3, FOO 16
计算一个Y值需要 16/4 = 4 个时钟周期，加速比 = 14/4 = 3.5
(6)
访存1 访存2 浮点指令1 浮点指令2 整数指令 时钟
周期
L.DF2, 0(R1) L.D F8, 8(R1) 1
L.DF14, 16(R1) L.DF20, 24(R1)
L.DF6, 0(R2) L.DF12, 8(R2) MUT.DF4, F2, F0 MUT.DF10, F8, F0 3
L.DF18, 16(R2) L.DF24, 24(R2) MUT.DF16, F14, F0 MUT.DF22, F20, F0 4
ADD.DF6, F4, F6 ADD.DF12, F10, F12 5
ADD.DF18, F16, F18 ADD.DF24, F22, F24 DADDIU R1, R1, #32 6
DADDIU R2, R2, #32 7
DSUBIUR3, R1, #DONE 8
BNEZ R3, FOO 9
S.DF6, -32(R2) S.DF12, -24(R2) 10
S.DF18,-16(R2) S.DF24, -8(R2) 11
计算一个Y值需要 11/4 个时钟周期，加速比 = 14/(11/4) = 56/11
LOOP: L.D F0,0(R1)
MUL.D F0,F0,F2
L.D F4,0(R2)
ADD.D F0,F0,F4
S.D F0,0(R2)
DSUBI R1,R1,#8
DSUBI R2,R2,#8
BNEZ R1,LOOP
解:将循环两次，进行指令调度，即可以消除延迟，代码如下:
LOOP: L.D F0，0(R1)
L.D F10，-8(R1)
MUL.D F0，F0，F2
MUL.D F10，F10，F2
L.D F4，0(R2)
L.D F14，-8(R2)
ADD.D F0，F0，F4
ADD.D F10，F10，F14
DSUBI R1，R1，16
S.D 0(R2)，F0
DSUBI R2，R2，16
BNEZ R1，LOOP
S.D 8(R2)，F10
4.4 假设有一条长流水线，仅仅对条件转移指令使用分支目标缓冲。假设分支预测错误的开销为4个时钟周期，缓冲不命中的开销为3个时钟周期。假设:命中率为90%，预测精度为90%，分支频率为15%，没有分支的基本CPI为1。
(1) 求程序执行的CPI。
(2) 相对于采用固定的2个时钟周期延迟的分支处理，哪种方法程序执行速度更快?
解:(1)程序执行的CPI = 没有分支的基本CPI(1) + 分支带来的额外开销
分支带来的额外开销是指在分支指令中，缓冲命中但预测错误带来的开销与缓冲没有命中带来的开销之和。
分支带来的额外开销= 15% * (90%命中×10%预测错误×4 + 10%没命中×3)= 0.099
所以，程序执行的CPI = 1 + 0.099 = 1.099
(2)采用固定的2 个时钟周期延迟的分支处理CPI = 1 + 15%×2 = 1.3
由(1)(2)可知分支目标缓冲方法执行速度快。
4.5 假设分支目标缓冲的命中率为90%，程序中无条件转移指令的比例为5%，没有无条件转移指令的程序CPI值为1。假设分支目标缓冲中包含分支目标指令，允许无条件转移指令进入分支目标缓冲，则程序的CPI值为多少?
解:设每条无条件转移指令的延迟为x，则有:
1+5%×x=1.1
x=2
当分支目标缓冲命中时，无条件转移指令的延迟为0。
所以 程序的CPI = 1 + 2 × 5% ×(1 -90%) =1.01
4.6 下面的一段MIPS汇编程序是计算高斯消去法中的关键一步，用于完成下面公式的计算:
Y = a X + Y
其浮点指令延迟如表4.3所示，整数指令均为1个时钟周期完成，浮点和整数部件均采用流水。整数操作之间以及与其它所有浮点操作之间的延迟为0，转移指令的延迟为0。X中的最后一个元素存放在存储器中的地址为DONE。
FOO: L.D F2,0(R1)
MUT.D F4,F2,F0
L.D F6,0(R2)
ADD.D F6,F4,F6
S.D F6,0[R2]
DADDIU R1,R1,#8
DADDIU R2,R2,#8
DSUBIU R3,R1,#DONE
BNEZ R3, FOO
(1) 对于标准的MIPS单流水线，上述循环计算一个Y值需要多少时间?其中有多少空转周期?
(2) 对于标准的MIPS单流水线，将上述循环顺序4次，不进行任何指令调度，计算一个Y值平均需要多少时间?加速比是多少?其加速是如何获得的?
(3) 对于标准的MIPS单流水线，将上述循环顺序4次，优化和调度指令，使循环处理时间达到最优，计算一个Y值平均需要多少时间?加速比是多少?
(1) 对于采用如图4.8前瞻执行机制的MIPS处理器(只有一个整数部件)。当循环第二次执行到
BNEZ R3,FOO
时，写出前面所有指令的状态，包括指令使用的保留站、指令起始节拍、执行节拍和写结果节拍，并写出处理器当前的状态。
(2) 对于2路超标量的MIPS流水线，设有两个指令流出部件，可以流出任意组合的指令，系统中的功能部件数量不受限制。将上述循环4次，优化和调度指令，使循环处理时间达到最优。计算一个Y值平均需要多少时间?加速比是多少?
(3) 对于如图4.13结构的超长指令字MIPS处理器，将上述循环4次，优化和调度指令，使循环处理时间达到最优。计算一个Y值平均需要多少时间?加速比是多少?
解:(1)
L.D F2, 0(R1) 1
Stall
MUT.D F4, F2, F0 2
L.D F6, 0(R2) 3
Stall
Stall
ADD.D F6, F4, F6 4
Stall
Stall
S.D F6, 0[R2] 5
DADDIU R1, R1, #8 6
DADDIU R2, R2, #8 7
DSUBIU R3, R1, #DONE 8
BNEZ R3, FOO 9
所以，共有14 个时钟周期，其中有5 个空转周期。
(2)循环顺序4 次，不进行任何指令调度，则指令1~5 及其间的stall 都是必要的，只是指令6~9 只需执行一次，因此，共有 10 × 4 + 4 = 44 个时钟周期，计算出4 个Y 值，所以计算一个Y 值需要11 个时钟周期，加速比为:14/11 = 1.27 。加速主要是来自减少控制开销，即减少对R1、R2 的整数操作以及比较、分支指令而来的。
(3)循环顺序4 次，优化和调度指令，如下:
L.D F2, 0(R1)
L.D F8, 8(R1)
L.D F14, 16(R1)
L.D F20, 24(R1)
MUT.D F4, F2, F0
MUT.D F10, F8, F0
MUT.D F16, F14, F0
MUT.D F22, F20, F0
L.D F6, 0(R2)
L.D F12, 8(R2)
L.D F18, 16(R2)
L.D F24, 24(R2)
ADD.D F6, F4, F6
ADD.D F12, F10, F12
ADD.D F18, F16, F18
ADD.D F24, F22, F24
S.D F6, 0[R2]
S.D F12, 8[R2]
S.D F18, 16[R2]
S.D F24, 24[R2]
DADDIU R1, R1, #32
DADDIU R2, R2, #32
DSUBIU R3, R1, #DONE
BNEZ R3, FOO
共用了24 个时钟周期，则计算一个Y 值平均需要 24/4 = 6 个时钟周期，
加速比:14/6 = 2.33
(4)
指令 指令执行时钟
流出 执行 写结果 确认
L.D F2, 0(R1) 1 2 3 4
MUL.D F4, F2, F0 2 4 5 6
L.D F6, 0(R2) 3 4 6 7
ADD.D F6, F4, F6 4 8 9 10
S.D F6, 0(R2) 5 11 12 13
DADDIU R1, R1, #8 6 7 8
DADDIU R2, R2, #8 7 8 9
DSUBIU R3,R1,#DONE 8 9 10
BNEZ R3, FOO 9 10
L.D F2, 0(R1) 10 11 13 14
MUL.D F4, F2, F0 11 13 14 15
L.D F6, 0(R2) 12 13 15 16
ADD.D F6, F4, F6 13 17 18 19
S.D F6, 0(R2) 14 20 21 22
DADDIU R1, R1, #8 15 16 17
DADDIU R2, R2, #8 16 17 18
DSUBIU R3,R1,#DONE 17 18 19
BNEZ R3, FOO 18
名称 保留站
Busy Op Vj Vk Qj Qk Dest A
Add1 yes ADD.D Regs[F4] Regs[F6 ]
Add2 no
Add3 no
Mult1 yes
Mult2 no
项号 ROB
Busy 指令 状态 目的 Value
1 yes ADD.D F6, F4, F6 执行 F6 Regs[F4]+Regs[F6]
2 yes S.D F6, 0(R2) 流出 Mem[0+Regs[R2]] #2
字段 浮点寄存器状态
F0 F2 F4 F6 F8 F10 … F30
ROB项编号 1
Busy yes …
(5)
整数指令 浮点指令 时钟周期数
L.D F2, 0(R1) 1
L.D F8, 8(R1) 2
L.D F14, 16(R1) MUT.D F4, F2, F0 3
L.D F20, 24(R1) MUT.D F10, F8, F0 4
L.D F6, 0(R2) MUT.D F16, F14, F0 5
L.D F12, 8(R2) MUT.D F22, F20, F0 6
L.D F18, 16(R2) ADD.D F6, F4, F6 7
L.D F24, 24(R2) ADD.D F12, F10, F12 8
DADDIU R1, R1, #32 ADD.D F18, F16, F18 9
S.D F6, 0(R2) ADD.D F24, F22, F24 10
S.D F12, 8(R2) 11
S.D F18,16(R2) 12
S.D F24, 24(R2) 13
DADDIU R2, R2, #32 14
DSUBIU R3, R1, #DONE 15
BNEZ R3, FOO 16
计算一个Y值需要 16/4 = 4 个时钟周期，加速比 = 14/4 = 3.5
(6)
访存1 访存2 浮点指令1 浮点指令2 整数指令 时钟
周期
L.DF2, 0(R1) L.D F8, 8(R1) 1
L.DF14, 16(R1) L.DF20, 24(R1)
L.DF6, 0(R2) L.DF12, 8(R2) MUT.DF4, F2, F0 MUT.DF10, F8, F0 3
L.DF18, 16(R2) L.DF24, 24(R2) MUT.DF16, F14, F0 MUT.DF22, F20, F0 4
ADD.DF6, F4, F6 ADD.DF12, F10, F12 5
ADD.DF18, F16, F18 ADD.DF24, F22, F24 DADDIU R1, R1, #32 6
DADDIU R2, R2, #32 7
DSUBIUR3, R1, #DONE 8
BNEZ R3, FOO 9
S.DF6, -32(R2) S.DF12, -24(R2) 10
S.DF18,-16(R2) S.DF24, -8(R2) 11
计算一个Y值需要 11/4 个时钟周期，加速比 = 14/(11/4) = 56/11
全部回答
- 1楼网友：底特律间谍
- 2021-02-14 18:20
没看懂什么意思？
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息
大家都在看
推荐资讯