计算机系统结构复习题

1、计算机系统结构(张晨曦) 题目汇总2011-01-10 10:25:01| 分类： HYPERLINK http:/wuzhaoqi597./blog/#m=0&t=1&c=fks_084067087095088074080087082095085082081068093086082065086计算机日志 | 标签：HYPERLINK http:/wuzhaoqi597./blog/#m=0&t=3&c=计算机系统结构(张晨曦)计算机系统结构(张晨曦) |字号 华南师范大学计算机学院荣誉出品1、多处理机结构的特点是什么？多处理机实现并行的主要类型是哪种？多机系统的耦合度有哪些分类？ 书上找不到

2、答案：多处理机系统的特点: 1. 结构灵活, 程序并行性，3. 并行任务派生4. 进程同步5. 资源分配和进程调度P26：多处理机的隅合度分为紧密耦合和松散耦合两大类：紧密耦合系统又称直接耦合系统。在这种系统中，计算机之间的物理连接的带宽比较高，一般是通过总线或高速开关互连，可以共享主存。由于具有较高的信息传输率，因而可以快速地并行处理多个作业或任务。松散耦合系统又称间接耦合系统，一般是通过通道或通信线路实现计算机之间的互连，可以共享外存设备（磁盘、磁带等）。2、同构型多处理机和异构型多处理机的特点是什么？它们所采用的提交并行性的技术途径有哪些？ P:26 异构型多处理机系统由多个不同类型、至

3、少负担不同功能的处理机组成，它们按照作业要求的顺序，利用时间重叠原理，依次对它们的多个任务进行加工，各自完成规定的功能动作。同构型处理机系统由多个类型或至少负担同等功能的处理机组成，它们同时处理同一作业中能并行执行的多个任务。3、跳转与分支的定义及作用？ P:36 当指令是无条件改变控制流时，称之为跳转指令；而当指令是有条件改变控制流时，则称之为分支指令。 作用：用来改变控制流。4、指令系统编码格式有哪些？（P41图2.8）（a）变长编码格式操作码地址描述符1地址码1地址描述符n地址码n（b）固定长度编码格式操作码地址码1地址码2地址码3（c）混合型编码格式操作码地址描述符地址码 操作码地址描

4、述符1地址描述符2地址码 操作码地址描述符地址码1地址码2 5、什么是流水线的深度？该指标是否越大越好？为什么？ 流水线中的每个子过程及其功能部件称为流水线的级或段，流水线的段数称为流水线的深度。（题解P44）不是。流水线深度的增加可以让处理器时钟频率进一步提高，但带来的反面影响就是处理器的单周期执行效率降低、发热量上升，同时容易产生分支预测等问题 6、流水线的瓶颈的定义？一般来说，产生瓶颈的原因是什么？流水线中各段的时间应尽可能相等，否则讲引起流水线堵塞和断流，因为时间最长的段将成为流水线的瓶颈。（P54） 7、流水线的最大吞吐率是如何定义的？影响线性流水线最大吞吐率有哪些？答：当任务数趋向

5、无限大时，吞吐率的极限即是最大吞吐率（书上没具体定义，这是个人的理解）。流水线的最大吞吐率由时间最长的那个段决定。（P59） 8、延迟分支方法有哪几种策略？各个策略的主要思想是什么？答：向前调度、从目标处调度、从失败处调度。向前调度：它把位于分支指令之前的一条独立的指令移到延迟槽。从目标处调度：把目标处的指令拷贝到延迟槽。同时，还要修改分支指令的目标地址。从目标处调度实际上是猜测了分支是成功的。从失败处调度：当猜测错误时，要保证调度到延迟槽中的指令的执行不会影响程序的正确性。（P82） 9.什么是向量指令的一个编队？编队有什么优点？答：我们把能在同一个时钟周期内一起开始执行的几条向量指令称为一

6、个编队。（P103）同一个编队中的向量指令之间一定不存在流水功能部件的冲突、Vi冲突或数据的相关性。 10、在向量流水处理机上，向量指令序列执行的特点是什么？编队执行时间如何确定？我们把能在同一时钟周期内一起开始执行的几条向量指令称为一个编队。同一编队中的向量指令之间不存在流水功能部件的冲突、i冲突或数据的相关性。编队后，这个微量指令序列的总的执行时间为各编队的执行时间的和，即： (书本P103) 11、“主存辅存”层次的目的是什么？“cache主存”层次的目的是什么？“主存辅存”层次的目的是为了弥补主存容量的不足。（书本192）“cache主存”层次的目的是为了弥补主存速度的不足 12、在“

7、Cache主存”层次中，CPU的访存地址分为哪几部分？CPU是按块进行管理的。Cache和主存均被分割成大小相同的块。信息是以块为单位调入Cache。相应地，CPU的访存地址被分割成两部分：块地址和块内位移。 13、cache存储器采用组相联映像的基本原理是什么？答：cache存储器采用组相联映像是指组间直接映像，组内各块之间是全相联映像。 14、增加块大小的方法在降低不命中率以及提高相联度等方面的特点是什么？答：增加块大小的方法在降低不命中率的同时会增加不命中开销，而提高相联度会增加命中时间。 15、消息传递机器的原理是什么？答：在消息传递机制中，消息一般是由若干个包组成，包的长度是固定的，

