郑纬民版计算机系统结构答案

1《计算机系统结构》习题解答目录第一章(P33)1.7-1.9（透明性概念），1.12-1.18（Amdahl定律），1.19、1.21、1.24（CPI/MIPS）第二章(P124)2.3、2.5、2.6（浮点数性能），2.13、2.15（指令编码）第三章(P202)3.3（存储层次性能），3.5（并行主存系统），3.15-3.15加1题（堆栈模拟），3.19中(3)(4)(6)(8)问（地址映象/替换算法--实存状况图）第四章(P250)4.5（中断屏蔽字表/中断过程示意图），4.8（通道流量计算/通道时间图）第五章(P343)5.9（流水线性能/时空图），5.15（2种调度算法）第六章(P391)6.6（向量流水时间计算），6.10（Amdahl定律/MFLOPS）第七章(P446)7.3、7.29（互连函数计算），7.6-7.14（互连网性质），7.4、7.5、7.26（多级网寻径算法），7.27（寻径/选播算法）第八章(P498)8.12（SISD/SIMD算法）第九章(P562)9.18（SISD/多功能部件/SIMD/MIMD算法）(注：每章可选1-2个主要知识点，每个知识点可只选1题。有下划线者为推荐的主要知识点。)2第一章(P33)1.7(1)从指定角度来看，不必要了解的知识称为透明性概念。(2)见下表，“√”为透明性概念，“P”表示相关课文页数。1.8见下表，“√”为透明性概念，“P”表示相关课文页数。1.9见下表，“√”表示都透明，“应”表示仅对应用程序员透明，“×”表示都不透明。1.12已知Se=20,求作Fe-Sn关系曲线。将Se代入Amdahl定律得enFS2019111.13上式中令Sn=2，解出Fe=10/19≈0.5261.14上式中令Sn=10，解出Fe=18/19≈0.9471.15已知两种方法可使性能得到相同的提高，问哪一种方法更好。(1)用硬件组方法，已知Se=40，Fe=0.7，解出Sn=40/12.7≈3.1496（两种方法得到的相同性能）(2)用软件组方法，已知Se=20，Sn=40/12.7，解出Fe=27.3/38≈0.7184（第二种方法的百分比）(3)结论：软件组方法更好。因为硬件组需要将Se再提高100%（20→40），而软件组只需将Fe再提高1.84%（0.7→0.7184）。1.1757.34.1559.01.01nS1.18记f──时钟频率，T=1/f──时钟周期，B──带宽（Byte/s）。方案一：)/(4411sBytefTB方案二：)/(5.3421%252%752sBytefTB模m交叉，√，浮点数据，×，P4通道与I/O处理机，×，P4总线宽度，√，阵列运算部件，×，结合型与独立型通道，√，单总线，√，访问保护，×，中断，×，指令控制方式，√，堆栈指令，×，最小编址单位，×，Cache存储器，√，指令地址寄存器，×，指令缓冲器，√，时标发生器，√，条件码寄存器，×，乘法器，√，主存地址寄存器，√，磁盘，×，先行进位链，√，移位器，√，通用寄存器，×，中断字寄存器，×，数据通路宽度，√，虚拟存储器，应，Cache存储器，√，程序状态字，×，“启动I/O”指令，应，“执行”指令，×，指令缓冲寄存器，√，Sn20101Fe31.19由各种指令条数可以得到总条数，以及各百分比，然后代公式计算。41510iiICIC(1)4155.108.0215.0232.0245.01)(iiiICICCPICPI(2)806.2555.1401055.1104010666CPIfMIPS(3)（秒）003876.040055.1106MIPSICT1.21(1)24.21.0812.0418.026.01CPI(2)86.171024.2104010666CPIfMIPS1.24记Tc──新方案时钟周期，已知CPI=CPIi=1原时间=CPI×IC×0.95Tc=0.95IC×Tc新时间=（0.3×2/3+0.7）×IC×Tc=0.9IC×Tc二者比较，新时间较短。第二章(P124)2.3（忽略P124倒1行～P125第8行文字，以简化题意）已知2种浮点数，求性能指标。此题关键是分析阶码、尾数各自的最大值、最小值。原图为数据在内存中的格式，阶码的小数点在其右端，尾数的小数点在其左端，遵守规格化要求。由于尾数均为原码，原码的绝对值与符号位无关，所以最大正数与最小负数的绝对值相同，可用“±最大绝对值”回答；最小正数与最大负数的绝对值相同，可用“±最小绝对值”回答。第1小问中，阶码全部位数为8，作无符号数看待真值为0～255，作移-127码看待真值为-127～+128；尾数（不计符号位）有23位小数，另加1位整数隐藏位，所以尾数绝对值为1.0～2.0–2-23，有效位数p=24；第2小问中，阶码全部位数为11，作无符号数看待真值为0～2047，作移-1023码看待真值为-1023～+1024；尾数（不计符号位）有52位小数，另加1位整数隐藏位，所以尾数绝对值为1.0～2.0–2-52，有效位数p=53。最大绝对值为最大阶码与最大尾数绝对值的组合，最小绝对值为最小阶码与最小尾数绝对值的组合。代入相关公式后得最终结果如下表。2.5(1)rm=2，re=2，p=24（隐藏最高位）,q=7。32位64位±最大绝对值±(1-2-24)·2129±(1-2-53)·21025±最小绝对值±2-127±2-1023表数精度δ2-242-53表数效率η100%100%4(2)Nmax=1.7×1038，-|N|min=-1.47×10-39δ≤5.96×10-8≈10-7.22，η=100%2.6(1)0.2=0.333333H×160设阶码为移-63码（即-26+1，原题未指明）0.2=0.110011001100110011001101B×2-2（其中最高有效位需隐藏）阶码为移-127码（即-27+1）(2)符号位不变，（阶码–63）×4+127；尾数左规，除去最高位；(3)符号位不变，（阶码–127）/4+63；尾数补最高位，按除法余数右移若干位，左补0。2.13已知10条指令使用频度，求3种编码方法的平均码长与信息冗余量。(1)此问中的“最优Huffman编码法”实际是指码长下限，即信源的平均信息量──熵，代公式得H=2.9566。(2)Huffman编码性能如下表；(3)2/8扩展编码是8/64/512法的变种，第一组2条指令，码长为2（1位扩展标志，1位编码）,第二组8条指令，码长为4（1位扩展标志，与第一组区别，加3位编码），编码性能如下表；(4)3/7扩展编码是15/15/15法的变种，第一组3条指令，码长为2（共有4种组合，其中3种组合分别代表3条指令，留1种组合作为扩展前缀标志）,第二组7条指令，码长为5（2位固定的前缀扩展标志，与第一组区别，加3位编码，只用其中7种组合），编码性能如下表。2.15(1)15条/63条/64条(2)14条/126条/128条第三章(P202)3.3直接代公式计算存储层次性能指标。(1)74ns，38ns，23.6ns(2)0.258，0.315，0.424(3)T256KT128KT64Kc256Kc128Kc64K(4)19.092，11.97，10.0064。答案是256K方案最优。3.5已知ggKnn)1(1，其中g=0.1依题意有2.0)1(12.0)1(111ggKggKnnnn1位7位6位001111113333331位8位23位00111110110011001100110011001101Huffman编码2/8扩展编码3/7扩展编码平均码长L2.993.13.2信息冗余量R1.10%4.61%7.59%5整理得0.9n≥0.2，解出28.159.0lg2.0lgn，向下取整，得15；按另一种题意理解是向上取整，得16，也对。3.15欲知可能的最高命中率及所需的最少主存页数，较好的办法是通过“堆栈模拟法”，求得命中次数随主存页数变化的函数关系。下图就是“堆栈模拟图”，其中“√”表示命中。(1)Hmax=7/12≈58.3%(2)n=4(3)当1次页面访问代表连续1024次该页内存储单元访问时，后1023次单元访问肯定是命中的，而第1次单元访问的命中情况与这1次页面访问的命中情况相同。根据上图中最高命中情况，共有7次页命中（折算为7×1024次单元命中），5次页不命中（折算为5×1023次单元命中，也可写为5×1024-5），单元访问总次数为12×1024，故有：Hcell=(12×1024-5)/(12×1024)=12283/12288≈99.96%3.15加1题一个二级存储层次，采用全相联映象和最久没有使用算法，实存共5页，为2道程序分享，页地址流分别如下P1=12341321P2=12342233试作2个实存分配方案，分别使2道程序满足(1)命中率相同；(2)命中次数之和最大。解：分别为2道程序作“堆栈模拟图”，其中“√”表示命中。P=453251323513命中次数4532513235134532513235145325112354432551224444444n=10n=2√1n=3√√√3n=4√√√√√√√7n=5√√√√√√√7P1=12341321命中次数N(1)12341321123413212341312244n1=10n1=20n1=3√√2n1=4√√√√46将两图结果综合，得到4个分配方案的命中率情况表如下结论如下(1)命中率相同的方案是n1=3而n2=2；(2)命中次数之和最大的方案是n1=4而n2=1。3.19中(3)(4)(6)(8)问(3)(4)通过作“实存状况图”模拟各虚块的调度情况，可获得Cache的块地址流序列。此问最容易出错的地方是忽略“组相联”地址约束，将虚页装错实组。另外没有及时标注“*”号也容易导致淘汰对象错误。(6)H=4/12≈33%(8)做法同3.15题(3)问，Hcell=(12×16-8)/(12×16)≈95.8%第四章(P250)P2=12342233命中次数N(2)12342233123442212334411111n2=1√√2n2=2√√2n2=3√√√√4n2=4√√√√465N(1)+N(2)432N(1)N(2)11+42+33+24+1n11234N(1)0024n24321N(2)4422N(1)+N(2)4446虚存实页0123虚组000√√1实存1√√虚组12·0实组02√√3·1虚3√√虚组24·2实组1页4√√5·35√√虚组366√√77√√(a)虚页集合与实页集合的对应关系(b)对应关系表（√为有关系）P=624146304573C044*4444*44*4*4*C111*1*1*00*555C266*6*6*6*66*6*6*6*77*C322222*33333*3入入入入中中替替中替替中C=23010231012374.5已知中断服务次序为3-2-4-1，。(1)中断屏蔽字表如下图；(2)中断过程示意图如右图。4.8(1)f=2×105字节/秒，T=5us(2)Ts+Td=5us，通道时间图如下。作图时注意：至少要画到最慢设备的第二次请求出现，才能确定是否丢失数据（因为响应优先级低的设备较易丢失数据）。(3)5，160，20，40；(4)D2丢失第一次请求的数据；(5)参见P245。第五章(P343)5.9为了缩短运算时间，首先应考虑“最少切换算法”，即先执行完所有乘法（任务编号1-6）再执行加法（任务编号7-11），其次在加法中采用“最少相关算法”（即二叉树算法）。记c1=A1×B1，……，c6=A6×B6，下图(a)是加法的计算顺序二叉树，注意任务10应该用前一级最早完成的任务7和8的结果，如果用任务9的结果则要推迟1拍启动，使总时间增加1拍。时间中断请求主