计算机体系结构课后答案和复习

第一章计算机体系结构的基本概念1.1 名词解释：1. 层次结构计算机系统可以按语言的功能划分为多级层次结构，每一层以不同的语言为特征。 2. 翻译（基于层次结构）先把N+1级程序全部变换成N级程序之后，再去执行N级程序，在执行过程中，N+1级程序不再被访问。3. 解释每当一条N+1级指令被译码后，就直接去执行一串等效的N级指令，然后再去取下一条N+1级指令，依此重复执行。4. 体系结构程序员所看到的计算机的属性，即概念性结构与功能特性。5. 透明性在计算机技术中，对本来存在的事物或属性，从某一角度来看又好像不存在的概念称为透明性。6. 系列机在一个厂家生产的具有相同的体系结构，但具有不同的组成和实现的一系列不同型号的机器。7. 软件兼容同一个软件可以不加修改地运行于体系结构相同的各档机器上，而且它们所获得的结果一样，差别只在于运行的时间不同。8. 兼容机不同厂家生产的、具有相同体系结构的计算机。9. 计算机组成计算机体系结构的逻辑实现。10. 计算机实现计算机组成的物理实现。11. 存储程序计算机（冯诺依曼结构）采用存储程序原理，将程序和数据存放在同一存储器中。指令在存储器中按其执行顺序存储，由指令计数器指明每条指令所在的单元地址。12. 并行性在同一时刻或同一时间间隔内完成两种或两种以上性质相同或不同的工作。13. 时间重叠在并行性中引入时间因素，即多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。14. 资源重复在并行性中引入时间因素，是根据“以数量取胜”的原则，通过重复设置资源，尤其是硬件资源，大幅度提高计算机系统的性能。15. 资源共享是一种软件方法，它使多个任务按一定的时间顺序轮流使用同一套硬件设备。16. 同构型多处理机由多个同种类型、至少同等功能的处理机组成、同时处理同一作业中能并行执行的多个任务的机器。17. 异构型多处理机由多个不同类型、功能不同的处理机组成、串行完成同一作业中不同任务的机器。18. 最低耦合是耦合度最低的系统，除通过某种中间存储介质之外，各计算机之间没有物理连接、也无共享的联机硬件资源。19. 松散耦合一般是通过通道或通信线路实现计算机之间连接、共享某些外围设备（例如磁盘、磁带），机器间的相互作用是在文件或数据集一级进行。20. 紧密耦合一般是指机间物理连接的频带较高，它们往往通过总线或高速开关实现互连，可以共享主存。21. 响应时间从事件开始到结束之间的时间，也称执行时间。22. 测试程序用于测试计算机性能的程序，可分为四类：真实程序、核心程序、小测试程序、合成测试程序。23. 测试程序组件选择一个各个方面有代表性的测试程序，组成一个通用的测试程序集合。这个通用的测试程序集合称为测试程序组件。24. 大概率事件优先此原则是计算机体系结构中最重要和最常用的原则。对于大概率事件（最常见的事件），赋予它优先的处理权和资源使用权，以获得全局的最优结果。25. 系统加速比系统改进前与改进后总执行时间之比。26. Amdahl定律加快某部件执行速度所获得的系统性能加速比，受限于该部件在系统中的所占的重要性。27. 程序的局部性原理程序在执行时所访问的地址不是随机的，而是相对簇聚；这种簇聚包括指令和数据两部分。28. CPI指令时钟数（Cycles per Instruction）。1.2 假设有一个计算机系统分为四级，每一级指令都比它下一级指令在功能上强M倍，即一条r+1级指令能够完成M条r指令的工作，且一条r+1级指令需要N条r级指令解释。对于一段在第一级执行时间为K的程序，在第二、第三、第四级上的一段等效程序需要执行多少时间？解：假设在第一级上用时间K执行了该级IC条指令。对第二级而言，为了完成IC条指令的功能，第二级指令的条数为：。为了执行第二级条指令，需要执行条第一级的指令对其进行解释，所以对于第二级而言，等效程序的执行时间是：对于第三级而言，为了完成IC条指令的功能，第三级指令的条数为：。为了执行第三级条指令，需要执行条第二级的指令对其进行解释。那么对第二级而言，总的指令条数为：而第二级等效于第一级条指令，同时还需要条第一级指令进行解释，所以第三级等效程序的执行时间是：按照同样的逐层递推关系，不难求得第四级等效程序的总的执行时间为：1.2 传统存储程序计算机的主要特征是什么？存在的主要问题是什么？目前的计算机系统是如何改进的？存储程序计算机在体系结构上的主要特点：(1) 机器以运算器为中心。(2) 采用存储程序原理。程序(指令)和数据放在同一存储器中，并且没有对两者加以区分。指令和数据一样可以送到运算器进行运算，即由指令组成的程序自身是可以修改的。(3) 存储器是按地址访问的、线性编址的空间。(4) 控制流由指令流产生。(5) 指令由操作码和地址码组成。操作码指明本指令的操作类型，地址码指明操作数和操作结果的地址。(6) 数据以二进制编码表示，采用二进制运算。传统存储程序计算机体系结构存在的主要问题及其改进：（1）分布的I/O处理能力存储程序计算机以运算器为中心、所有部件的操作都由控制器集中控制，这一特点带来了慢速输入输出操作占用快速运算器的矛盾。为了克服这一缺点，人们先后提出各种输入/输出方式。（2）保护的存储器空间把指令和数据放在同一存储器中有优缺点。现在绝大多数计算机都规定：在执行过程中不准修改程序。（3）存储器组织结构的发展按地址访问的存储器具有结构简单、价格便宜、存取速度快等优点。但是在数据处理时，往往要求查找具有某种内容特点的信息。但由于访问存储器的次数较多而影响计算机系统的性能。采用了通用寄存器的概念、设置高速缓冲存储器Cache、构成了以相联存储器为核心的相联处理机。（4）并行处理技术传统的存储程序计算机解题算法是顺序型的，即使问题本身可以并行处理，由于程序的执行受程序计数器控制，故只能是串行、顺序地执行。如何挖掘传统机器中的并行性？改进CPU的组成在体系结构上使本来可以并行计算的题目能并行计算多机并行处理系统（5）指令集的发展 计算机系统指令的种类愈来愈多，这种计算机称为复杂指令集计算机CISC。日趋庞杂的指令集不但不容易实现，而且还可能降低计算机系统的性能。把指令集设计成只包含那些使用频率高的少量指令，并提供一些必要的指令以支持操作系统和高级语言。按照这个原则而构成的计算机称为精简指令集计算机RISC。1.4 对于一台400MHz计算机执行标准测试程序，程序中指令类型，执行数量和平均时钟周期数如下：指令类型指令执行数量平均时钟周期数整数450001数据传送750002浮点80004分支15002求该计算机的有效CPI、MIPS和程序执行时间。解： 程序执行时间=（）400=575s1.5 计算机系统有三个部件可以改进，这三个部件的加速比如下： 部件加速比130； 部件加速比220； 部件加速比310；(1) 如果部件1和部件2的可改进比例为30，那么当部件3的可改进比例为多少时，系统的加速比才可以达到10？(2) 如果三个部件的可改进比例为30、30和20，三个部件同时改进，那么系统中不可加速部分的执行时间在总执行时间中占的比例是多少？解：在多个部件可改进情况下Amdahl定理的扩展: 式中，fi为可加速部件i在未优化系统中所占的比例；Si是部件i的加速比。第二章 计算机指令集结构设计2.1 名词解释1. 堆栈型机器CPU中存储操作数的单元是堆栈的机器。2. 累加型机器CPU中存储操作数的单元是累加器的机器。3. 通用寄存器型机器CPU中存储操作数的单元是通用寄存器的机器。4. CISC复杂指令集计算机。5. RISC精简指令集计算机。2.2 堆栈型机器、累加器型机器和通用寄存器型机器各有什么优缺点？ 指令集结构类型优点缺点堆栈型 是一种表示计算的简单模型；指令短小。 堆栈不能被随机访问，从而很难生成有效代码。同时，由于堆栈是瓶颈，所以很难被高效地实现。累加器型 减小了机器的内部状态；指令短小。 由于累加器是唯一的暂存器，这种机器的存储器通信开销最大。寄存器型 是代码生成最一般的模型。 所有操作数均需命名，且显式表示，因而指令比较长。2.3 常见的三种通用寄存器型机器的优缺点各有哪些？指令集结构类型优 点缺 点寄存器寄存器型（0,3） 简单，指令字长固定，是一种简单的代码生成模型，各种指令的执行时钟周期数相近。 和指令中含有对存储器操作数访问的结构相比，指令条数多，因而其目标代码较大。寄存器存储器型（1,2） 可以直接对存储器操作数进行访问，容易对指令进行编码，且其目标代码较小。 指令中的操作数类型不同。在一条指令中同时对一个寄存器操作数和存储器操作数进行编码，将限制指令所能够表示的寄存器个数。由于指令的操作数可以存储在不同类型的存储器单元，所以每条指令的执行时钟周期数也不尽相同。存储器存储器型（3,3） 是一种最紧密的编码方式，无需“浪费”寄存器保存变量。 指令字长多种多样。每条指令的执行时钟周期数也大不一样，对存储器的频繁访问将导致存储器访问瓶颈问题。2.4 指令集结构设计所涉及的内容有哪些？(1) 指令集功能设计：主要有RISC和CISC两种技术发展方向；(2) 寻址方式的设计：设置寻址方式可以通过对基准程序进行测试统计，察看各种寻址方式的使用频度，根据适用频度设置相应必要的寻址方式；(3) 操作数表示和操作数类型：主要的操作数类型和操作数表示的选择有，浮点数据类型（可以采用IEEE 754标准）、整型数据类型（8位、16位、32位的表示方法）、字符型（8位）、十进制数据类型（压缩十进制和非压缩十进制数据表示）等等。(4) 寻址方式的表示：可以将寻址方式编码与操作码中，也可将寻址方式作为一个单独的域来表示。(5) 指令集格式的设计：有固定长度编码方式、可变长编码方式和混合编码方式三种选择。2.5 简述CISC计算机结构指令集功能设计的主要目标。从当前的计算机技术观点来看，CISC 结构有什么缺点？CISC结构追求的目标是强化指令功能，减少程序的指令条数，以达到提高性能的目的。从目前的计算机技术观点来看，CISC结构存在以下几个缺点：(1) 在CISC结构的指令系统中，各种指令的使用频率相差悬殊。(2) CISC结构的指令系统的复杂性带来了计算机体系结构的复杂性，这不仅增加了研制时间和成本，而且还容易造成设计错误。(3) CISC结构的指令系统的复杂性给VLSI设计带来了很大负担，不利于单片集成。(4) CISC结构的指令系统中，许多复杂指令需要很复杂的操作，因而运行速度慢。(5) 在结构的指令系统中，由于各条指令的功能不均衡性，不利于采用先进的计算机体系结构技术（如流水技术）来提高系统的性能。2.6 简述RISC结构的设计原则。(1) 选取使用频率最高的指令，并补充一些最有用的指令；(2) 每条指令的功能应尽可能简单，并在一个机器周期内完成；(3) 所有指令长度均相同；(4) 只有Load和Store操作指令才访问存储器，其它指令操作均在寄存器之间进行(5) 以简单有效的方式支持高级语言。2.7 简述操作数的类型及其相应的表示方法。操作数的类型主要有：整数（定点）、浮点、十进制、字符、字符串、向量、堆栈等。操作数类型有两种表示方法：（1）操作数的类型由操作码的编码指定，这也是最常见的一种方法；（2）数据可以附上由硬件解释的标记，由这些标记指定操作数的类型，从而选择适当的运算。2.8 表示寻址方式的主要方法有哪些？简述这些方法的优缺点。 表示寻址方式有两种常用的方法：（1） 将寻址方式编于操作码中，由操作码在描述指令的同时也描述了相应的寻址方式。这种方式译码快，但操作码和寻址方式的结合不仅增加了指令的条数，导致了指令的多样性，而且增加了CPU对指令译码的难度。（2） 为每个操作数设置一个地址描述符，由该地址描述符表示相应操作数的寻址方式。 这种方式译码较慢，但操作码和寻址独立，易于指令扩展。2.9 通常有哪几种指令格式？简述其适用范围。（1） 变长编码格式。如果体系结构设计者感兴趣的是程序的目标代码大小，而不是性能，就可以采用变长编码格式。（2） 固定长度编码格式。如果感兴趣的是性能，而不是程序的目标代码大小，则可以选择固定长度编码格式。（3） 混合型编码格式。需要兼顾降低目标代码长度和降低译码复杂度时，可以采用混合型编码格式。2.10为了对编译器设计提供支持，在进行指令集设计时，应考虑哪些问题？(1) 规整性。(2) 提供基本指令，而非解决方案。(3) “简化方案的折中取舍标准”。(4) “对于在编译时已经知道的量，提供将其变为常数的指令”。2.11 试就指令格式、寻址方式和每条指令的周期数（CPI）等方面比较RISC和CISC处理机的指令系统结构。比较内容CISCRISC指令格式变长编码定长编码寻址方式各种都有只有load/store指令可以访存CPI远远大于1为12.12 现有如下C语言源代码：for (I=0;i=100,i+)Ai=Bi+C;其中，A和B是两个32位整数的数组，C和i均是32位整数。假设所有数据的值及其地址均保存在存储器中，A和B的起始地址分别是0和5000。C和i的地址分别是 1500和2000。在循环的两次迭代之间不将任何数据保存在寄存器中。（1） 请写出该C语言源程序的DLX实现代码。（2） 该程序段共执行了多少条指令。（3） 程序对存储器中的数据访问了多少次？（4） DLX代码的大小是多少？解：（1）ADDIR1,R0,#1; 初始化iSW2000（R0）,R1; 存储iloop:LWR1,2000(R0); 得到i的值MULTR2,R1,#4; R2 = B的字偏移ADDIR3,R2,#5000; 对R2加上基址LWR4,0(R3); LD Bi的值LWR5,1500(R0); LD C的值ADDR6,R4,R5; Bi + CLWR1,2000(R0); 得到i的值MULTR2,R1,#4; R2 = A的字偏移ADDIR7,R2,#0; 对R2加上基址SW0(R7),R6;Ai Bi + CLWR1,2000(R0); 得到i的值ADDIR1,R1,#1; 增加iSW2000(R0),R1;存储iLWR1,2000(,R0);得到i的值ADDIR8,R1,#-101;计数器是否为101BNEZR8,loop;不是101，重复（2）总共执行的指令数是设置（setup）指令数加上循环中重复的指令条数：执行的指令 = 2+（16101）=1618为了计算数据访问的次数，可以用循环次数乘以每次循环数据访问次数再加上设置代码的次数：（3）数据访问次数 = 1+(810)101= 809代码大小就是程序中汇编指令数乘以4（DLX中每条指令占4字节）：（4）代码大小 = 418 = 722.13 参考2.12题，现在假设将i的值和数组变量的地址在程序运行过程中，只要有可能就一直保存在寄存器中。（1） 请写出该C语言源程序的DLX实现代码。（2） 该程序断共执行了多少条指令。（3） 程序对存储器中的数据访问了多少次？（4） DLX代码的大小是多少？解：本题对上题再次讨论，只不过是在对机器代码进行基本的优化后。特别的，寄存器中的值可以重用，并且循环变量的代码应该提到循环之外。注意到循环下标变量i的值仅在最后一次循环中存储，而且和以前一样，变量的地址小于16位，可以用立即数指令load地址。对C代码进行优化后的一个可能DLX代码如下：ADDIR1,R0,#1; 初始化iADDIR3,R0,#0; A的基址ADDIR4,R0,#5000; B的基址LWR5,1500（R0）; LD C的值loop:MULTR2,R1,#4; 计算字偏移ADDR6,R2,R4; 计算Bi地址LWR7,0(R6); LD Bi的值ADDR8,R7,R5; Bi + CADDR9，R2，R3; 计算Ai的地址SW0(R9),R8;Ai - Bi + CADDIR1,R1,#1; 增加iADDIR10,R1,#-101;计数器是否为101BNEZR10,loop;不是101，重复out_of_loop:SW2000(R0),R1; 存储最后的i值（2）总共执行的指令数是设置指令（setup）加上循环次数和循环指令数的乘积再加上清除指令数（cleanup）：执行指令数 = 4 +（9101）+1 = 914（3）计算数据访问的次数可以用每次循环数据访问次数乘以循环次数再加上设置代码中的数据访问：数据访问次数 = 1 + (2101) +1 = 204（4）代码大小是程序中汇编指令数乘以4（DLX中每条指令占4字节）：代码大小 = (414) = 562.14 读写存储器的频率、访问指令和沪剧的频率是设计存储器系统的重要依据之一。参考表2.16中的整型平均指标，求：（1） 所有对数据的存储器访问所占的百分比；（2） 所有数据访问中读操作所占的百分比；（3） 所有存储器访问中读操作所占的百分比。解：（1） 所有对数据的存储器访问所占的比例为：26%;（2） 所有数据访问中读操作所占的比例为：74%;（3） 所有存储器访问中读操作所占的比例为：93%。2.15 对表2.16中的所有类型指令，通过测量其CPI，得到如下结果：指令时钟周期所有的ALU指令1Load/Store指令1.4成功的条件分支指令2.0失败的条件分支指令1.5跳转指令1.2假设60的条件分支指令转移成功，同时将上题表中其它一些类别的指令（没有被包含在上述类别中的指令）看作是ALU指令，请根据gcc和espresso基准程序计算上述各种类型指令出现的平均频率，以及这两个基准程序的有效（等效）CPI。解：上述指令所占的百分比如下表所示：指令时钟周期百分比所有ALU152%Load/Store指令1.431.6%成功的条件分支指令2.09.8%失败的条件分支指令1.55.2%跳转指令1.22.7%其等效CPI为：152%1.431.6%2.09.8%1.55.2%1.22.7% 1.23三章 流水线技术3.1名词解释1. 流水线将一个重复的时序过程，分解为若干个子过程，而每一个子过程都可有效地在其专用功能段上与其他子过程同时执行。2. 单功能流水线只能完成一种固定功能的流水线。3. 多功能流水线流水线的各段可以进行不同的连接，从而使流水线在不同的时间，或者在同一时间完成不同的功能。4. 静态流水线同一时间内，流水线的各段只能按同一种功能的连接方式工作。5. 动态流水线同一时间内，当某些段正在实现某种运算时，另一些段却在实现另一种运算。6. 部件级流水线（运算操作流水线）把处理机的算术逻辑部件分段，以便为各种数据类型进行流水操作。7. 处理机级流水线（指令流水线）把解释指令的过程按照流水方式处理。8. 处理机间流水线（宏流水线）由两个以上的处理机串行地对同一数据流进行处理，每一个处理机完成一项任务。9. 线性流水线指流水线的各段串行连接，没有反馈回路。10. 非线性流水线指流水线中除有串行连接的通路外，还有反馈回路。11. 标量流水处理机处理机不具有向量数据表示，仅对标量数据进行流水处理。12. 向量流水处理机处理机具有向量数据表示，并通过向量指令对向量的各元素进行处理。13. 结构相关某些指令组合在流水线中重叠执行时，发生资源冲突，则称该流水线有结构相关。14. 数据相关当指令在流水线中重叠执行时，流水线有可能改变指令读/写操作的顺序，使得读/写操作顺序不同于它们非流水实现时的顺序，将导致数据相关。15. 定向将计算结果从其产生的地方直接送到其他指令需要它的地方，或所有需要它的功能单元，避免暂停。16. RAW两条指令i，j，i在j前进入流水线，j执行要用到i的结果，但当其在流水线中重叠执行时，j可能在i写入其结果之前就先行对保存该结果的寄存器进行读操作，得到错误值。17. WAW两条指令i，j，i在j前进入流水线，j、i的操作数一样，在流水线中重叠执行时，j可能在i写入其结果之前就先行对保存该结果的寄存器进行写操作，导致写错误。18. WAR两条指令i，j，i在j前进入流水线，j可能在i读某个寄存器之前对该寄存器进行写操作，导致i读出数据错误。3.2 简述流水线技术的特点。（1） 流水过程由多个相联系的子过程组成，每个过程称为流水线的“级”或“段” ；（2） 每个子过程由专用的功能段实现；（3） 各个功能段所需时间应尽量相等，否则，时间长的功能段将成为流水线的瓶颈，会造成流水线的“堵塞”和“断流”；（4） 流水线需要有“通过时间”(第一个任务流出结果所需的时间)，在此之后流水过程才进入稳定工作状态，每一个时钟周期(拍)流出一个结果；（5） 流水技术适合于大量重复的时序过程，只有在输入端能连续地提供任务，流水线的效率才能充分发挥。3.3 请画出DLX基本流水线，并简述其工作原理。工作原理：把一条DLX指令在5个周期内实现，将每一个时钟周期看作是流水线的一个时钟周期，硬件每个时钟周期启动一条新的指令，并执行5条不同指令中的某一部分。每条指令虽仍需5个时钟周期完成，但提高了吞吐率，实现了流水。指令/时钟123456789IIFIDEXMEMWBI+1IFIDEXMEMWBI+2IFIDEXMEMWBI+3IFIDEXMEMWBI+4IFIDEXMEMWB3.5 解决流水线结构相关的方法有哪些？（1） 流水化功能单元（2） 资源重复（3） 暂停流水线3.6 降低流水线分支损失的方法有哪些？（1）在流水线中尽早判断出分支转移是否成功；（2）尽早计算出分支转移成功时的PC值（即分支的目标地址）l “冻结”或“排空”流水线的方法l 预测分支失败l 预测分支成功l 延迟分支3.7 请对延迟分支办法中的三种调度策略进行评价。1从前调动：分支必须不依赖于被调度的指令，总是可以有效提高流水线性能。2从目标处调度：若分支转移失败，必须保证被调度的指令对程序的执行没有影响，可能需要复制被调度指令。分支转移成功时，可提高流水线性能。但由于复制指令，可能加大程序空间。3从失败处调度：若分支转移成功，必须保证被调度的指令对程序的执行无影响。分支转移失败时，可提高流水线性能。3.8 简述三种向量处理方法，它们对向量处理机的结构要求有什么不同？1水平处理方式：若向量长度为N，则水平处理方式相当于执行N次循环。若使用流水线，在每次循环中可能出现数据相关和功能转换，不适合对向量进行流水处理。2垂直处理方式：将整个向量按相同的运算处理完毕之后，再去执行其他运算。适合对向量进行流水处理，向量运算指令的源/目向量都放在存储器内，使得流水线运算部件的输入、输出端直接与存储器相联，构成M-M型的运算流水线。3分组处理方式：把长度为N的向量分为若干组，每组长度为n，组内按纵向方式处理，依次处理各组，组数为，适合流水处理。可设长度为n的向量寄存器，使每组向量运算的源/目向量都在向量寄存器中，流水线的运算部件输入、输出端与向量寄存器相联，构成R-R型运算流水线。3.9 有一条流水线如下所示。（1） 求连续输入10条指令，该流水线的实际吞吐率和效率；（2） 该流水线的瓶颈在哪一段？请采取三种不同的措施消除此“瓶颈”。对于你所给出的新流水线，计算连续输入10条指令时，其实际吞吐率和效率。解：（1）（2）瓶颈在3、4段。l 变成八级流水线（细分）l 变成两级流水线（合并）l 重复设置部件123-13-24-14-24-34-43.10 一个流水线由四段组成，其中每当流经第三段时，总要在该段循环一次才能流到第四段。如果每段经过一次的时间都是t，问：（1） 当在流水线的输入端每t时间输入任务时，该流水线会发生什么情况？（2） 此流水线的实际吞吐率为多少？如果每2t输入一个任务，连续处理10个任务的实际吞吐率和效率是多少？（3） 当每段时间不变时，如何提高该流水线的吞吐率？仍连续处理10个任务 时，其吞吐率提高多少？解：（1）会发生流水线阻塞情况。（2）（3）重复设置部件吞吐率提高倍数1.643.11 如果流水线有m段，各段的处理时间分别是ti（i=1，2，m），现在有n个任务需要完成，且每个任务均需流水线各段实现，请计算：（1） 流水线完成这n个任务所需要的时间；（2） 和非流水线实现相比，这n个任务流水实现的加速比是多少？加速比的峰值是多少？解：（1）（2）3.12 在改进的DLX流水线上运行如下代码序列：LOOP:LWR1, 0(R2)ADDIR1, R1, #1SW0(R2), R1ADDIR2, R2, #4SUBR4, R3, R2BNZR4, LOOP其中，R3的初始值是R2396。假设：在整个代码序列的运行过程中，所有的存储器访问都是命中的，并且在一个时钟周期中对同一个寄存器的读操作和写操作可以通过寄存器“定向”。问：（1） 在没有任何其它定向（或旁路）硬件的支持下，请画出该指令序列执行的流水线时空图。假设采用排空流水线的策略处理分支指令，且所有的存储器访问都可以命中Cache，那么执行上述循环需要多少个时钟周期？（2） 假设该DLX流水线有正常的定向路径，请画出该指令序列执行的流水线时空图。假设采用预测分支失败的策略处理分支指令，且所有的存储器访问都可以命中Cache，那么执行上述循环需要多少个时钟周期？（3） 假设该DLX流水线有正常的定向路径，请对该循环中的指令进行调度。注意可以重新组织指令的顺序，也可以修改指令的操作数，但是不能增加指令的条数。请画出该指令序列执行的流水线时空图，并计算执行上述循环需要的时钟周期数？解：（1） 寄存器读写可以定向，无其他旁路硬件支持。排空流水线。第i次迭代（i0.98）开始周期：1（i17）总的时钟周期数：（9817）181684（2） 有正常定向路径，预测分支失败。第i次迭代（i0.98）开始周期：1（i10）总的时钟周期数：（9810）11991（3） 有正常定向路径。单周期延迟分支。Loop: lw r1,0(r2)addi r2,r2,#4addi r1,r1,#1sub r4,r3,r2bnz r4,loopsw r1,-4(r2)第i次迭代（i 0.98）开始周期：1（i 6 ）总的时钟周期数：（986）105983.13 假设各种分支所占指令数地百分比如下表所示：条件分支20（其中60是成功的）跳转和调用5现有一深度为4地流水线（流水线有4段），无条件分支在第二个时钟周期结束时就被解析出来，而条件分支要到第三个时钟周期结束时才能被解析出来。第一个流水段是完全独立于指令类型的，即所有的指令都必须经过第一个流水段的处理。请问在没有任何结构相关地情况下，该流水线相对于存在上述结构相关情况下地加速比是多少？解：在不存在结构相关时，每条指令的平均执行时间是1个时钟周期，而存在上述条件相关的情况下，并假设条件分支预测成功，那么无条件分支和成功的条件分支的等待时间都是1，而不成功地条件分支等待时间是2个周期；所以加速比就等于存在相关的每条指令的平均执行时间和不存在相关的每条指令的执行时间1的比值：每条指令的平均等待时间：所以：3.14 CRAY-1机器上，按照链接方式执行下述4条向量指令（括号中给出了相应功能部件的时间），如果向量寄存器和功能部件之间数据传输需要1拍，试求此链接流水线的通过时间是多少拍？如果向量长度为64，则需要多少拍才能得到全部结果。V0存储器（从存储器中取数：7拍）V2V0V1（向量加：3拍）V2V2 A3（按(A3)左移：4拍）V5V3V4（向量逻辑乘：2拍）解：通过时间就是每条向量指令的第一个操作数执行完毕需要的时间，也就是各功能流水线由空到满的时间，具体过程如下图所示。要得到全部结果，在流水线充满之后，向量中后继操作数继续以流水方式执行，直到整组向量执行完毕。3.15 向量处理机有16个向量寄存器，其中V0V5中分别存放有向量A、B、C、D、E、F，向量长度均为8，向量各元素均为浮点数；处理部件采用两个单功能流水线，加法功能部件时间为2拍，乘法功能部件时间为3拍。采用类似CRAY-1的链接技术，先计算（AB）*C，在流水线不停留的情况下，接着计算（DE）*F。（1） 求此链接流水线的通过时间为多少拍？（设寄存器入、出各需1拍）（2） 假如每拍时间为50ns，完成这些计算并把结果存进相应寄存器，此处理部件地实际吞吐率为多少MFLOPS？解：（1）我们在这里假设AB的中间结果放在V6中，（AB）*C地最后结果放在V7中，DE地中间结果放在V8中，（DE）*F的最后结果放在V9中。具体实现参考下图：通过时间应该为前者（AB）*C）通过的时间：T通过= (1+2+1)+(1+3+1) =9（拍）（2）在做完（AB）*C之后，作（CD）*E就不需要通过时间了。第五章 存储层次5.1名词解释1 存储层次采用不同的技术实现的存储器，处在离CPU不同距离的层次上，目标是达到离CPU最近的存储器的速度，最远的存储器的容量。2 全相联映象主存中的任一块可以被放置到Cache中任意一个地方。3 直接映象主存中的每一块只能被放置到Cache中唯一的一个地方。4 组相联映象主存中的每一块可以放置到Cache中唯一的一组中任何一个地方（Cache分成若干组，每组由若干块构成）。5 替换算法由于主存中的块比Cache中的块多，所以当要从主存中调一个块到Cache中时，会出现该块所映象到的一组（或一个）Cache块已全部被占用的情况。这时，需要被迫腾出其中的某一块，以接纳新调入的块。6 LRU选择最近最少被访问的块作为被替换的块。实际实现都是选择最久没有被访问的块作为被替换的块。7 写直达法在执行写操作时，不仅把信息写入Cache中相应的块，而且也写入下一级存储器中相应的块。8 写回法只把信息写入Cache中相应块，该块只有被替换时，才被写回主存。9 按写分配法写失效时，先把所写单元所在的块调入Cache，然后再进行写入。10 不按写分配法写失效时，直接写入下一级存储器中，而不把相应的块调入Cache。11 写合并在往缓冲器写入地址和数据时，如果缓冲器中存在被修改过的块，就检查其地址，看看本次写入数据的地址是否和缓冲器内某个有效块的地址匹配。如果匹配，就将新数据与该块合并。12 命中时间访问Cache命中时所用的时间。13 失效率CPU访存时，在一级存储器中找不到所需信息的概率。14 失效开销CPU向二级存储器发出访问请求到把这个数据调入一级存储器所需的时间。15 强制性失效当第一次访问一个块时，该块不在Cache中，需要从下一级存储器中调入Cache，这就是强制性失效。16 容量失效如果程序在执行时，所需要的块不能全部调入Cache中，则当某些块被替换后又重新被访问，就会产生失效，这种失效就称作容量失效。17 冲突失效在组相联或直接映象Cache中，若太多的块映象到同一组（块）中，则会出现该组中某个块被别的块替换（即使别的组或块有空闲位置），然后又被重新访问的情况。18 2：1Cache经验规则大小为N的直接映象Cache的失效率约等于大小为N /2的两路组相联Cache的实效率。19 相联度在组相联中，每组Cache中的块数。20 Victim Cache位于Cache和存储器之间的又一级Cache，容量小，采用全相联策略。用于存放由于失效而被丢弃（替换）的那些块。每当失效发生时，在访问下一级存储器之前，先检查Victim Cache中是否含有所需块。21 伪相联Cache一种既能获得多路组相联Cache的低失效率，又能获得直接映象Cache的命中速度的相联办法。22 故障性预取在预取时，若出现虚地址故障或违反保护权限，就会发生异常。23 非故障性预取在预取时，若出现虚地址故障或违反保护权限，不发生异常。24 非阻塞CacheCache在等待预取数据返回时，还能继续提供指令和数据。25 子块放置技术把一个Cache块划分为若干小块，称为子块（sub-blocks），并为每个子块赋予一位有效值，用于说明该子块中的数据是否有效。失效时，只需从下一级存储器调入一个子块。26 尽早重启动在请求字没有到达时，CPU处于等待状态。一旦请求字到达，就立即发送给CPU，让等待的CPU尽早重启动，继续执行。27 请求字优先调 块时，首先向存储器请求CPU所要的请求字。请求字一旦到达，就立即送往CPU，让CPU继续执行，同时从存储器调入该块的其余部分。28 多级包容性一级存储器（Cache）中的数据总位于下一级存储器中。29 虚拟Cache地址使用虚地址的Cache。30 多体交叉技术具有多个存储体，各体之间按字交叉的存储技术。31 存储体冲突多个请求要访问同一个体。32 TLB一个专用高速存储器，用于存放近期经常使用的页表项，其内容是页表部分内容的一个副本。5.2 简述“Cache主存”和“主存辅存”层次的区别。 存储层次比较项目“Cache主存”层次“主存辅存”层次目 的为了弥补主存速度的不足为了弥补主存容量的不足存储管理实现全部由专用硬件实现主要由软件实现访问速度的比值（第一级比第二级）几比一几百比一典型的块（页）大小几十个字节几百到几千个字节CPU对第二级的访问方式可直接访问均通过第一级失效时CPU是否切换不切换切换到其它进程5.3 降低Cache失效率有哪几种方法？简述其基本思想。常用的降低Cache失效率的方法有下面几种：（1） 增加Cache块大小。增加块大小利用了程序的空间局部性。（2） 提高相联度，降低冲突失效。（3） Victim Cache，降低冲突失效。（4） 伪相联Cache，降低冲突失效。（5） 硬件预取技术，指令和数据都可以在处理器提出访问请求前进行预取。（6） 由编译器控制的预取，硬件预取的替代方法，在编译时加入预取的指令，在数据被用到之前发出预取请求。（7） 编译器优化，通过对软件的优化来降低失效率。5.4简述减小Cache失效的几种方法。（1） 让读失效优先于写。（2） 子块放置技术。（3） 请求字处理技术。（4） 非阻塞Cache技术。（5） 采用两级Cache、5.5通过编译器对程序优化来改进Cache性能的方法有哪几种？简述其基本思想。（1） 数组合并，通过提高空间局部性来减少失效次数。有些程序同时用相同的索引来访问若干个数组的同一维，这些访问可能会相互干扰，导致冲突失效，可以将这些相互独立的数组合并成一个复合数组，使得一个Cache块中能包含全部所需元素。（2） 内外循环交换。循环嵌套时，程序没有按数据在存储器中的循序访问。只要简单地交换内外循环，就能使程序按数据在存储器中的存储循序进行访问。（3） 循环融合。有些程序含有几部分独立的程序断，它们用相同的循环访问同样的数组，对相同的数据作不同的运算。通过将它们融合成一个单一循环，能使读入Cache的数据被替换出去之前得到反复的使用。（4） 分块。通过改进时间局部性来减少失效。分块不是对数组的整行或整列进行访问，而是对子矩阵或块进行操作。5.6 在“Cache主存”层次中，主存的更新算法有哪几种？它们各有什么特点？（1） 写直达法 易于实现，而且下一级存储器中的数据总是最新的。（2） 写回法速度块，“写”操作能以Cache存储器的速度进行。而且对于同一单元的多个写最后只需一次写回下一级存储器，有些“写”只到达Cache，不到达主存，因而所使用的存储器频带较低。5.7 组相联Cache比相同容量的之直接映象Cache的失效率低。由此是否可以得出结论：采用组相联Cache一定能带来性能上的提高？为什么？答：不一定。因为组相联命中率的提高是以增加命中时间为代价的，组相联需要增加多路选择开关。5.8 写出三级Cache的平均访问时间TA的公式。 平均访存时间 命中时间失效率失效开销只有第I层的失效时才会访问第I1设三级Cache的命中率分别为HL1、 Hl2、 HL3，失效率分别为Ml1、Ml2、ML3，第三级Cache的失效开销为PL3。 平均访问时间TA HL1Ml1Hl2Ml2(HL3ML3PL3)5.9 给定以下的假设，试计算直接映象Cache和两路组相联Cache的平均访问时间以及CPU的性能。由计算结果能得出什么结论？（1） 理想Cache情况下的CPI为2.0，时钟周期为2ns，平均每条指令访存1.2次；（2） 两者Cache容量均为64KB，块大小都是32字节；（3） 组相联Cache中的多路选择器使CPU的时钟周期增加了10；（4） 这两种Cache的失效开销都是80ns；（5） 命中时间为1个时钟周期；（6） 64KB直接映象Cache的失效率为1.4，64KB两路组相联Cache的失效率为1.0。解： 平均访问时间命中时间失效率失效开销平均访问时间1-路=2.0+1.4% *80=3.12ns平均访问时间2-路=2.0*(1+10%)+1.0% *80=3.0ns两路组相联的平均访问时间比较低CPUtime=（CPU执行+存储等待周期）*时钟周期CPU time=IC（CPI执行+总失效次数/指令总数*失效开销） *时钟周期=IC（CPI执行*时钟周期）+（每条指令的访存次数*失效率*失效开销*时钟周期）CPU time 1-way=IC(2.0*2+1.2*0.014*80)5.344ICCPU time 2-way=IC(2.2*2+1.2*0.01*80)5.36IC相对性能比：5.36/5.344=1.003直接映象cache的访问速度比两路组相联cache要快1.04倍，而两路组相联Cache的平均性能比直接映象cache要高1.003倍。因此这里选择两路组相联。5.10 假设一台计算机具有以下特性：（1） 95的访存在Cache中命中；（2） 块大小为两个字，且失效时整个块被调入；（3） CPU发出访存请求的速率为109字/秒；（4） 25的访存为写访问；（5） 存储器的最大流量为109字/秒（包括读和写）；（6） 主存每次只能读或写一个字；（7） 在任何时候，Cache中 有30的块被修改过；（8） 写失效时，Cache采用写分配法。现欲给计算机增添一台外设，为此想先知道主存的频带已经使用了多少。试对于以下两种情况计算主存频带的平均使用比例。（1） 写直达Cache；（2） 写回法Cache。解：采用按写分配（1）写直达cache访问命中，有两种情况：读命中，不访问主存；写命中，更新cache和主存，访问主存一次。访问失效，有两种情况：读失效，将主存中的块调入cache中，访问主存两次；写失效，将要写的块调入cache，访问主存两次，再将修改的数据写入cache和主存，访问主存一次，共三次。上述分析如下表所示。访问命中访问类型频率访存次数Y读95%*75%=71.3%0Y写95%*25%=23.8%1N读5%*75%=3.8%2N写5%*25%=1.3%3一次访存请求最后真正的平均访存次数=(71.3%*0)+(23.8%*1)+(3.8%*2)+(1.3%*3)0.35已用带宽=0.35109/10 9 =35.0%（2）写回法cache访问命中,有两种情况：读命中，不访问主存；写命中，不访问主存。采用写回法，只有当修改的cache块被换出时，才写入主存；访问失效,有一个块将被换出，这也有两种情况：如果被替换的块没有修改过，将主存中的块调入cache块中，访问主存两次；如果被替换的块修改过，则首先将修改的块写入主存，需要访问主存两次；然后将主存中的块调入cache块中，需要访问主存两次，共四次访问主存。访问命中块为脏频率访存次数YN95%*70%=66.5%0YY95%*30%=28.5%0NN5%*70%=3.5%2NY5%*30%=1.5%4所以：一次访存请求最后真正的平均访存次数=66.5*028.5%*0+3.5%*2+1.5%*4=0.13已用带宽0.1310 9/10 913%5.11 伪相联中，假设在直接映象位置没有发现匹配，而在另一个位置才找到数据（伪命中）时，需要1个额外的周期，而且不交换两个Cache中的数据，失效开销为50个时钟周期。试求：（1） 推导出平均访存的时间公式。（2） 利用（1）中得到的公式，对于2KBCache和128KBCache，重新计算伪相联的平均访存时间。请问哪一种伪相联更快？假设 2KB直接映象Cache的总失效率为0.098，2路相联的总失效率为0.076；128KB直接映象Cache的总失效率为0.010，2路相联的总失效率为0.007。解：不管作了何种改进，失效开销相同。不管是否交换内容，在同一“伪相联”组中的两块都是用同一个索引得到的，因此失效率相同，即：失效率伪相联失效率2路。伪相联cache的命中时间等于直接映象cache的命中时间加上伪相联查找过程中的命中时间*该命中所需的额外开销。命中时间伪相联命中时间1路伪命中率伪相联1交换或不交换内容，伪相联的命中率都是由于在第一次失效时，将地址取反，再在第二次查找带来的。因此 伪命中率伪相联命中率2路命中率1路（1失效率2路）（1失效率1路）失效率1路失效率2路。交换内容需要增加伪相联的额外开销。平均访存时间伪相联命中时间1路（失效率1路失效率2路）1失效率2路失效开销1路将题设中的数据带入计算，得到：平均访存时间2Kb=1+(0.098-0.076)*1+(0.076 *50 ) =4.822平均访存时间128Kb=1+(0.010-0.007)*1+(0.007 *50 ) =1.353显然是128KB的伪相联Cache要快一些。5.12 假设采用理想存储器系统时的基本CPI是1.5，试利用表5.5 ，分别对于下述三种Cache计算CPI：(1) 16KB直接映象统一Cache，采用写回法；(2) 16KB两路组相联统一Cache，采用写回法；(3) 32KB直接映象统一Cache，采用写回法。解： CPI=CPI 执行+存储停顿周期数/指令数存储停顿由下列原因引起：l 从主存中取指令l Lload和Store指令访问数据l 由TLB引起.对于理想TLB,TLB失效开销为0。而对于统一Cache, R指令=R数据P指令=主存延迟传输一个块需要使用的时间4032/448（拍）若为读失效，P数据主存延迟传输一个块需要使用的时间4032/448（拍）若为写失效，且块是干净的，P数据主存延迟传输一个块需要使用的时间4032/448（拍）若为写失效，且块是脏的，P数据主存延迟传输两个块需要使用的时间4064/456（拍）CPI=1.5+RP+(RP*20%)+0 指令访存全是读，而数据传输指令Load或Store指令，f数据*P数据读百分比*（f数据*P数据）写百分比*（f数据*P干净数据*其对应的百分比f数据*P脏数据*其对应的百分比）20%*（754825*（50*48+50*（4816）=50（拍）代入