8、但一条消息中所包含的包的个数可变的。包又可以进一步分成一些更小的固定长度的单位，称为片。消息寻径方式可以分为线路交换和包交换两大类。包交换又分为存储转发、虚拟直通和虫蚀3种方式。 16、从计算机系统结构来看，机器语言程序员看到机器属性是什么？属性是编程要用到的硬件组织。（习题册P10、1.3习题，选择题1.6） 17、流水处理机，多处理机，阵列处理机，机群系统能够实现并行处理吗？它们的工作原理是什么？它们都能够实现并行处理。流水处理机原理：利用流水线技术（将一个重复的时序过程，分解成为若干子过程，而每一个子过程都可有效地在其专用功能段上与其他子过程同时执行）处理计算机任务的处理机。（自己概括的

9、）多处理机原理：具有多个处理机的计算机。（百度百科）阵列处理机原理: 其核心是由多个处理单元构成的阵列，用单一的控制部件来控制多个处理单元对各自的数据进行相同的运算和操作（习题册P250）机群系统原理：有多台同构或异构的的独立计算机通过高性能网络连接在一起而构成的高性能并行计算机系统。构成机群的计算机都有自己独立的存储器、IO设备和操作系统，他们在机群操作系统的控制下协同完成特定的并行计算任务。（习题册P241） 18、信息按整数边界存储的主要优点有哪些？为了避免出现一个信息字被截断存储在两个存储字中的情况，可以要求信息宽度不超过主存宽度的信息必须存储在一个存储字内，不能跨边界。（习题册P25

10、） 19、RISC执行程序的速度比CISC要快的原因？采用寄存器窗口重叠技术对于RISC有何好处？RISC执行程序的速度比CISC要快是因为RISC指令平均执行周期数较少。好处：大大减少了程序调用引起的访存次数P32 20、线性流水线、动态流水线、静态流水线的特点是什么？线性流水线：各段串行连接，没有反馈回路，数据通过流水线各段时，每段最多只流过一次动态流水线：指同一时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能的流水线。它允许某些段正在实现某种运算时，另一些段在实现另一种运算。静态流水线：同一时间内，多功能流水线中的各段只能按同一种功能的的连接方式工作。当流水线要切换另

11、一种功能时，必须等到前面的任务都流出流水线之后，才能改变连接（P61，根据定义回答的） 21、程序的局部性原理的定义是什么？它又分哪些局部性？这些局部性各有什么特点？（P10，名词解释或填空题）程序的局部性原理是指程序执行时所访问的存储器地址不是随机分布的，而是相对地簇聚。局部性原理包括时间局部性和空间局部性。时间局部性是指：程序即将用到的信息很可能就是目前正在使用的信息。空间局部性是指：程序即将用到的信息很可能与目前正在使用的信息在空间上相邻或者邻近。 22、指令系统的完整性与正交性是如何进行定义的？习题册P34 2.4.1答:完整性:在一个有限可用的存储空间内,对于任何可解的问题,编制计算

12、机程序时,指令系统提供的指令足够使用.正交性:指在指令中各个不同含义的字段,如操作类型,数据类型,寻址方式字段等,在编码时应互不相关,相互独立. 23、排空时间指的是那段时间？习题册P60答:流水线中最后一个任务从进入流水线到流出结果所需懂得时间 24、流水线冲突是如何定义的？ 习题册P61答:指对于具体的流水线来说,由于相关的存在,使得指令流的下一条指令不能在指定的时钟周期开始执行 25、分段开采技术，循环开采技术，链接技术的定义分别是什么？答:分段开采技术（循环开采技术）当向量长度大于向量寄存器的长度时，必须把长向量分成长度固定的段，然后循环分段处理，每一次循环只处理一个向量段。 链接技术

13、当前一个向量功能部件长生第一个结果并送到结果向量寄存器的入口时，将该结果立即送往下一个功能部件的入口，开始后续的向量处理操作。 26、采用动态分支预测技术的目的是什么？在所采用的方法中，需要解决哪些关键问题？答:目的有两个：分支预测是否成功和尽快找到分支目标地址（或指令），从而避免控制相关造成流水线停顿。需要解决的两个关键问题：如何记录分支的历史信息；如何根据这些信息来预测分支的去向，甚至提前取出分支目标地址（或指令）。 27、基于硬件的前瞻执行是把哪三种思想结合在一起的？答:（1）动态分支预测。用来选择后续执行的指令。 （2）在控制相关的结果尚未出来之前，前瞻地执行后续指令。 （3）用动态调

14、度的基本快=块的各种组合进行跨基本块的调度。 28、指令多流出处理器的流出能力受哪些因素的影响？P148程序所固有的指令级并行性。硬件实现上困难。超标量和超长指令字处理器固有的技术限制。其中，第一个限制是最简单的也是最根本的因素。第二个限制，是多留出的处理器需要大量的硬件资源。（其他剩下的都是浮云，请明察） 29、什么是共享数据的迁移和复制？这么做的原因是什么？共享数据的迁移是把远程的共享数据项拷贝放在本处理器局部的Cache中使用，从而降低了对远程共享数据的访问延迟。共享数据的复制是把多个处理器需要同时读取的共享数据项的拷贝放在各自局部Cache中使用，复制不仅降低了访存的延迟，也减少了访问

