计算机系统结构试题及答案

2009—2010学年度第一学期2007级《计算机系统结构》期末考试试卷（A）（闭卷）姓名：学号：专业：（注：①考试时间为120分钟；②所有解答必须写在答题纸上。）一、单项选择题（每小题3分,共30分)1．在系列机中发展一种新型号机器，你认为下列（)设想是不行的?【A】新增加字符数据类型和若干条字符处理指令【B】将中断分级由原来的4级增加到5级【C】在CPU和主存之间增设Cache存贮器【D】将浮点数的下溢处理法由原来的恒置“1"法，改为查表舍入法2。对计算机系统结构来说，不透明的是（）.【A】存储器采用交叉存取还是并行存取【B】CPU内部的数据通路的宽度是8位还是16位【C】采用浮点数据表示还是标志符数据表示【D】指令采用硬联逻辑实现还是微程序实现3．一个平衡的计算机系统，应该是（）。【A】1MIPS的CPU速度【B】1MB的主存容量【C】1Mb/s的I/O吞吐率【D】A、B和C4、（）设计是现代计算机系统设计所采用的方法。【A】由上往下【B】由下往上【C】由中间开始【D】上下同时开始5．当今微型机中实现软件移植最好的方法是()。【A】系列机【B】兼容机【C】仿真技术【D】统一高级语言6、不能够对向量数据结构提供直接支持的是()数据表示。【A】向量【B】堆栈【C】描述符【D】A和C7、采用整数边界存储技术，其主要目的是(）.【A】节约主存空间【B】提高数据的访问速度【C】一个主存周期可取多条指令【D】一个主存周期至少可取到一条指令8、在指令的操作码编码方式中，优化实用的编码是（).【A】Huffman编码【B】等长编码【C】Huffman扩展编码【D】BCD码9、流水计算机中将指令Cache和数据Cache分开，主要是为了()。【A】提高存储系统的速度【B】增加主存容量【C】解决功能部件冲突【D】解决访存冲突10、当N=16时,能描述4组4元交换的函数是（).【A】C1+C2【B】C0+C1【C】C0+C2【D】C2+C3二、（10分）在采用通用寄存器指令集结构的计算机上得到了如下所示的数据：指令类型执行频率时钟周期数ALU指令43%1LOAD指令21％2STORE指令12%2分支指令24%2假若编译器优化后能去掉50%的ALU指令,但不能去掉其它三类指令。求优化后的MIPS与优化前的MIPS速率比。三、（10分）设某机器系统指令字长12位，每个操作码和地址均占3位，试提出一种分配方案，使该指令系统有4条三地址指令，8条二地址指令和180条单地址指令。四、（10分）设通道在数据传送期中,选择设备需4。9μS,传送一个字节数据需0.lμS。（1）其低速设备每隔250μS发出一个字节数据传送请求，问最多可接多少台这种设备？（2）若有A~E共5种高速设备，要求字节传送的间隔时间如下表所示，其时间单位为μS.若一次通信传送的字节数不少于1024个字节，问哪些设备可挂在此通道上？哪些则不能？设备ABCDE时间间隔（μS)0.130。10.110.20。3五、（10分）有一非线线性流水线预约表如下.功能段123456S1√√S2√√√S3√√S4√（1)求平均延迟最小的最佳调度方案;（2)画出按最佳方案之一连续输入3个任务的时空图。六、（10分）有一四段线性流水线,每功能段延时时间分别是：△t1=△t3=△t4=△t0，△t2=3△t0.若在这个流水线上执行40个任务。求实际吞吐率、效率和加速比。01234567输01234567输出端01234567输入端AABCDK0EFGHK1IJKLK2C0C2C1C3八、（10分）在8个PE构成的双向环互连的并行处理机中，计算点积S=(n=8)所需要的时间。设初始化时将A，B各分量已分配到各PE中,且设相邻处理单元之间传送一次数据需要时间△t，完成一次加法需要时间2△t，完成一次乘法需要时间4△t。（全部试题完）武汉大学计算机学院2009—2010学年度第二学期2007级《计算机系统结构》期末考试试卷(A）参考答案一、（每小题3分，共30分)[解]：1-10：BCDCABDCDB二、（10分）［解]：三、（10分)［解］：000×××××××××011×××××××××100000××××××100111××××××101000000×××64+116=180101111111×××64+116=180110000000×××111110011×××四、（10分）[解］：（1）低速设备应接字节多路通道所以，n≤50台,即最多可接50台（2）根据题意，此通道为选择通道其中，n≥1024，应使¦select·i≤¦max·select，由此可得出通道工作周期为：T≈0.1014(us)所以，只有A、C、D、E可挂在此通道上,B则不行。五、（10分）［解]:(1)状态图略。最佳调度方案为(3）和(1，5）（2）输入3个任务时空图略。六、（10分）[解]：七、（10分）[解]：不能与输出的2、3、6、7结点相连。八、(10分）［解]：需要8次乘法，7次加法；共14△t计算机系统结构姓名：学号:一、名词解释(每题3分,共15分）1。Cache2：1经验规则 3.同构型多处理机5.堆栈型机器2。计算机体系结构4。通道处理机PAGEPAGE17二、填空(每空1分,共20分)设计I/O系统的三个标准是（）、(）和（).存储器层次结构设计技术的基本依据是程序的（).相联度越高,（）失效就越少;（）失效不受Cache容量的影响，但（）失效却随着容量的增加而减少。在虚拟存储器中，一般采用(）地址映象方法和（）更新策略。计算机系统中提高并行性的技术途径有（）、（）和（）三种。在高性能单处理机的发展中,起主导作用的是(）.在处理机中，若指令序列完成的顺序总是与它们开始执行的顺序保持一致，则只可能出现（）相关,否则就有可能出现（）、（）和（）相关。对向量的处理有（)方式、(）方式、（)方式。三、简答题（每题6分，共24分）任写出三种Cache的优化技术，并简述其基本思想.在指令集结构设计中,应该考虑哪些主要问题？数据相关有哪几种类型？解决数据相关有哪些主要方法？试以系列机为例，说明计算机体系结构、计算机组成和计算机实现三者之间的关系。四、计算题1。给定以下的假设,试计算直接映象Cache和两路组相联Cache的平均访问时间以及CPU的性能。由计算结果能得出什么结论?理想Cache情况下的CPI为2。0，时钟周期为2ns，平均每条指令访存1.4次。两者Cache容量均为128KB,块大小都是32字节。组相联Cache中的多路选择器使CPU的时钟周期增加了10%。这两种Cache的失效开销都是80ns。命中时间为1个时钟周期。128KB直接映象Cache的失效率为1。0％，128KB两路组相联Cache的失效率为0.7%。（15分)2。计算机系统字长64位，包含三个选择通道和一个多路通道，每个选择通道上连接了两台磁盘机和三台磁带机，多路通道上连接了了两台行式打印机，两台读卡机、10台终端，假定各设备的传输率如下：磁盘机：600KBps，磁带机：200KBps，行打机:6.6KBps，读卡机：1。2KBps，终端：1KBps。计算该计算机系统的最大I/O数据传输率。(6分）3。某计算机系统采用浮点运算部件后使浮点运算速度提高到原来的20倍,而系统运行一程序的整体性能提高到原来的10倍，试计算该程序中浮点操作所占的比例。(5分)4。动态多功能流水线由6个功能段组成，如下图所示：其中,s1、s4、s5、s6组成乘法流水线，s1、s2、s3、s6组成加法流水线，各个功能段时间为：s1、s3、s4、s6为△t，s2、s5为2△t，假设该流水线的输出结果可以直接返回输入端，而且设置有足够地缓冲寄存器,若以最快的方式用该流水计算:∏（Ai＋Bi)（其中i＝1。.4，∏为连乘符号)(1）画出其处理过程的时空图.（2）计算其实际的吞吐率和效率.（15分)2003～2004学年度第2学期《计算机系统结构》试题A答案填空题:（）由软件实现的机器称为虚拟机器;由硬件和微程序（固件）实现的机器称为实际机器。软件和硬件在逻辑上是等效的.由于软、硬件紧密相关,软硬界面常常是模糊不清的。计算机组成设计主要是围绕：1.提高速度，2.提高操作的并行度、重叠流水,3.分散功能，4.设置专用功能部件来进行。具有相同“系统结构”（如指令系统相同）的计算机可以因为速度要求等因素的不同而采用不同的组成。一种“计算机组成”可以采用多种不同的“计算机实现”。“计算机组成"反过来也会影响“系统结构”。计算机系统结构设计的主要任务是：进行软、硬件的功能分配。计算机系统设计，从多级层次结构出发，可以分为：由上往下、由下往上和从中间开始三种不同的设计思路。10．计算机应用可以归纳为向上升级的四类它们分别是：数据处理（DataProcessing）.信息处理(InformationProcessing）。知识处理（KnowledgeProcessing）.智能处理(IntelligenceProcessing）.简答题：1．计算机实现（ComputerImplementation）？:是指计算机组成的物理实现，包括:处理机、主存等部件的物理结构，器件的集成度和速度,器件、模块、插件、底板的划分与连接，专用器件的设计,微组装技术，信号传输，电源、冷却及整机装配技术等.2．计算机组成（ComputerOrganization)?：是指计算机系统结构的逻辑实现,包括:机器级内的数据流和控制流的组成以及逻辑设计等。3．软件的可移植性？是指软件不用修改或只需经少量加工就能由一台机器搬到另一台机器上运行，即同一软件可以不同的系统环境.4．向上（下）兼容？：是指按某档机器编制的软件,不加修改就能运行于比它高（低)档的机器上。5．向前（后）兼容？:指的是，在按某个时期投入市场的该型号机器上编制的软件，不加修改就能运行在它之前（后)投入市场的机器上.6．兼容机(CompatibleMachine）？：具有同一系统结构的计算机称为～。采用兼容机的思想与采用系列机的思想实际上是一致的.7．模拟（Simulation)：用机器语言程序解释实现软件移植的方法称为~。8．仿真（Emulation）：用微程序直接解释另一种机器指令系统的方法称为～。9．现场片：使用户可根据需要改变器件内部的功能或内容，以适应结构和组成变化的需要。10．全用户片：完全按用户要求设计的用户片称为全用户片。简述题：算机系统结构研究的是什么?答：软、硬件之间的功能分配以及对传统机器级界面的确定.计算机组成设计要解决的问题是什么？答:在所希望能达到的性能和价格比的前提下，怎样最佳、最合理地把各种设备和部件组织成为一台计算机,以实现所确定的系统结构。3．器件的发展对系统结构的影响？（1）器件的发展改变了逻辑设计的传统方法。（2）器件的发展也使系统结构的“下移”速度加快.（3）器件的发展还促进了算法、语言和软件的发展.4。什么是并行性?只要在同一时刻或是在同一时间间隔内完成两种或两种以上性质相同或不同的工作，它们在时间上能相互重叠，都体现了并行性.5。CISC指令系统的含义?复杂指令系统计算机，即机器指令系统变得越来越庞杂,这就是所谓的CISC指令系统.6。什么是页式存贮管理？页式存贮管理是把主存空间和程序空间都机械地等分成固定大小的页，按页顺序编号.（页面大小随机器而异,一般在512到几KB）。7.什么是向量流水处理机？向量流水处理机是将向量数据表示和流水线技术结合在一起，构成向量流水处理机,简称向量流水处理机.8.什么是相联处理机？相联处理机是以相联存贮器为核心，配上必要的中央处理部件、指令存贮器、控制器和I/O接口,就构成一台以存贮器操作并行为特点的相联处理机.计算题：设一台模型机有7条指令，其使用频度为：____________________________________________________指令使用频度|指令使用频度I10。03｜I40。05I20.03｜I50。15I30.04｜I60。3|I70。4_____________________________________________________求出：（1）利用哈夫曼(Huffman）压缩技术，构造哈夫曼树;（2）.操作码平均码长和扩展码长。要求：哈夫曼树节点为1.0（1)1.010.60.610.30.310.150.15100000.090.060.090.0610100.030.040.050.150.30.40.030.030.040.050.150.30.40.03（2）H=2.17H=2。22。如果设一个系统有四个中断级，个级中断响应次序为1-〉2-〉3—〉4。见中断级屏蔽位表中断处理程序级别中断级屏蔽位1级2级3级4级第1级第2级第3级第4级0111001100010000求当把中断次序改为1—>4->3-〉2时，画出中断级屏蔽位表.中断处理程序级别中断级屏蔽位1级2级3级4级第1级第2级第3级第4级01110000010001103.计算流水线实际吞吐率TP和效率η.设有两个向量C和D,各有4个元素，在图中的静态双功能流水线上工作。其中,1-〉2—〉3->5组成加法流水线，1—>4—>5组成乘法流水线。设每个流水线所经过的时间均为Δt，而且流水线的输出结果可以直接返回到输入或暂存于相应的缓冲寄存器中,其延迟时间和功能切换所需要的时间都可以忽略不计。求：该流水线的实际吞吐率TP和效率η.空间54321012345678910111213141516时间Δt实际吞吐率TP=7/（15Δt)η=32%4。计算多级立方体互连网络。见图N=8多级立方体互连网络，求当输入端级控制信号为S2S1S0=010时，输入端为01234567时，输出端为：23016745。输入输出5。由表达式：E=a+bx+cx2+dx3,利用减少树高的办法来加速运算，要求（1)画出树形流程图；（2)确定TP、P、SP、EP诸值++*+*+d**+**+*acx*****bxxxxxp=3,TP=4,SP=3/2,EP=1/2计算机系统结构试题第一部分选择题一、单项选择题(每小题1分,共10分)在每小题的四个备答案中有一个正确的答案，将正确答案的序号写在题干后的括号内)1。计算机使用的语言是(）A.专属软件范畴，与计算机体系结构无关B.分属于计算机系统各个层次C。属于用以建立一个用户的应用环境D.属于符号化的机器指令2.动态数据流机最突出的特点是使(）A.数据流令牌无标号B。需要程序记数器来实现C。令牌带上标号D。同步由门（Latch）寄存器来实现3。多处理机上两个程序段之间若有先写后读的数据相关，则（)A。可以并行执行B。不可能并行C。任何情况均可交换串行D。必须并行执行4.多处理机的各自独立型操作系统(）A。要求管理程序不必是可再入的B.适合于紧耦合多处理机C。工作负荷较平衡D。有较高的可靠性5。输入输出系统硬件的功能对（）是透明的。A.操作系统程序员B.应用程序员C。系统结构设计人员D.机器语言程序设计员6。“启动I/O”指令是主要的输入输出指令，是属于()A。目态指令B.管态指令C。目态、管态都能用的指令D。编译程序只能用的指令7。全相联地址映象是指（）A.任何虚页都可装入主存中任何实页的位置B.一个虚页只装进固定的主存实页位置C.组之间是固定的，而组内任何虚页可以装入任何实页位置D。组间可任意装入,组内是固定装入8.（）属于MIMD系统结构.A.各处理单元同时受同一个控制单元的管理B。各处理单元同时接受同一个控制单元送来的指令C.松耦合多处理机和多计算机D.阵列处理机9。设16个处理器编号分别为0，1，2，…，15用Cube3互联函数时,第10号处理机与第（）号处理机相联。A。11B.8C.14D.210.若输入流水线的指令既无局部性相关,也不存在全局性相关，则(）A。可获得高的吞吐率和效率B。流水线的效率和吞吐率恶化C。出现瓶颈D.可靠性提高第二部分非选择题二、填空题（每空1分，共20分）11。标志符与每个数据相连，合存于_______，用于描述单个数据的_______。12.总线仲裁算法有：静态优先级算法、固定时间片算法、_______算法和_______算法。13。计算机仿真用_______解释，计算机模拟用_______解释.14.按弗林（MichaelJ.Flynn）的观点，计算机系统可分为单指令流单数据流、_______、多指令流单数据流和_______四大类。15。要实现两条指令在时间上重叠解释，首先需要付出_______，其次，要处理好指令之间可能存在的_______。16。与重叠机器一样，流水机器在遇到_______指令，尤其是_______指令时，效率也会显著下降。17。超长指令字(VLIW)结构是将_______和_______两者相结合。18.互连网络的交换方法主要有线路交换、包交换、线路/包交换，SIMD互连网络多采用_______交换，多处理机常采用_______交换。19。数据流机采用_______,执行的操作序列取决于输入数据的可用性；归约机则采用_______，执行的操作序列取决于对数据的要求，对数据的需求又来源于函数式程序设计语言对表达式的归纳。20.输入输出系统包括输入输出设备、设备_______及与输入输出操作有关的_______件.三、改错题（每小题2分，共10分）（下列每小题划线部分A、B、C中有一处错误，请先写出错处，并在括号中写出正确文字)21。对操作码进行优化编码时，在了解每种指令在程序中出现的概率后，使用Huffman算AB法构造Huffman树,这样获得的Huffman编码是唯一的。（）C22.多处理机中,两个程序段之间若同时有先写后读和先读后写2种相关，以交换数据为目的时,则必须并行执行，读写要完全同步，允许顺序串行和交换串行.()ABC23.计算机仿真适合在两种结构差距大的机器间运用.（）ABC24.主存空间数相关是相间隔的两条指令之间出现对主存同一单元要求先写而后读的关联。ABC()25.由于Cache存贮器的地址变换和块替换算法是用软件实现的，因此Cache存贮器对应用A程序员是透明的，而且Cache对处理机和主存间的信息交往也是透明的。(）BC四、简答题（每小题6分,共30分)26。简述标志符数据表示的主要优点。27。简述设计RISC结构用了哪些基本技术?28。设Pi和Pj程序段都是一条语句，且Pi在Pj之前执行,试举出Pi和Pj间存在3种可能的数据相关。29.简述控制驱动的控制流方式的特点?30。模拟与仿真的主要区别和适合场合是什么？五、应用题（共30分）31。(12分）假设某模型机共有7条指令,7条指令I1—I7使用的频度分别为:0.35,0。25，0.20，0。10，0。04,0。03,0.03。(1）利用Huffman算法，构造Huffman树，并给出Huffman编码和平均码长。（2)给出Huffman扩展码编码。32。(10分）多级混洗交换网络是如何组成的？它与间接二进制n立方体网络有何差异?并画出N=8时的多级混洗交换网络图。33。（8分）设向量A和B各有4个元素在下图所示的静态双功能流水线上计算向量点积A·B=，其中1→2→3→5组成加法流水线,1→4→5组成乘法流水线。若假定流水线的各段所经过的时间均为△t=2。5,流水线输出可直接送回输入或暂存于相应缓冲寄存器中，其延迟时间和功能切换所需的时间都可忽略.求出吞吐率和加速比.计算机系统结构试题参考答案一、单项选择题(每小题1分，共10分）1。B2.C3。B4。D5。B6。B7.A8.C9。D10。A二、填空题（每空1分，共20分)11.同一存储单元类型特征12。动态优先级先来先服务13。微程序机器语言14。单指令流多数据流多指令流多数据流15。空间代价关联16.转移条件转移17.水平型微码超标量处理18.线路包19.数据驱动需求驱动20。控制器软硬三、改错题(每小题2分，共10分)21.(C错改为“不是唯一的”）22.(C错改为“不允许顺序串行和交换串行”)23.（B错改为“差距不大")24。（A错改为“相邻”）25.（A错改为“硬件”)四、简答题（每小题6分，共30分）

26。(1）简化了指令系统和程序设计；（2）简化了编译程序；（3）便于实现一致性校验；（4)能由硬件自动变换数据类型；(5)支持数据库系统的实现与数据类型无关的要求；(6)为软件调试和应用软件开发提供了支持。27。（1）按RISC一般原则设计；(2）逻辑实现用硬联和微程序结合；(3)用重叠寄存器窗口（4)指令用流水和延迟转移;(5)优化设计编译系统。28.（1）若Pi的左部变量在Pj的右部变量集内，且Pi必须取出Pi运算的结果来作为操作数，则称Pi“数据相关"于Pi.（2）若Pj的左部变量在Pi的右部变量集内，且当Pi未取用其变量的值之前，是不允许被Pj所改变，则称Pi“数据反相关”于Pj.（3)若Pi的左部变量也是Pj的右部变量，且Pj存入其算得的值必须在Pi存入之后，则称Pj“数据输出相关"于Pi。29.控制驱动的控制流方式的特点是：通过访问共享存储单元让数据在指令之间传递;指令的执行顺序隐含于控制流中，可以显式地使用专门的控制操作符来实现并行处理，指令执行顺序受程度计数器的控制，即受控制令牌所支配.30.模拟与仿真的主要区别在于解释用的语言。仿真是用微程序解释，其解释程序存在控制存储器中，而模拟是用机器语言程序解释，其解释程序存在主存中。模拟灵活,可实现不同系统间的软件移植，但结构差异太大时，效率、速度会急剧下降。仿真在速度上损失小，但不灵活，只能在差别不大的系统之间使用，否则效率也会过低且难以仿真，需与模拟结合才行.五、应用题（共30分)31.表操作码的Huffman码及扩展操作码的编码指令频度（Pi）操作码使用Huffman编码OP长度(Li)利用Huffman概念的扩展操作码OP长度（Li）I10．3501002I20．25102012I30.201103102I40。1011100511004I50.0411101511014I60。0311110511104I70.031111151111432。多级混洗交换网络由n级相同的网络组成，每一级都包含一个全混拓扑和随后一列2n—1个四功能交换单元,采用单元控制方式.多级混洗交换网络与间接二进制n方体网络只有两点差别：前者数据流向的级号顺序n—1,n—2，…，1，0，用四功能交换单元，后者数据流向相反,其级号顺序0,1，…，n—1,用二功能交换单元。33．实际吞吐率为=因顺序方式所需时间为4，因此加速比SP=24=1。61。（30分）解释下列术语

（1）冯·诺依曼结构:冯·诺依曼等人于１９４６年提出了一个完整的现代计算机雏型,它由运算器、控制器、存储器和输入输出设备组成，这种结构称为冯·诺依曼结构。

(2）数据表示:数据表示研究的是计算机硬件能够直接识别，可以被指令系统直接调用的那些数据类型。数据表示是数据类型中最常用,也是相对比较简单，用硬件实现相对比较容易的几种。如定点数（整数）、逻辑数（布尔数）、浮点数（实数)、十进制数、字符、字符串、堆栈和向量等.

(3）CISC：复杂指令系统计算机

(4）存储系统：两个或两个以上速度、容量和价格各不相同的存储器用硬件、软件、或软件与硬件相结合的方法连接起来成为一个系统,这就是存储系统。

(5)时空图：描述流水线的工作，最常用的方法是采用“时空图”。在时空图中，横坐标表示时间，也就是输入到流水线中的各个任务在流水线中所经过的时间。当流水线中的各个功能部件的执行时间都相等时，横坐标被分割成相等长度的时间段。纵坐标表示空间，即流水线的各个子过程。在时空图中，流水线的一个子过程通常称为“功能段”。

(6)多功能流水线:多功能流水线（MultifunctionPipelining)是指流水线的各段可以进行不同的连接.在不同时间内，或在同一时间内，通过不同的连接方式实现不同的功能.

（7)加速比：完成一批任务，不使用流水线所用的时间与使用流水线所用的时间之比称为流水线的加速比(Speedupratio）。

(8）链接技术：链接是当从一个流水线部件得到的结果直接送入另一个功能流水线的操作数寄存器时所发生的连接过程。换句话说，中间结果不必送回存储器,而且甚至在向量操作完成以前就使用。链接允许当第一个结果一变成可用的操作数时就马上发出相继的操作。

（9)存储转发寻径：存储转发寻径（storeandforward）在存储转发网络中包是信息流的基本单位。每个结点有一个包缓冲区.包从源结点经过一系列中间结点到达目的结点.

（