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速率和程序的执行时间速率和程序的执行时间 第1页，共38页。解：解：CPI=145%+245%+232%+232%+215%
2、+215%+28%8%=1.55=1.55时钟周期时钟周期 MIPS=Rc/（CPI*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页，共38页。2、假定要在一个时钟速率为40MHz处理机上执行200000条指令的目标代码，程序主要由四种指令组成。根据程序跟踪实验结果，已知指令混合比和每种指令所需的指令数如下：要求计算：要求计算：（1 1）在单处理机上用上述跟踪数据运行程序的平均在单处理机上用上述跟踪数据运行程序的
3、平均CPICPI。（2 2）根据（根据（1 1）所得到的）所得到的CPICPI值，计算相应的值，计算相应的MIPSMIPS速率。速率。指令类型指令类型CPICPI指令混合比指令混合比 算术和逻辑算术和逻辑 高速缓存命中的加载高速缓存命中的加载/存储存储 转移转移高速缓存缺失的存储器访问高速缓存缺失的存储器访问1 12 24 48 860%60%18%18%12%12%10%10%第3页，共38页。答案：答案：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
4、*106)=17.86(百万次百万次/秒秒)第4页，共38页。第5页，共38页。指令Ii频率Pi霍夫曼编码霍夫曼扩展编码普通编码I10.300000000I20.300101001I30.201010010I40.1011011111011I50.05111011110100I60.021111011101101I70.0211111011100110I80.0111111111011111PiLi 2.382.63.00 减少0.62减少0.40 第6页，共38页。1、假设在一个采用组相联映象方式的、假设在一个采用组相联映象方式的Cache中，主中，主 存由存由B0B7共共8块组成，块组成，
5、Cache有有2组，每组组，每组2块，每块的大小为块，每块的大小为16个字个字节，采用节，采用LFU块替换算法。在一个程序执行过程中依次访问这块替换算法。在一个程序执行过程中依次访问这个个Cache的块地址流如下的块地址流如下:6，2，4，1，4，6，3，0，4，5，7，3 (1)写出主存地址的格式，并标出各字段的长度。写出主存地址的格式，并标出各字段的长度。(2)写出写出Cache地址的格式，并标出各字段的长度。地址的格式，并标出各字段的长度。(3)画出主存与画出主存与Cache之间各个块的映象对应关系。之间各个块的映象对应关系。(4)如果如果Cache的各个块号为的各个块号为C0、C1、C
6、2和和C3，列出程序执，列出程序执行过程中行过程中Cache的块地址流情况。的块地址流情况。(5)如果采用如果采用FIFO替换算法，计算替换算法，计算Cache的块命中率。的块命中率。(6)采用采用LFU替换算法，计算替换算法，计算Cache的块命中率。的块命中率。第7页，共38页。(1)主存地址：主存地址：区号区号组号组号块号块号块内地址块内地址 6 5 4 3 0(2)缓存地址：缓存地址：组号组号块号块号块内地址块内地址 5 4 3 0 区号区号Ei块号块号Bi缓存块号缓存块号bi 3 2 1 0 相关存储器的格式：相关存储器的格式：相关存储器的容量，应与缓存的块数相同，相关存储器的容量，
7、应与缓存的块数相同，即即:组数组内块数组数组内块数=22=22=4个存储单元。个存储单元。解解：(3)对应关系：对应关系：主存主存0 1 4 52 3 6 7Cache0 12 3装入位装入位第8页，共38页。时间时间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%第9页，共
8、38页。时间时间t 1 2 3 4 5 6 7 8 9 10 11 12块地址流块地址流 6 2 4 1 4 6 3 0 4 5 7 3666661313343FIFO调调进进调调进进调调进进替替换换替替换换替替换换441144140430545命命中中命中命中3次次345C1C2C0C3222622222277调调进进命命中中命命中中替替换换替替换换命中率命中率H=3/12=25%第10页，共38页。第11页，共38页。第12页，共38页。1、若有一静态多功能流水线分为、若有一静态多功能流水线分为6段，如下图所示，其中乘段，如下图所示，其中乘法流水线由法流水线由1、2、3、6段组成，加法流水
9、线由段组成，加法流水线由1、4、5、6段段组成。使用流水线时，要等某种功能（如加法）操作都组成。使用流水线时，要等某种功能（如加法）操作都处理完毕后才能转换成另一种功能（如乘法）。处理完毕后才能转换成另一种功能（如乘法）。若要计算：若要计算：AB=（a1+b1）（a2+b2）（a3+b3）问：（问：（1）在上述流水方式下，完成）在上述流水方式下，完成AB需多少时间？画出需多少时间？画出时空图并计算此流水线的使用效率和吞吐率。时空图并计算此流水线的使用效率和吞吐率。（2）与顺序运算方式相比，加速比为多少？）与顺序运算方式相比，加速比为多少？123456 2第13页，共38页。T解:(1)1234
10、1234455512312319 S6 1 2 345 4 5第14页，共38页。完成A*B需要的时间=19 114256195253195Tp 1925195253Sp效率为：吞吐率为：（2）加速比为：第15页，共38页。2、已知某单功能非线性流水线的预约表如下图，要求：、已知某单功能非线性流水线的预约表如下图，要求：（1）列出禁止表）列出禁止表F和冲突向量和冲突向量C。（2）画出该流水线状态图，确定其最小平均延迟以及此时的调度）画出该流水线状态图，确定其最小平均延迟以及此时的调度方案？方案？当按此流水调度方案共输入当按此流水调度方案共输入8个任务时，则其实际吞吐率为多少？个任务时，则其实际
11、吞吐率为多少？时间时间t段段st1t2t3t4t5t61234 附图附图第16页，共38页。解：(1)禁止表F=4 冲突向量 C=(1000)(2)最佳调度策略(1，1，1，5)吞吐率=8/17t 10001100101010011110101111011111=5=5=5=5=5=5=5=5123233132112第17页，共38页。各种调度方案及其相应的平均延迟：调度方案调度方案平均延迟平均延迟（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
12、.52.532.33.53.32.743.32.52.5252第18页，共38页。3、有一个双输入端的加、有一个双输入端的加-乘双功能静态流水线，由经过时间为乘双功能静态流水线，由经过时间为t、t、2t、t的的1、2、3、4四个子过程构成。加按四个子过程构成。加按1 2 4连接，乘按连接，乘按1 3 4连接，流水线输出设有数据缓冲器，也可将数据直接返回输入。现要连接，流水线输出设有数据缓冲器，也可将数据直接返回输入。现要执行执行 A*（B+C*（D+E*F）+G*H的运算，请调整计算顺序，画出能获得吞吐率尽量高的流水时空图，标出的运算，请调整计算顺序，画出能获得吞吐率尽量高的流水时空图，标出流
13、水线入、出端数据的变化情况，求出完成全部运算的时间及此期间整个流水线入、出端数据的变化情况，求出完成全部运算的时间及此期间整个流水线吞吐率，效率，加速比？如对流水线瓶颈子过程再细分，最少只需流水线吞吐率，效率，加速比？如对流水线瓶颈子过程再细分，最少只需多少时间可完成全部运算？若子过程多少时间可完成全部运算？若子过程3不能再细分，只能用并联方法改不能再细分，只能用并联方法改进，问流水线的效率为多少？进，问流水线的效率为多少？第19页，共38页。解：根据题意，对算法经调整后，能使流水吞吐率尽量高的流水时空图如图所示。图中已标出了流水线入、出端的数据变化情况。S123412121233312345
14、64545 66456787878999输入输出ACEFABGHACDACEFABACDACEFGHACEF+GHACD+ABACEFABGHACDACEFACD+ABACEF+GHACEF+GH+ACD+AB21t 第20页，共38页。S123132121324356456787878999根据上图的流水时空图，可以看出，完成全部运算的时间为21t。28114213346ttt如果现在将瓶颈子过程3细分成两个子过程，则时空图如下图所示。413245613245616t tt73219Tp711213346Spttt第21页，共38页。S1231321213133554567878789994
15、24246 613245616t 由上图可见，完成全部运算最少需要16t的时间即可。现在若子过程3不能再细分了，只能用2个子过程3通过并联来改进，则其时空图如下图所示。完成全部运算时的流水线效率8033165924ttt第22页，共38页。4、超级标量机和超级流水线机都能开发指令级的并行、超级标量机和超级流水线机都能开发指令级的并行性，现假定这两种机器的流水线都为性，现假定这两种机器的流水线都为4段，每段均需段，每段均需1个时个时钟周期。若在超级标量机中，每个时钟周期可同时启动钟周期。若在超级标量机中，每个时钟周期可同时启动3条条指令，而超级流水线机中则是每隔指令，而超级流水线机中则是每隔1/
16、3时钟周期启动一条指时钟周期启动一条指令。现若要执行令。现若要执行6条指令的代码序列，问在两种机器上条指令的代码序列，问在两种机器上各需用多少个时钟周期方可执行完毕？各需用多少个时钟周期方可执行完毕？解：超级标量机需5个时钟周期，超级流水线机需5.67个时钟周期。第23页，共38页。5、在在CRAY-1机上，机上，V是向量寄存器，设向量长度均为是向量寄存器，设向量长度均为32。S是是标量寄存器，所用浮点功能执行部件的执行时间分别为：加法标量寄存器，所用浮点功能执行部件的执行时间分别为：加法需需6拍，相乘需拍，相乘需7拍，从存储器读存数需拍，从存储器读存数需6拍，求倒数近似值及除拍，求倒数近似值
17、及除法需法需14拍，写入寄存器及启动功能部件（包括存储器）各需拍，写入寄存器及启动功能部件（包括存储器）各需1拍拍。问下列各指令组中的哪些指令可以链接？哪些指令不可链接。问下列各指令组中的哪些指令可以链接？哪些指令不可链接？哪些指令可以并行执行？试说明其原因并分别计算出各指令？哪些指令可以并行执行？试说明其原因并分别计算出各指令组全部完成所需的拍数。组全部完成所需的拍数。（1）V0存储器存储器 （2）V2V0+V1 V1V2+V3 V3存储器存储器 V4V5*V6 V4V2*V3（3）V0存储器存储器 （4）V0存储器存储器 V3V1+V2 V11/V0 V4V0*V3 V3V1+V2 V6V
18、4+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 第24页，共38页。解：(1)三条指令可全并行执行,需(1+7+1)+(32-1)=40(拍)(2)前两条并行,和第三条链接，需(1+7+1)+(1+6+1)+(32-1)=48拍(3)前两条并行和第三条链接,而第四条指令与第三条指令串行（因第二条和第四条功能部件冲突），需 (1+6+1
19、)+(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
20、+1)+(1+6+1)+(32-1)+(1+6+1)+(1+7+1)+(32-1)=95拍 第25页，共38页。1、若有一静态多功能流水线分为、若有一静态多功能流水线分为6段，如下图所示，其中乘段，如下图所示，其中乘法流水线由法流水线由1、2、3、6段组成，加法流水线由段组成，加法流水线由1、4、5、6段段组成。使用流水线时，要等某种功能（如加法）操作都组成。使用流水线时，要等某种功能（如加法）操作都处理完毕后才能转换成另一种功能（如乘法）。处理完毕后才能转换成另一种功能（如乘法）。若要计算：若要计算：AB=（a1+b1）（a2+b2）（a3+b3）问：（问：（1）在上述流水方式下，完成）在上
21、述流水方式下，完成AB需多少时间？画需多少时间？画出时空图并计算此流水线的使用效率和吞吐率。出时空图并计算此流水线的使用效率和吞吐率。（2）与顺序运算方式相比，加速比为多少？）与顺序运算方式相比，加速比为多少？123456 2第26页，共38页。T解:(1)12341234455512312319 S6 1 2 345 4 5第27页，共38页。完成A*B需要的时间=19 114256195253195Tp 1925195253Sp效率为：吞吐率为：（2）加速比为：第28页，共38页。2、已知某单功能非线性流水线的预约表如下图，要求：、已知某单功能非线性流水线的预约表如下图，要求：（1）列出禁
22、止表）列出禁止表F和冲突向量和冲突向量C。（2）画出该流水线状态图，确定其最小平均延迟以及此时的调）画出该流水线状态图，确定其最小平均延迟以及此时的调度方案？度方案？当按此流水调度方案共输入当按此流水调度方案共输入8个任务时，则其实际吞吐率为多少？个任务时，则其实际吞吐率为多少？时间时间t段段st1t2t3t4t5t61234 附图附图第29页，共38页。解：(1)禁止表F=4 冲突向量 C=(1000)(2)最佳调度策略(1，1，1，5)吞吐率=8/17t 10001100101010011110101111011111=5=5=5=5=5=5=5=5123233132112第30页，共38
23、页。各种调度方案及其相应的平均延迟：调度方案调度方案平均延迟平均延迟（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.5252第31页，共38页。3、有一个双输入端的加、有一个双输入端的加-乘双功能静态流水线，由经过时间为乘双功能静态流水线，由经过时间为t、t、2t、t的的1、2、3、4四个子过程构成。加按四个子过程构成。加按1 2 4连接，乘按连接，乘按1 3 4连接，流水线输出设有数据缓冲器
24、，也可将数据直接返回输入。连接，流水线输出设有数据缓冲器，也可将数据直接返回输入。现要执行现要执行 A*（B+C*（D+E*F）+G*H的运算，请调整计算顺序，画出能获得吞吐率尽量高的流水时空图的运算，请调整计算顺序，画出能获得吞吐率尽量高的流水时空图，标出流水线入、出端数据的变化情况，求出完成全部运算的时间，标出流水线入、出端数据的变化情况，求出完成全部运算的时间及此期间整个流水线吞吐率，效率，加速比？如对流水线瓶颈子过及此期间整个流水线吞吐率，效率，加速比？如对流水线瓶颈子过程再细分，最少只需多少时间可完成全部运算？若子过程程再细分，最少只需多少时间可完成全部运算？若子过程3不能再细不能再
25、细分，只能用并联方法改进，问流水线的效率为多少？分，只能用并联方法改进，问流水线的效率为多少？第32页，共38页。解：根据题意，对算法经调整后，能使流水吞吐率尽量高的流水时空图如图所示。图中已标出了流水线入、出端的数据变化情况。S1234121212333123456454566456787878999输入输出ACEFABGHACDACEFABACDACEFGHACEF+GHACD+ABACEFABGHACDACEFACD+ABACEF+GHACEF+GH+ACD+AB21t 第33页，共38页。S123132121324356456787878999根据上图的流水时空图，可以看出，完成全部运
26、算的时间为21t。28114213346ttt如果现在将瓶颈子过程3细分成两个子过程，则时空图如下图所示。413245613245616t tt73219Tp711213346Spttt第34页，共38页。S123132121313355456787878999424246613245616t 由上图可见，完成全部运算最少需要16t的时间即可。现在若子过程3不能再细分了，只能用2个子过程3通过并联来改进，则其时空图如下图所示。完成全部运算时的流水线效率8033165924ttt第35页，共38页。4、超级标量机和超级流水线机都能开发指令级的并行性、超级标量机和超级流水线机都能开发指令级的并行性
27、，现假定这两种机器的流水线都为，现假定这两种机器的流水线都为4段，每段均需段，每段均需1个时钟个时钟周期。若在超级标量机中，每个时钟周期可同时启动周期。若在超级标量机中，每个时钟周期可同时启动3条条指令，而超级流水线机中则是每隔指令，而超级流水线机中则是每隔1/3时钟周期启动一条指时钟周期启动一条指令。现若要执行令。现若要执行6条指令的代码序列，问在两种机器上各需条指令的代码序列，问在两种机器上各需用多少个时钟周期方可执行完毕？用多少个时钟周期方可执行完毕？解：超级标量机需5个时钟周期，超级流水线机需5.67个时钟周期。第36页，共38页。5、在在CRAY-1机上，机上，V是向量寄存器，设向量
28、长度均为是向量寄存器，设向量长度均为32。S是是标量寄存器，所用浮点功能执行部件的执行时间分别为：加法标量寄存器，所用浮点功能执行部件的执行时间分别为：加法需需6拍，相乘需拍，相乘需7拍，从存储器读存数需拍，从存储器读存数需6拍，求倒数近似值及除拍，求倒数近似值及除法需法需14拍，写入寄存器及启动功能部件（包括存储器）各需拍，写入寄存器及启动功能部件（包括存储器）各需1拍拍。问下列各指令组中的哪些指令可以链接？哪些指令不可链接。问下列各指令组中的哪些指令可以链接？哪些指令不可链接？哪些指令可以并行执行？试说明其原因并分别计算出各指令？哪些指令可以并行执行？试说明其原因并分别计算出各指令组全部完
29、成所需的拍数。组全部完成所需的拍数。（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 第37页，共38页。解：(
30、1)三条指令可全并行执行,需(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拍 第38页，共38页。