15、共享数据所产生的冲突。共享数据的迁移和复制对于提高访问共享数据的性能来说是非常重要的。30、增加块大小导致Cache不命中率先下降后上升的原因是什么？ P208-209导致不命中率先下降后上升的原因，在于增加块大小会产生双重作用。(1)增强了空间局部性，减少了强制性不命中。(2)减少了Cache中块的数目，所以有可能会增加冲突不命中。在块大小比较小的情况下，上述的第一种作用超过第二种作用，从而使不命中率下降。但等到块大小较大时，第二种作用超过了第一种作用，就反而使不命中率上升了。 31、降低cache不命中率有哪几种方法？简述其基本思想？(题解：P158 题7.37 题型：问答题)答：常用的降

16、低cache不命中率的方法有下面几种： (1)、增加cache块大小，增加块大小利用了程序的空间局部性。 (2)、增加cache的容量。 (3)、提高相联度，降低冲突不命中。 (4)、伪相联cache，降低冲突不命中。当对伪相联cache进行访问时，首先是按与直接映像相同的方式进行访问。如果命中，则从相应的块中取出所访问的数据，送给CPU，访问结束。如果不命中，就将索引字段的最高位取反，然后按照新索引去寻找“伪相联组”中的对应块。如果这一块的标识匹配，则称发生了“伪命中”。否则，就访问下一级存储器。 (5)、硬件预取技术。指令和数据都可以在处理器提出访问请求前进行预取。 (6)、由编译器控制的

17、预取。硬件预取的替代方法，在编译时加入预取的指令，在数据被用到之前发出预取请求。 (7)、编译器优化。通过对软件的优化来降低不命中率。 (8)、“牺牲”cache。在cache和其下一级存储器的数据通路之间增设一个全相联的小cache，存放因冲突而被替换出去的那些块。每当发生不命中时，在访问下一级存储器之前，先检查“牺牲”cache中是否含有所需的块。如果有，就将该块与cache中某个块做交换，把所需的块从“牺牲”cache调入cache。32、简述减小Cache不命中开销的几种方法？（题解：P158 题7.38 题型：问答题）答 (1)、让读不命中优先于写。 (2)、写缓冲合并。 (3)、请

18、求字处理技术。 (4)、非阻塞cache或非锁定cache技术。 (5)、采用二级cache。33.通过编译器对程序优化来改进Cache性能的方法有哪种？简述其基本思想。（题解： P158 题7.41 题型：问答题）答 (1)、数组合并。通过提高空间局部性来减少不命中次数。有些程序同时用相同的索引来访问若干个数组的同一维，这些访问可能会相互干扰，导致冲突不命中。可以将这些相互独立的数组合并成一个复合数组，使得一个cache块中能包含全部所需元素。 (2)、内外循环交换。循环嵌套时，程序没有按数据在存储器中的顺序访问。只要简单地交换内外循环，就能使程序按数据在存储器中的存储顺序进行访问。 (3)

19、、循环融合。有些程序含有几部分独立的程序段，他们用相同的循环访问同样的数组，对相同的数据作不同的运算。通过将它们融合成一个单一循环，能使读入cache的数据被替换出去之前得到反复的使用。 (4)、分块。通过改进时间局部性来减少不命中。分块不是对数组的整行或整列进行访问，而是对子矩阵或块进行操作。34、在设计Cache时并非都采用虚拟Cache，为什么？虚拟Cache有什么作用？（“原因”：题解： P158 题7.46 ；“作用”： 课本： P220 第一段 题型：问答题）答 原因： (1)、每当进行进程切换时，由于新进程的虚拟地址（有可能与原进程的相同）所指向的物理空间与原进程的不同，故需要清

20、空cache。 (2)、操作系统和用户程序对于同一个物理地址可能采用两种以上不同形式的虚拟地址来访问。他们可能会导致同一个数据在虚拟cache中存在两个副本。 作用： 虚拟cache是指可以直接用虚拟地址进行访问的cache，其标识存储器中存放的是虚拟地址，地址检测用的也是虚拟地址。在命中时不需要地址转换，省去地址转换的时间。另外，即使不命中，地址转换和访问cache是并行进行的，其速度比物理cache快很多。35、主存地址，逻辑地址，物理地址以及有效地址有什么关系？程序员编写程序时，使用的访存地址是什么？（题解：P156 题7.2 选择题） 程序员编写程序时，使用的访存地址是逻辑地址。36、

21、单体多字存储器，多体存储器各有什么作用？单级存储器的主要矛盾是什么？（题解：P147 、 P156 题7.29）在相同的器件条件下，如果要提高主存的带宽，可以采用这两种并行存储器结构：单体多字存储器和多体交叉存储器。单体多字并行存储器实现简单，但访存效率不高，而多体交叉存储器由多个单字存储体构成，每个体都有自己的地址寄存器以及地址译码和读写驱动等电路。单级存储器的主要矛盾有（1）速度越快，每位价格就越高；（2）容量越大，每位价格就越低；（3）容量越大，速度越慢。37、超标量的定义。（题解：P100 题5.1）一种多指令流出技术。它在每个时钟周期流出多余的指令，但指令的条数不固定，依代码的具体情

