第一章作业答案概要课件.ppt

1、第一章第一章1、用一台、用一台40MHz处理机执行标准测试处理机执行标准测试程序，它含的混合指令数和相应所需的程序，它含的混合指令数和相应所需的时钟周期数如下：时钟周期数如下：指令类型指令类型 指令数指令数 时钟周期数时钟周期数 整数运算整数运算 数据传送数据传送 浮点浮点 控制传送控制传送 45 000 45 000 32 000 32 000 15 000 15 000 8 000 8 000 1 1 2 2 2 2 2 2 求有效求有效CPICPI、MIPSMIPS速率和程序的执行时间速率和程序的执行时间 解：解：CPI=145%+245%+232%+232%+215%+215%+28%

2、8%=1.55=1.55时钟周期时钟周期 M IPS=Rc/（CP I*106）=(40*106)/(1.55*106)=25.81(百万次百万次/秒秒)T=IT=IN NCPICPITcTc=10=105 51.551.55(1/40(1/4010106 6)=3.875ms=3.875ms 2、假定要在一个时钟速率为40MHz处理机上执行200000条指令的目标代码，程序主要由四种指令组成。根据程序跟踪实验结果，已知指令混合比和每种指令所需的指令数如下：要求计算：要求计算：（1 1）在单处理机上用上述跟踪数据运行程序的平均在单处理机上用上述跟踪数据运行程序的平均CPICPI。（2 2）根据

3、（根据（1 1）所得到的）所得到的CPICPI值，计算相应的值，计算相应的MIPSMIPS速率。速率。指令类型指令类型CPICPI指令混合比指令混合比 算术和逻辑算术和逻辑 高速缓存命中的加载高速缓存命中的加载/存储存储 转移转移高速缓存缺失的存储器访问高速缓存缺失的存储器访问1 12 24 48 860%60%18%18%12%12%10%10%答案：答案：Rc=40*106 IN=2*105条条 (1)CPI=1*0.6+2*0.18+4*0.12+8*0.1=2.24 (2)MIPS=Rc/（CPI*106）=(40*106)/(2.24*106)=17.86(百万次百万次/秒秒)指令I

4、i频率Pi霍夫曼编码霍夫曼扩展编码普通编码I10.300000000I20.300101001I30.201010010I40.1011011111011I50.05111011110100I60.021111011101101I70.0211111011100110I80.0111111111011111PiLi 2.382.63.00 减少0.62减少0.40 1、假设在一个采用组相联映象方式的、假设在一个采用组相联映象方式的Cache中，主中，主 存由存由B0B7共共8块组成，块组成，Cache有有2组，每组组，每组2块，每块的大小块，每块的大小为为16个字节，采用个字节，采用LFU块替

5、换算法。在一个程序执行过程块替换算法。在一个程序执行过程中依次访问这个中依次访问这个Cache的块地址流如下的块地址流如下:6，2，4，1，4，6，3，0，4，5，7，3 (1)写出主存地址的格式，并标出各字段的长度。写出主存地址的格式，并标出各字段的长度。(2)写出写出Cache地址的格式，并标出各字段的长度。地址的格式，并标出各字段的长度。(3)画出主存与画出主存与Cache之间各个块的映象对应关系。之间各个块的映象对应关系。(4)如果如果Cache的各个块号为的各个块号为C0、C1、C2和和C3，列出程列出程序执行过程中序执行过程中Cache的块地址流情况。的块地址流情况。(5)如果采用

6、如果采用FIFO替换算法，计算替换算法，计算Cache的块命中率。的块命中率。(6)采用采用LFU替换算法，计算替换算法，计算Cache的块命中率。的块命中率。(1)主存地址：主存地址：区号区号组号组号块号块号块内地址块内地址 6 5 4 3 0(2)缓存地址：缓存地址：组号组号块号块号块内地址块内地址 5 4 3 0 区号区号Ei块号块号Bi缓存块号缓存块号bi 3 2 1 0 相关存储器的格式：相关存储器的格式：相关存储器的容量，应与缓存的块数相同，相关存储器的容量，应与缓存的块数相同，即即:组数组内块数组数组内块数=22=22=4个存储单元。个存储单元。解：解：(3)对应关系：对应关系：

7、主存主存0 1 4 52 3 6 7Cache0 12 3装入位装入位时间时间t 1 2 3 4 5 6 7 8 9 10 11 12块地址流块地址流 6 2 4 1 4 6 3 0 4 5 7 3666661606657LFU调调进进调调进进调调进进替替换换替替换换替替换换441144144064454命命中中命命中中命中命中4次次754C1C2C0C3222622333333调调进进命命中中命命中中替替换换命中率命中率H=4/12=33.3%时间时间t 1 2 3 4 5 6 7 8 9 10 11 12块地址流块地址流 6 2 4 1 4 6 3 0 4 5 7 366666131334

8、3FIFO调调进进调调进进调调进进替替换换替替换换替替换换441144140430545命命中中命中命中3次次345C1C2C0C3222622222277调调进进命命中中命命中中替替换换替替换换命中率命中率H=3/12=25%1、若有一静态多功能流水线分为、若有一静态多功能流水线分为6段，如下图所示，段，如下图所示，其中乘法流水线由其中乘法流水线由1、2、3、6段组成，加法流水线由段组成，加法流水线由1、4、5、6段组成。使用流水线时，要等某种功能（如加段组成。使用流水线时，要等某种功能（如加法）操作都处理完毕后才能转换成另一种功能（如乘法）操作都处理完毕后才能转换成另一种功能（如乘法）。法

9、）。若要计算：若要计算：AB=（a1+b1）（a2+b2）（a3+b3）问：（问：（1）在上述流水方式下，完成）在上述流水方式下，完成AB需多少时间需多少时间？画出时空图并计算此流水线的使用效率和吞吐率。？画出时空图并计算此流水线的使用效率和吞吐率。（2）与顺序运算方式相比，加速比为多少？）与顺序运算方式相比，加速比为多少？123456 2T解:(1)12341234455512312319 S6 1 2 345 4 5完成A*B需要的时间=19 114256195253195Tp 1925195253Sp效率为：吞吐率为：（2）加速比为：2、已知某单功能非线性流水线的预约表如下图，要求：、已

10、知某单功能非线性流水线的预约表如下图，要求：（1）列出禁止表）列出禁止表F和冲突向量和冲突向量C。（2）画出该流水线状态图，确定其最小平均延迟以及此时的）画出该流水线状态图，确定其最小平均延迟以及此时的调度方案？调度方案？当按此流水调度方案共输入当按此流水调度方案共输入8个任务时，则其实际吞吐率为个任务时，则其实际吞吐率为多少？多少？时间时间t段段st1t2t3t4t5t61234 附图附图解：(1)禁止表F=4 冲突向量 C=(1000)(2)最佳调度策略(1，1，1，5)吞吐率=8/17t 10001100101010011110101111011111=5=5=5=5=5=5=5=512

11、3233132112各种调度方案及其相应的平均延迟：调度方案调度方案平均延迟平均延迟（5）（3）（1，1，1，5）（2，3）（3，2）（1，5）（1，1，5）（2，5）（2，3，5）（2，1，5）（3，5）（3，2，5）（2，1，2，5）(1，2，3，5)（2，1，2，3）5322.52.532.33.53.32.743.32.52.52523、有一个双输入端的加、有一个双输入端的加-乘双功能静态流水线，由经过时间为乘双功能静态流水线，由经过时间为t、t、2t、t的的1、2、3、4四个子过程构成。加按四个子过程构成。加按1 2 4连接，乘按连接，乘按1 3 4连接，流水线输出设有数据缓冲器，也

12、可将连接，流水线输出设有数据缓冲器，也可将数据直接返回输入。现要执行数据直接返回输入。现要执行 A*（B+C*（D+E*F）+G*H的运算，请调整计算顺序，画出能获得吞吐率尽量高的流水时空的运算，请调整计算顺序，画出能获得吞吐率尽量高的流水时空图，标出流水线入、出端数据的变化情况，求出完成全部运算的图，标出流水线入、出端数据的变化情况，求出完成全部运算的时间及此期间整个流水线吞吐率，效率，加速比？如对流水线瓶时间及此期间整个流水线吞吐率，效率，加速比？如对流水线瓶颈子过程再细分，最少只需多少时间可完成全部运算？若子过程颈子过程再细分，最少只需多少时间可完成全部运算？若子过程3不能再细分，只能用

13、并联方法改进，问流水线的效率为多少？不能再细分，只能用并联方法改进，问流水线的效率为多少？解：根据题意，对算法经调整后，能使流水吞吐率尽量高的流水时空图如图所示。图中已标出了流水线入、出端的数据变化情况。S123412121233 31234564545 6 64567 87 87 8999输入输出ACEFABGHACDACEFABACDACEFGHACEF+GHACD+ABACEFABGHACDACEFACD+ABACEF+GHACEF+GH+ACD+AB21t S1231321 2132435 64 5 67 87 87 8999根据上图的流水时空图，可以看出，完成全部运算的时间为21t。

14、28114213346ttt如果现在将瓶颈子过程3细分成两个子过程，则时空图如下图所示。41324 5 61324 5 616t tt73219Tp711213346SptttS1231321 2131335 54 5 67 87 87 899942424 6 61324 5 616t 由上图可见，完成全部运算最少需要16t的时间即可。现在若子过程3不能再细分了，只能用2个子过程3通过并联来改进，则其时空图如下图所示。完成全部运算时的流水线效率8033165924ttt4、超级标量机和超级流水线机都能开发指令级的并、超级标量机和超级流水线机都能开发指令级的并行性，现假定这两种机器的流水线都为行

15、性，现假定这两种机器的流水线都为4段，每段均段，每段均需需1个时钟周期。若在超级标量机中，每个时钟周期个时钟周期。若在超级标量机中，每个时钟周期可同时启动可同时启动3条指令，而超级流水线机中则是每隔条指令，而超级流水线机中则是每隔1/3时钟周期启动一条指令。现若要执行时钟周期启动一条指令。现若要执行6条指令的代码条指令的代码序列，问在两种机器上各需用多少个时钟周期方可执序列，问在两种机器上各需用多少个时钟周期方可执行完毕？行完毕？解：超级标量机需5个时钟周期，超级流水线机需5.67个时钟周期。5、在在CRAY-1机上，机上，V是向量寄存器，设向量长度均为是向量寄存器，设向量长度均为32。S是是

16、标量寄存器，所用浮点功能执行部件的执行时间分别为：加法标量寄存器，所用浮点功能执行部件的执行时间分别为：加法需需6拍，相乘需拍，相乘需7拍，从存储器读存数需拍，从存储器读存数需6拍，求倒数近似值及除拍，求倒数近似值及除法需法需14拍，写入寄存器及启动功能部件（包括存储器）各需拍，写入寄存器及启动功能部件（包括存储器）各需1拍。拍。问下列各指令组中的哪些指令可以链接？哪些指令不可链接？问下列各指令组中的哪些指令可以链接？哪些指令不可链接？哪些指令可以并行执行？试说明其原因并分别计算出各指令组哪些指令可以并行执行？试说明其原因并分别计算出各指令组全部完成所需的拍数。全部完成所需的拍数。（1）V0存

17、储器存储器 （2）V2V0+V1 V1V2+V3 V3存储器存储器 V4V5*V6 V4V2*V3（3）V0存储器存储器 （4）V0存储器存储器 V3V1+V2 V11/V0 V4V0*V3 V3V1+V2 V6V4+V5 V5V3*V4（5）V0存储器存储器 （6）V3存储器存储器 V1V2+V3 V2V0+V1 V4V5*V6 s0s2+s3 s0s1+s2 V3V1*V4（7）V3存储器存储器 （8）V0存储器存储器 V2V0+V1 V2V0+V1 V4V2*V3 V3V1+V2 存储器存储器V4 V5V3*V4 解：(1)三条指令可全并行执行,需(1+7+1)+(32-1)=40(拍)

18、(2)前两条并行,和第三条链接，需(1+7+1)+(1+6+1)+(32-1)=48拍(3)前两条并行和第三条链接,而第四条指令与第三条指令串行（因第二条和第四条功能部件冲突），需 (1+6+1)+(1+7+1)+(32-1)+(1+6+1)+(32-1)=87拍(4)全部链接 (1+6+1)+(1+14+1)+(1+6+1)+(1+7+1)+(32-1)=72拍(5)全并行执行，需(1+7+1)+(32-1)=40(拍)(6)前三条指令并行，与第四条指令串行（V1源操作数冲突），需(1+6+1)+(32-1)+(1+7+1)+(32-1)=79拍(7)前两条指令并行，与第三条链接，再与第四条

19、串行（因第一条和第四条冲突），需(1+6+1)+(1+7+1)+(32-1)+(1+6+1)+(32-1)=87拍(8)前两条指令链接，与第三条串行（V1源操作数冲突），与第四条链接，需(1+6+1)+(1+6+1)+(32-1)+(1+6+1)+(1+7+1)+(32-1)=95拍 1、若有一静态多功能流水线分为、若有一静态多功能流水线分为6段，如下图所示，段，如下图所示，其中乘法流水线由其中乘法流水线由1、2、3、6段组成，加法流水线由段组成，加法流水线由1、4、5、6段组成。使用流水线时，要等某种功能（如加段组成。使用流水线时，要等某种功能（如加法）操作都处理完毕后才能转换成另一种功能（

20、如乘法）操作都处理完毕后才能转换成另一种功能（如乘法）。法）。若要计算：若要计算：AB=（a1+b1）（a2+b2）（a3+b3）问：（问：（1）在上述流水方式下，完成）在上述流水方式下，完成AB需多少时间需多少时间？画出时空图并计算此流水线的使用效率和吞吐率。？画出时空图并计算此流水线的使用效率和吞吐率。（2）与顺序运算方式相比，加速比为多少？）与顺序运算方式相比，加速比为多少？123456 2T解:(1)12341234455512312319 S6 1 2 345 4 5完成A*B需要的时间=19 114256195253195Tp 1925195253Sp效率为：吞吐率为：（2）加速比

21、为：2、已知某单功能非线性流水线的预约表如下图，要求：、已知某单功能非线性流水线的预约表如下图，要求：（1）列出禁止表）列出禁止表F和冲突向量和冲突向量C。（2）画出该流水线状态图，确定其最小平均延迟以及此时的）画出该流水线状态图，确定其最小平均延迟以及此时的调度方案？调度方案？当按此流水调度方案共输入当按此流水调度方案共输入8个任务时，则其实际吞吐率为个任务时，则其实际吞吐率为多少？多少？时间时间t段段st1t2t3t4t5t61234 附图附图解：(1)禁止表F=4 冲突向量 C=(1000)(2)最佳调度策略(1，1，1，5)吞吐率=8/17t 100011001010100111101

22、01111011111=5=5=5=5=5=5=5=5123233132112各种调度方案及其相应的平均延迟：调度方案调度方案平均延迟平均延迟（5）（3）（1，1，1，5）（2，3）（3，2）（1，5）（1，1，5）（2，5）（2，3，5）（2，1，5）（3，5）（3，2，5）（2，1，2，5）(1，2，3，5)（2，1，2，3）5322.52.532.33.53.32.743.32.52.52523、有一个双输入端的加、有一个双输入端的加-乘双功能静态流水线，由经过时间为乘双功能静态流水线，由经过时间为t、t、2t、t的的1、2、3、4四个子过程构成。加按四个子过程构成。加按1 2 4连接，

23、乘按连接，乘按1 3 4连接，流水线输出设有数据缓冲器，也可将连接，流水线输出设有数据缓冲器，也可将数据直接返回输入。现要执行数据直接返回输入。现要执行 A*（B+C*（D+E*F）+G*H的运算，请调整计算顺序，画出能获得吞吐率尽量高的流水时空的运算，请调整计算顺序，画出能获得吞吐率尽量高的流水时空图，标出流水线入、出端数据的变化情况，求出完成全部运算的图，标出流水线入、出端数据的变化情况，求出完成全部运算的时间及此期间整个流水线吞吐率，效率，加速比？如对流水线瓶时间及此期间整个流水线吞吐率，效率，加速比？如对流水线瓶颈子过程再细分，最少只需多少时间可完成全部运算？若子过程颈子过程再细分，最

24、少只需多少时间可完成全部运算？若子过程3不能再细分，只能用并联方法改进，问流水线的效率为多少？不能再细分，只能用并联方法改进，问流水线的效率为多少？解：根据题意，对算法经调整后，能使流水吞吐率尽量高的流水时空图如图所示。图中已标出了流水线入、出端的数据变化情况。S123412121233 31234564545 6 64567 87 87 8999输入输出ACEFABGHACDACEFABACDACEFGHACEF+GHACD+ABACEFABGHACDACEFACD+ABACEF+GHACEF+GH+ACD+AB21t S1231321 2132435 64 5 67 87 87 8999根

25、据上图的流水时空图，可以看出，完成全部运算的时间为21t。28114213346ttt如果现在将瓶颈子过程3细分成两个子过程，则时空图如下图所示。41324 5 61324 5 616t tt73219Tp711213346SptttS1231321 2131335 54 5 67 87 87 899942424 6 61324 5 616t 由上图可见，完成全部运算最少需要16t的时间即可。现在若子过程3不能再细分了，只能用2个子过程3通过并联来改进，则其时空图如下图所示。完成全部运算时的流水线效率8033165924ttt4、超级标量机和超级流水线机都能开发指令级的并、超级标量机和超级流水

26、线机都能开发指令级的并行性，现假定这两种机器的流水线都为行性，现假定这两种机器的流水线都为4段，每段均段，每段均需需1个时钟周期。若在超级标量机中，每个时钟周期个时钟周期。若在超级标量机中，每个时钟周期可同时启动可同时启动3条指令，而超级流水线机中则是每隔条指令，而超级流水线机中则是每隔1/3时钟周期启动一条指令。现若要执行时钟周期启动一条指令。现若要执行6条指令的代码条指令的代码序列，问在两种机器上各需用多少个时钟周期方可执序列，问在两种机器上各需用多少个时钟周期方可执行完毕？行完毕？解：超级标量机需5个时钟周期，超级流水线机需5.67个时钟周期。5、在在CRAY-1机上，机上，V是向量寄存

27、器，设向量长度均为是向量寄存器，设向量长度均为32。S是是标量寄存器，所用浮点功能执行部件的执行时间分别为：加法标量寄存器，所用浮点功能执行部件的执行时间分别为：加法需需6拍，相乘需拍，相乘需7拍，从存储器读存数需拍，从存储器读存数需6拍，求倒数近似值及除拍，求倒数近似值及除法需法需14拍，写入寄存器及启动功能部件（包括存储器）各需拍，写入寄存器及启动功能部件（包括存储器）各需1拍。拍。问下列各指令组中的哪些指令可以链接？哪些指令不可链接？问下列各指令组中的哪些指令可以链接？哪些指令不可链接？哪些指令可以并行执行？试说明其原因并分别计算出各指令组哪些指令可以并行执行？试说明其原因并分别计算出各

28、指令组全部完成所需的拍数。全部完成所需的拍数。（1）V0存储器存储器 （2）V2V0+V1 V1V2+V3 V3存储器存储器 V4V5*V6 V4V2*V3（3）V0存储器存储器 （4）V0存储器存储器 V3V1+V2 V11/V0 V4V0*V3 V3V1+V2 V6V4+V5 V5V3*V4（5）V0存储器存储器 （6）V3存储器存储器 V1V2+V3 V2V0+V1 V4V5*V6 s0s2+s3 s0s1+s2 V3V1*V4（7）V3存储器存储器 （8）V0存储器存储器 V2V0+V1 V2V0+V1 V4V2*V3 V3V1+V2 存储器存储器V4 V5V3*V4 解：(1)三条指

29、令可全并行执行,需(1+7+1)+(32-1)=40(拍)(2)前两条并行,和第三条链接，需(1+7+1)+(1+6+1)+(32-1)=48拍(3)前两条并行和第三条链接,而第四条指令与第三条指令串行（因第二条和第四条功能部件冲突），需 (1+6+1)+(1+7+1)+(32-1)+(1+6+1)+(32-1)=87拍(4)全部链接 (1+6+1)+(1+14+1)+(1+6+1)+(1+7+1)+(32-1)=72拍(5)全并行执行，需(1+7+1)+(32-1)=40(拍)(6)前三条指令并行，与第四条指令串行（V1源操作数冲突），需(1+6+1)+(32-1)+(1+7+1)+(32-1)=79拍(7)前两条指令并行，与第三条链接，再与第四条串行（因第一条和第四条冲突），需(1+6+1)+(1+7+1)+(32-1)+(1+6+1)+(32-1)=87拍(8)前两条指令链接，与第三条串行（V1源操作数冲突），与第四条链接，需(1+6+1)+(1+6+1)+(32-1)+(1+6+1)+(1+7+1)+(32-1)=95拍