计算机系统结构(习题补充例题与练习).ppt
《计算机系统结构(习题补充例题与练习).ppt》由会员分享,可在线阅读,更多相关《计算机系统结构(习题补充例题与练习).ppt(46页珍藏版)》请在装配图网上搜索。
习题1,存在的问题大多数同学较认真,少数不太认真、有抄袭现象关于参考答案,要知其然,更要知其所以然第5、7两题理解透明性的含义掌握计算机系统结构、组成、实现研究的范围,P4、5凡编写机器语言和汇编语言程序要用到的(数据表示、指令系统、寄存器)对计算机系统结构都是不透明的凡是只影响系统速度和价格的逻辑实现(计算机组成)和物理实现(计算机实现)对系统结构都是透明的,习题1,第5题:哪些对计算机系统结构是透明的存储器的模m交叉存取:目的加快存储器速度,透明浮点数据表示:硬件可直接识别的数据类型,不透明I/O是通道方式还是处理机方式:I/O方式选择属于系统结构,不透明阵列运算部件(多个相同运算部件阵列排列):加快运算速度,透明数据总线宽度:只影响数据传输速度,不影响功能,透明通道类型(结合、独立,P6):功能相同、速度不同,透明访问方式保护:属于系统结构,不透明程序性中断:属于系统结构,不透明控制方式(串行、流水等):仅影响速度,透明堆栈指令:指令系统属于系统结构,不透明存储器最小编址单位:属于系统结构,不透明Cache存储器:为了提高存储系统速度,组原课中细讲的,透明,习题1,第7题:从机器(汇编)语言看哪些是透明的指令地址寄存器:指的是程序计数器PC,80X86中为IP,相对转移指令中用到,不透明指令缓冲器:缓冲和排队技术属于计算机组成P5,透明时标发生器:产生系统时钟,汇编语言不能控制的具体硬件,透明条件码寄存器:存放转移条件,也叫程序状态字PSW,是条件转移指令的测试条件,不透明乘法器、移位器:汇编语言不能控制的具体硬件,透明主存地址寄存器:也称存储器地址寄存器MAR,透明磁盘外设:I/O指令可直接对其操作(通过端口号),不透明先行进位链:提高加法器运算速度的,组原和数字逻辑中学到,汇编语言不能控制的具体硬件,透明通用寄存器、中断字寄存器(中断响应、优先级、屏蔽等):程序中要用到,不透明,习题1,第8题掌握三个公式,第12题优化之后各类指令所占比例,ALU指令的减少也导致总指令数减少优化后算术运算指令所占比例从MIPS之比得出的结论:减少ALU指令的比例会使速度变慢减少使用频率高的指令会使速度变慢减少速度快的指令的比例会使速度变慢,习题2,OP编码优化的目标平均长度短(冗余小)编码规整(长度种类少)最短平均长度(信息源熵):信息冗余量(实际长度-H)/实际长度,Huffman编码平均长度最短的方案编码不唯一,但长度确定每次选择两个最小值节点非叶子结点值相加,习题2,扩展编码等长、不等长X-Y-Z、X/Y/Z短编码不能是长编码的前缀一定要用短编码表示频率高的指令变址位移量补码表示(-2n-12n-1-1)指令类型R-R:速度快,给频率高的指令使用M-M,习题2,第3题(10条指令)第2问:要求OP平均长度最短,则一定是Huffman编码(画Huffman树时要注意,确保每次选两个概率最小的),2.7第3问:OP平均长度最短的扩展编码(不一定是等长扩展),究竟哪种最短,要一个一个去试,本题可以试一下2-5、2-4、3-4,结果2-5最短,2.9第4问:OP平均长度最短的等长扩展编码,只需考虑2-4(1-2不可能、3-6太长),2.92第5题(三地址12条,单地址254条,总长16位,每个地址4位)4-8-12等长扩展,12/X/254若不考虑单地址指令,则二地址最多416=64条考虑单地址指令,每预留一个二地址指令码点,则可以扩展16条单地址指令,要使单地址指令达到254条,则应预留254/16=15.9个二地址指令码点因此,二地址最多可以设计64-16=48条,习题2,第6题(9条指令,8位(R-R)、16位(R-M)两种指令字长)第1问:OP平均长度最短的扩展编码,与第3题类似,2-4、2-5比较后可知,2-5平均长度最短,2.9第2问:为提高速度,应将使用频率高的指令安排成R-R型,为减少存储容量,应将使用频率高的指令安排成短OP(2位),因此R编码占3位,可以表示8个通用寄存器第3、4问:通用寄存器做变址寄存器,则变址位移量只能是5位(16位-5位OP-3位R-3位X),偏移范围-1615(补码),补充习题,1、若某机要求有:3地址指令4条,单地址指令255条,0地址指令16条。设指令字长为12位,每个地址码为3位。问能否用扩展操作码为其编码?单地址指令为254条呢?请说明理由。3-9-12不等长扩展,4/255/16;4/254/16若不考虑0地址指令,则单地址最多426=256条考虑0地址指令,每预留一个单地址指令码点,则可以扩展8条0地址指令,要使0地址指令达到16条,则应预留16/8=2个单地址指令码点因此,单地址最多可以设计256-2=254条4/255/164/254/16,补充习题,2、某机指令字长为16位。设有单地址指令和双地址指令两类。若每个地址字段均为6位,且双地址指令有x条。问单地址指令可以有多少条?4-10扩展双地址指令剩余16-x个码点作扩展标志共可扩出单地址指令(16-x)26条,补充习题,某处理机的指令字长为16位,有2地址指令、1地址指令和0地址指令3类,每个地址字段的长度均为6位。如果2地址指令有15条,0地址指令和1地址指令的条数基本相等,那么0地址指令和1地址指令各有多少条?为3类指令分配操作码。如果要求3类指令条数的比例为1:9:9。那么3类指令的条数各有多少条?为3类指令分配操作码。解4-10-1615/63/64、14/126/128,补充习题,用于文字处理的某专用机,每个文字字符用4位十进制数(0-9)编码表示,空格用-表示,在对传送的文字符和空格进行统计后,得出其出现的概率为:若上述数字和空格均用二进制编码,试设计二进制信息位平均长度最短的编码。若传送106个文字符号(每个文字符号后均跟一个空格),按最短编码,共需传送多少个二进制位?若十进制数字和空格均用4位二进制码表示,共需传送多少个二进制位?,练习,计算机中优化使用的操作码编码方法是()A、Huffman编码B、ASCII码C、BCD码D、扩展编码支持动态再定位的寻址方式是()A、基址寻址B、间接寻址C、变址寻址D、间接寻址变址寻址的主要作用是()A、支持程序的动态定位B、支持访存地址的越界检查C、支持向量、数组的运算寻址D、支持OS的进程调度对系统程序员不透明的是()A、CacheB、系列机各档不同的数据通路宽度C、指令缓冲寄存器D、虚拟存储器,练习,对应用程序员不透明的是()A、先行进位链B、乘法器C、指令缓冲寄存器D、条件码寄存器计算机系统结构不包括()A、主存速度B、机器工作状态C、信息保护D、数据表示判断题系统是否设置浮点指令对计算机系统结构是透明的。存储器采用单体单字,还是多体交叉存取,对系统结构设计应是透明的。系列机增加新型号时,为增加寻址灵活性和缩短平均指令字长,可以由原等长操作码改为有多种码长的扩展操作码。对概率不等的事件用Huffman编码,其具体编码不唯一,但平均长度肯定是唯一的,且是最短的。,习题3,4、直接利用公式:P41Ta=fi(HiTc+(1-Hi)Tm)+(1-fi)(HdTc+(1-Hd)Tm)=22.16nsfi=20%、Tc=20ns、Tm=80ns、Hi=98%、Hd=96%10、页面失效的虚页号:装入位为0的虚页,1、2、5、6由虚地址计算实地址:虚地址页面大小虚页号页内位移由虚页号查页表得实页号实地址=实页号页面大小页内位移809610247928310249284000页面失效的无实地址,习题3,补充:某段页式虚拟存储器,虚地址由2位段号、2位页号和11位页内位移组成,主存容量32KB,每段可有访问方式保护,其页表和保护位如下表所示。此地址空间中共有多少虚页当程序中遇到下列情况时,由虚地址计算实地址,说明哪个会发生段失效、页失效和保护失效。,习题3,由主存容量为32KB,可知实地址:,虚地址:,页面大小:211=2048B实地址计算方法同上页表不在主存内的段2发生段失效页面在辅存上的发生页失效取数表示读,取出的数不能作为指令执行;只读单元不能写、执行;转移至此为执行,不能读、写,访问不当的为保护方式失效,习题3,习题4,第6题A1+A2+A3+A4+A5+A6+A7+A8+A9+A10,1,2,3,4,5,6,7,8,9,TP=9/21t=3/7tSp=(95)/21=2.14E=(95)/(215)=42.9%,8,1,5,10,15,21,习题4,第7题:静态流水线A1B1+A2B2+A3B3+A4B4+A5B5+A6B6,1,2,3,4,5,6,7,8,9,10,11,1,22,请改为动态流水线练习,1,2,3,4,5,6,习题4,第8题算法:(a1+b1)c1+(a2+b2)c2+(a3+b3)c3+(a4+b4)c4总时间:(3+31)+(4+32)+(3+1)+3=23效率:(73+44)/(234)=37/92=40.2%,23,习题4,第9题动态流水线a1b1+a2b2+a3b3+a4b4+a5b5+a6b6+a7b7+a8b8,1,23,请改为静态流水线练习,A,B,C,D,E,F,习题4,第10题6个任务的总执行时间为:8(第一个任务用8个周期)+53(后5个任务,每3周期执行一个,取决于最慢部件)实际吞吐率=6/23t效率=(86)/(235)=48/115=41.7%,8,习题4,第11题禁止向量(延迟禁止表)=(1,3,4,8)原始冲突向量=(10001101)状态转移图略最大吞吐率的调度方案(2,5),吞吐率=1/3.5输入6个任务的实际吞吐率:6/(9+2+5+2+5+2)=6/25补:有长度为8的向量A和B,分别画出在下列4中结构的处理器上求点积的时空图有一个乘法部件和一个加法部件,不能同时工作,部件内部采用顺序方式,完成一次加、乘需要5拍同上,只是乘法器和加法器可以并行工作有一个乘、加双功能静态流水线,均由5段组成,每段1拍有乘、加两条流水线,可并行工作,每段1拍,习题4,解(1)(2)(a1b1+a2b2)+a3b3)+a4b4)+a5b5)+a6b6)+a7b7)+a8b8,5,40,75,5,40,45,习题4,(3)静态双功能流水线(a1b1+a2b2)+(a3b3+a4b4)+(a5b5+a6b6)+(a7b7+a8b8),12,30,习题4,(4)两条流水线可同时工作(a1b1+a2b2)+a7b7+(a5b5+a6b6)+(a3b3+a4b4)+a8b8,12,27,习题4(补充),有一条静态加、乘多功能流水线由5段组成,加法用1、3、4、5段,乘法用1、2、5段,第3段的时间为2t,其余段为t,而且流水线的输出可以直接返回到输入端或暂存于相应的流水线寄存器中,现在要在该流水线上计算,画出其时空图,并计算其吞吐率、加速比和效率。有一条动态多功能流水线由5段组成,加法用1、3、4、5段,乘法用1、2、5段,第2段的时间为2t,其余段为t,而且流水线的输出可以直接返回到输入端或暂存于相应的流水线寄存器中,现在要在该流水线上计算,画出其时空图,并计算其吞吐率、加速比和效率。,习题4(补充),有一条动态多功能流水线由6段组成,其中1、4、5、6段组成乘法流水线,1、2、3、6段组成加法流水线,各流水段的时间均为50ns,假设流水线的输出可以直接返回到输入端,而且有足够的缓冲寄存器,现在要用最快的方式在该流水线上计算,画出其时空图,并计算其吞吐率、加速比和效率。,习题4(补充),有一5段流水线,各段执行时间均t,其预约表如下:画出流水线任务调度的状态转移图分别求出允许不等时间间隔的调度和等时间间隔的调度的两种最优调度策略,以及这两种调度策略的流水线最大吞吐率若连续输入10个任务,求这两种调度策略的实际吞吐率和加速比,练习,下列关于标量流水机的说法不正确的是()A、可对标量进行流水处理B、没有向量数据表示C、不能对向量数据进行运算D、可以对向量、数组进行运算以下说法不正确的是()A、线性流水线是单功能流水线B、动态流水线是双功能流水线C、静态流水线是多功能流水线D、动态流水线只能是单功能流水线静态流水线是指()A、只有一种功能的流水线B、可同时执行多种功能的流水线C、同时只能完成一种功能的多功能流水线D、功能不能改变的流水线非线性流水线是指()A、一次运算中使用流水线的多个功能段B、一次运算中要多次使用流水线的某些功能段C、流水线中某些功能段在各次运算中的作用不同D、流水线中的各个功能段在各种运算中有不同的组合,练习,与流水线最大吞吐率高低有关的是()A、各个子过程的时间B、最快子过程的时间C、最慢子过程的时间D、最后子过程的时间在流水线中,全局相关是指()A、先写后读相关B、先读后写相关C、指令相关D、由转移指令引起的相关流水机器对全局相关的处理不包括()A、猜测法B、提前形成条件码C、加快短循环程序的执行D、设置相关专用通路CRAY-1向量机要实现指令的链接,必须满足的条件是()A、源向量相同,功能部件不冲突,有指令相关B、源向量不同,功能部件相同,无指令相关C、源向量、功能部件都不同,指令有先写后读相关D、源向量、功能部件都不同,指令有先读后写相关,练习,CRAY-1机启动存储器、流水部件及寄存器打入各需1拍,“加”6拍、“乘”7拍、“访存”6拍,下列向量指令串中的向量长度均为N,则指令串最短的执行时间是()拍V3存储器V4V0+V1V2V4*V3A、N+19B、N+18C、N+17D、N+16CRAY-1的两条向量指令属于()V1V2+V3V4V1*V5A、没有功能部件冲突和源向量冲突,可以并行B、没有功能部件冲突和源向量冲突,可以链接C、没有源向量冲突,可以交换顺序执行D、有向量寄存器冲突,只能串行,习题5,4、32个处理器,编号031,11号处理器与哪个相连Cube3:11D=01011B,00011B=3D,3号PM2+3:(11+23)mod32=19,19号PM2-4:(11-24)mod32=27,27号Shuffle:01011B循环左移一位=10110B=22D,22号Butterfly:01011B最高位与最低位交换=11010B=26D,26号Shuffle(shuffle):01011B循环左移二位=01101B=13D,13号Shuffle(Cube0(PM2-1):(11-21)mod32=9D=01001B,再最低位取反得01000B,最后循环左移一位得:10000B=16D,16号7、256个PE的SIMD机器,采用全混洗互连函数,混洗10次后,197号PE与哪个PE相连197D=11000101B(8位,因为共256个PE)循环左移10次(相当于2次,因为共8位)为:00010111B=23D,23号,习题5,18、32个处理器的5(log232)级STARAN网,当级控制信号为10110(从右至左分别控制第0级至第4级)时,17号处理器连接哪个处理器根据STARAN网作为交换网络的特点,某级控制信号为1,就实现了某个Cubei,因此本题实现Cube4+Cube2+Cube1功能17D=10001B,第4、2、1位取反后为00111B=7D,7号19、16个处理器,先8组2元交换、再4组4元交换,最后2组8元交换,写出互连函数输入:0123456789ABCDEF8组2元交换:1032547698BADCFE4组4元交换:23016745AB89EFCD2组8元交换:54761032DCFE98BA(输出)可见实现了Cube2+Cube0互连函数表达式:,习题5,补:N=16的STARAN网在级控制下实现分组交换置换,如果实现的分组交换置换是:首先是4组4元交换,然后是2组8元交换,最后是1组16元交换,请写出网络实现的互连函数。0123456789ABCDEF32107654BA98FEDC45670123CDEF89ABBA98FEDC32107654(0B)(1A)(29)(38)(4F)(5E)(6D)(7C)Cube3+Cube1+Cube0补:用一个N=8的3级Omega网络连接8个处理机P0P7,如果P6要把数据广播给P0P4,如果P3要把数据广播给P5P7,能否同时实现播送要求,画出开关状态图。,习题5,能,习题5,补:对于采用级控制的3级立方体互连网络,当第i级为直连状态时,不能实现哪些节点之间的通信?为什么?反之,当第i级为交换状态呢?因为第i级为交换状态时,实现的是cubei互连函数,所以第i级为直连状态时,不能实现第i位取反的节点间的通信第i级为交换状态时,不能实现第i位不变的节点间的通信,习题6,5、(1)3条指令全并行,72拍(乘法最慢:1+7+1+63)(2)1、2并行与3链接,要求1比2早启动1拍,否则不能与3链接,80拍(1+7+1+1+6+1+63)(3)1、2并行,3、4链接,1、2和3、4之间串行。151拍(1+6+1+63+1+6+1+1+7+1+63)(4)1、2、3两级链接与4串,166拍(1+6+1+1+14+1+1+6+1+63+1+6+1+63)(5)1、2并与3链接,要求2比1早启动1拍,否则不能与3链接,与4串151拍(1+7+1+1+6+1+63+1+6+1+63)(6)1、2并,2与3链接,4与3串行,152拍(1+6+1+1+7+1+63+1+7+1+63),习题6,8、参考例6.9设平均数度为Ra,可向量化比例为x,则有要使Ra=6,则x=83.3%也可以直接利用amdhal定律,P15,fnew=x,rnew=10/2=5要使Ra=6,则Sp=6/2=3,则x=83.3%,习题6,9、设标量速度为Rs,平均速度为为Ra,可向量化比例为x,加速比为SP,则有要使SP=2,则X=55.6%也可以直接利用Aamdhal定律,P15,fnew=x,rnew=10,习题6,10、用自己学过的C语言描述for(i=1;i=32;i+)Ci=Ai+Bi;len=16for(i=1;i=5;i+)for(j=1;j=len:j+)Cj=Cj+Cj+len;len=len/2;,练习,ILLIAC阵列处理机中,PE之间所用的互连函数是()A、PM20和PM23B、Cube0和Cube1C、ShuffleD、PM22阵列处理机主要实现的是()A、作业级并行B、任务级并行C、指令操作级并行D、指令内操作步骤并行16个处理器编号为015,采用PM2+3单级网络互连,与13号处理器相连的处理器号是()A、5B、1C、7D、14用互连循环表示8个结点的PM2-1互连函数,应该是()A、(6420)(7531)B、(0246)(1357)C、(01234567)D、(04)(15)(26)(37),练习,16号处理器用单级互连网络互连,将9号连到13号处理器,可用()A、Cube3B、PM2+2C、PM2+4D、Shuffle16个处理器编号为015,采用单级Cube3互连函数,与13号处理器相连的处理器号是()A、2B、3C、4D、5交换置换互连函数得到输出端地址的方法是把输入端二进制地址()A、最高位取反B、最低位取反C、最高位与最低位交换D、循环左移一位64个结点的方体置换互连函数的个数是()A、3B、4C、5D、664个结点的PM2I互连函数的个数是()A、6B、8C、12D、64,练习,结构不对称的静态互连网络是()A、线性阵列B、环形C、立方体网络D、全连接网络结构对称的静态互连网络是()A、二叉树B、星型C、二维网格D、超立方体STARAN网络是一种()A、多级立方体网络B、多级混洗交换网络C、静态互连网络D、非阻塞网络三级STARAN网络对8个输入端实现2组4元分组交换后,输入端端号序列01234567置换连接的输出端序列是()A、76543210B、32107654C、10325476D、67452301三级STARAN网络对8个输入端实现模8移4的移数置换后,输入端端号序列01234567置换连接的输出端序列是()A、12345670B、23456701C、45670123D、12305674,练习,用N=16的互连网络互连16个处理器,编号为0-15,若网络实现的互连函数是Shuffle(Shuffle),则与12号处理器连接的是()A、9B、6C、3D、12,- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机系统 结构 习题 补充 例题 练习
![提示](https://www.zhuangpeitu.com/images/bang_tan.gif)
关于本文