22、况而定，但有个上限。38、提高向量处理机的性能有哪些方法？（题解：P74）为了提高向量处理机的性能，可采用多种方法。设置多个功能部件，使它们并行工作；采用连接技术，加快一串向量指令的执行；采用循环开采技术，加快循环的处理；采用多处理机系统，进一步提高性能。39、非线性流水线的突出特点是什么？（课本P57 题型：填空和选择）答：突出特点是：有反馈回路。40、什么是MIPS？在MIPS的指令流水线中，可能发生的冲突有哪些？（题解P56 题3.6 题型：选择题）答：（1）一种基于RISC结构的微型处理器出处：课本P47中间 题型：填空或简答题。（2）先流入的指令的写操作与后流入的指令的读操作之间的写

23、后读冲突。41、“由中间开始设计”的“中间”目前多指那些？（题解：P12 题1.31 题型：问答题）答：指多级层次结构中的软硬件交界面，即传统机器级与操作系统机器级之间。42、计算机系统结构定义是什么？（课本 P3）（题解 P14 名词解析题）答：计算机系统结构是指传统机器语言程序员所看到的计算机属性，即概念性结构与功能特性。43、操作码优化的主要目的是什么？（题解P31 选择题）答：缩短指令字长；减少程序总位数；增加指令字表示的信息。44、编码的分类有哪些？平均码长最短的编码是什么？（题解P32 选择题）（课本P38P40）答：共三种：哈夫曼编码、等长扩展码、等长操作码。平均码长最短的编码是

24、哈夫曼编码。45.面向目标程序优化的思想是什么？减少程序的执行时间，并减少程序所占用的空间，即对大量的目标程序及其执行情况进行统计分析，找出哪些使用频率高、执行时间长的指令或指令串；对于使用频率高的指令，使用硬件加快其执行，对于使用频率高的指令串，用一条新的指令来代替。46.系列机是什么？它对计算机发展的意义？系列机软件兼容的基本要求是什么？系列机指基本指令系统相同、基本体系结构相同的一系列计算机（百度）/系列机是指由同一厂家生产的具有相同的系统结构，但具有不同组成和实现的一系列不同型号的计算机（课本）。系列机能较好地解决软件开发要求系统结构相对稳定与器件、硬件技术迅速发展的矛盾。系列机的软件

25、兼容有4种：向上兼容、向下兼容、向前兼容、向后兼容。向上（下）兼容是指按某档计算机编制的程序，布甲修改就能运行于比它高（低）档的计算机。向后（前）兼容是指按某个使其投入市场的某种型号计算机编制的程序，不加修改就能运行于在它之后（前）投入市场的计算机。 47.简述在指令操作码优化中哈弗曼压缩的基本思想？当各种事件发生的概率不均等时，可对发生概率高的事件用短的位数（时间）来表示（处理），而对于发生概率较低的事件，则可用较长的位数（时间）来表示（处理），从而使总的平均位数（时间）缩短。 48.简述RICS结构的设计原则？1.指令条数少，指令功能简单。2.采用简单而又统一的指令格式，并减少寻址方式。3

26、.指令的执行在单周期内完成（采用流水线技术后）。4.采用load-store结构。5.大多数指令都采用硬连逻辑来实现。6.强调优化编译器的作用，为高级语言程序生成优化的代码。7.充分利用流水技术来提高性能。 49.什么是流水寄存器？作用是？流水线每一个段的后面都要有一个缓冲寄存器（锁存器），成为流水寄存器。P54作用：在相邻的两段间传送数据，以提供后面流水段要用到的信息。P54 50.解决流水线结构冲突的方法有？方法：一：在将要发生结构冲突的前一条指令访问存储器时，将流水线停顿一个时钟周期，推迟后面指令的执行操作。二：分别设置指令存储器和数据存储器或者只设置一个存储器但采用两个分离的Cache

27、：指令Cache，数据Cache。P75 51有哪些方法可以处理由前瞻执行指令引起的异常？四种方法：一：立即处理每一个异常。二：借助专门的检测指令判断是否需要进行异常处理。三：为每个通用增加一个标志位“poison”位。可继续异常将被立即处理，引发终止性异常时，目的寄存器R的poison位置1，否则改为清0。当之后的另一条指令访问R时，若poison位为1将触发一个终止性异常。四：将指令的执行结果保存到再定序缓冲器内，并将指令流出的顺序依次确认，但是前瞻指令的确认时机却被推迟，直至能够确定该指令都的前瞻执行是正确（或错误）的。P170-P171 52.采用链接技术时，向量指令能链接执行必须有哪

