系统结构复习

中国地质大学（武汉）计算机学院吴湘宁计算机体系结构习题及答案第一章基础知识1．名词解释翻译解释模拟仿真透明性程序访问局部性[答案]略2.一个经解释实现的计算机可以按功能划分为四级.每一级为了执行一条指令需要下一级的N条指令.若执行第一级的一条指令需要的时间为Kns,那么执行第二、三、四级的一条指令各需要多少时间?计算机系统按功能划分层次结构的好处主要体现在哪些方面?[答案](1)有利于理解软件,硬件和固件在系统中的地位和作用;(2)有利于理解各种语言的实质和实现途径;(3)有利于推动计算机系统结构的发展;(4)有利于理解计算机系统结构的定义.什么是透明性?对计算机系统结构,下列哪些是透明的?哪些是不透明的?1)存储器的模m交叉存取;2)浮点数据表示;3)I/O系统是采用通道方式还是I/O处理机方式;4)阵列运算部件;5)数据总线宽度;6)通道是采用结合型的还是独立型的;7)访问方式保护;8)程序性中断;9)串行、重叠还是流水控制方式;10)堆栈指令;11)存储器的最小编址单位;12)Cache存储器.[答案]一种本来是存在的事务或属性,但从某种角度看却好像不存在,称为透明性.对计算机系统结构来说透明的是:1),4),5),6),9),12)对计算机系统结构来说不透明的是:2),3),7),8),10),11)5.什么是计算机体系结构?什么是计算机组成?什么是计算机实现?并说明三者的关系和相互影响?[答案]计算机系统结构是计算机系统的软,硬件分界面,是机器语言程序员或是编译程序员所需了解的计算机属性;计算机组成是计算机系统结构的逻辑事项;计算机实现是计算机组成的物理实现.三者的关系和互相影响为:具有相同系统结构的计算机可以采用不同的组成;(2)一种计算机组成可以采用多种不同的计算机实现;(3)计算机组成、计算机实现对计算机系统结构有着很大的影响;(4)计算机系统结构的设计不应限制计算机组成和实现技术，应能用于高档机，也可用于低挡机;(5)在不同时期,计算机系统结构,、组成和实现所包含的内容会有所变化，三者之间的界线常常很模糊.从机器(汇编)语言程序员角度看,以下哪些是透明的?1)指令地址存储器;2)指令缓冲器;3)时标发生器;4)条件码寄存器;5)乘法器;6)主存地址寄存器;7)磁盘外设;8)先行进位链;10)通用寄存器;11)中断字寄存器.[答案]对机器(汇编)语言程序员来说透明的有:2),3),5),6),8),9)对机器(汇编)语言程序员来说不透明的有:1),4),7),10),11)7.假设在一台40MHz处理机上运行200000条指令的目标代码,程序主要由四种类型的指令所组成.根据程序跟踪实验结果,各类指令的混合比和每类指令的CPI值如表1.9所示.(1)试计算在单处理机上执行上述该程序时的平均CPI;(2)根据(1)所得到的CPI,计算相应的MIPS速率及程序的执行时间.[答案](1)2.24CPI(2)17.86MPIS;0.0112s8.某工作站采用时钟频率为15MHz、处理速率为10MIPS的处理机来执行一个程序，假定每次存储器存取为1周期延迟,试问:(1)此计算机的有效CPI是多少?(2)假定将处理机的时钟频率提高到30MHz,但存储器子系统速率不变,这样,每次存储器存取需要两个时钟周期.如果30%的指令每条只需要一次存储存取,而另外5%的指令每条需要两次存储存取,还假定已知混合程序的指令数不变,并与原工作站兼容,试求改进后的处理机性能.[答案](1)1.5CPI;(2)15.8MPIS什么是并行性？它分为哪两种类型？开发计算机系统并行性的主要技术途径有哪三个？沿这些途径分别发展出什么类型的计算机？[答案]略实现软件移植的途径有哪些？[答案]略什么是Flynn分类法，按照Flynn分类法可将计算机系统分为哪几类？[答案]略第二章指令系统1.名词解释数据类型、数据表示、规格化浮点数、Huffman编码、扩展编码、RISC[答案]略2.某模型机有8条指令I1~I8,它们的使用频度分别为0.3,0.3,0.2,0.1,0.05,0.02,0.02,0.01.(1)试分别用Huffman编码和平均码长最短的等长扩展码(限定为两种码长)对其操作码进行编码.(2)分别计算Huffman编码和等长扩展码编码的平均长度.[答案](1)操作码的Huffman编码和2-4等长扩展码编码如下表1所示.(2)Huffman编码的平均长度为2.38位;等长扩展码编码的平均码长为2.8位.3.某模型机有10条指令I=1\*Arabic1~I10,它们的使用频度分别为0.3,0.24,0.16,0.12,0.07,0.04,0.03,0.02,0.01,0.01.(1)计算机采用等长操作码表示时的信息冗余量.(2)要求操作码平均码长最短,试设计操作码的编码,并计算所设计操作码的平均长度.(3)设计2-5扩展操作码编码，并计算平均码长.(4)设计2-4（2/8）等长扩展码编码，并计算平均码长.[答案](1)采用等长操作码表示时的信息冗余量为33.5%.(2)操作码的Huffman编码如表2所示,此种编码的平均长度为2.7位.(3)操作码的2-5扩展码编码如表2所示,此种编码的平均长度为2.9位.(4)操作码的2-4（2/4）等长扩展码编码如表2所示,此种编码的平均长度为2.92位.4.何谓指令格式的优化?操作码和地址码的优化一般采用哪些方法?[答案]指令格式的优化是指通过采用多种不同的寻址方式,地址制,地址形式和地址码长度以及多种指令字长,并将它们与可变长操作码的优化表示相结合,就可以构成冗余度尽可能少的指令字.操作码的优化采用扩展操作码编码法.地址码优化有以下四种方法:在指令中采用不同的寻址方式;(2)在指令中采用多地址制;(3)同一种地址制还可以采用多种地址形式和长度,也可以考虑利用空白处来存放直接操作数或常数等;在以上措施的基础上,还可以进一步考虑采用多种指令字长度的指令.若某机设计有如下指令格式的指令:三地址指令12种,一地址指令254种,设计指令的长度为16位,每个地址码字段的位数均为4位.若操作码的编码采用扩展操作码,问二地址指令最多可以设计多少种?[答案]二地址指令最多可以设计48种.一台模型机共有九条指令I1~I9,各指令的使用频度分别为0.3，0.2，0.2，0.1，0.08，0.6，0.03,0.02,0.01.该模型机有8位和16位两种指令字长.8位字长指令为寄存器----寄存器(R--R)二地址类型,16位字长指令为寄存器----存储器(R--M)二地址变址寻址类型.(1)试设计有两种码长的扩展操作码,使其平均码长最短,并计算此种编码的平均码长.(2)在(1)的基础上,该机允许使用多少个可编址的通用寄存器?(3)若采用通用寄存器作为变址寄存器,试设计该机的两种指令格式,并标出各字段的位数.计算变址寻址的偏移地址范围.[答案](1)操作码的2-5扩展码编码如表3所示,此种编码的平均长度位2.9位.2)在(1)的基础上,该机允许使用8个可编址的通用寄存器.(3)该机的两种指令格式及各字段的位数如下:R-R型:操作码OP(2位)|源寄存器RS(3位)|目的寄存器Rd(3位)R-M型:操作码OP(5位)|源寄存器RS(3位)|变址寄存器RX(3位)|偏移地址(5位)(4)变址寻址的偏移地址范围为-16~+15.简述CISC的特点.[答案]CISC的特点如下:(1)庞大的指令系统;(2)采用了可变长度的指令格式;(3)指令使用的寻址方式繁多;(4)CISC指令系统中包括一些用于特殊用途的指令,各种指令的使用频度相当悬殊.从指令格式,寻址方式以及平均CPI三个方面,比较经典CISC和纯RISC体系结构.[答案]略简述RISC设计的一般原则。[答案]1、精简指令条数，保留使用频度高的指令；2、简化指令格式，采用简单寻址方式，绝大多数指令可以在单周期内执行完成；3、采用寄存器间运算结构，减少访存次数；4、指令以硬联组合电路实现为主，少量指令可以用微程序解释方式执行；5、优化编译程序的设计。RISC计算机采用了哪些关键技术？各是什么含义？[答案]1、遵循按RISC机器一般原则设计的技术；2、指令采用交叉和流水的方式解释执行，并采用优化延迟转移技术；3、在CPU中设置大量的寄存器组，并采用重叠寄存器窗口的技术；4、在逻辑上采用硬联实现为主，适当辅以微程序解释的技术；5、优化编译系统设计的技术.。第三章存储系统1.名词解释低位交叉存储器、虚拟存储器、地址映象、地址变换、页面失效、页面冲突、替换算法、组相联映象、写直达法[答案]略2以页式虚拟存储器为例，说明什么是内部地址变换和外部地址变换？什么时候发生外部地址变换？[答案]程序运行时，虚拟存储系统按照地址映象方式把虚拟地址转换成主存物理地址的过程称为地址变换，又称为内部地址变换。如果要访问的指令或数据已经在主存中，则命中主存，否则就发生了页面失效，此时需要进行外部地址变换，即将虚拟地址变换成为辅存物理地址，然后再根据这个辅存物理地址从辅存上将所需指令或数据所在的页面调入主存。可见，当发生页面失效的时候，需要进行外部地址变换。3什么是堆栈型替换算法？哪些算法属于堆栈型替换算法？[答案]堆栈型替换算法是指如果以任意一个程序的页地址流作两次主存页面数分配，分别分配m个主存页面和n个主存页面，并且有m≤n。如果在任何时刻t，主存页面数集合Bt都满足关系：Bt(m)⊆Bt(n)，则这类算法称为堆栈型替换算法。堆栈型算法的基本思想是：随着分配给程序的主存页面数增加，主存的命中率也提高，至少不下降。LRU、LFU、OPT算法都是堆栈型算法，而RAND和FIFO算法都不是堆栈型算法。4Cache存储系统中有哪些常用的地址映象方法？各有什么优缺点？[答案]Cache存储系统有以下几种常用的地址映象方法：①

