《《计算机系统结构》总复习-习题2014》由会员分享，可在线阅读，更多相关《《计算机系统结构》总复习-习题2014（158页珍藏版）》请在金锄头文库上搜索。
1、1,计算机系统结构,总复习,2,第一章 基本概念（P1）,本章介绍计算机系统结构的一些基本知识。包括定性知识和定量知识两大组内容。为了便于学习，本章各节重新编号，与教材编号不同。 定量知识：对计算机性能进行定量评价的几个重要公式。,3,本章重点,本章从定性知识和定量知识两个方面介绍计算机系统结构的基本概念。有关重点如下：(1) Amdahl定律；(2) 平均周期数CPI公式，程序执行时间Te公式；(3) 每秒百万指令数MIPS公式，每秒百万浮点数MFLOPS公式。,4,1.定量知识3个性能公式,1.1 Amdahl定律（加快经常性事件原理，P9）,其中：Sn 全局加速比； To 原执行时间（o
2、ld）； Tn 新执行时间（new）； Se 被改进部分的局部加速比； Fe 被改进部分原执行时间占原来总时间的百分比。,5,Amdahl定律的推导,6,Amdahl定律的图形,从图1.2可以看出，增大Se和Fe对Sn都有提升作用；但当Fe固定时，一味增大Se对Sn的作用会越来越不显著。,作1.12 假定利用增加向量模块来提高计算机的运算速度。计算机处理向量的速度比其通常的运算要快20倍，将可用向量处理部分所花费的时间占总时间的百分比称为可向量化百分比。 （1）求出加速比S和向量化百分比之间的关系式作1.13 （2）当要得到加速比为2时的可向量化百分比F为多少？作1.14 （3）为了获得在向量
3、模式所得到的最大加速比的一半，可向量化百分比F为多少？,7,(2) 由（1）式有,解（1）：由Amdahl定律知,(1),8,(3) 由题意可知,9,作1.17 假设高速缓存Cache工作速度为主存的5倍，且Cache被访问命中的概率为90，则采用Cache后，能使整个存储系统获得多高的加速比？,解：fe=0.9 ，re=5,10,1.2 CPI与程序执行时间Te（P11）,CPI是衡量CPU执行指令效率的重要指标。让我们先考虑一个标准测速程序的全部执行时间Te和其中所有第i种指令的累计时间Ti，易知,11,12,1.3 每秒百万指令数MIPS与每秒百万浮点数MFLOPS（P11）,例题：P1
4、0，例1.1例1.5。 P33，题12 ，题13 ，题14 。,例1.19 用一台4OMHz处理机执行标准测试程序，它含的混合指令数和相应所需的时钟周期数如下：指令类型 指令条数 时钟周期数整数运算 45000 1数据传送 32000 2浮点运算 15000 2控制传送 8000 2求有效CPI、MIPS速率和程序的执行时间。,13,解：依题意可知 IN=105条，n=4,14,作1.20 某工作站采用时钟频率为15MHz、处理速率为10MIPS的处理机来执行一个巳知混合程序。假定每次存储器存取为1周期延迟、试问： (1) 此计算机的有效CPI是多少? (2) 假定将处理机的时钟提高到30MH
5、z，但存储器子 系统速率不变。这样，每次存储器存取需要两个时钟 周期。如果30指令每条只需要一次存储存取，而另 外5每条需要两次存储存取，还假定已知混合程序 的指令数不变，并与原工作站兼容，试求改进后的处 理机性能。,解 (1),15,(2) 依题意可知：30%的指令需要一次存储存取，则这些指令在处理器提高时钟频率之后需要增加1个时钟周期；另外5%的指令需要增加2个时钟周期。,改进后性能提高情况可用CPU时间之比表示：,16,作1.21 假设在一台40MHz处理机上运行200 000条指令的目标代码，程序主要由四种指令组成。根据程序跟踪实验结果，已知指令混合比和每种指令所需的指令数如下：,(1
6、)计算在单处理机上用上述踪数据运行程序的平均CPI(2)根据(1)所得CPI，计算相应的MIPS 速率和程序的执行时间,17,解：依题意可知 IN=2105条，n=4，,18,19,第二章 指令系统（P36）,本章介绍指令系统设计中2个最基本的内容：数据表示、操作码优化。,本章重点,(1) Huffman编码方法；(2) 等长扩展编码方法（15/15/15法，8/64/512法）；(3) 编码方法性能指标（平均码长L，信息冗余量R）。,20,2.1 Huffman压缩编码（P91）,(1)Huffman压缩概念（最佳编码定理）：当用n个长度不等的代码分别代表n种发生概率不等的事件时，按照短代码
7、给高概率事件、把长代码给低概率事件的原则分配，可使平均码长达到最低。(2) Huffman编码方法 这种编码方法由两个过程组成。频度合并：将全部n个事件（在此即为n条指令）的频度值排序，选取其中最小的2个频度合并，然后将剩下的n-1个频度再次排序，再合并最小的2个频度，如此重复，直至剩下1个频度为止。记录所有的合并关系，形成一棵二叉树 Huffman树，所有原始频度值充当树叶，而最后剩下的总频度1为树根；码元分配：从树根开始，对每个中间结点的左右2个分支边各赋予一位代码“0”和“1”（“0”在哪一侧不限）。读出从根结点到任一片树叶的路径上依次出现的代码位就排成了这个事件（即指令）的完整编码。由
8、于频度高的事件较晚被合并，它的编码位数也就较少，符合Huffman压缩原则。 上面所说的频度值就是各事件实际出现次数的百分比，它是理论出现概率的近似值。,21,平均码长：各事件编码长度的数学期望。,信息冗余量：它表明消息编码中“无用成分”所占的百分比。,22,2.2 扩展编码方法（等长扩展法，P94-95）,用码长表示：例如4-8-12法。这并不能说明具体编码方法，例如下面两种编码方法都是4-8-12法。用码点数表示：例如15/15/15法，8/64/512法15/15/15法，每一种码长都有4位可编码位（前头可以有相同的扩展标识前缀），可产生16个码点（即编码组合），但是至多只能使用其中15
9、个来表示事件，留下1个或多个码点组合作为更长代码的扩展标识前缀。已经用来表示事件的码点组合不能再作为其它更长代码的前导部分，否则接收者会混淆。这就是“非前缀原则”。8/64/512法，每一种码长按4位分段，每一段中至少要留下1位或多位作为扩展标识。各段剩下的可编码位一起编码，所产生的码点用来对应被编码事件。每一段中的标识位指出后面还有没有后续段。,1,0,0,0,0,0,0,1,1,1,0.09,0.15,1,0.06,1,0.03,0.03,0.04,0.05,0.15,0.30,0.40,I7 I6 I5 I4 I3 I2 I1,例2.1 某指令系统各指令使用频度如下：I1 I2 I3 I
10、4 I5 I6 I7 0.4 0.3 0.15 0.05 0.04 0.03 0.03 1.Huffman编码,23,由此可得到哈夫曼编码如下： I1: 0 I2: 10 I3: 110 I4: 11100 I5: 11101 I6: 11110 I7: 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% 指令长度个数=4,24,2.扩展哈夫曼编码I1, I2, I3 用两位: 00, 01, 10I4, I5, I6, I7 用四位: 1100, 1
11、101, 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%,25,操作码的扩展（等长扩展）,平均码长： 2. 2 2.3,26,作 2.13 采用最优Huffman编码法（信息熵）的操作码最短平均长度为：,27,28,例2.2 指令系统共有42种指令，前15种使用频率平均为0.05，中间13种使用频率平均为0.015，最后14种使用频率平均为0.004。如何编码？,解：因频率分布有三种，故码长可有三种；,因每段指令数基本相同，故可采用等长扩展(4-8-1
12、2位)， 保留特征码的每段指令数相同(15-15-15)方法。结果如图所示；,结果：采用15-15-15扩展方法，最后一种编码用于扩展，每段00001110用于编码，1111用于扩展。,29,例2.3 某模型机有9条指令，其使用频率为：ADD（加）30%SUB（减）24%JOM（按负转移）6% STO（存）7%JMP（转移）7% SHR（右移）2%CIL（循环左移）3% CLA（清加）20%STP（停机）1% 要求有两种指令字长，都按双操作数指令格式编,采用扩展操作码，并限制只能有两种操作码码长。设该机有若干个通用寄存器，主存为16位宽，按字节编址，采用整数边界存贮，任何指令都在一个主存周期中
13、取得，短指令为寄存器寄存器型，长指令为寄存器主存型，主存地址应能变址寻址。,30,解：(1) Huffman树的形式如图所示。,0.01,0.02,0.03,0,1,0.03,0.06,0,1,0.06,0.12,0,1,0.07,0.07,0.14,0,1,0.26,0,1,0,0.30,0.20,0.24,0.44,0,1,0.56,1,0,0,1,1,31,由上图可得到的Huffman编码为： ADD(加) 30% 01 SUB(减) 24% 11 CLA(清加) 20% 10 JOM(按负转移) 6% 0001 STO(存) 7% 0011 JMP(转移) 7% 0010 CIL(循环
14、左移) 3% 00001 SHR(右移) 2% 000001 STP(停机) 1% 000000因此，操作码的平均码长为：,32,(2) 采用2-5扩展的操作码编码为： ADD(加) 30% 00 SUB(减) 24% 01 CLA(清加) 20% 10 JOM(按负转移) 6% 11000 STO(存) 7% 11001 JMP(转移) 7% 11010 SHR(右移) 2% 11011 CIL(循环左移) 3% 11100 STP(停机) 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个字节),
