《计算机系统结构》总复习-习题.pptx
《《计算机系统结构》总复习-习题.pptx》由会员分享,可在线阅读,更多相关《《计算机系统结构》总复习-习题.pptx(103页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、计算机系统结构总复习-习题2016 Four short words sum up what has lifted most successful Four short words sum up what has lifted most successful individuals above the crowd: a little bit more. individuals above the crowd: a little bit more. -author -author -date-date精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除2第一章第一章 基本概念(基本概
2、念(P1P1) 本章介绍计算机系统结构的一些基本知识。包括定性知识和定量知识两大组内容。为了便于学习,本章各节重新编号,与教材编号不同。 定量知识:对计算机性能进行定量评价的几个重要公式。精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除3本章重点本章重点 本章从定性知识和定量知识两个方面介绍计算机系统结构的基本概念。有关重点如下:(1) Amdahl定律;(2) 平均周期数CPI公式,程序执行时间Te公式;(3) 每秒百万指令数MIPS公式,每秒百万浮点数MFLOPS公式。精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除41.定量知识3个性能公式1.1 Amda
3、hlAmdahl定律定律(加快经常性事件原理,P9)其中:Sn 全局加速比; To 原执行时间(old); Tn 新执行时间(new); Se 被改进部分的局部加速比; Fe 被改进部分原执行时间占原来总时间的百分比。精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除5Amdahl定律的推导精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除6Amdahl定律的图形 从图1.2可以看出,增大Se和Fe对Sn都有提升作用;但当Fe固定时,一味增大Se对Sn的作用会越来越不显著。精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除作作1.12 假定利用增加向量
4、模块来提高计算机的运假定利用增加向量模块来提高计算机的运算速度。计算机处理向量的速度比其通常的运算速度。计算机处理向量的速度比其通常的运算要快算要快20倍,将可用向量处理部分所花费的时倍,将可用向量处理部分所花费的时间占总时间的百分比称为可向量化百分比。间占总时间的百分比称为可向量化百分比。 (1)求出加速比)求出加速比S和向量化百分比之间的关系式和向量化百分比之间的关系式作作1.13 (2)当要得到加速比为当要得到加速比为2时的可向量化百时的可向量化百分比分比F为多少?为多少?作作1.14 (3)为了获得在向量模式所得到的最大加为了获得在向量模式所得到的最大加速比的一半,可向量化百分比速比的
5、一半,可向量化百分比F为多少?为多少?7精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除(2) 由(1)式有解(1):由Amdahl定律知FFFS*192020)20/()1 (153.01910)20/()1(12FFF(1)8精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除(3) 由题意可知95.01918)20/()1(110FFF9精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除作作1.17 假设高速缓存假设高速缓存Cache工作速度为主存的工作速度为主存的5倍,倍,且且Cache被访问命中的概率为被访问命中的概率为90,则采用,则采用C
6、ache后后,能使整个存储系统获得多高的加速比?,能使整个存储系统获得多高的加速比?57.328.015/9.0)9.01(1oePTTS解:解:fe=0.9 ,re=510精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除1.2 CPI与程序执行时间Te(P11)CPI是衡量CPU执行指令效率的重要指标。让我们先考虑一个标准测速程序的全部执行时间Te和其中所有第i种指令的累计时间Ti,易知11精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除121.3 每秒百万指令数MIPS与每秒百万浮点数MFLOPS(P11)例题:P10,例1.1例1.5。 P33,题12 ,
7、题13 ,题14 。精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除 例例1.191.19 用一台用一台4OMHz4OMHz处理机执行标准测试程序,处理机执行标准测试程序,它含的混合指令数和相应所需的时钟周期数如它含的混合指令数和相应所需的时钟周期数如下:下: 指令类型指令类型 指令条数 时钟周期数时钟周期数 整数运算整数运算 4500045000 1 数据传送数据传送 32000 232000 2 浮点运算浮点运算 15000 215000 2 控制传送控制传送 8000 28000 2 求有效求有效CPICPI、MIPSMIPS速率和程序的执行时间。速率和程序的执行时间。1
8、3精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除 解:依题意可知 IN=105条,n=455.1)08.0215.0232.0245.01 ()(411iniNiiIICPICPI8 .251055. 1104010666CPIfMIPSC)(875. 31040/155. 11065msTCPIITCNCPU14精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除作作1.201.20 某工作站采用时钟频率为某工作站采用时钟频率为15MHz15MHz、处理速率为、处理速率为10MIPS10MIPS的处理机来执行一个巳知混合程序。假定每次的处理机来执行一个巳知混合程
9、序。假定每次存储器存取为存储器存取为1 1周期延迟、试问:周期延迟、试问: (1)(1) 此计算机的有效此计算机的有效CPICPI是多少是多少? ? (2) (2) 假定将处理机的时钟提高到假定将处理机的时钟提高到30MHz30MHz,但存储器子,但存储器子 系统速率不变。这样,每次存储器存取需要两个时钟系统速率不变。这样,每次存储器存取需要两个时钟 周期。如果周期。如果3030指令每条只需要一次存储存取,而另指令每条只需要一次存储存取,而另 外外5 5每条需要两次存储存取,还假定已知混合程序每条需要两次存储存取,还假定已知混合程序 的指令数不变,并与原工作站兼容,试求改进后的处的指令数不变,
10、并与原工作站兼容,试求改进后的处 理机性能。理机性能。 解解 (1)5 . 11010101510666MIPSfCPIoldold15精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除(2) 依题意可知:依题意可知:30%的指令需要一次存储存取,则的指令需要一次存储存取,则这些指令在处理器提高时钟频率之后需要增加这些指令在处理器提高时钟频率之后需要增加1个时个时钟周期;另外钟周期;另外5%的指令需要增加的指令需要增加2个时钟周期。个时钟周期。 改进后性能提高情况可用改进后性能提高情况可用CPU时间之比表示:时间之比表示: 9 . 12%51%30oldnewCPICPI79.1
11、5109 . 1103010666newnewnewCPIfMIPS58. 1/)()(newNnewoldNoldnewCPUoldCPUfICPIfICPITT16精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除作作1.21 1.21 假设在一台假设在一台40MHz40MHz处理机上运行处理机上运行200 000200 000条条指令的目标代码,程序主要由四种指令组成。根据指令的目标代码,程序主要由四种指令组成。根据程序跟踪实验结果,已知指令混合比和每种指令所程序跟踪实验结果,已知指令混合比和每种指令所需的指令数如下:需的指令数如下: 指令类型指令类型CPI指令混合百分比算
12、术和逻辑运算算术和逻辑运算160%CacheCache命中的加载命中的加载/ /存储存储 218%转移转移 412%CacheCache失效时访问主存失效时访问主存810%(1)(1)计算在单处理机上用上述踪数据运行程序的平均计算在单处理机上用上述踪数据运行程序的平均CPICPI(2)(2)根据根据(1)(1)所得所得CPICPI,计算相应的,计算相应的MIPS MIPS 速率和程序的执行时间速率和程序的执行时间17精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除 解:依题意可知 IN=2105条,n=4,24.2) 1 .0812.0418.026 .01 ()(411ini
13、NiiIICPICPI86.17102 . 2104010666CPIfMIPSC)(2 .111024.210264015msTCPIITCNCPU18精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除19第二章第二章 指令系统(指令系统(P36P36) 本章介绍指令系统设计中2个最基本的内容:数据表示、操作码优化。本章重点本章重点 (1) Huffman编码方法;(2) 等长扩展编码方法(15/15/15法,8/64/512法);(3) 编码方法性能指标(平均码长L,信息冗余量R)。精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除202.1 Huffman压缩
14、编码(P91)(1)Huffman压缩概念(最佳编码定理):当用n个长度不等的代码分别代表n种发生概率不等的事件时,按照短代码给高概率事件、把长代码给低概率事件的原则分配,可使平均码长达到最低。(2) Huffman编码方法 这种编码方法由两个过程组成。频度合并:将全部n个事件(在此即为n条指令)的频度值排序,选取其中最小的2个频度合并,然后将剩下的n-1个频度再次排序,再合并最小的2个频度,如此重复,直至剩下1个频度为止。记录所有的合并关系,形成一棵二叉树 Huffman树,所有原始频度值充当树叶,而最后剩下的总频度1为树根;码元分配:从树根开始,对每个中间结点的左右2个分支边各赋予一位代码
15、“0”和“1”(“0”在哪一侧不限)。读出从根结点到任一片树叶的路径上依次出现的代码位就排成了这个事件(即指令)的完整编码。由于频度高的事件较晚被合并,它的编码位数也就较少,符合Huffman压缩原则。 上面所说的频度值就是各事件实际出现次数的百分比,它是理论出现概率的近似值。精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除21 平均码长平均码长:各事件编码长度的数学期望。 信息冗余量信息冗余量:它表明消息编码中“无用成分”所占的百分比。精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除222.2 扩展编码方法(扩展编码方法(等长扩展法,P94-95)用码长表示:
16、例如4-8-12法。这并不能说明具体编码方法,例如下面两种编码方法都是4-8-12法。用码点数表示:例如15/15/15法,8/64/512法15/15/15法,每一种码长都有4位可编码位(前头可以有相同的扩展标识前缀),可产生16个码点(即编码组合),但是至多只能使用其中15个来表示事件,留下1个或多个码点组合作为更长代码的扩展标识前缀。已经用来表示事件的码点组合不能再作为其它更长代码的前导部分,否则接收者会混淆。这就是“非前缀原则”。8/64/512法,每一种码长按4位分段,每一段中至少要留下1位或多位作为扩展标识。各段剩下的可编码位一起编码,所产生的码点用来对应被编码事件。每一段中的标识
17、位指出后面还有没有后续段。精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除10000001110.090.300.601.000.1510.0610.030.030.040.050.150.300.4023精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除由此可得到哈夫曼编码如下:由此可得到哈夫曼编码如下: I1: 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 平均码长平均码长
18、L L=0.4=0.4* *1+0.31+0.3* *2+0.152+0.15* *3+0.053+0.05* *5+0.045+0.04* *5 5 +0.03 +0.03* *5+0.035+0.03* *5 = 2.205 = 2.20位位 信息冗余量信息冗余量R=(2.20-2.17)/2.20=1.36%R=(2.20-2.17)/2.20=1.36% 指令长度个数指令长度个数=4=424精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除2.2.扩展哈夫曼编码扩展哈夫曼编码 I1, I2, I3 I1, I2, I3 用两位用两位: 00, 01, 10: 00, 01
19、, 10 I4, I5, I6, I7 I4, I5, I6, I7 用四位用四位: 1100, 1101, 1110, : 1100, 1101, 1110, 11111111L L=(0.4+0.3+0.15)=(0.4+0.3+0.15)* *2+(0.05+0.04+0.03+0.03)2+(0.05+0.04+0.03+0.03)* *4 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%25精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除41
20、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精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除作 2.13 采用最优Huffman编码法(
21、信息熵)的操作码最短平均长度为: 27精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除28精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除例例2.22.2 指令系统共有指令系统共有4242种指令,前种指令,前1515种使用频率平均种使用频率平均为为0.050.05,中间,中间1313种使用频率平均为种使用频率平均为0.0150.015,最后,最后1414种种使用频率平均为使用频率平均为0.0040.004。如何编码?。如何编码?00000000 : 1515种种111011101111 00001111 0000 : : 1515种种1111 11101111
22、11101111 1111 00001111 1111 0000 : : : 1515种种1111 1111 11101111 1111 1110解:解:因频率分布有三种,故因频率分布有三种,故码长可有三种;码长可有三种; 因每段指令数基本相同,因每段指令数基本相同,故可采用故可采用等长扩展等长扩展(4-8-12(4-8-12位位) ), 保留特征码的每段指令保留特征码的每段指令数相同数相同(15-15-15)(15-15-15)方法。结方法。结果如图所示;果如图所示; 结果:采用结果:采用15-15-1515-15-15扩展方法,最后一种编码用于扩展方法,最后一种编码用于扩展,每段扩展,每段
23、0000000011101110用于编码,用于编码,11111111用于扩展。用于扩展。29精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除例例2.32.3 某模型机有某模型机有9 9条指令,其使用频率为:条指令,其使用频率为:ADDADD(加)(加)30%30%SUBSUB(减)(减)24%24%JOMJOM(按负转移)(按负转移)6%6% STOSTO(存)(存)7%7%JMPJMP(转移)(转移)7%7% SHRSHR(右移)(右移)2%2%CILCIL(循环左移)(循环左移)3%3% CLACLA(清加)(清加)20%20%STPSTP(停机)(停机)1%1% 要求有两
24、种指令字长,都按双操作数指令格式编要求有两种指令字长,都按双操作数指令格式编, ,采用扩展操作码,并限制只能有两种操作码码长。设采用扩展操作码,并限制只能有两种操作码码长。设该机有若干个通用寄存器,主存为该机有若干个通用寄存器,主存为1616位宽,按字节编位宽,按字节编址,采用整数边界存贮,任何指令都在一个主存周期址,采用整数边界存贮,任何指令都在一个主存周期中取得,短指令为寄存器寄存器型,长指令为寄存中取得,短指令为寄存器寄存器型,长指令为寄存器主存型,主存地址应能变址寻址。器主存型,主存地址应能变址寻址。30精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除 解:解:(1)
25、Huffman树的形式如图所示。树的形式如图所示。0.010.020.03010.030.06010.060.12010.070.070.14010.260100.300.200.240.44010.561001131精品ppt文档收集于网络,仅供学习交流,如有侵权请联系管理员删除 由上图可得到的由上图可得到的Huffman编码为:编码为: ADD(ADD(加加) 30% 01) 30% 01 SUB( SUB(减减) 24% 11) 24% 11 CLA( CLA(清加清加) 20% 10) 20% 10 JOM( JOM(按负转移按负转移) 6% 0001) 6% 0001 STO( ST
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机系统结构 计算机系统 结构 复习 习题
限制150内