- 2022-08-13 发布 |
- 37.5 KB |
- 24页
申明敬告： 本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
文档介绍
计算机系统结构习题答案(李学干)
计算机系统结构习题解答第一章习题一1.2一台经解释实现的计算机，可以按照功能划分成4级。每一级为了执行一条指令需要下一级的N条指令解释。若执行第1级的一条指令需K纳秒时间，那么执行第2、3、4级的一条指令个需要多少时间？解：①分析：计算机按功能分级时，最底层的为第1级。向上一次是第2、3、4级。解释执行是在低级机器级上，用它的一串指令或语句来解释执行高一级上的一条指令的功能。是逐条解释的。②解答：执行第2、3、4级的一条指令各需KNns,KN2ns,KN3ns的时间。1.3操作系统机器级的某些指令就用传统机器级的指令，这些指令可以用微程序直接实现，而不由操作系统自己来实现。根据你对习题1.2的回答，你认为这样做有哪两个好处？答：可以加快操作系统操作命令解释的速度。同时也节省了存放解释操作命令这部分解释程序所占用的空间。简化了操作系统机器级的设计。也有利于减少传统机器级的指令条数。1.5硬件和软件在什么意义上是等效的？在什么意义上是不等效的？试举例说明。答：硬件和软件在逻辑意义上是等效的。在物理意义上是不等效的。①在原理上，用硬件或固件实现的功能完全可以用软件来完成。用软件实现的功能也可以用硬件或固件来完成。功能一样。②只是反映在速度、价格、实现的难易程度上，这两者是不同的。性能不同。③例如，浮点运算在80386以前一直是用软件实现的。到了80486，将浮点运算器集成到了CPU中，可以直接通过浮点运算指令用硬件实现。但速度却高的多。1.9下列哪些对系统程序员是透明的？哪些对应用程序员是透明的？系列机各档不同的数据通路宽度；虚拟存储器；Cache存储器；程序状态字；“启动I/O”指令；“执行”指令；指令缓冲器。答：①对系统程序员和应用程序员均透明的：是全用硬件实现的计算机组成所包含的方面。有：数据通路宽度、Cache存储器、指令缓冲器。②仅对应用程序员透明的：是一些软硬件结合实现的功能。有：虚拟存储器、程序状态字、“启动I/O”指令。③均不透明的：“执行”指令。24\n1.16假设高速缓存Cache工作速度为贮存的5倍，且Cache被访问命中的概率为90%，则采用Cache后，能使整个存储系统获得多高的加速比？解：Se=5Fe=90%=0.9根据Amdahl定律，加速比Sn=1/((1-Fe)+Fe/Se)=1/(0.1+0.9/5)=1/0.28=3.571.18用一台40MHz处理机执行标准测试程序，它含的混合指令数和相应所需的时钟周期数如下：指令类型指令数时钟周期数整数运算450001数据传送320002浮点150002控制传送80002解：IC=45000+32000+15000+8000=100000=105CPI=（1/IC）*∑（CPIi*Ii）=（1/105）*（45000*1+（32000+15000+8000）*2）=155000/100000=1.55MIPS=f/(CPI*106)=40*106/(1.55*106)=25.8Te=IC/(MIPS*106)s=3.875ms1.22对在SUNSPARC2工作站上，对SPECBenchmark进行测试，获得了如下所示的速率值，求其算术、几何以及调和平均值（以MFLOPS表示）。解：nn∑Ti=∑1/Ri=(1/10.7+1/8.9+1/8.3+1/5.0+1/8.7+1/9.0+1/9.7+1/11.1+1/7.8+1/5.6)i=1i=1=1.25229nAm=(∑Ti)/10=0.125229Am=0.125229*1/(106)s=0.125μSi=1nHm=n/(∑1/Ri)=10/1.25229=7.985MFLOPSi=124\n第二章习题二2.3解1:①最大正数：尾数最大m=0.1111…1=(1-2-23),阶码最大e=+127。加上一个隐藏位，最大正数为FMax32=（2-2-23）*2+127=+（3.4*1038）②最小正数：尾数最小m=1.000…0=1.0,阶码最小e=-126。所以，规格化的最小数Min1=1*2-126=5.877*10-39若e=0,且m≠0,N=(-1)s*2-127*(0.m)。则最小正数为：FMin32=+2-127*(0.000…1)=+2-150=1.5*10-45。√③最大负数：为=-（1.5*10-45）④最小负数:为=-（3.4*1038）⑤表数精度：δ=2-p=2-24⑥表数效率：η=100%解2：①最大正数：FMax64=+（（2-2-52）*2+1023）=+（1.798*10308）②最小正数：FMin64=+2-1023*(0.000…1)=+（2-1075）=+（5.0*10-324）10-x=2-1075à10x=21075àx=㏒1021075=1075*㏑2/㏑10=323.62.5解：①浮点数格式：六个参数rmremepq四个已经确定rm=2、re=2。尾数m取原码、纯小数，阶码e用移码。只剩p和qδ=10-7.2N=103824\n㏒δP>-------------=23.94㏒2㏒N㏒(-------+1)㏒2q>------------------=7.08㏒2取p=24q=8则整个浮点数为34位。11qpmfefem②表数精度：δ=2-p=2-24③表数效率：η=50%2.10解：①最短平均长度nH=-∑Pi*㏒2Pi=2.96i=1②Huffman树：010110111011110111110111111011111110111111110111111111平均长度H2=0.25*1+0.20*2+0.15*3+0.10*4+0.08*5+0.08*6+0.05*7+0.04*8+0.03*9+0.02*9=3.50冗余R2=15.6%24\n③2/8扩展码：00011000平均长度H3=3.1010011010冗余R3=4.5%10111100110111101111④3/7扩展码000110平均长度H4=3.101100011001冗余R4=4.5%11010110111110011101111102.12解：①466OPA1A2106OPA16OP双：0000----1110共15种，留1111一个编码单：1111000000…63中，留1111111111一个编码1111111110零1111111111000000--------1111111111111110共63种属于15/63/6324\n②双地址指令的编码空间为四位二进制，最多16种。单地址指令的编码空间为六位二进制，最多64种。∵15×9=135，而14×9=12664+64=128∴取14比较合适。双0000----1101共14种单1110000000…64种11101111111111000000…62种1111111101零1111111110000000…64种11111111101111111111111111000000…62种1111111111111101共为14/126/126种第二章习题33.3解：(0)T1=10ns,T2=60ns,e=0.5,T2/T1=60/10=6①e=1/(H-(1-H)*6)=1/(6-5H)∴6-5H=2命中率H=4/5=0.80等效访问周期为T=HT1+(1-H)T2=0.80*10+(1-0.80)*60=20ns②e2=1/(6-5H′)=0.94∴6-5H′=1/0.94命中率H′=4.64/4.7=0.9872等效访问周期为T′=H′T1+(1-H′)T2=0.9872*10+0.0128*60=10.64ns③设块的大小为bH+n-1H′=-------->H′n=n+h-1n1-H1-Hn=------->4b=-------b=3.91取4个字1-H′1-H′24\n3.7解：CPU性能为1GIPS。其中：CPU取指令，防存一次，带宽1000MW/S。CPU取数和存数，两个字，带宽2000MW/S。总带宽为：1000+2000=3000MW/S。要求存储器系统的等效访问周期不大于：1/3000M=0.333ns三种途径解决主存带宽平衡：①采用并行访问存储器、交叉访问存储器。若体数为m，提高倍数不到m/3。--〉P104。②采用Cache-主存存储系统。设Cache访问周期为Tc,主存访问周期为Tm。Cache命中率为H。则加速比为：SP=Tm/(HTc+(1-H)Tm)=1/(H*(TC/Tm)+(1-H))但实际H一般很高，可达0.9甚至0.99，故SP接近其最大值Tm/Tc③设置各种缓冲存储器：CPU内设置Level1的ICache和DCache。外设置Level2Cache。弥补的倍数计算类似第二步。3.17解：①主存地址：1114区号E组号G组内块号B块内地址W②Cache地址：114组号g组内块号b块内地址w③映像对应：24\n④用LRU替换算法：时间t123456789101112主存块B6B2B4B1B4B6B3B0B4B5B7B3组0C044*4444*44*4*4*C111*1*1*00*555组1C266*6*6*6*66*6*6*6*77*C322222*33333*3命中情况HHHH⑥命中率：Hc=4/12=0.333其他：设主存每个分体的存取周期为2μs,宽度为4个字节。采用模m多体交叉存取，但实际频宽只能达到最大频宽的0.6倍。现要求贮存实际频宽为4MB/S.问主存模数m应取多少方能使两者速度基本适配？其中m取2的幂。解：多体交叉存储器的最大频宽为：分体数*单位频宽=m*宽度/存储周期=m*4B/2μs。实际频宽为0.6*m*4B/2μs根据要求0.6*m*4B/2μs〉=4MB/Sm>=3.667所以m应取4。第五章习题55.6解：24\nTP1=5/8ΔtTP2=2*5/(8Δt+7Δt)∴TP=5n/(Δt+7nΔt)TPmax=limTP=5/7Δtn->∝S=T0/TK=4*5*nΔt/(Δt+7nΔt)≈20/7=2.857E=(4*5*nΔt)/(4*(Δt+7nΔt))=5n/(7n+1)Emax=lime=5/7=0.71=71%5.7解：为了避免流水线的先写后读相关，使流水线性能尽可能高，将F的表达式调整为：{[（A1+A2）+（A3+A4）]+（A9+A10）}+[（A5+A6）+（A7+A8）]即A1—A10先两两成对，5个加法流水执行。两个和一出来，就进行下一加法。所以：TP=9/21ΔtS=（9*5Δt）/21Δt=2.143E=（9*5Δt）/（5*21Δt）=9/21=0.43=43%24\n5.15解：C=A*B其中点积7Cij=∑aik*bkj(i,j=0,1,2…7)K=0每项的计算，共有8个乘法，7个加法。每种运算：取指1、译码1、运算3。共需5个时钟周期。①顺序执行：一项的运算共需：8*5+7*5=75拍8*8项共需：8*8*75*20=96000ns②两功能静态流水线：先计算8个流水执行，再计算7个加法，时空图如下：步骤为：{[（ai0b0j+ai1b1j）+(ai2b2j+ai3b3j)]+[(ai4b4j+ai5b5j)+(ai6b6j+ai7b7j)]}共需12+13+5=30拍8*8项共需8*8*30*20ns=38400ns③两部件并行工作：时空图如下：24\n解题步骤为：{[（（（（（ai0b0j+ai1b1j）+ai2b2j）+ai3b3j）+ai4b4j）+ai5b5j）+ai6b6j]+ai7b7j}每次点积共需5*9=45拍。8*8项共需8*8*45*20ns=57600ns①乘、加两条流水线，可同时工作.其流水线工作时空图如下：解题步骤：{[（（ai0b0j+ai1b1j）+（ai6b6j））+（ai4b4j+ai5b5j）]（（ai2b2j+ai3b3j）+ai7b7j）}完成点积共需26拍。8*8项共需8*8*26*20ns=33280ns。其他：设指令由取指、分析、执行3个子部件组成。每个子部件经过时间为Δ24\nt,连续执行12条指令。请分别画出在常规标量流水处理机以及度为m=4的超标量处理机、超流水线处理机上工作的时空图。分别计算出他们相对常规标量处理机的加速比SP。解：①常规标量流水处理器：连续执行12条指令共需14Δt。②超标量处理机：m=4连续执行完共需5Δt比常规标量流水处理的加速比SP=14Δt/5Δt=2.8。24\n连续执行12条共需5.76Δt。比常规标量流水处理的加速比为：SP=14Δt/5.75Δt=2.43。第五章习题66.6解：①三条向量指令之间：既没有源Vi冲突，又没有功能部件的使用冲突，更没有Vi先写后读相关。因此，三条向量指令，可以并行流水执行。执行拍数，取三条指令拍数最多的。1+6+1+311+6+1+311+7+1+31=40拍∴三条指令执行完共需40拍。②三条向量指令之间：没有源Vi冲突没有功能部件冲突但是第1、2条的结果是第三条的源（先写后读相关）。因此，需要第一条比第二条先一拍启动。同时第1、2条链接到第3条。1+7+11+6+1+1+6+1+31=48拍③第1、2两条既没有源Vi冲突，又没有功能部件的使用冲突，更没有Vi先写后读相关。可以并行。但与第三条有先写后读相关。故第1、2两条并行后与第三条链接执行。第四条与第二条有功能部件冲突，只能串行。24\n1+6+11+6+1+1+7+1+31+1+6+1+31=87拍。④四条向量指令之间：没有源Vi冲突，也没有功能部件冲突。但依次有“先写后读”相关。因此，可以把四条指令全部链接执行。执行总拍数为：（1+6+1）+（1+7+1）+（1+6+1）+（1+6+1）+31=72拍⑤前三条指令之间：既没有源Vi冲突，又没有功能部件的使用冲突，更没有Vi先写后读相关。完全可以并行执行。第四条尽管执行加法，但却是标量加法，参照P262的图6.10，实际无功能部件冲突。得出结论：四条指令完全可以并行执行。1+6+11+6+11+7+1+31=40拍。执行时间取四条中最长的。但标量的执行拍数要远比向量指令低，故未列出。6.7解：四条指令无源Vi冲突，又没有功能部件冲突。但依次出现“先写后读”相关。将四条指令依次链接成一个更大的流水链，流水执行。（1+7+1）+（1+3+1）+（1+4+1）+（1+2+1）+63=87拍6.8解：①V0V1V2V3V4V5ABCDEF还有V6---V15可以用。计算（A+B）*C用：V6<-V0+V1V7<-V2*V6采用链接技术。（1+2+1）+（1+3+1）+7=16拍②流水线不停流情况下，计算（D+E）*F用：V8<-V3+V4V9<-V5*V8采用链接技术。（1+2+1）+（1+3+1）+7=16拍③共需16+16=32拍④（A+B）*C计算，有8次加法，8次乘法。（D+E）*F计算相同。共执行8+8+8+8=32次浮点运算。总执行时间为32*50*10-3S=1.6S。所以：实际吞吐率为：32/1.6=20MFLOPS。6.9解：Z=A*（B+C）①运算分解成2条向量指令：V3<-V0+V1V4<-V2*V3②采用链接技术：第1条与第2条链接执行。但一次只能进行64个分量的计算。执行时间为:(1+6+1)+(1+7+1)+63=80拍③采用分段开采技术：后64个分量的计算仍然为80拍④其实际吞吐率：浮点运算次数为：（64+64）+（64+64）=25624\n总时间为：（80+80）=160拍，假设一拍的时间为ks。则实际吞吐率：256/(160*k*106)=(1.6/k)*10-6MFLOPS附加题：7在下列的处理机上计算S=∏（Xi+a）,求最短执行时间。向量X和标量a在i=0内存中。从内存读一个数据到寄存器需10ns，做一次乘法需要20ns,做一次加法需要15ns,取指令、译码、读寄存器、写寄存器的时间忽略不计。写出主要计算步骤。向量处理机，有访存、乘法、加法三个独立的操作部件。三个操作部件均采用流水线结构，流水线周期为5ns。（求最后4个数的成绩可以用标量流水线方法计算）。解：n①S==∏（Xi+a）i=0=(X0+a)(X1+a)(X2+a)(X3+a)(X4+a)(X5+a)(X6+a)(X7+a)②用4条指令实现：V0<-存储器S<-aV1<-V0+SV2<-V2*V1第1、2两条，既没有源Vi冲突，又没有功能部件冲突，更没有Vi先写后读相关。并行执行。第1条的结果第3条引用，故此与第三条链接执行。第4条的头4个分量都设置为1，递归执行。四条指令的执行时间为：2+3+4+7=16拍。③得到结果：V20=V20×V10=1×V10=(X0+a)V21=V20×V11=1×V11=(X1+a)V22=V20×V12=1×V12=(X2+a)V23=V20×V13=1×V13=(X3+a)V24=V20×V14=(X0+a)(X4+a)V25=V21×V15=(X1+a)(X5+a)V26=V22×V16=(X2+a)(X6+a)V27=V23×V17=(X3+a)(X7+a)④将V24、V25、V26、V27标量流水执行三个乘法。24\n需9拍。共需16+9=25拍。最短执行之间为：25*5ns=125ns。第七章习题77.2解：①16台处理器仿ILLACIV连接模式如下：②PU0经一步可将信息传送到他的四个邻居：PU1、PU4、PU12、PU15③PU0经二步可将信息传送到PU2、PU3、PU5、PU8、PU11、PU13、PU14④PU0经三步可将信息传送到PU6、PU7、PU9、PU10。所以最多经过三步，就可以将PU0的信息传送到任何其他处理单元。附加题：写出16台处理器按ILLIACIV闭合螺线阵列互联的互连函数。列出任意处理部件PUi（i=0---15）可任意连到的处理器部件号的一般式。解：N=16n=log2N=4(i=0,1,2,3)①一步可到达的，互联函数有4个，为PM2±0PM2±2PM2-2（x）=（x-4）Mod16上北N1PM2+2（x）=（x+4）Mod16下南S1PM2-0（x）=（x-1）Mod16左西W1PM2+0（x）=（x+1）Mod16右东E124\n②两步可到达的为：垂直PM2+3（x）=（x+8）Mod16南S2水平PM2-1（x）=（x-2）Mod16西W2PM2+1（x）=（x+2）Mod16东E2四角PM2-2（x）-1西北NW2PM2-2（x）+1东北NE2PM2+2（x）-1西南SW2PM2+2（x）+1东南SE2③三步可到达的：还剩4个。（一步的4，两步的7之外的）7.3解：①Cube3(P3P2P1P0)=(~P3)P2P1P0=(~1)101=0101=5②PM2+3（i）=(i+23)Mod16=(13+8)Mod16=5③PM2-0（i）=(i-1)Mod16=(13-1)Mod16=12④Shuffle(P3P2P1P0)=P2P1P0P3=1011=11⑤Shuffle(Shuffle(P3P2P1P0))=P1P0P3P2=0111=724\n7.5画出编号分别为0，1，2…7共8个处理器之间实现多级互联的互连网络。当采用级控制信号为110（丛右到左分别为第0、1、2级）时，第5号处理器连向哪个处理器？级0级1级2级控制K2K1K0=110时：级0的ABCD均为直通，级1的EFGH都为交叉，级2的交叉。则5号处理器与3号相连。7.6解：级控制K2K1K000000101001110010111011100123456711032547622301674533210765444567012355476103266745230177654321024\n①当第i级为直连状态，即K2K1K0=110K2K1K0=101K2K1K0=011时。②当第i级为交换状态，即K2K1K0=001K2K1K0=010K2K1K0=100时请对照表自己总结。③7.5题的三级立方体互连网络：三要素交换单元Ki=0直通连接。1交叉连接。拓扑结构：当第i级处于交叉时，实现Cubei互联函数。控制方式：级控制。同一级的所有开关（比如ABCD）只用一个控制信号（比如K0）。附加题：请画出N=8的三级混洗交换网络，即Omega网络。并说明其三要素。再说明2号处理器将信息广播到4567号处理器时的控制信号。（假定级2的交换开关是A、B、C、D，控制信号分别是KA10、KB10、KC10、KD10）解：①拓扑结构：每一级都包含一个全混拓扑。重复画三次。②采用单元控制方式。每一级有四个（2n-1）四功能交换单元。24\n控制信号是每个交换单元两根线。③广播的实现：C下播，F下播J下播K下播。7.27试确定下列网格计算机和超立方体计算机中的最优寻径路径①假设有一个64个结点的超立方体网络，根据E立方体寻径算法，画出从结点101101发送消息给结点011010的路径，并标出这条路径上的所有中间结点。解：结点数N=64，维数n=log2N=6。源结点S=101101，目的结点D=011010方位R=r5r4r3r2r1r0=SD=110111SD101101101100101110101010111010011010r0=1r1=1r2=1r4=1r5=1第8章习题88.2答：参看P334—P335。8.38.6解：8①P=∑Ai*Bi=A1B1+A2B2+A3B3+A4B4+A5B5+A6B6+A7B7+A8B8i=1共有8个乘法和七个加法。那么对于i=1---n,则有n个乘法和（n-1）个加法。在SISD机器上，是串行执行的，故顺序对速度没有影响。共需拍数：4*8+7*2=46拍----〉4n+2(n-1)=6n-2拍。②在SIMD机器上：24\nPE之间传送一次为一拍，为减少传送步距，在运算中及时地调整互连关系。而PE则可以根据需要处于：活跃或者不活跃。从而画出时空图来。由图可以看出，全部完成点积共需14拍。T=4+1+2+1+2+2+2=14③加速比：Sp=46/14=3.28④设有m个PE：若m查看更多