《计算机系统结构》总复习-习题2016.ppt
《《计算机系统结构》总复习-习题2016.ppt》由会员分享,可在线阅读,更多相关《《计算机系统结构》总复习-习题2016.ppt(104页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、计算机系统结构总复习-习题2016第一章第一章 基本概念(基本概念(P1P1)本章介绍计算机系统结构的一些基本知识。包括定性知识和定量知识两大组内容。为了便于学习,本章各节重新编号,与教材编号不同。定量知识:对计算机性能进行定量评价的几个重要公式。2Amdahl定律的图形 从图1.2可以看出,增大Se和Fe对Sn都有提升作用;但当Fe固定时,一味增大Se对Sn的作用会越来越不显著。6作作1.12假定利用增加向量模块来提高计算机的运假定利用增加向量模块来提高计算机的运算速度。计算机处理向量的速度比其通常的运算算速度。计算机处理向量的速度比其通常的运算要快要快20倍,将可用向量处理部分所花费的时间
2、占倍,将可用向量处理部分所花费的时间占总时间的百分比称为可向量化百分比。总时间的百分比称为可向量化百分比。(1)求出加速比)求出加速比S和向量化百分比之间的关系式和向量化百分比之间的关系式作作1.13(2)当要得到加速比为当要得到加速比为2时的可向量化百时的可向量化百分比分比F为多少?为多少?作作1.14(3)为了获得在向量模式所得到的最大加为了获得在向量模式所得到的最大加速比的一半,可向量化百分比速比的一半,可向量化百分比F为多少?为多少?7(2)由(1)式有解(1):由Amdahl定律知(1)8(3)由题意可知9作作1.17假假设设高高速速缓缓存存Cache工工作作速速度度为为主主存存的的
3、5倍倍,且且Cache被被访访问问命命中中的的概概率率为为90,则则采采用用Cache后后,能使整个存储系统获得多高的加速比?能使整个存储系统获得多高的加速比?解:解:fe=0.9,re=5101.2 CPI与程序执行时间Te(P11)CPI是衡量CPU执行指令效率的重要指标。让我们先考虑一个标准测速程序的全部执行时间Te和其中所有第i种指令的累计时间Ti,易知111.3 每秒百万指令数MIPS与每秒百万浮点数MFLOPS(P11)例题:P10,例1.1例1.5。P33,题12,题13,题14。12例例1.191.19 用用一一台台4OMHz4OMHz处处理理机机执执行行标标准准测测试试程程序
4、序,它它含含的的混混合合指指令令数数和和相相应应所所需需的的时时钟钟周周期期数数如如下:下:指令类型指令类型 指令条数 时钟周期数时钟周期数整数运算整数运算 4500045000 1数据传送数据传送 32000 232000 2浮点运算浮点运算 15000 215000 2控制传送控制传送 8000 28000 2求有效求有效CPICPI、MIPSMIPS速率和程序的执行时间。速率和程序的执行时间。13解:依题意可知 IN=105条,n=414作作1.201.20 某工作站采用时钟频率为某工作站采用时钟频率为15MHz15MHz、处理速率为、处理速率为10MIPS10MIPS的处理机来执行一个
5、巳知混合程序。假定每次的处理机来执行一个巳知混合程序。假定每次存储器存取为存储器存取为1 1周期延迟、试问:周期延迟、试问:(1)(1)此计算机的有效此计算机的有效CPICPI是多少是多少?(2)(2)假定将处理机的时钟提高到假定将处理机的时钟提高到30MHz30MHz,但存储器子,但存储器子 系统速率不变。这样,每次存储器存取需要两个时钟系统速率不变。这样,每次存储器存取需要两个时钟 周期。如果周期。如果3030指令每条只需要一次存储存取,而另指令每条只需要一次存储存取,而另 外外5 5每条需要两次存储存取,还假定已知混合程序每条需要两次存储存取,还假定已知混合程序 的指令数不变,并与原工作
6、站兼容,试求改进后的处的指令数不变,并与原工作站兼容,试求改进后的处 理机性能。理机性能。解解(1)15(2)依题意可知:依题意可知:30%的指令需要一次存储存取,则的指令需要一次存储存取,则这些指令在处理器提高时钟频率之后需要增加这些指令在处理器提高时钟频率之后需要增加1个时个时钟周期;另外钟周期;另外5%的指令需要增加的指令需要增加2个时钟周期。个时钟周期。改进后性能提高情况可用改进后性能提高情况可用CPU时间之比表示:时间之比表示:16作作1.21 1.21 假设在一台假设在一台40MHz40MHz处理机上运行处理机上运行200 000200 000条条指令的目标代码,程序主要由四种指令
7、组成。根据指令的目标代码,程序主要由四种指令组成。根据程序跟踪实验结果,已知指令混合比和每种指令所程序跟踪实验结果,已知指令混合比和每种指令所需的指令数如下:需的指令数如下:指令类型指令类型CPI指令混合百分比算术和逻辑运算算术和逻辑运算160%CacheCache命中的加载命中的加载/存储存储218%转移转移412%CacheCache失效时访问主存失效时访问主存810%(1)(1)计算在单处理机上用上述踪数据运行程序的平均计算在单处理机上用上述踪数据运行程序的平均CPICPI(2)(2)根据根据(1)(1)所得所得CPICPI,计算相应的,计算相应的MIPS MIPS 速率和程序的执行时间
8、速率和程序的执行时间17解:依题意可知 IN=2105条,n=4,18第二章第二章 指令系统(指令系统(P36P36)本章介绍指令系统设计中2个最基本的内容:数据表示、操作码优化。本章重点本章重点 (1)Huffman编码方法;(2)等长扩展编码方法(15/15/15法,8/64/512法);(3)编码方法性能指标(平均码长L,信息冗余量R)。192.1 Huffman压缩编码(P91)(1)Huffman压缩概念(最佳编码定理):当用n个长度不等的代码分别代表n种发生概率不等的事件时,按照短代码给高概率事件、把长代码给低概率事件的原则分配,可使平均码长达到最低。(2)Huffman编码方法
9、这种编码方法由两个过程组成。频度合并:将全部n个事件(在此即为n条指令)的频度值排序,选取其中最小的2个频度合并,然后将剩下的n-1个频度再次排序,再合并最小的2个频度,如此重复,直至剩下1个频度为止。记录所有的合并关系,形成一棵二叉树 Huffman树,所有原始频度值充当树叶,而最后剩下的总频度1为树根;码元分配:从树根开始,对每个中间结点的左右2个分支边各赋予一位代码“0”和“1”(“0”在哪一侧不限)。读出从根结点到任一片树叶的路径上依次出现的代码位就排成了这个事件(即指令)的完整编码。由于频度高的事件较晚被合并,它的编码位数也就较少,符合Huffman压缩原则。上面所说的频度值就是各事
10、件实际出现次数的百分比,它是理论出现概率的近似值。20 平均码长平均码长:各事件编码长度的数学期望。信息冗余量信息冗余量:它表明消息编码中“无用成分”所占的百分比。212.2 扩展编码方法(扩展编码方法(等长扩展法,P94-95)用码长表示:例如4-8-12法。这并不能说明具体编码方法,例如下面两种编码方法都是4-8-12法。用码点数表示:例如15/15/15法,8/64/512法15/15/15法,每一种码长都有4位可编码位(前头可以有相同的扩展标识前缀),可产生16个码点(即编码组合),但是至多只能使用其中15个来表示事件,留下1个或多个码点组合作为更长代码的扩展标识前缀。已经用来表示事件
11、的码点组合不能再作为其它更长代码的前导部分,否则接收者会混淆。这就是“非前缀原则”。8/64/512法,每一种码长按4位分段,每一段中至少要留下1位或多位作为扩展标识。各段剩下的可编码位一起编码,所产生的码点用来对应被编码事件。每一段中的标识位指出后面还有没有后续段。2210000001110.090.300.601.000.1510.0610.030.030.040.050.150.300.40 I7I6I5I4I3I2I1I7I6I5I4I3I2I1例例例例2.12.12.12.1 某指令系统各指令使用频度如下:某指令系统各指令使用频度如下:某指令系统各指令使用频度如下:某指令系统各指令使
12、用频度如下:I1 I2 I3 I4 I5 I6 I7 I1 I2 I3 I4 I5 I6 I7 I1 I2 I3 I4 I5 I6 I7 I1 I2 I3 I4 I5 I6 I7 0.4 0.3 0.15 0.05 0.04 0.03 0.03 0.4 0.3 0.15 0.05 0.04 0.03 0.03 0.4 0.3 0.15 0.05 0.04 0.03 0.03 0.4 0.3 0.15 0.05 0.04 0.03 0.03 1.Huffman 1.Huffman 1.Huffman 1.Huffman编码编码编码编码23由此可得到哈夫曼编码如下:由此可得到哈夫曼编码如下:I1:
13、0 I2:10 I3:110 I4:11100 I1:0 I2:10 I3:110 I4:11100 I5:11101 I6:11110 I7:11111 I5:11101 I6:11110 I7:11111 平均码长平均码长L L=0.4*1+0.3*2+0.15*3+0.05*5+0.04*5=0.4*1+0.3*2+0.15*3+0.05*5+0.04*5+0.03*5+0.03*5=2.20+0.03*5+0.03*5=2.20位位 信息冗余量信息冗余量R=(2.20-2.17)/2.20=1.36%R=(2.20-2.17)/2.20=1.36%指令长度个数指令长度个数=4=4242
14、.2.扩展哈夫曼编码扩展哈夫曼编码I1,I2,I3 I1,I2,I3 用两位用两位:00,01,10:00,01,10I4,I5,I6,I7 I4,I5,I6,I7 用四位用四位:1100,1101,1110,:1100,1101,1110,11111111L L=(0.4+0.3+0.15)*2+(0.05+0.04+0.03+0.03)*4=(0.4+0.3+0.15)*2+(0.05+0.04+0.03+0.03)*4=2.30=2.30位位信息冗余量信息冗余量=(2.30-2.20)/2.30=0.0565=5.65%=(2.30-2.20)/2.30=0.0565=5.65%2541
15、 1 1 151 1 1 1 10.03I741 1 1 051 1 1 1 00.03I641 1 0 151 1 1 0 10.04I541 1 0 051 1 1 0 00.05I421 031 1 00.15I320 1 2 1 00.30I220 0100.40I1OP长度长度lihuffman扩展编扩展编码码OP长长度度li操作码操作码OP使用哈夫曼使用哈夫曼编码编码 频频 度度(Pi)指指 令令操作码的扩展(等长扩展)操作码的扩展(等长扩展)平均码长:2.2 2.326作 2.13 采用最优Huffman编码法(信息熵)的操作码最短平均长度为:2728例例2.22.2 指令系统共
16、有指令系统共有4242种指令,前种指令,前1515种使用频率平均种使用频率平均为为0.050.05,中间,中间1313种使用频率平均为种使用频率平均为0.0150.015,最后,最后1414种种使用频率平均为使用频率平均为0.0040.004。如何编码?。如何编码?00000000 :1515种种111011101111 00001111 0000 :1515种种1111 11101111 11101111 1111 00001111 1111 0000 :1515种种1111 1111 11101111 1111 1110解:解:因频率分布有三种,故因频率分布有三种,故码长可有三种;码长可有
17、三种;因每段指令数基本相同,因每段指令数基本相同,故可采用故可采用等长扩展等长扩展(4-8-12(4-8-12位位),保留特征码的每段指令保留特征码的每段指令数相同数相同(15-15-15)(15-15-15)方法。结方法。结果如图所示;果如图所示;结果:采用结果:采用15-15-1515-15-15扩展方法,最后一种编码用于扩展方法,最后一种编码用于扩展,每段扩展,每段0000000011101110用于编码,用于编码,11111111用于扩展。用于扩展。29例例2.32.3 某模型机有某模型机有9 9条指令,其使用频率为:条指令,其使用频率为:ADDADD(加)(加)30%30%SUBSU
18、B(减)(减)24%24%JOMJOM(按负转移)(按负转移)6%6%STOSTO(存)(存)7%7%JMPJMP(转移)(转移)7%7%SHRSHR(右移)(右移)2%2%CILCIL(循环左移)(循环左移)3%3%CLACLA(清加)(清加)20%20%STPSTP(停机)(停机)1%1%要求有两种指令字长,都按双操作数指令格式编要求有两种指令字长,都按双操作数指令格式编,采用扩展操作码,并限制只能有两种操作码码长。设采用扩展操作码,并限制只能有两种操作码码长。设该机有若干个通用寄存器,主存为该机有若干个通用寄存器,主存为1616位宽,按字节编位宽,按字节编址,采用整数边界存贮,任何指令都
19、在一个主存周期址,采用整数边界存贮,任何指令都在一个主存周期中取得,短指令为寄存器寄存器型,长指令为寄存中取得,短指令为寄存器寄存器型,长指令为寄存器主存型,主存地址应能变址寻址。器主存型,主存地址应能变址寻址。30解:解:(1)Huffman树的形式如图所示。树的形式如图所示。0.010.020.03010.030.06010.060.12010.070.070.14010.260100.300.200.240.44010.561001131由上图可得到的由上图可得到的Huffman编码为:编码为:ADD(ADD(加加)30%01)30%01 SUB(SUB(减减)24%11)24%11 C
20、LA(CLA(清加清加)20%10)20%10 JOM(JOM(按负转移按负转移)6%0001)6%0001 STO(STO(存存)7%0011)7%0011 JMP(JMP(转移转移)7%0010)7%0010 CIL(CIL(循环左移循环左移)3%00001)3%00001 SHR(SHR(右移右移)2%000001 )2%000001 STP(STP(停机停机)1%000000)1%000000因此,操作码的平均码长为:因此,操作码的平均码长为:32(2)采用采用2-5扩展的操作码编码为:扩展的操作码编码为:ADD(ADD(加加)30%00)30%00 SUB(SUB(减减)24%01)
21、24%01 CLA(CLA(清加清加)20%10)20%10 JOM(JOM(按负转移按负转移)6%11000)6%11000 STO(STO(存存)7%11001)7%11001 JMP(JMP(转移转移)7%11010)7%11010 SHR(SHR(右移右移)2%11011 )2%11011 CIL(CIL(循环左移循环左移)3%11100)3%11100 STP(STP(停机停机)1%11101)1%11101因此,操作码的平均码长为:因此,操作码的平均码长为:33(3)该机允许使用的可编址的通用寄存器个数为该机允许使用的可编址的通用寄存器个数为23=8个个(4)短指令为寄存器短指令为
22、寄存器-寄存器型,格式如下:寄存器型,格式如下: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位字长的寄存器寄存器
23、型指令3条,16位字长的寄存器存储器型变址寻址方式指令4条,变址范围不小于正、负127。请设计指令格式,并给出各字段的长度和操作码的编码。35答:(1)要使得到的操作码长度最短,应采用Huffman编码,Huffman树构造如下36由此可以得到7条指令的编码分别如下:这样,Huffman编码法得到的操作码的平均长度为:l =2(0.35+0.25+0.20)+30.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%111113738作2.14(改)一
24、台模拟机共有7条指令,各指令的使用频度分别为35%,25%,20%,10%,5%,3%,2%。该模拟机有8位和16位两种指令长,采用2-4扩展操作码,8位字长指令为寄存器-寄存器(R-R)二地址类型,16位字长指令为寄存器-存贮器(R-M)二地址变址寻址(-128变址范围127)类型。(1)计算操作码的平均码长(2)该机允许使用多少个可编址的通用寄存器,多少个变址寄存器?设计该机的两种指令格式,标出各字段位数并给出操作码编码。39 扩展码有2种方案(下图)00 00013条 01 2条10 10001100 10011101 4条 10105条1110 10111111 1100(3-7型)(
25、2-8 型)简版402-4扩展码有2种方案(上图)前一种方案里短指令占的比例较大,应该选用它。平均码长/L=(0.35+0.25+0.20)2+(0.1+0.05+0.03+0.02)4=2.4 用R代表寄存器编号,A代表变址偏移量。题目未指明R-R型R-M型谁是短码,所以先列出2种方案:418 位:操作码 2,寄存器(8-2)/2=3 (右边为 操作码4 位)16位:操作码 2,寄存器 3,变址寻址(-128变址范围127):27=128,符号1位,共 8位,变址器:16-4-3-8=142 2.2.2 操作数优化寻址方式比较(P95)指令中操作数占用的位数由操作数的个数与寻址方式决定。按操
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机系统结构 计算机系统 结构 复习 习题 2016
限制150内