28、些条件？1.不出现功能部件冲突和其他Vi冲突2.只有在前一条指令的第一个结果元素送入结果向量寄存器的那一个时钟周期才可以进行链接。3.当一条向量指令的两个源操作数分别来自于前面紧邻的两条指令的结果时，要求这两条指令产生运算结果的时间必须相等，即要求有关功能部件的通过时间相等。4.要进行链接执行的向量指令的向量长度必须相等，否则无法进行链接。P99-P101 53、记分牌算法中，记分牌记录的信息由哪3部分构成？各部分功能是什么？ P1173部分：（1 ）指令状态表：记录正在执行的各条指令已经进入到了哪一段（2） 功能部件状态表：记录各个功能部件的状态。每个功能部件有一项，每一项由9个字段组成：B

29、usy Op Fi Fj Fk Qj Qk Rj Rk （3） 结果寄存器状态表Result：每个寄存器在该表中有一项，用于指出哪个功能不见（编号）将结果写入该寄存器。如果当前正在运行的指令都不以它为目的寄存器，则其相应项伟“no”。Result各项的初值为“no”（全0） 54、半性能向量长度的定义？P105半性能向量长度 n1/2 是指向量处理机的性能达到其最大性能R 的一半时所需的向量长度。它是评价响亮流水线的建立时间对性能影响的重要参数。（若向量长度 n=n1/2，则表示整个响亮流水处理时间中只有一半是在做有效操作，而另一半则是浪费掉了。） 55、写更新协议的主要思想P304当一个处理

30、器对某数据项进行写入时，它将该新数据广播给所有其它Cache。这些Cache用该新数据对其中的副本（如果有的话）进行更新。当然，如果知道其他Cache中都没有相应的副本，就不必进行广播和更新。这样处理能够减少实现该协议所需的带宽。P304有例子 56、写作废协议的主要思想。（课本P304）在处理器对某个数据项进行写入之前，它拥有对该数据项的唯一访问权，具体做法是在处理器P进行写入操作之前，把所有其他cache中的副本全部作废。这称为写作废协议 57、超流水的主要内容是什么？（课本P149）超流水线处理机：在一个时钟周期内能够分时流出多条指令的处理机。在流水处理机中，把一条指令的执行过程的5个流

31、水段：取指令、译码、执行、访存、写结果，进一步细分，这样使得在一个时钟周期内各流水段都在处理各自的多条指令。 58、补偿代码的定义（课本P159）有一些复杂的调度机制可以确保在调度I的情况下保持执行结果不变，但需要向基本快elsepart中增加若干指令以保证结果正确，这些新增的指令被称为补偿代码。 59、尾复制的定义及作用。答：定义：超块调度时往往也需要进行代码复制，以确保结果的正确。由于被复制的代码段总是作为退出超块后必须执行的补偿代码，故这种技术被形象地称为尾复制。（练习P126）作用：在超块调度中，除最后一个出口外，其余出口退出超块后利用尾复制技术完成余下的迭代工作。尾复制实质上通过复制

32、代码，使原超块扩展为更大的超级块，从而更好地进行指令级并行开发。反映并行程序性能的一个重要的度量。在并行计算中，它是指每次数据通信要进行的计算与通信开销的比值。（练习P230） 60、前瞻执行的主要思想是什么？答：前瞻执行并不仅仅是在数据相关或控制相关尚未消除的情况下，简单地将指令调度到与之相关的指令之前猜测执行，它还是通过一系列复杂的硬件机制完成异常处理、正确性保证等工作。(P169) 61、命中时间的定义。答：访问Cache命中所需要的时间。(P190)62、不命中开销的定义答：CPU向二级存储器发出访问请求到把这个数据调入一级存储器所需要的时间。(P190) 63、相联度的定义答：在组相

33、联中，每组所包含的块数。n=M/G（P195）(M未Cache的块数，见P193，G为Cache的组数，见P194) 64、计算/通讯比指的是什么？答：计算/通信比率是指反映并行程序性能的一个重要的度量。如果比值较高，就意味着应用程序中相对于每次数据通信要进行较多的计算。通常状况下，计算/通信比率随着处理的数据规模的增大而增大，随着处理器数目的增加而减少。（P301） 65、多cache一致性的主要思想？答：允许共享数据进入Cache，出现多个处理器的Cache中都有同一存储块的副本，当其中某个处理器对其Cache中的数据进行修改后，对某个数据项的任何操作均可得到其最新写入的值，则认为这个存储

34、系统是一致的。（P302） 66、IPC的定义？它的作用是？答：（1）定义：每个时钟周期完成的指令条数，是CPI的倒数。(2) 作用：衡量流水线最高性能的一个指标(P111) 67、全相联映像？组相联映像？它们的优点分别是什么？答：（1）全相联：Cache空间的利用率高，块冲突概率低，Cache的不命中率也低。 （2）组相联：Cache被分成若干组，每组有若干个块构成，主存中的每一块可以被放置到的Cache中唯一的一个组的任何一个位置，它是直接相联和全相联的一种折中。(P194到195) 68、LRU替换算法的主要思想。答：这种方法本来是选择近期使用次数最少的块作为被替换的怀，但由于起实现比较

