第一章作业答案概要

第一章1、用一台40MHz处理机执行标准测试程序，它含的混合指令数和相应所需的时钟周期数如下：指令类型指令数时钟周期数整数运算数据传送浮点控制传送45000320001500080001222求有效CPI、MIPS速率和程序的执行时间解：CPI=1×45%+2×32%+2×15%+2×8%=1.55时钟周期MIPS=Rc/（CPI*106）=(40*106)/(1.55*106)=25.81(百万次/秒)T=IN×CPI×Tc=105×1.55×(1/40×106)=3.875ms2、假定要在一个时钟速率为40MHz处理机上执行200000条指令的目标代码，程序主要由四种指令组成。根据程序跟踪实验结果，已知指令混合比和每种指令所需的指令数如下：要求计算：（1）在单处理机上用上述跟踪数据运行程序的平均CPI。（2）根据（1）所得到的CPI值，计算相应的MIPS速率。指令类型CPI指令混合比算术和逻辑高速缓存命中的加载/存储转移高速缓存缺失的存储器访问124860%18%12%10%答案：Rc=40*106IN=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(百万次/秒)1、某模型机有8条指令，使用频率分别为：0.3，0.3，0.2，0.1，0.05，0.02，0.02，0.01。试分别用霍夫曼编码和扩展编码对其操作码进行编码，限定扩展编码只能有两种长度。则它们的平均编码长度各比定长操作码的平均编码长度减少多少？指令Ii频率Pi霍夫曼编码霍夫曼扩展编码普通编码I10.300000000I20.300101001I30.201010010I40.1011011111011I50.05111011110100I60.021111011101101I70.0211111011100110I80.0111111111011111∑PiLi2.382.63.00减少0.62减少0.401、假设在一个采用组相联映象方式的Cache中，主存由B0～B7共8块组成，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、C2和C3，列出程序执行过程中Cache的块地址流情况。(5)如果采用FIFO替换算法，计算Cache的块命中率。(6)采用LFU替换算法，计算Cache的块命中率。(1)主存地址：区号组号块号块内地址65430(2)缓存地址：组号块号块内地址5430区号Ei块号Bi缓存块号bi3210相关存储器的格式：相关存储器的容量，应与缓存的块数相同，即:组数×组内块数=22=2×2=4个存储单元。解：(3)对应关系：主存01452367Cache0123装入位时间t123456789101112块地址流624146304573666661606657LFU调进调进调进替换替换替换441144144064454命中命中命中4次754C1C2C0C3222622333333调进命中命中替换Cache的块地址流情况:C2C3C0C1C0C2C3C1C0C1C2C3命中率H=4/12=33.3%时间t123456789101112块地址流624146304573666661313343FIFO调进调进调进替换替换替换441144140430545命中命中3次345C1C2C0C3222622222277调进命中命中替换替换命中率H=3/12=25%2、假设机器的时钟周期为10ns,Cache失效时的访存时间为20个时钟周期，Cache的访问时间为一个时钟周期。(1)设失效率为0.05，忽略写操作时的其它延迟，求机器的平均访存时间。(2)假设通过增加Cache容量一倍而使失效率降低到0.03，但使得Cache命中时的访问时间增加到了1.2时钟周期（即12ns），指出这样的改动设计是否合适？(3)如果时钟周期取决于Cache的访问时间(也就是用延长时钟周期的方法)，上述改动设计是否合适？答案：（1）机器的平均访存时间T=TcHc+(1-Hc)Tm=0.95×10+0.05×20×10=19.5ns（2）T=TcHc+(1-Hc)Tm=0.97×10×1.2+0.03×20×10=17.64ns这种改动合适，使机器的平均访存时间降低。(3)T=TcHc+(1-Hc)Tm=0.97×10×1.2+0.03×20×10×1.2=18.84ns合适。1、若有一静态多功能流水线分为6段，如下图所示，其中乘法流水线由1、2、3、6段组成，加法流水线由1、4、5、6段组成。使用流水线时，要等某种功能（如加法）操作都处理完毕后才能转换成另一种功能（如乘法）。若要计算：A×B=（a1+b1）×（a2+b2）×（a3+b3）问：（1）在上述流水方式下，完成A×B需多少时间？画出时空图并计算此流水线的使用效率和吞吐率。（2）与顺序运算方式相比，加速比为多少？123456τττττ2τT解:(1)12341234455512312319τS61234545完成A*B需要的时间=19τ114256195253195Tp1925195253Sp效率为：吞吐率为：（2）加速比为：2、已知某单功能非线性流水线的预约表如下图，要求：（1）列出禁止表F和冲突向量C。（2）画出该流水线状态图，确定其最小平均延迟以及此时的调度方案？当按此流水调度方案共输入8个任务时，则其实际吞吐率为多少？时间t段st1t2t3t4t5t61××2××3×4×附图解：(1)禁止表F={4}冲突向量C=(1000)(2)最佳调度策略(1，1，1，5)吞吐率=8/17Δt10001100101010011110101111011111〉=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、2△t、△t的1、2、3、4四个子过程构成。加按124连接，乘按134连接，流水线输出设有数据缓冲器，也可将数据直接返回输入。现要执行A*（B+C*（D+E*F））+G*H的运算，请调整计算顺序，画出能获得吞吐率尽量高的流水时空图，标出流水线入、出端数据的变化情况，求出完成全部运算的时间及此期间整个流水线吞吐率，效率，加速比？如对流水线瓶颈子过程再细分，最少只需多少时间可完成全部运算？若子过程3不能再细分，只能用并联方法改进，问流水线的效率为多少？解：根据题意，对算法经调整后，能使流水吞吐率尽量高的流水时空图如图所示。图中已标出了流水线入、出端的数据变化情况。S1234121212333123456454566456787878999输入输出ACEFABGHACDACEFABACDACEFGHACEF+GHACD+ABACEFABGHACDACEFACD+ABACEF+GHACEF+GH+ACD+AB21△tS123132121324356456787878999根据上图的流水时空图，可以看出，完成全部运算的时间为21△t。28114213346ttt如果现在将瓶颈子过程3细分成两个子过程，则时空图如下图所示。413245613245616△ttt73219Tp711213346SptttS123132121313355456787878999424246613245616△t由上图可见，完成全部运算最少需要16△t的时间即可。现在若子过程3不能再细分了，只能用2个子过程3通过并联来改进，则其时空图如下图所示。完成全部运算时的流水线效率8033165924ttt4、超级标量机和超级流水线机都能开发指令级的并行性，现假定这两种机器的流水线都为4段，每段均需1个时钟周期。若在超级标量机中，每个时钟周期可同时启动3条指令，而超级流水线机中则是每隔1/3时钟周期启动一条指令。现若要执行6条指令的代码序列，问在两种机器上各需用多少个时钟周期方可执行完毕？解：超级标量机需5个时钟周期，超级流水线机需5.67个时钟周期。5、在CRAY-1机上，V是向量寄存器，设向量长度均为32。S是标量寄存器，所用浮点功能执行部件的执行时间分别为：加法需6拍，相乘需7拍，从存储器读存数需6拍，求倒数近似值及除法需14拍，写入寄存器及启动功能部件（包括存储器）各需1拍。问下列各指令组中的哪些指令可以链接？哪些指令不可链接？哪些指令可以并行执行？试说明其原因并分别计算出各指令组全部完成所需的拍数。（1）V0←存储器（2）V2←V0+V1V1←V2+V3V3←存储器V4←V5*V6V4←V2*V3（3）V0←存储器（4）V0←存储器V3←V1+V2V1←1/V0V4←V0*V3V3←V1+V2V6←V4+V5V5←V3*V4（5）V0←存储器（6）V3←存储器V1←V2+V3V2←V0+V1V4←V5*V6s0←s2+s3s0←s1+s2V3←V1*V4（7）V3←存储器（8）V0←存储器V2←V0+V1V2←V0+V1V4←V2*V3V3←V1+V2存储器←V4V5←V3*V4解：(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拍1、若有一静态多功能流水线分为6段，如下图所示，其中乘法流水线由1、2、3、6段组成，加法流水线由1、4、5、6段组成。使用流水线时，要等某种功能（如加法）操作都处理完毕后才能转换成另一种功能（如乘法）。若要计算：A×B=（a1+b1）×（a2+b2）×（a3+b3）问：（1）在上述流水方式下，完成A×B需多少时间？画出时空图并计算此流水线的使用效率和吞吐率。（2）与顺序运算方式相比，加速比为多少？123456τττττ2τT解:(1)12341234455512312319τS61234545完成A*B需要的时间=19τ114256195253195Tp1925195253Sp效率为：吞吐率为：（2）加速比为：2、已知某单功能非线性流水线的预约表如下图，要求：（1）列出禁止表F和冲突向量C。（2）画出该流水线状态图，确定其最小平均延迟以