清华第2版《计算机系统结构》习题解答 华中科技大学计算机学院林安 目录 第一章(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题。有下划线者为推荐的主要知识点。)
1 清华第 2 版《计算机系统结构》习题解答 华中科技大学计算机学院 林安 目录 第一章(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 题。有下划线者为推荐的主要知识点。)
第一章(P33) (1)从指定角度来看,不必要了解的知识称为透明性概念 (2)见下表,“√”为透明性概念,“P”表示相关课文页数 模m父义,了 浮点数据,X,P4 通道与LO处理机,×,P4 总线觅度,√ 阵列运算部件,×, 结合型与独立型通道,√, 访问保护 指令控制方式,√ 堆栈指令,X 最小编址单位,X ache存储器,√ 1.8见下表,“√”为透明性概念,“P”表示相关课文页 指令地址寄存器,×, 指令缓冲器,√ 时标发生器,√ 条件码寄存器, 乘法器,√ 主存地址寄存器,√ 磁盘, 先行进位链,√, 移位器,√ 通用寄存器,X, 中断字寄存器,×, 1.9见下表,“√”表示都透明,“应”表示仅对应用程序员透明,“×”表示都不透明 数据通路宽度,√, 虚拟存储器,应, Cache存储器,√ 程序状态子, “启动IO”指令,应, “执行”指令, 指令缓冲寄存器,√ 1.12已知Se=20,求作Fe-Sn关系曲线。 将Se代入 Adah定律得 1-F。 1.13上式中令Sn=2,解出Fe=10/19≈0.526 1.14上式中令Sn=10,解出Fe=18/19≈0.947 1.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)
2 第一章(P33) 1.7 (1)从指定角度来看，不必要了解的知识称为透明性概念。 (2)见下表，“√”为透明性概念，“P”表示相关课文页数。 1.8 见下表，“√”为透明性概念，“P”表示相关课文页数。 1.9 见下表，“√”表示都透明，“应”表示仅对应用程序员透明，“×”表示都不透明。 1.12 已知 Se=20 , 求作 Fe-Sn 关系曲线。 将 Se 代入 Amdahl 定律得 e n F S 20 19 1 1 − = 1.13 上式中令 Sn=2，解出 Fe=10/19≈0.526 1.14 上式中令 Sn=10，解出 Fe=18/19≈0.947 1.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）。 模 m 交叉，√， 浮点数据，×，P4 通道与 I/O 处理机，×，P4 总线宽度，√， 阵列运算部件，×， 结合型与独立型通道，√， 单总线，√， 访问保护，×， 中断，×， 指令控制方式，√， 堆栈指令，×， 最小编址单位，×， Cache 存储器，√， 指令地址寄存器，×， 指令缓冲器，√， 时标发生器，√， 条件码寄存器，×， 乘法器，√， 主存地址寄存器，√， 磁盘，×， 先行进位链，√， 移位器，√， 通用寄存器 ，×， 中断字寄存器，×， 数据通路宽度，√， 虚拟存储器，应， Cache 存储器，√， 程序状态字，×， “启动 I/O”指令，应， “执行”指令，×， 指令缓冲寄存器，√， Sn 20 1 0 1 Fe
0.1 0914 1.18记f—时钟频率,T=1/f—时钟周期,B——带宽(Byte/s) 方案一:B1==4f(Byte/s) 方案二:B2 75%×2+25%×1 ×4=3.5f(Byte/s) 2T 1.19由各种指令条数可以得到总条数,以及各百分比,然后代公式计算。 IC=>IC:=10 (1)CP=∑(CP1x)=1×045+2×0.32+2×015+2×0.08=1.55 40×10 (2) MIPS ≈25.806 CPIx 155×10°1.55 (3)T= ≈0.003876(秒) MPS×106400 (1)CPI=1×06+2×0.18+4×0.12+8×0.1=224 (2)MIPS= 40×10 CPI×10°2.24×10 1.24记Tc—新方案时钟周期,已知CPI=CPI:=1 原时间=CPI×IC×0.95c=0.95IC×Tc 新时间=(0.3×2/3+0.7)×IC×Tc=0.9IC×Tc 二者比较,新时间较短
3 1.17 3.57 1.4 5 5 0.9 0.1 1 = + Sn = 1.18 记 f ── 时钟频率，T=1/f ── 时钟周期，B ── 带宽（Byte/s）。 方案一： 4 ( / ) 1 4 1 f Byte s T B = = 方案二： 4 3.5 ( / ) 2 75% 2 25% 1 2 f Byte s T B = + = 1.19 由各种指令条数可以得到总条数，以及各百分比，然后代公式计算。 = = = 4 1 5 10 i i IC IC (1) = = = + + + = 4 1 ( ) 1 0.45 2 0.32 2 0.15 2 0.08 1.55 i i i IC IC CPI CPI (2) 25.806 1.55 40 1.55 10 40 10 10 6 6 6 = = = CPI f MIPS (3) 0.003876（秒） 400 1.55 106 = = MIPS IC T 1.21 (1) CPI =10.6+ 20.18+ 40.12+80.1= 2.24 (2) 17.86 2.24 10 40 10 10 6 6 6 = = CPI f MIPS 1.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 223,有效位数p=24 第2小问中,阶码全部位数为11,作无符号数看待真值为0~2047,作移-1023码看待真值为 -1023~+1024;尾数(不计符号位)有52位小数,另加1位整数隐藏位,所以尾数绝对值为1.0~ 2.0-252,有效位数p=53 最大绝对值为最大阶码与最大尾数绝对值的组合,最小绝对值为最小阶码与最小尾数绝对值的 组合。代入相关公式后得最终结果如下表 士最大绝对值 ±(1-22)·223 ±(1-2-3)·203 士最小绝对值 表数精度δ 表数效率n 100% 100% 2.5 (1)r,=2,r。=2,p=24(隐藏最高位),q=7。 (2)Nx=1.7×103,-|N|=-1.47×103 6≤5.96×108≈1072,n=100% 2.6 (1)0.2=0.33333H×16 1位7位 位 设阶码为移-63码(即-2°+1,原题未指明) L01111133331 0.2=0.110011001100110011001101B×22 (其中最高有效位需隐藏) 阶码为移-127码(即-2+1) 001111100110010 101 (2)符号位不变,(阶码-63)×4+127:尾数左规,除去最高位 (3)符号位不变,(阶码-127)/4+63:尾数补最高位,按除法余数右移若干位,左补0。 2.13已知10条指令使用频度,求3种编码方法的平均码长与信息冗余量 (1)此问中的“最优 Huffman编码法”实际是指码长下限,即信源的平均信息量—熵,代公式
4 第二章(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。 (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 码（即-2 6 +1，原题未指明） 0.2 = 0.110011001100110011001101B×2 -2 （其中最高有效位需隐藏） 阶码为移-127 码（即-2 7 +1） (2) 符号位不变，（阶码 – 63）×4 + 127；尾数左规，除去最高位； (3) 符号位不变，（阶码 – 127）/ 4 + 63；尾数补最高位，按除法余数右移若干位，左补 0。 2.13 已知 10 条指令使用频度，求 3 种编码方法的平均码长与信息冗余量。 (1)此问中的“最优 Huffman 编码法”实际是指码长下限，即信源的平均信息量──熵，代公式 32 位 64 位 ±最大绝对值 ±(1-2 -24)·2 129 ±(1-2 -53)·2 1025 ±最小绝对值 ±2 -127 ±2 -1023 表数精度δ 2 -24 2 -53 表数效率η 100% 100% 1 位 7 位 6 位 0 0111111 333333 1 位 8 位 23 位 0 01111101 10011001100110011001101
得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种组合),编码性能如下表 Huffman编码 2/8扩展编码 3/7扩展编码 平均码长L 2.99 信息冗余量R 4.61% 7.59% 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)T256K<T128K<T64K c256K>c128K>c64K (4)19.092,11.97,10.0064。答案是256K方案最优 5已知K 1-(1-g),其中g=0 g 依题意有K=1-(1-g)”1 ≥Kn+021-(-8) g 整理得09≥0.2,解出nS02 ≈1528,向下取整,得15: lg0.9 按另一种题意理解是向上取整,得16,也对。 3.15欲知可能的最高命中率及所需的最少主存页数,较好的办法是通过“堆栈模拟法”,求得命 中次数随主存页数变化的函数关系。下图就是“堆栈模拟图”,其中“√”表示命中
5 得 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)T256K < T128K < T64K c256K > c128K > c64K (4)19.092，11.97，10.0064。答案是 256K 方案最优。 3.5 已知 g g K n n 1− (1− ) = ，其中 g=0.1 依题意有 0.2 1 (1 ) 0.2 1 (1 ) 1 1 + − − + = − − = + + g g K g g K n n n n 整理得 0.9n≥0.2，解出 15.28 lg 0.9 lg 0.2 n ，向下取整，得 15； 按另一种题意理解是向上取整，得 16，也对。 3.15 欲知可能的最高命中率及所需的最少主存页数，较好的办法是通过“堆栈模拟法”，求得命 中次数随主存页数变化的函数关系。下图就是“堆栈模拟图”，其中“√”表示命中。 Huffman 编码 2/8 扩展编码 3/7 扩展编码 平均码长 L 2.99 3.1 3.2 信息冗余量 R 1.10% 4.61% 7.59%