35、复杂，现在实际上实现的LRU都只是选择最久没有被访问的块，一居室局部性原理的一个推论：最近刚用过的块很可能就是马上要再用到的块，因此最久没有用的块就是最佳的被替换者。（P199） 69、组相联映像、全相联映像以及直接映像三者的关系。答：（1）全相联。实现查找的机制复杂，代价高，速度慢。Cache空间的利用率高，块冲突概率低，Cache的不命中率也低。 （2）直接映像：实现查找的机制简单，代价低，速度快。Cache空间的利用率低，块冲突概率高，Cache的不命中率也高。 （3）组相联映像是直接影响和全相联影响的这中(课本P199或者 白色练习册的P) 70、监听协议的主要思想是？目录协议的主要思

36、想是？目录协议的分类？每种分类的主要内容？答：（1）监听协议的基本思想是当物理存储器中的数据块被调入Cache时，其共享状态信息与该数据块一起放在该cache中。系统中没有集中的状态表。这些cache通常连接在共享存储器的总线上。当某个cache需要访问存储器时，它会把请求防盗总线上广播出去，其他各个cache控制器通过监听总线（它们一直在监听）来判断它们是否有总线上请求的数据块，如果有，就进行相应的操作。（P304）（2）目录协议的基本思想物理存储器中数据块的共享状态被保存在一个称为目录的地方。目录协议采用了一个集中的数据结构目录来实现Cache一致性。对于存储器中的每一个可以调入Cache

37、的数据块，在目录中设置一条目录项，用于记录该块的状态以及那些cache中有副本等相关信息。这样，对于任何一个数据块，都可以快速地在唯一的一个位置（根据该存储器的地址来确定）中找到相关的信息。这使目录协议避免了广播操作。(P310)（3）目录协议分为3类：全映像目录，有限映像目录和链式目录(P316)（4）全映像目录：在这种结构中，每一个目录项都包含一个N位（N为处理机的个数）的位向量，其每一位对应一个处理机。全映像目录的处理比较简单，速度比较快，但它的存储空间的开销比较大。 有限映像目录：是对全映像目录的改进，为的是提高其可扩放性和减少目录所占用的空间。核心思想是采用位数固定的目录项目，这是通

38、过对同一数据块在所有Cache中的副本总数进行限制来实现。 链式目录：用一个目录指针链表来表示共享集合。当一个数据块的副本数增加（或减少）时，其指针链表就跟着变长（变短）。由于链表长度不受限制，因此既不限制副本的个数，又保持了可扩展性。(P316) 71、链式目录的分类？答：分为单链法和双链法。(P317)72、在各种编码中，平均码长最短的编码是什么？它的主要思想是什么？答：（1）哈夫曼编码；(2) 思想是当各种事件发生的概率不均等时，可以对发生概率最高的事件用位数最短的位数（时间）来表示（处理），而对于出现概率较低的事件，则可以用较长的位数（时间）来表示（处理），从而使总的平均位数（时间）缩

39、短.(P38) 73、结构冲突、数据冲突、控制冲突产生原因、定义，如何消除？（课本P75，题解P49P50）（求高手更新控制冲突）（1）结构冲突产生原因：功能部件不是完全流水或者资源份数不够，某种指令 因为资源冲突而不能正常执行。定义：因硬件资源满足不了指令重叠执行的要求而发生的冲突。消除方法：对功能部件进行全流水处理或重复设置足够多的资源。（2）数据冲突产生原因：当相关的指令彼此靠得足够近时，它们在流水线中的 重叠执行或者重新排序会改变指令读/写操作数的顺 序，使之不同于它们串行执行时的顺序。定义：当指令在流水线中重叠执行时，因需要用到前面指令的执行结果而发 生的冲突。消除方法： 使用定向技

40、术减少数据冲突引起的停顿。 设置流水线互锁机制检测和发现数据冲突，使流水线停顿至冲突消失。 依靠编译器解决数据冲突。（3）控制冲突产生原因：分支指令或其他指令改变PC值， 定义：流水线遇到分支指令或其他会改变PC值的指令所引起的冲突。 消除方法：冻结或者排空流水线预测分支失败预测分支成功延迟分支 74、什么是向量长度临界值？（题解P78 ，概念题）向量长度临界值是指向量流水方式的处理速度优于标量串行方式的处理速 度时所需的向量长度的最小值。 75、什么是Vi冲突？（题解P78，概念题）指多条向量指令的源向量或结果向量要使用相同的Vi。 76、超长指令字？（题解P100，概念题）一种多指令流出技

41、术。VLIW处理机在每个时钟周期流出的指令条数是固定 的，这些指令构成一条长指令或者一个指令包，在这个指令包中，指令之间 的并行性是通过指令显式地表示出来的。 77、指令的cpi是如何进行计算的？（书本111页）答： CPI是cycles per instruction的缩写，意思是每条计算机指令执行所需的时钟周期。它的计算方法是： 流水线处理机的实际CPI等于理想流水线的CPI加上各类停顿的时钟周期数 CPI流水线=CPI理想+停顿结构冲突+停顿数据冲突+停顿控制冲突 78、指令操作码的哈夫曼编码（哈夫曼树）设计方法，以及操作码的平均码长的计算。（书本38、39页）答： 哈夫曼树的设计方法是

