计算机体系结构期末复习题答案.docx

计算机体系构造期末复习题答案系别 _ 班级 _ 姓名_ 学号_一、 填空题每空1分1.依据弗林Flynn分类法，计算机系统可以分为4类：SISD计算机, SIMD计算机, MISD计算机和MIMD计算机。2. 改良之后的冯诺依曼计算机的只要特点是存储器为中心，总线构造，分散限制。3. 当前计算机系统中的存储系统是一个层次构造，其各层分别为：通用存放器，高速缓存，主存，辅存，脱机大容量存储器。4.高速缓冲存储器的地址映象方式有三种，它们分别是：全向量方式，干脆相联方式，组相联方式。5.虚拟存储器的三种管理方式是段式管理，页式管理和段页式管理。6.目前计算机中常用数据有用户定义数据，系统数据和指令数据三种类型。7.通常可能出现的流水线的相关性有资源相关，数据相关和限制相关。8.解决中断引起的流水线断流的方法有不精确断点法和精确断点法。9.目前向量处理机的系统构造有两种：存储器存储器型和存放器存放器型。10.通用计算机根本指令分为5类，它们分别是：数据传送类，运算类，程序限制类，输入输出类，处理机限制和调试类。11执行指令x1=x2+x3；x4=x1-x5会引起RAW类型的数据相关，执行指令x5=x4*x3；x4=x0+x6会引起WAR类型的数据相关，执行指令x6=x1+x2；x6=x4*x5会引起WAW类型的数据相关。12多计算机网络中，通常出现的4种通信模式是单播模式，选播模式，播送模式和会议模式。诺依曼计算机是以限制驱动方式工作，以数据驱动方式工作的典型计算机是数据流计算机，以需求驱动方式工作的典型计算机是归约机，以模式匹配驱动方式工作的典型计算机是人工智能计算机。二, 名词说明每题2分1.计算机体系构造：计算机系统构造就是计算机的机器语言程序员或编译程序编写者所看到的外特性，是硬件子系统的概念构造及其功能特性。2.系列机： 所谓系列机是指同一厂家生产的具有一样的系统构造，但实行了不同的组成和实现的技术方案，形成了不同型号的多种机型。3.模拟: 模拟是指用软件的方法在一台计算机上，实现另一台计算机的指令系统，被模拟的机器是不存在的，称为虚拟机，执行模拟程序的机器称宿主机。4.程序的局部性原理: 程序访问局部性原理说明白计算机在程序执行过程中呈现出的一种规律，即程序往往重复运用它刚刚运用过的数据和指令。局部性分为时间上的局部性和空间上的局部性两种。所谓时间局部性是指近期被访问的代码，很可能不久又将再次被访问；空间局部性是指地址上相邻近的代码可能会被连续地访问。5.MIPS：它表示每秒百万条指令数。6.高速缓冲存储器: 高速缓冲存储器是存在于主存及CPU之间的一级存储器，由静态存储芯片SRAM组成，容量比拟小但速度比主存高得多，接近于CPU的速度。7.虚拟存储器: 虚拟存储器是由主存储器和协助存储器组成，通过必需的软件和硬件的支持，使得CPU可以访问的存储器具有近似于主存的速度和近似于辅存的容量。8.快表: 为了提高地址转换速度，缩短查表时间，采纳一个小容量的, 高速的相关存储部件，用来存放当前最常常用到的那一局部页表，实行按内容相联方式进展访问。这样，查页表的时间就相当于访问小容量的相关存储器的时间，从而大大地提高了速度，这个小容量相关存储器称为快表。9.程序定位： 把一个程序交给处理机运行，必需首先把这个程序的指令和数据装入到主存储器中。一般状况下，程序所安排到的主存物理空间及程序本身的逻辑地址空间是不同的，把指令和数据中的逻辑地址(相对地址)转变成主存物理地址(肯定地址)的过程称为程序定位。10.延迟转移技术：为了使指令流水线不断流，在转移指令之后插入一条不相关的有效的指令，而转移指令被延迟执行，这种技术称为延迟转移技术。11.窗口重叠技术： 为了能更简洁, 更干脆地实现过程及过程之间的参数传递，大多数RISC机器的CPU中都设置有数量较大的存放器组，让每个过程运用一个有限数量的存放器窗口，并让各个过程的存放器窗口局部重叠，这就是窗口重叠技术。12.流水线技术： 把一个重复的时序过程分成假设干个子过程，每个子过程都可以有效地在其专用功能段上和其他子过程同时执行的一种技术，称为流水线技术。13.动态流水线： 动态流水线在同一时间内允许按多种不同运算的联结方式工作。14.静态流水线： 静态流水线在同一时间内只能按一种运算的联结方式工作。15.线性流水线： 线性流水线中，从输入到输出，每个功能段只允许经过一次，不存在反应回路。16.非线性流水线： 非线性流水线存在反应回路，从输入到输出过程中，某些功能段将数次通过流水线，这种流水线适合于进展线性递归的运算。17.流水线的吞吐率： 流水线单位时间完成的任务数。18.超流水线计算机： 超级流水线构造是把每一个流水线(一个周期)分成多个(例如3个)子流水线，而在每一个子流水线中取出的仍只有一条指令，但总的来看，在一个周期内取出了三条指令。即在一个时钟周期内能够分时放射多条指令的处理机。19.向量的分段开采技术： 当向量的长度大于向量存放器的长度时，必需把长向量分成长度固定的段，采纳循环构造处理这个长向量，这种技术称为向量循环开采技术，也称为向量分段开采技术。三, 简答题每题5分1.什么是存储系统？答：存储系统是两个或两个以上的速度, 容量, 价格不同的存储器采纳硬件，软件或软, 硬件结合的方法联结成一个系统，使得整个系统看起来象一个存储器，其速度接近其中最快的一个，容量接近其中最大的一个，价格接近其中最廉价的一个。 2.简述全相联映象规那么。答：1主存及缓存分成一样大小的数据块。2主存的某一数据块可以装入缓存的随意一块空间中。3.简述干脆相联映象规那么。答：1主存及缓存分成一样大小的数据块。2主存容量应是缓存容量的整数倍，将主存空间按缓存的容量分成区，主存中每一区的块数及缓存的总块数相等。 3主存中某区的一块存入缓存时只能存入缓存中块号一样的位置。4.引起Cache及主存内容不一样的缘由是什么？为了保持Cache的一样性，在单计算机系统中一般实行哪些措施？答：不一样的缘由：(1) 由于CPU写Cache，没有马上写主存(2) 由于I/O处理机或I/O设备写主存实行措施：1全写法，亦称写直达法(WT法Write through)方法：在对Cache进展写操作的同时，也对主存该内容进展写入。2写回法WB法Write back方法：在CPU执行写操作时,只写入Cache,不写入主存。5影响虚拟存储器命中率的因素有哪些？它们是如何影响的？答：1页面大小：当页面比拟小时，随着页面的增大，命中率明显提高，但当页面增大到肯定值时，命中率不再增大，而随着页面的增大而下降。2主存容量：当主存容量增加时，命中率不断提高；当容量增大到肯定程度后，命中率的提高就不大了。3页面调度方式：页面的调度都是发生在产生缺页中断时进展，因此在程序刚开场运行时命中率很低，为此可以采纳预取式调度法，提高命中率。6.模拟及仿真的主要区分和适合场合是什么？答：模拟是指用软件的方法在一台计算机上，实现另一台计算机的指令系统，被模拟的机器是不存在的，称为虚拟机，执行模拟程序的机器称宿主机。由于模拟采纳纯软件说明执行方法，因此运行速度较慢，实时性差。因此只适合于移植运行时间短，运用次数少，而且在时间上没有约束和限制的软件。仿真是指用微程序的方法在一台计算机上实现另一台计算机的指令系统。执行微程序的机器为宿主机，被实现的为目标机。仿真的运行速度比模拟快，但仿真计算机的系统构造，因此对于系统构造差异较大的机器难于用仿真的方法实现软件移植。7.什么是程序干脆定位方式？什么是程序静态定位方式？答：(1)干脆定位方式 程序员在编写程序时或编译程序对源程序进展编译时，就已经准确知道该程序应占用的主存物理空间。因此可以干脆运用实际主存物理地址来编写或编译程序。目前大多不用这种方式。 (2)静态定位方式 特地用装入程序来完成并要求程序本身可以重定位。在程序装入主存的过程中，把那些带有标识的指令或数据中的逻辑地址全部变成主存的物理地址，集中一次完成地址变换，一旦装入主存就不能再变动了。8.什么是程序动态定位方式？答：动态定位方式是利用类似变址寻址方法，有硬件支持完成。程序装入主存时，指令或数据地址不作修改，只把主存的起始地址装入该程序对应的基址存放器中。在程序运行时，利用地址加法器，指令中的逻辑地址及已经存放在基址存放器中的程序起始地址相加，就形成了主存的物理地址。指令的地址码不需全部修改。9什么是指令的重叠说明方式？重叠说明方式有哪三种？答：所谓重叠说明方式，即是在两条相邻指令的说明过程中，某些不同说明阶段在时间上存在重叠局部。重叠说明方式分三种：一次重叠, 先行限制技术和多操作部件并行。10.什么是数据相关，数据相关冲突可分为哪三种类型？答：数据相关是在几条相近的指令间共用一样的操作数时发生的。例如，指令部件中的某一条指令在进展操作数地址计算时要用到一个通用存放器的内容，而这个通用存放器的内容又要由这条指令前的另一条指令产生，但前面那条指令还未进入执行部件，还未产生通用存放器的内容，这时指令部件中的那条指令只能停下来等待。数据相关冲突可分为RAW, WAR和WAW三种类型。 11.如有一个经说明实现的计算机，可以按功能划分成4级。每一级为了执行一条指令须要下一级的N条指令说明。假设执行第一级的一条指令需K(ns)时间，那么执行第2, 3, 4级的一条指令各须要用多少时间(ns)解： 第二级的一条指令需第1级的N条指令说明 第二级的一条指令执行时间为NKns； 第三级的一条指令执行时间为N2Kns； 第四级的一条指令执行时间为N3Kns。12.假设将某系统的某一部件的处理速度加快到10倍，但该部件的原处理时间仅为整个运行时间的40%，那么采纳加快措施后能使整个系统的性能提高多少？解：由题意可知 fe=0.4, re=10, 依据Amdahl定律13.假设某机要求有：三地址指令4条，单地址指令192条，零地址指令16条。设指令字长为12位，每个地址码长3位。问能否以扩展操作码为其编码？14.简述冯。诺依曼计算机的特征。答：一般认为其主要特征有以下几点：(1)机器以运算器为中心。除了完成运算以外，机器内部的数据传输都经过运算器。各部件的操作以及它们之间的协调由限制器集中限制。(2)存储器按一维线性编址，依次访问存储器地址单元，每个存储单元的位数固定。 (3)程序存储，指令和数据无区分存放在存储器中，指令和数据一样可以送到运算器中进展运算，指令及数据的区分主要在于地址区域不同。(4)指令在存储器中按其执行依次存放，由一个依次限制器亦称程序计数器或指令计数器指定即将被执行的指令地址。每读取一条指令后，计数器自动按依次递增。 (5)指令由操作码和地址码组成，操作码指明操作类型，地址码指明操作数的地址和结果地址。(6)数据以二进制表示。15.试述页式管理虚拟存储器的工作过程。答：页式管理是将主存空间及虚存空间按固定的大小划分成块，每块称为一页。页的大小和划分及程序的逻辑功能无关，由操作系统软件来执行。一般而言，一页的大小应当是512Bit的整数倍，因为协助磁盘存储的物理块的大小为512Bit。虚页中的页称为虚页，实存中的各页称为实页，各虚页及实页之间按全相联方式映象，也就是虚页中的一页，可以存入主存中的随意一页的位置。当CPU给出所要访问的虚地址后，依据用户号访问基址存放器，求得用户的页表首地址Pa，然后及虚地址中的虚页号P相加，得到该页的表目，由此表目中得到该页存入主存中的实页号为p，将该页号读出及页内地址组装即可得到主存的实际地址。 16.简述计算机系统构造用软件实现和用硬件实现各自的优缺点。答：硬件实现:速度快, 本钱高；敏捷性差, 占用内存少。 软件实现:速度低, 复制费用低;敏捷性好, 占用内存多。17.简述字节多路, 数组多路和选择通道的数据传送方式。答：1字节多路通道：用于连接多台慢速外设，一般采纳字节穿插传送数据的方式，即连接在通道上的各个设备轮番占用一个很短的时间片通常小于100微秒传输一个字节。 2选择通道：是指每一个通道连接一台高速外设，也可以连接多台一样的高速外设，但通道只能对各台外设串行效劳。当某一设备工作时，那么通道及该设备相连，始终到整个数组传送完后，才可能转向为其他设备效劳。3数组多路通道：数组多路通道是字节多路通道及选择通道工作方式的综合，是在数组传送的根底上，再分时为多个高速外设效劳。它每次选择一个高速设备后传送一个数据块，并轮番为多台外围设备效劳。每台高速外设，如磁盘，其工作时间有寻址时间及传送时间之分。而寻址时间很长，在这段时间中并不须要通道的限制，所以是通道空闲时间，那么通道可以为其他打算好的高速外设效劳。四, 问答及计算题每题15分1. 某机主存容量为512KB，Cache的容量为32KB，每块的大小为16个字或字节。划出全相联方式主, 缓存的地址格式, 书目表格式及其容量。答：主存块数：512K/1632K215；缓存块数：32K/162K211；块内地址：1624容量：与缓冲块数量一样即2112048(或32K/162048)。 主存块号Bi 块内地址 18 4 3 0 主存地址 缓存块号Bi 块内地址 14 4 3 0 缓存地址 主存块地址 缓存块地址 有效位 26 12 11 1 0 书目表 2. 主存容量为512KB，Cache的容量为32KB，每块为64个字或字节，缓存共分128组。划出组相联方式主, 缓存的地址格式, 书目表格式及其容量。答：主存区数：512K/32K1624；缓存组数：12827； 缓存块数：32K/6451229；组内块数：512/128422； 块内地址：6426容量：与缓冲块数量一样即29512(或32K/64512)。 区号 块号 缓存块号 有效位 8 5 4 3 2 1 0 书目表 组号 缓存块号 块内地址 14 8 7 6 5 0 缓存地址 区号 组号 块号 块内地址 18 15 14 8 7 6 5 0 主存地址 3. 什么是方体置换？写出方体置换函数的表达式，假设互联网有16个结点，请画出4个方体置换函数即C0，C1，C2，C3的输入端及输出端的连接关系。答：方体置换是实现二进制地址编号中第k位位值不同的输入端输出端之间的连接。其表达式为： C0立方置换函数：10001001101010111100110111101111100010011010101111001101111011110000000100100011010001010110011100000001001000110100010101100111 C1立方置换函数：00000000000100100011010001010110011100010010001101000101011001111001101010111100110111101111100110101011110011011110111110001000C2立方置换函数：10001001101010111100110111101111100010011010101111001101111011110000000100100011010001010110011100000001001000110100010101100111C3立方置换函数：100010011010101111001101111011111000100110101011110011011110111100000001001000110100010101100111000000010010001101000101011001114. 在页式虚拟存储器中，一个程序由P1P5共5个页面组成。在程序执行过程中依次访问的页面如下：P2，P3，P2，P1，P5，P2，P4，P5，P3，P2，P5，P2 假设系统安排给这个程序的主存有3个页面，分别采纳FIFO, LFU和OPT三种页面替换算法对这3页主存进展调度。1画出主存页面调入, 替换和命中的状况表。2统计三种页面替换算法的页命中率。解：三种替换算法的替换过程：页地址流232152453252 FIFO命中3次223232*3153*1521*5*245*2432*432*4354*3*52调进调进命中调进替换替换替换命中替换命中替换替换LRU命中5次22323123*512*251*425*542*354*235*523*253*调进调进命中调进替换命中替换命中替换替换命中命中OPT命中6次22323231*23*52*354*354*354*3523*5235235调进调进命中调进替换命中替换命中命中替换命中命中5. 一个有快表和慢表的页式虚拟存储器，最多有64个用户，每个用户最多要用1024个页面，每页4K字节，主存容量8M字节。1写出多用户虚地址的格式，并标出各字段的长度。2写出主存地址的格式，并标出各字段的长度。3快表的字长为多少位？分几个字段？各字段的长度为多少位？4慢表的容量是多少个存储字？每个存储字的长度为多少位？答：用户号：6426，虚页号：1024210，页内地址：4K212，主存页数：8M/4K2111多用户虚地址： 用户号6位虚页号10位页内地址12位 共28位2主存地址： 主存实页号11位页内地址12位 共23位3快表字长27位；分3个字段：用户号6位，虚页号10位，实页号11位4慢表容量为26+10，每个存储字长为：主存页号112位。6. 一个程序由五个虚页组成，采纳LFU替换算法，在程序执行过程中依次访问的地址流如下： 4，5，3，2，5，1，3，2，3，5，1，31可能的最高页命中率是多少？2至少要安排给该程序多少个主存页面才能获得最高的命中率。3假如在程序执行过程中访问一个页面，平均要对该页面内的存储单元访问1024次，求访问存储单元的命中率。 解：1由于在页地址流中互不一样的页共有5页，因此最多安排5个主存页面就可获得最高页中命中率，可能的最高命中率为2因为LFU替换算法为堆栈型换算法，即随着安排给该程序的主存页面数的削减，其命中率单调递减，所以为获得最高命中率H7/12，可采纳逐步削减所安排的主存页数的方法来推算，假设安排n个主存页面时可获得最高命中率，但安排n1个页面时命中率却削减，那么此时我们可以得出这样的结论：至少要安排给该程序n个主存页面才能获得最高的命中率。由表可知，至少要安排给该程序4个主存页面才能获得最高的命中率。页地址流453251322513 S(1)堆 S(2)栈 S(3)内 S(4)容 S(5) S(6)4543542354523415234315242315423154523141523431524 n=1实 n=2页 n=3数 n=4 n>=5HHHHHHHHHHHHHHHHHH3访问存储单元的命中率为值得说明的是，在此例中，尽管LFU属于堆栈替换算法，但是安排的实际页数n也并不是越多越好，当命中率H到达饱和后，实际页数n的增加不仅不会提高命中率，反而会使实存的利用率下降。7. 假设一台模型计算机共有10种不同的操作码，假如采纳固定长操作码须要4位。各种操作码在程序中出现的概率如下表所示，计算采纳Huffman编码法的操作码平均长度，并计算固定长操作码和Huffman操作码的信息冗余量假设最短平均长度H3.1位。指令序号指令运用频度Pi指令序号指令运用频度PiI1I6I2I7I3I8I4I9I5I10答：构造Huffman树如下：Huffman编码如下表：指令号指令使用频度PiHuffman编码码长指令号指令使用频度PiHuffman码码长I1102I601104I20003I701114I30013I811104I40103I9111105I51103I10111115Huffman编码的平均码长为： 冗余量3.153.10/3.151.59%固定码长：log2104冗余量43.10/422.5%8一台模型机的各条指令的频度如下：ADD加：43% SHR右移：1%SUB减：13% CLL循环左移：2%JOM按页转移：6% CLA累加器清0：22%STO存：5% STP停机：1%JMP转移：7 试设计这9条指令的哈夫曼编码的操作码表示以及2-4等长扩展操作码表示，并计算这两种表示的平均操作码长度。答：构造Huffman树如下：Huffman编码如下表：指令指令使用频度PiHuffman编码码长2-4扩展码码长ADD01002CLA1003012SUB101310004JMP1100410014JOM1101410104STO1110410114CLL11110511004SHR111110611014STP111111611104Huffman编码的平均码长为：2-4编码的平均码长为： 14用一条4段浮点加法器流水线求8个浮点数的和: ZABCDEFGH,求流水线的吞吐率, 加速比和效率,其中t1=t2=t3=t4=t。输入 S1 S2 S3 S4 输出 t1 t2 t3 t4 答：可对原式作一简洁改变，得到： ZABCDEFGH7个加法8个数的流水线时空图如下：从流水线的时空图中可以很清晰地看到，7个浮点加法共用了15个时钟周期。 流水线的吞吐率为： 流水线的加速比为： 流水线的效率为： 9设有两个向量A，B，各有4个元素，假设在如下图的静态双功能流水线上，计算向量点积： 其中，1235组成加法流水线，145组成乘法流水线。又设每个流水线所经过的时间均为t，而且流水线的输出结果可以干脆返回到输入或暂存于相应的缓冲存放器中，其延迟时间和功能切换所需的时间都可以忽视不计。请运用合理的算法，能使完成向量点积A*B所用的时间最短，并求出流水线在此期间实际的吞吐率TP和效率E。解：首先，应选择适合于静态流水线工作的算法。对于此题，应先连续计算al*bl, a2*b2, a3*b3和a4*b4共4次乘法，然后功能切换，按(albl+a2b2)+(a3b3+a4b4)经3次加法来求得最终的结果。按此算法可画出流水线工作时的时空图。由图可见，总共在15个t的时间内流出7个结果，所以在这段时间里，流水线的实际吞吐率TP为7/15t。假设不用流水线，由于一次求积需3t,产生上述结果就须要4´3t+3´4t=24t。因此,加速比为S=24t/(15t)=1.6。该流水线的效率可用阴影区面积和全部5个段的总时空图面积之比求得，即