《计算机系统结构》总复习-习题2016.

1计算机系统结构总复习2第一章基本概念（P1）本章介绍计算机系统结构的一些基本知识。包括定性知识和定量知识两大组内容。为了便于学习，本章各节重新编号，与教材编号不同。定量知识：对计算机性能进行定量评价的几个重要公式。3本章重点本章从定性知识和定量知识两个方面介绍计算机系统结构的基本概念。有关重点如下：(1)Amdahl定律；(2)平均周期数CPI公式，程序执行时间Te公式；(3)每秒百万指令数MIPS公式，每秒百万浮点数MFLOPS公式。41.定量知识───3个性能公式1.1Amdahl定律（加快经常性事件原理，P9）其中：Sn──全局加速比；To──原执行时间（old）；Tn──新执行时间（new）；Se──被改进部分的局部加速比；Fe──被改进部分原执行时间占原来总时间的百分比。5Amdahl定律的推导6Amdahl定律的图形从图1.2可以看出，增大Se和Fe对Sn都有提升作用；但当Fe固定时，一味增大Se对Sn的作用会越来越不显著。作1.12假定利用增加向量模块来提高计算机的运算速度。计算机处理向量的速度比其通常的运算要快20倍，将可用向量处理部分所花费的时间占总时间的百分比称为可向量化百分比。（1）求出加速比S和向量化百分比之间的关系式作1.13（2）当要得到加速比为2时的可向量化百分比F为多少？作1.14（3）为了获得在向量模式所得到的最大加速比的一半，可向量化百分比F为多少？7(2)由（1）式有解（1）：由Amdahl定律知FFFS*192020)20/()1(153.01910)20/()1(12FFF(1)8(3)由题意可知95.01918)20/()1(110FFF9作1.17假设高速缓存Cache工作速度为主存的5倍，且Cache被访问命中的概率为90％，则采用Cache后，能使整个存储系统获得多高的加速比？解：fe=0.9，re=5101.2CPI与程序执行时间Te（P11）CPI是衡量CPU执行指令效率的重要指标。让我们先考虑一个标准测速程序的全部执行时间Te和其中所有第i种指令的累计时间Ti，易知11121.3每秒百万指令数MIPS与每秒百万浮点数MFLOPS（P11）例题：P10，例1.1~例1.5。P33，题12，题13，题14。•例1.19用一台4OMHz处理机执行标准测试程序，它含的混合指令数和相应所需的时钟周期数如下：•指令类型指令条数时钟周期数•整数运算450001•数据传送320002•浮点运算150002•控制传送80002•求有效CPI、MIPS速率和程序的执行时间。13•解：依题意可知IN=105条，n=414作1.20某工作站采用时钟频率为15MHz、处理速率为10MIPS的处理机来执行一个巳知混合程序。假定每次存储器存取为1周期延迟、试问：(1)此计算机的有效CPI是多少?(2)假定将处理机的时钟提高到30MHz，但存储器子系统速率不变。这样，每次存储器存取需要两个时钟周期。如果30％指令每条只需要一次存储存取，而另外5％每条需要两次存储存取，还假定已知混合程序的指令数不变，并与原工作站兼容，试求改进后的处理机性能。解(1)15(2)依题意可知：30%的指令需要一次存储存取，则这些指令在处理器提高时钟频率之后需要增加1个时钟周期；另外5%的指令需要增加2个时钟周期。改进后性能提高情况可用CPU时间之比表示：16作1.21假设在一台40MHz处理机上运行200000条指令的目标代码，程序主要由四种指令组成。根据程序跟踪实验结果，已知指令混合比和每种指令所需的指令数如下：指令类型CPI指令混合百分比算术和逻辑运算160%Cache命中的加载/存储218%转移412%Cache失效时访问主存810%(1)计算在单处理机上用上述踪数据运行程序的平均CPI(2)根据(1)所得CPI，计算相应的MIPS速率和程序的执行时间17•解：依题意可知IN=2×105条，n=4，1819第二章指令系统（P36）本章介绍指令系统设计中2个最基本的内容：数据表示、操作码优化。本章重点(1)Huffman编码方法；(2)等长扩展编码方法（15/15/15法，8/64/512法）；(3)编码方法性能指标（平均码长L，信息冗余量R）。202.1Huffman压缩编码（P91）(1)Huffman压缩概念（最佳编码定理）：当用n个长度不等的代码分别代表n种发生概率不等的事件时，按照短代码给高概率事件、把长代码给低概率事件的原则分配，可使平均码长达到最低。(2)Huffman编码方法这种编码方法由两个过程组成。频度合并：将全部n个事件（在此即为n条指令）的频度值排序，选取其中最小的2个频度合并，然后将剩下的n-1个频度再次排序，再合并最小的2个频度，如此重复，直至剩下1个频度为止。记录所有的合并关系，形成一棵二叉树──Huffman树，所有原始频度值充当树叶，而最后剩下的总频度1为树根；码元分配：从树根开始，对每个中间结点的左右2个分支边各赋予一位代码“0”和“1”（“0”在哪一侧不限）。读出从根结点到任一片树叶的路径上依次出现的代码位就排成了这个事件（即指令）的完整编码。由于频度高的事件较晚被合并，它的编码位数也就较少，符合Huffman压缩原则。上面所说的频度值就是各事件实际出现次数的百分比，它是理论出现概率的近似值。21平均码长：各事件编码长度的数学期望。•信息冗余量：它表明消息编码中“无用成分”所占的百分比。222.2扩展编码方法（等长扩展法，P94-95）•用码长表示：例如4-8-12法。这并不能说明具体编码方法，例如下面两种编码方法都是4-8-12法。•用码点数表示：例如15/15/15法，8/64/512法–15/15/15法，每一种码长都有4位可编码位（前头可以有相同的扩展标识前缀），可产生16个码点（即编码组合），但是至多只能使用其中15个来表示事件，留下1个或多个码点组合作为更长代码的扩展标识前缀。已经用来表示事件的码点组合不能再作为其它更长代码的前导部分，否则接收者会混淆。这就是“非前缀原则”。–8/64/512法，每一种码长按4位分段，每一段中至少要留下1位或多位作为扩展标识。各段剩下的可编码位一起编码，所产生的码点用来对应被编码事件。每一段中的标识位指出后面还有没有后续段。10000001110.090.300.601.000.1510.0610.030.030.040.050.150.300.40I7I6I5I4I3I2I1例2.1某指令系统各指令使用频度如下：I1I2I3I4I5I6I70.40.30.150.050.040.030.031.Huffman编码23由此可得到哈夫曼编码如下：I1:0I2:10I3:110I4:11100I5:11101I6:11110I7:11111平均码长L=0.4*1+0.3*2+0.15*3+0.05*5+0.04*5+0.03*5+0.03*5=2.20位信息冗余量R=(2.20-2.17)/2.20=1.36%指令长度个数=4242.扩展哈夫曼编码•I1,I2,I3用两位:00,01,10•I4,I5,I6,I7用四位:1100,1101,1110,1111L=(0.4+0.3+0.15)*2+(0.05+0.04+0.03+0.03)*4=2.30位信息冗余量=(2.30-2.20)/2.30=0.0565=5.65%25411115111110.03I7411105111100.03I6411015111010.04I5411005111000.05I421031100.15I32012100.30I2200100.40I1OP长度lihuffman扩展编码OP长度li操作码OP使用哈夫曼编码频度（Pi）指令操作码的扩展（等长扩展）平均码长：2.22.326作2.13采用最优Huffman编码法（信息熵）的操作码最短平均长度为：2728例2.2指令系统共有42种指令，前15种使用频率平均为0.05，中间13种使用频率平均为0.015，最后14种使用频率平均为0.004。如何编码？0000：15种111011110000：：15种11111110111111110000：：：15种111111111110解：因频率分布有三种，故码长可有三种；因每段指令数基本相同，故可采用等长扩展(4-8-12位)，保留特征码的每段指令数相同(15-15-15)方法。结果如图所示；结果：采用15-15-15扩展方法，最后一种编码用于扩展，每段0000～1110用于编码，1111用于扩展。29例2.3某模型机有9条指令，其使用频率为：ADD（加）30%SUB（减）24%JOM（按负转移）6%STO（存）7%JMP（转移）7%SHR（右移）2%CIL（循环左移）3%CLA（清加）20%STP（停机）1%要求有两种指令字长，都按双操作数指令格式编,采用扩展操作码，并限制只能有两种操作码码长。设该机有若干个通用寄存器，主存为16位宽，按字节编址，采用整数边界存贮，任何指令都在一个主存周期中取得，短指令为寄存器－寄存器型，长指令为寄存器－主存型，主存地址应能变址寻址。30解：(1)Huffman树的形式如图所示。0.010.020.03010.030.06010.060.12010.070.070.14010.260100.300.200.240.44010.561001131•由上图可得到的Huffman编码为：ADD(加)30%01SUB(减)24%11CLA(清加)20%10JOM(按负转移)6%0001STO(存)7%0011JMP(转移)7%0010CIL(循环左移)3%00001SHR(右移)2%000001STP(停机)1%000000因此，操作码的平均码长为：32•(2)采用2-5扩展的操作码编码为：ADD(加)30%00SUB(减)24%01CLA(清加)20%10JOM(按负转移)6%11000STO(存)7%11001JMP(转移)7%11010SHR(右移)2%11011CIL(循环左移)3%11100STP(停机)1%11101因此，操作码的平均码长为：33(3)该机允许使用的可编址的通用寄存器个数为23=8个(4)短指令为寄存器-寄存器型，格式如下：OP(2位)R1(3位)R2(3位)OP(5位)R1(3位)X(2位)相对位移d(6位)(5)访主存操作数地址寻址的最大相对位移量为64个字节(-32~+31个字节)长指令为寄存器-主存型，格式如下：34•作2.14一台模型机共有7条指令，各指令的使用频度分别是35％、25％、20％、10％、5％、3％、2％，有8个通用数据寄存器，2个变址寄存器。•(1)要求操作码的平均长度最短，请设计操作码的编码，并计算所设计操作码的平均长度。•(2)设计8位字长的寄存器－寄存器型指令3条，16位字长的寄存器－存储器型变址寻址方式指令4条，变址范围不小于正、负127。请设计指令格式，并给出各字段的长度和操作码的编码。•。35答:(1)要使得到的操作码长度最短，应采用Huffman编码，Huffman树构造如下36由此可以得到7条指令的编码分别如下：37这样，Huffman编码法得到的操作码的平均长度为：l=2×(0.35+0.25+0.20)+3×0.10+4×0.05+5×(0.03+0.02)=1.6+0.3+0.2+0.25=2.35指令号出现的频率编码135%00225%01320%10410%11055%111063%1111072%1111138作2.14(改）一台模拟机共有7条指令，各指令的使用频度分别为35%，25%，20%，10%，5%，3%，2%。该模拟机有8位和16位两种指令长，采用2-4扩展操作码，8位字长指令为寄存器-寄存器（R-R）二地址类型，16位字长指令为寄存器-存贮器（R-M）二地址变址寻址（-128≤变址范围≤127）类型。•(1)计算操作码的平均码长•(2)该机允许使用多少个可编址的通用寄存器，多少个变址寄存器？•设计该机的