42、：将各事件按其使用频度从大到小依次排列，每次从中选择两个频度值最小的结点，将其合并成一个新的结点，并把新结点画在所选结点的上面，然后用两条边把新结点分别与那两个结点相连，新结点的频度值是所选两个结点的频度值的和。把新结点与其他剩余未结合的结点一起，再以上面的步骤进行处理，反复进行，指导全部结点都结合完毕形成根结点为止。 平均码长的计算公式：L= 其中pi为频度，li为操作码的长度。 79、2-4-6等长扩展编码的编码方法以及计算平均码长的方法？题解P154【题7.58】设某台计算机有9条指令，各指令的使用频度分别为：I1 ：52% I2 ：14% I3：12% I4 ：7% I5：6%I6 ：

43、5% I7 ：2% I8 ：1% I9 ：1%试分别用哈夫曼编码和2-4-6等长扩展码为其操作码编码，并分别计算平均码长。解：哈夫曼树如下所示。 由哈夫曼树生成的哈夫曼编码和2-4-6扩展编码如下所示。 指令使用频度pi哈夫曼编码2-4-6编码I10.5200 0I20.141 0 00 1I30.121 1 01 0I40.071 0 1 01 1 0 0I50.061 0 1 11 1 0 1I60.051 1 1 01 1 1 0I70.021 1 1 1 01 1 1 1 0 0I80.011 1 1 1 1 01 1 1 1 0 1I90.011 1 1 1 1 11 1 1 1 1

44、 0 哈夫曼编码的平均码长为：2-4-6扩展编码的平均码长：80、在多处理机系统中，根据有无远程访问情况来计算CP2的方法，以及系统快慢的比较。没有远程访问时，CPI等于系统中指令基本CPI（这个题目一定会给出来的），有远程访问时，CPI=基本指令CPI+P X C。C为远程访问开销=t/T,t为远程访问时间，T时钟周期。P为远程访问率。比较两种情况下的系统快慢，就将两种情况下计算出来的CPI相除，说远程访问的速度是没有远程访问速度的多少倍。 81、静态指令调度方法的主要思想，以及程序中指令序列的调度方法。在静态调度的超标量处理机中，指令按序流出。所有的冲突检测都在流出时进行，由硬件检测当前流

45、出的指令之间是否存在冲突以及当前流出的指令与正在执行的指令是否有冲突。如果在当前的流出的指令序列中，某条指令存在着上述冲突，那么就只流出该指令之前的指令。指令序列的调度方法：指令调度是指要求充分开发指令之间存在的并行性，找出不相关的指令序列，让它们在流水线上重叠并行执行。指令调度不会真正消除指令的相关，而是通过重新安排指令的流出顺序，使得指令间的相关尽可能少地引起流水线空转，从而减少整个指令序列在流水线的执行时间。另外指令调度不能跨越分支指令。 82、流水线的实际吞吐率和效率的计算方法？以及流水线中“瓶颈”的确定？流水线的实际吞吐率为TP=n/(k+n-1)tK为流水线的段数，n为流水线的任务

46、数，t为短时间流水线的效率E=knt/kTkTk符号中的k是下标而已，Tk是一个完整的符号。还可以写出，E=n/(k+n-1) 流水线中“瓶颈”是指流水线的各段执行时间应该尽可能相等，否则会引起堵塞或断流现象。执行时间长的段会成为整个流水线的瓶颈，这时，流水线的各个功能部件不能充分发挥作用。 83、局部不命中率？全局不命中率？以及这二者在多Cache系统中的计算？局部不命中率对于某一级Cache来说：局部不命中率 = 该级Cache的不命中次数/到达该级Cache的访存次数全局不命中率对于某一级Cache来说：全局不命中率 = 该级Cache的不命中次数/CPU发出的访存总次数全局不命中率是一

47、个比局部不命中率更有用的衡量指标，它指出了在CPU发出的访存中，究竟有多大比例是穿过各级Cache，最终到达存储器的。（课本P214）题解P153 【题7.53】【题7.54】可作参考（注：在课本中找不到这两个名词的具体概念） 84、根据不命中率，通过提高相联度，或者提高Cache容量大小等方法来计算能够消除的最大不命中次数的方法。题解P154【题7.58】某个程序共访问存储器1 000 000次，该程序在某个系统中运行，系统中cache的不命中率为7%，其中，强制性不命中和容量不命中各占25%，冲突不命中占50%。问：（1）当允许对该cache所做的唯一改变是提高相联度时，此时期望能够消除的

48、最大不命中次数是多少？（2）当允许同时提高cache的容量大小和相联，此时期望能够消除的最大不命中次数是多少？解：（1）提高cache的相联度，可以养活冲突不命中的次数，但不会影响强制性不命中和容量不命中的次数。已知cache的不命中率为7%，程序共访问存储器1 000 000次，所以总的不命中次数为70 000，其中50%为冲突不命中的次数。因此，提高cache的相联度能够消除的最大不命中次数是：70 000 x 50% = 35 000 。（2）当同时提高cache的容量大小和相联度时，可以消除容量不命中和冲突不命中的次数。而这两种不命中占总不命中次数的75%，所以，能够消除的最大不命中次