全相联地址映象：把主存空间和Cache空间都划分为大小相等的块，块的大小一般是一个主存访问周期内对主存访问的信息量，主存的任意一块可以装入到Cache中的任意一块位置上。优点是块冲突概率最低，缺点是要使用相联存储器，所以检索过程昂贵，需要的硬件成本比较高。而且当Cache较大时，相联存储器的表长也较大，查表速度难以提高。②

直接地址映象：把主存空间按照Cache的大小划分为若干个区，主存各个区中块号相同的主存块只能够装入到Cache中具有同一块号的特定块位置上。直接映象的优点是硬件实现简单，不需要相联查找，不需要页面替换算法，因而成本较低且地址变换速度快。缺点是块的冲突的概率高，Cache的利用率低。③

组相联映象：把主存按照Cache的大小分区，主存中的各区和Cache再按照同样大小划分成数量相等的组，组内按照同样大小划分成块，主存的组与Cache的组之间采用直接映象，组内的块之间采用全相联映象。具有较好的性能价格比，其优缺点介于全相联映象和直接映象的优缺点之间。与全相联映象相比，实现起来更加经济，查表的速度也较快。与直接映象相比，块的冲突概率显著降低。5什么是Cache的一致性问题？说明单处理机中Cache一致性问题的产生原因及解决方法。[答案]一般情况下，Cache中存放的是主存的部分副本，因此，Cache块应该与相应主存块的内容保持一致。但是在某些情况下，Cache块与相应主存块的内容会不相同，也就是产生了Cache的一致性问题。在单处理机中，造成Cache一致性问题的原因主要有：