49、数是：70 000 X 75% = 52 500 。 85、流水时空图的画法？系统运行时钟周期的计算？（P54）图中横坐标表示时间纵坐标表示空间，即流水线中的流水段。格子中的数字1代表第1个运算，2代表第2个运算，。第1个运算在时刻0进入流水线；第2个运算在时刻1进入流水线，同时第1个运算离开“求阶差”段而进入“对阶”段；第3个运算在时刻2进入流水线，同时第1个运算离开“对阶”段而进入“尾数相加”段，第2个运算离开“求阶差”段而进入“对阶”段；第4个运算在时刻3进入流水线，同时第1个运算离开“尾数相加”段而进入“规格化”段，第2个运算离开“对阶”段而进入“尾数相加”段，第3个运算离开“求阶差”

50、段而进入“对阶”段；以此类推。求阶差对阶尾数相加求阶差 入 出 t t t t 空间 通过时间 排空时间 规格化 尾数相加 对阶 求阶差 0 1 2 3 4 5 6 7 时间题解P59【题3.41】在MIPS流水线上运行如下代码序列： LOOP：LW R1,0(R2) DADDIU R1,R1,#1 SW R1,0(R2) DADDIU R2,R2,#4 DSUB R4,R3,R2 BNEZ R4,LOOP 其中，R3的初值是R2 + 396 。假设：在整个代码序列的运行过程中，所有的储存器访问都是命中的，并且在一个时钟周期中对同一个寄存器的读操作和写操作可以通过寄存器组“定向”。问：（1）在

51、没有任何其他定向（或旁路）硬件的支持下，请画出该指令序列执行的流水线时空图。假设采用排空流水线的策略处理分支指令，且所有的存储器访问都命中cache，那么执行上述循环需要多少个时钟周期？（2）假设该流水线有正常的定向路径，请画出该指令序列执行的流水线时空图。假设采用预测的策略处理分支指令，且所有的存储器访问都命中cache，那么执行上述循环需要多少个时钟周期？（3）假设该流水线有正常的定向路径和一个单周期延迟分支，请对该循环中的指令进行调试，你可以重新组织指令的顺序，也可以修改指令的操作数，但是注意不能增加指令的条数。请画出该指令序列执行的流水线时空图，并计算执行上述循环所需要的时钟周期数。解

52、：（1）寄存器读写可以定向，无其他旁路硬件支持。排空流水线。 指令 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22LW IF ID EX M WBDADDIU IF S S ID EX M WBSW IF S S ID EX M WBDADDIU IF ID EX M WBDSUB IF S S ID EX M WBBNEZ IF S S ID EX M WBLW IF S S IF ID EX M WB 第i次迭代（i=0.98）开始周期：1+（i+17）总的时钟周期数：（98 X 17）+ 18 = 1684有正常定向路径，

53、预测分支失败。 指令 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15LW IF ID EX M WBDADDIU IF ID S EX M WBSW IF S ID EX M WBDADDIU IF ID EX M WBDSUB IF ID EX M WBBNEZ IF ID EX M WBLW IF miss miss IF ID EX M WB 第i次迭代（i=0.98）开始周期：1 +（i X 10）总的时钟周期数：（98 X 10）+ 11 = 991有正常定向路径。单周期延迟分支。 LOOP：LW R1,0(R2) DADDIU R2,R2,#4 DADDIU

54、 R1,R1,#1 DSUB R4,R3,R2 BNEZ R4,LOOP SW R1,-4(R2)第i次迭代（i=0.98）开始周期：1 +（i X 6）总的时钟周期数：（98 X 6）+ 10 = 598 指令 1 2 3 4 5 6 7 8 9 10 11LW IF ID EX M WBDADDIU IF ID EX M WBSW IF ID EX M WBDADDIU IF ID EX M WBDSUB IF ID EX M WBBNEZ IF ID EX M WBLW IF ID EX M WB 86、在长流水线指令中，使用分支目标缓冲，有分支预测错误的开销，有缓冲不命中的开销，此时如

55、何计算CPI？如何与采用固定时钟周期延迟的分支处理程序进行执行速度上的比较？题解P97【题5.27】假设有一条长流水线，仅仅对条件转移指令使用分支目标缓冲。假设分支预测错误的开销为4个时钟周期，缓冲不命中的开销为3个时钟周期。假设命中率为90%，预测精度为90%，分支频率为15%，没有分支的基本CPI为1。（1）求程序执行的CPI。（2）相对于采用固定的2个时钟周期延迟的分支处理，哪种方法程序执行的速度更快？解：（1）程序执行的CPI = 没有分支的基本CPI（1）+ 分支带来的额外开销分支带来的额外开销是指在分支指令中，缓冲命中但预测错误带来的开销与缓冲没有命中带来的开销之和。分支带来的额外开销 = 15% X（90%命中 X 10%预测错误 X 4 + 10%没命中 X 3）= 0.099所以程序执行的CPI = 1 + 0.099 = 1.099采用固定的2个时钟周期延迟的分支处理CPI = 1 + 15% X 2 = 1.3由（1）（2）可知分支目标缓冲方法执行速度快。 87、向量处理机