CPU修改了Cache中的内容，而主存中相应内容却没有改变；

I/O处理机或I/O设备读入数据到主存，修改了主存的内容，而Cache中对应的内容却没有改变。在单处理机中，解决Cache一致性问题主要有两种方法：①

写直达法：又称为全写法、写贯通法，是指当Cache写命中时，必须把数据同时写入Cache和主存中。②

写回法：是指当Cache写命中时，只修改Cache的内容，而不立即写入主存，只有当这一块将被替换出Cache的时候，才把已修改的Cache块写回到主存。6假设二级存储系统两级物理存储器的访问时间的关系为T2＝5T1，在命中率H为0.9和0.99两种情况下，分别计算存储系统的访问效率。7要求主存实际频宽为4MB／s，现设主存每个分体的存取周期为2us，宽度为4个字节，采用模m多分体交叉存取，但实际频宽只能达到最大频宽的0.6倍，问主存模数m应取多少方能使两者的速度基本匹配？其中m取2的幂。8在一个Cache存储系统中，主存储器的访问周期、存储容量和单位价格分别为60ns、64MB和10元/MB，Cache的访问周期、存储容量和单位价格分别为10ns、512KB和100元/MB，Cache的命中率为0.98。计算这个Cache存储系统的等效访问周期、存储容量和单位价格。（2）计算这个Cache存储系统的访问效率。9一个由Cache和主存构成的二级存储系统，已知主存容量为1M字，Cache容量为32K字。采用组相联地址映象与变换，Cache共分8组，主存和Cache的块的大小为64字。（1）写出主存和Cache的地址格式，要求说明各字段名称和位数。（2）如果Cache的存取周期为20ns，命中率为0.95，希望采用Cache后的加速比达到10，那么要求主存的存取周期应该为多少？主存容量为字，故主存地址有20位。Cache的容量为32K＝字，所以Cache的地址有15位。主存按照Cache的容量分区，所以区号E长度＝20－15＝5位。采用组相联映象，Cache共分8组，所以组号G和g为3位。主存和Cache的块的大小为64字，所以块内地址W和w的长度为6位。块号B和b的长度＝15－3－6＝6位。（2）已知Cache的存取周期TC＝20ns，命中率H＝0.95，设主存的存取周期为TM，有：得到所要求的主存存取周期为：＝380ns10．在页式虚拟存储器中，一个程序由0～4共5个虚页组成，在程序执行过程中，访存虚页地址流为：0,1,0,4,3,0,2,3,1,3假设分配给这个程序的主存空间有3个实页，分别采用FIFO、LRU、OPT替换算法进行替换调度。分别画出3种替换算法对主存3个实页位置的使用情况。（2）分别计算3种替换算法的主存命中率。[答案]（1）分别用FIFO、LRU、OPT替换算法对主存3个实页使用过程如下图所示，其中“*”表示准备替换出去的页。（2）FIFO替换算法的主存命中率：H＝2/10＝0.20LRU替换算法的主存命中率：H＝4/10＝0.40OPT替换算法的主存命中率：H＝5/10＝0.5011．设某程序包含5个虚页，其页地址为4，5，3，2，5，1，3，2，2，5，1，3。当使用LRU法替换时，为获得最高的命中率，至少应分配给该程序几个实页？其可能的最高命中率为多少？[答案]：由于LRU是堆栈型替换算法，因此，随着分配给该程序的实页数的增加，主存命中率会单调上升。但是在实页数增加到一定的程度后，命中率就不再提高，下面使用堆栈处理法，该程序处理过程如下表所示，其中N为主存页面数。由上表可以看出，采用LRU替换算法，要达到最高命中率，只需要分配该该程序4个实页，最高命中率为：H=7/12=0.58。第四章输入输出系统1名词解释中断屏蔽码、中断响应次序、中断处理次序、通道极限流量、通道实际最大流量。[答案]略2从系统结构的角度来讲，I/O系统的设计对整个计算机系统有何影响？[答案]I/O系统的好坏直接影响到整个计算机系统的性能，即会影响系统的处理速度，因为根据Amdal定律，系统性能的性能受系统中速度最慢部分制约，因此，不论其他部件如CPU，存储系统速度再快，但是I/O系统比较慢的话，系统的性能仍然比较低。3简述通道的工作过程。[答案]略4简述字节多路通道、选择型通道、数组通道的数据传输过程。[答案]略5设中断屏蔽位“1”对应开放，为“0”对应屏蔽，各级中断处理程序的中断屏蔽位设置如下：1）当中断响应先后次序为1→2→3→4时，其中断处理次序是什么？2）如果所有的中断处理都各需3Δt，若在运行用户程序时，同时出现了2、3级中断请求，经过2Δt又同时出现了1、4级中断请求，画出程序运行过程示意图。6若计算机共有5级中断，中断响应的优先次序从高到低依次是1→2→3→4→5。（1）若要将中断的优先次序改为1→4→5→2→3，设计各级中断处理程序的中断级屏蔽码（中断级屏蔽位为“1”对应屏蔽，为“0”对应开放）。若在运行用户程序时，同时出现了4、2级中断请求，而在处理第2级中断未完成时，又同时出现了第1，3，5级中断请求，请画出程序运行过程示意图。7设某个字节多路通道的设备选择时间为TD＝9.8üs，传送一个字节的数据传送时间为TS＝0.2üs，若某种低速外设每隔500üs发出一次传送请求，那么，该通道最多可连接多少台这样的设备？[答案]50台（分析过程略，可参考习题书）。8设某个数组多路通道的设备选择时间为TS＝1üs，传送一个字节数据的传送时间为TD＝1üs，一次传送定长数据块的大小k＝512B，现有8台外设的数据传输率分别如下表所示，问哪些设备可以连接到通道上正常工作？[答案]2,3,4,5,6,可连接到通道上正常工作（分析过程略，可参考习题书）。9一个通道型I/O系统，由一个字节多路通道A（其中包括两个子通道A1和A2），两个数组多路通道B1和B2，以及一个选择通道C构成，各通道所接设备和设备的数据传输速率如下表所示，（1）分别结算通道A,B1,B2,C的最大流量至少为多少才不会丢失传送的数据？（2）若整个I/O系统的流量占主存频宽的1/2时，才认为两者的速度是匹配的，问主存的频宽应达到多少？[答案]（1）只有当A的最大流量为512KB/s，B1的最大流量为512KB/s，B2的最大流量为512KB/s，C的最大流量为1024KB/s,时，才不会丢失数据。主存的频宽应达到5MB/S（分析过程略，可参考习题书）。10某个字节多路通道连接6台外设，它们的数据传输率分别如下表所示（1）计算通道的实际流量fbyte（2）若通道最大流量fmax.byte=fbyte，求通道的工作周期TS+TD（3）设通道对外设数据传送请求的响应优先次序按外设的数据传输速率从高到低排序。若6台外设同时发出传送请求，请画出该通道处理这6台外设传送请求的处理时间示意图，并由此指出哪台外设会局部丢失数据？试提出避免数据丢失的解决方法。[答案]（1）通道的实际流量fbyte=200B/s（2）通道的工作周期TS+TD=5üs（3）处理时间示意图略，避免数据丢失的解决方法可参考教材。第五章流水线技术1.名词解释指令的重叠解释方式:在解释第k条指令的操作完成之前,就可开始解释第k+1条指令.一次重叠:指把一条指令的解释过程分为”分析”和”执行”两个子过程,分别由指令分析部件和指令执行部件来完成相应的功能.无论何时,在指令分析部件和指令执行部件内部只有相邻的两条指令在重叠执行.操作数相关:指在第k条指令和第k+1条指令的数据地址之间发生关联而造成第k条指令和第k+1条指令不能同时解释的现象.指令相关:指第k条指令的结果会影响第k+1条指令内容而产生关联,造成第k条指令和第k+1条指令不能同时解释的现象.静态流水线:指在同一时间内,多功能流水线中的各个功能段只能按一种功能的联接方式工作.动态流水线:指在同一时间内,多功能流水线中的各个功能段可按不同功能或运算的联接方式工作.线性流水线:流水线各段串行连接,没有反馈回路,各个段只经过一次.非线性流水线:流水线中除了由串行连接的通路外,还有某种反馈回路,使得一个任务流经流水线时,需经过某个段或越过某些段.流水线的实际吞吐率:指从启动流水线处理机开始到流水线操作结束,单位时间内流出的任务数.流水线的加速比:指流水线工作相对于等效的非流水线顺序串行工作方式,速度提高的比值.流水线的效率:指流水线设备的利用率.预约表:它用于非线性流水线,是一张二维的表格,其横坐标表示流水线工作的时钟周期,纵坐标表示流水线的功能段,中间画”√”表示该功能段在这一时钟周期处于工作状态,空白的地方表示该功能段在这个时刻周期不工作.冲突向量:用一个有N-1位的位向量来表示后继新任务间隔各种不同拍数流入流水线时,是否会发生功能段使用的冲突,称此位向量为冲突向量.局部性相关:指令相关,主存操作数相关和通用/变址寄存器组操作数相关，只影响相关的两条或几条指令,或至多影响流水线某些段的推后工作,并不会改动指令缓冲器中预取到的指令的内容,影响是局部的.全局性相关:转移指令和其后的指令之间存在关联,使不能同时解释,其造成的对流水机器的吞吐率和效率下降的影响要比指令相关,主存操作数相关和通用/变址寄存器组操作数相关严重得多,它可能会造成流水线中很多已被解释的指令作废,需要重新预取指令进入指令缓冲寄存器等,它将会影响整个程序的执行顺序.先写后读相关:若后一条指令的源操作数地址与前一条指令的目的操作数地址相同,就称这两条指令发生了先写后读相关.先读后写相关:若后后一条指令的目的操作数地址与前一条指令的源操作数地址相同,就称这两条指令发生了先读后写相关.写－写相关:若前后两条指令使用了相同的目的操作数地址,就称这两条指令发生了写—写相关.超标量流水线:指在每个时钟周期同时并行发射多条指令，并产生多个结果的流水线.超流水线:指在每个基本时钟周期内分时发射多条指令,每一时刻只发射一条指令,并产生多个结果的流水线.超标量超流水线:是超标量流水线与超流水流水线的结合,指在一个基本时钟周期内能分时发射多条指令,且每一时刻能同时发射多条指令,并产生多个结果的流水线.VLIW:超长指令字，指在每个时钟周期发射一条超长指令，每条超长指令由多个短指令构成，在流水线的执行段，这些短指令被分散到不同的运算部件上并行处理，因此该流水线每个始终周期可并产生多个短指令运行结果..2.试解释重叠方式中出现的相关问题和解决办法.[答]重叠方式中出现的相关问题主要有指令相关,主存空间数相关,通用寄存器组数相关和通用寄存器组基址值或变址值相关等.指令相关可转化成操作数的相关来处理;主存空间数相关的处理办法一般采用推后相关单元的读的方法;通用寄存器组数相关的处理可采用推后相关单元的读,设置相关专用通路两种方法;通用寄存器组基址值或变址值相关的处理也可采用推后相关单元的读,设置相关专用通路两种方法.3.假设一条指令的执行过程分为”取指令”,

“分析”

和”执行”三个阶段,每一个阶段的执行时间分别为,在下列各种情况下,分别写出连续执行n条指令所需要的时间表达式.1)顺序执行方式;(2)仅”取指令”和”执行”重叠;(3)先行控制方式.4.一台非流水处理器X的时钟频率为26MHz,平均CPI为4.处理器Y是对X机的改进,它有一条5级流水线,各级经过的时间为一个时钟周期,但由于锁定器延迟和时钟扭斜效应,其时钟频率仅为20MHz.(1)若有100条指令的程序运行在两台处理机上时,假设每条指令之间不发生任何相