福建师大网络教育学院

《计算机体系结构》期末复习题

系别 _________ 班级 _________ 姓名__________ 学号__________

一、      填空题（每空1分）

1. 从主存的角度来看，“Cache—主存”层次的目的是为了________， 而“主存—辅存”层次的目的是为了________。

2．减少流水线处理分支指令时的暂停时钟周期数有两种途径，一种是________，另一种是________。

3. 当前计算机系统中的存储系统是一个层次结构，其各层分别为：________。

4.高速缓冲存储器的地址映象方式有三种，它们分别是：________。

5.虚拟存储器的三种管理方式是________。

6.目前计算机中常用数据有________三种类型。

7.通常可能出现的流水线的相关性有________ 。

8.解决中断引起的流水线断流的方法有________。

9. 设计I/O 系统的三个标准是________、________和________。

10. 当代计算机体系结构的概念包括________、________和________ 三个方面的内容

11．执行指令x1=x2+x3；x4=x1-x5会引起________类型的数据相关，执行指令x5=x4*x3；x4=x0+x6会引起________类型的数据相关，执行指令x6=x1+x2；x6=x4*x5会引起________类型的数据相关。

12．多计算机网络中，通常出现的4种通信模式是________。

13.传统的冯•诺依曼计算机是以控制驱动方式工作，以数据驱动方式工作的典型计算机是________，以需求驱动方式工作的典型计算机是________，以模式匹配驱动方式工作的典型计算机是________。

14.多流水线的调度主要有三种方法：________。

15. 早期冯•诺依曼计算机的主要特点是________、________、________。

16.根据指令间的对同一寄存器读和写操作的先后次序关系，数据相关冲突可分为________ 三种类型。

17．多流水线的调度主要有三种方法：________。

18.计算机模型按有关控制机制分类，可将计算机分为________驱动，________驱动，________驱动，________驱动四种类型。

19.根据指令间的对同一寄存器读和写操作的先后次序关系，数据相关冲突可分为________三种类型。

20．Amdahl 定律表明系统的加速比依赖于________和________两个因素。

21. 减小容量失效方法是________

二、名词解释（每题2分）

1.计算机体系结构：

2. 存储程序计算机（冯·诺依曼结构）

3.并行性

4.程序的局部性原理:

5.MIPS：

6.高速缓冲存储器:

7.虚拟存储器:

8.快表:

9.程序定位：

10.延迟转移技术：

11.窗口重叠技术：

12.流水线技术：

13.动态流水线：

14.静态流水线：

15.线性流水线：

16.非线性流水线：

17.流水线的吞吐率：

18.超流水线计算机：

19.向量的分段开采技术：

20.基准测试程序：

21.RAW

22.WAR

23.WAW

24.失效开销

25.强制性失效

26.容量失效

27.冲突失效

28.全相联映象

29.直接映象

30.组相联映象

31.替换算法

32.相联度

33.线路交换

34. 分组交换

35.静态互连网络

36.  动态互连网络

三、简答题（每题5分）

1.什么是存储系统？

2.简述全相联映象规则。

3.简述直接相联映象规则。

4.引起Cache与主存内容不一致的原因是什么？为了保持Cache的一致性，在单计算机系统中一般采取哪些措施？

5．影响虚拟存储器命中率的因素有哪些？它们是如何影响的？

6.模拟与仿真的主要区别和适合场合是什么？

7.什么是程序直接定位方式？什么是程序静态定位方式？

8.什么是程序动态定位方式？

9．什么是指令的重叠解释方式？重叠解释方式有哪三种？

10.什么是数据相关，数据相关冲突可分为哪三种类型？

11.如有一个经解释实现的计算机，可以按功能划分成4级。每一级为了执行一条指令需要下一级的N条指令解释。若执行第一级的一条指令需K(ns)时间，那么执行第2、3、4级的一条指令各需要用多少时间(ns)?

12.假设将某系统的某一部件的处理速度加快到10倍，但该部件的原处理时间仅为整个运行时间的40%，则采用加快措施后能使整个系统的性能提高多少？

解：由题意可知 fe=0.4, re=10, 根据Amdahl定律

13.若某机要求有：三地址指令4条，单地址指令192条，零地址指令16条。设指令字长为12位，每个地址码长3位。问能否以扩展操作码为其编码？

14.计算机系统设计中经常使用的4个定量原理是什么？并说出它们的含义。

15.试述页式管理虚拟存储器的工作过程。

16.简述计算机系统结构用软件实现和用硬件实现各自的优缺点。

17.简述字节多路、数组多路和选择通道的数据传送方式。

18.在指令编码中，缩短地址码的方法很多，请列出三种缩短地址码的方法，并说明理由。

19.指令流水线的中断处理有哪 2 种方法？各有何优缺点？

20. 流水线按级别分为哪几类？从处理对象对流水线的段的使用要求来看，线性流水线与非线性流水线的区别是什么？从对段的连接控制来看，静态流水线与动态流水线的区别是什么？

21. 实现软件移植的途径有哪些？各受到什么限制？

22.试用实例说明计算机系统结构、计算机组成与计算机实现之间的相互关系。

23.简要说明提高计算机系统并行性的 3 种技术途径，并各举一例。

24. CISC 的一条指令的功能在 RISC 中要用一串指令才能实现，为什么完成

相同功能的 CISC 目标程序比 RISC 目标程序的执行时间更长？

25.区别不同指令集结构的主要因素是什么？根据这个主要因素可将指令集结构分为哪3类？

26.简述CISC指令集结构功能设计的主要目标。从当前的计算机技术观点来看，CISC指令集结构的计算机有什么缺点？

27.简述先行控制的基本思想。

28. 减少流水线分支延迟的静态方法有哪些？

29.地址映象方法有哪几种？它们各有什么优缺点？

30.简述虚拟存储器中的两级地址变换过程（要求附图说明）与地址变换的加速方法。

31.简述实地址Cache在虚拟存储器中的工作过程及其加速作用。

四、问答与计算题（每题15分）

1.  对于一台400MHz计算机执行标准测试程序，程序中指令类型，执行数量和平均时钟周期数如下：

求该计算机的有效CPI、MIPS和程序执行时间。

2.计算机系统有三个部件可以改进，这三个部件的加速比如下：

  部件加速比1＝30；部件加速比2＝20；部件加速比3＝10；

(1) 如果部件1和部件2的可改进比例为30％，那么当部件3的可改进比例为多少时，系

    统的加速比才可以达到10？

(2) 如果三个部件的可改进比例为30％、30％和20％，三个部件同时改进，那么系统中不

    可加速部分的执行时间在总执行时间中占的比例是多少？

3.假设某应用程序中有4类操作，通过改进，各操作获得不同的性能提高。具体数据如下表所示：

（1）改进后，各类操作的加速比分别是多少？

（2）各类操作单独改进后，程序获得的加速比分别是多少？

（3）4类操作均改进后，整个程序的加速比是多少？

4.某机主存容量为512KB，Cache的容量为32KB，每块的大小为16个字（或字节）。划出全相联方式主、缓存的地址格式、目录表格式及其容量。

5.主存容量为512KB，Cache的容量为32KB，每块为64个字（或字节），缓存共分128组。划出组相联方式主、缓存的地址格式、目录表格式及其容量。

6.在页式虚拟存储器中，一个程序由P1～P5共5个页面组成。在程序执行过程中依次访问的页面如下：P2，P3，P2，P1，P5，P2，P4，P5，P3，P2，P5，P2

假设系统分配给这个程序的主存有3个页面，分别采用FIFO、LFU和OPT三种页面替换算法对这3页主存进行调度。

（1）画出主存页面调入、替换和命中的情况表。

（2）统计三种页面替换算法的页命中率。

7.一个有快表和慢表的页式虚拟存储器，最多有64个用户，每个用户最多要用1024个页面，每页4K字节，主存容量8M字节。

（1）写出多用户虚地址的格式，并标出各字段的长度。

（2）写出主存地址的格式，并标出各字段的长度。

（3）快表的字长为多少位？分几个字段？各字段的长度为多少位？

（4）慢表的容量是多少个存储字？每个存储字的长度为多少位？

8.一个程序由五个虚页组成，采用LFU替换算法，在程序执行过程中依次访问的地址流如下：

4，5，3，2，5，1，3，2，3，5，1，3

（1）可能的最高页命中率是多少？

（2）至少要分配给该程序多少个主存页面才能获得最高的命中率。

（3）如果在程序执行过程中访问一个页面，平均要对该页面内的存储单元访问1024次，求访问存储单元的命中率。

9.假设一台模型计算机共有10种不同的操作码，如果采用固定长操作码需要4位。已知各种操作码在程序中出现的概率如下表所示，计算采用Huffman编码法的操作码平均长度，并计算固定长操作码和Huffman操作码的信息冗余量（假设最短平均长度H＝3.1位）。

10．一台模型机的各条指令的频度如下：

ADD（加）：43%                      SHR（右移）：1%

SUB（减）：13%                      CLL（循环左移）：2%

JOM（按页转移）：6%                 CLA（累加器清0）：22%

STO（存）：5%                       STP（停机）：1%

JMP（转移）：7％

  试设计这9条指令的哈夫曼编码的操作码表示以及2-4等长扩展操作码表示，并计算这两种表示的平均操作码长度。

11．用一条4段浮点加法器流水线求8个浮点数的和: Z＝A＋B＋C＋D＋E＋F＋G＋H,求流水线的吞吐率、加速比和效率,其中△t1=△t2=△t3=△t4=△t。

12.有一条静态多功能流水线由5段组成，加法用1、3、4、5段，乘法用1、2、5段，第3段的时间为2△t，其余各段的时间均为△t，而且流水线的输出可以直接返回输入端或

暂存于相应的流水寄存器中。现要在该流水线上计算             ，画出其时空图，并计算其吞吐率、加速比和效率。

13.动态多功能流水线由6个功能段组成，如下图：

其中，S1、S4、S5、S6组成乘法流水线，S1、S2、S3、S6组成加法流水线，各个功能段时间均为50ns，假设该流水线的输出结果可以直接返回输入端，而且设置有足够的缓冲寄存器，若以最快的方式用该流水计算：

（1）画出时空图；

（2）计算实际的吞吐率、加速比和效率。

14.假设有一条长流水线，仅仅对条件转移指令使用分支目标缓冲。假设分支预测错误的开销为4个时钟周期，缓冲不命中的开销为3个时钟周期。假设：命中率为90%，预测精度为90%，分支频率为15%，没有分支的基本CPI为1。

（1）       求程序执行的CPI。

（2）       相对于采用固定的2个时钟周期延迟的分支处理，哪种方法程序执行速度更快？

15.什么是PM2I置换？写出PM2I置换函数的表达式，假设互联网有16个结点，请画出PM2I置换当i＝2时的输入端与输出端的连接关系。

16.在一个时钟频率 f 为 40MHz 的处理机上执行一个典型测试程序，该程序有 4 种类型指令，每种类型指令在程序中出现的条数和每种指令的 CPI 如表 1.1 所示。计算这个测试程序在该处理机上运行的 CPI 和相应的 MIPS。

表 1.1  指令在程序中出现的条数和每种指令的 CPI

17. 假设高速缓存 Cache 的工作速度为主存的 5 倍，且 Cache 被访问命中的

概率为 90%，那么，采用 Cache 后能使整个存储系统获得多高的加速比？

18.某个流水线由 4 个功能部件组成，每个功能部件的执行时间都为∆t。当连续输入 10 个数据后，停顿 5∆t，又连续输入 10 个数据，如此重复。画出时空图，计算流水线的实际吞吐率、加速比和效率。

19.某虚拟存储器采用页式管理，主存容量为 4 个页面，使用 LRU 替换算法。若程序访存的虚页地址流为：0，7，0，6，7，1，6，3，0，7，2，7，1，4，0，2

（1）画出该程序使用主存实页位置的过程。

（2）计算该程序对主存的命中率和缺失率。

20. 在页式虚拟存储器中，一个程序由 0~4 共 5 个虚页组成，在程序执行过程中，访存虚页地址流为：0，1，0，4，3，0，2，3，1，3

假设分配给这个程序的主存空间有 3 个实页，分别采用 FIFO、LRU 和 OPT 替换算法进行替换调度。

（1）分别画出 3 种替换算法对主存 3 个实页位置的使用过程。

（2）分别计算 3 种替换算法的主存命中率。

福建师大网络教育学院

《计算机体系结构》期末复习题答案

系别 _________ 班级 _________ 姓名__________ 学号__________

二、      填空题（每空1分）

1. 从主存的角度来看，“Cache—主存”层次的目的是为了（    提高速度           ）， 而“主存—辅存”层次的目的是为了（     扩大容量             ）。

2．减少流水线处理分支指令时的暂停时钟周期数有两种途径，一种是（尽早判断出分支 转移是否成功），另一种是（尽早计算出分支转移的目标地址）。

3. 当前计算机系统中的存储系统是一个层次结构，其各层分别为：（通用寄存器，高速缓存，主存，辅存，脱机大容量存储器）。

4.高速缓冲存储器的地址映象方式有三种，它们分别是：（全向量方式，直接相联方式，组相联方式）。

5.虚拟存储器的三种管理方式是（段式管理，页式管理和段页式管理）。

6.目前计算机中常用数据有（用户定义数据，系统数据和指令数据）三种类型。

7.通常可能出现的流水线的相关性有（资源相关，数据相关和控制相关）。

8.解决中断引起的流水线断流的方法有（不精确断点法和精确断点法）。

9. 设计I/O 系统的三个标准是（性能）、（价格）和（容量）。

10. 当代计算机体系结构的概念包括（指令集结构）、（计算机组成）和（计算机实现） 三个方面的内容11．执行指令x1=x2+x3；x4=x1-x5会引起（RAW）类型的数据相关，执行指令x5=x4*x3；x4=x0+x6会引起（WAR）类型的数据相关，执行指令x6=x1+x2；x6=x4*x5会引起（WAW）类型的数据相关。

12．多计算机网络中，通常出现的4种通信模式是（单播模式，选播模式，广播模式和会议模式）。

13.传统的冯•诺依曼计算机是以控制驱动方式工作，以数据驱动方式工作的典型计算机是（数据流计算机），以需求驱动方式工作的典型计算机是（归约机），以模式匹配驱动方式工作的典型计算机是（人工智能计算机）。

14.多流水线的调度主要有三种方法：(顺序发射顺序完成，顺序发射乱序完成，乱序发射乱序完成)。

15. 早期冯•诺依曼计算机的主要特点是（程序存储）、（指令驱动）、（集中控制）。

16.根据指令间的对同一寄存器读和写操作的先后次序关系，数据相关冲突可分为（RAW、WAR和WAW）  三种类型。

17．多流水线的调度主要有三种方法：(顺序发射顺序完成，顺序发射乱序完成，乱序发射乱序完成)。

18.计算机模型按有关控制机制分类，可将计算机分为（控制）驱动，（数据）驱动，（需求）驱动，（模式匹配）驱动四种类型。

19.根据指令间的对同一寄存器读和写操作的先后次序关系，数据相关冲突可分为（RAW、WAR和WAW）三种类型。

20．Amdahl 定律表明系统的加速比依赖于（被加速部分在系统中所占的比例）和（对被加速部分的性能提高程度）两个因素。

21. 减小容量失效方法是增加容量

二、名词解释（每题2分）

1.计算机体系结构：

计算机系统结构就是计算机的机器语言程序员或编译程序编写者所看到的外特性，是硬件子系统的概念结构及其功能特性。

2. 存储程序计算机（冯·诺依曼结构）

    采用存储程序原理，将程序和数据存放在同一存储器中。指令在存储器中按其执行顺序存储，由指令计数器指明每条指令所在的单元地址。

4.并行性

    在同一时刻或同一时间间隔内完成两种或两种以上性质相同或不同的工作。

4.程序的局部性原理:

    程序访问局部性原理说明了计算机在程序执行过程中呈现出的一种规律，即程序往往重复使用它刚刚使用过的数据和指令。局部性分为时间上的局部性和空间上的局部性两种。所谓时间局部性是指近期被访问的代码，很可能不久又将再次被访问；空间局部性是指地址上相邻近的代码可能会被连续地访问。

5.MIPS：

它表示每秒百万条指令数。

6.高速缓冲存储器:

    高速缓冲存储器是存在于主存与CPU之间的一级存储器，由静态存储芯片（SRAM）组成，容量比较小但速度比主存高得多，接近于CPU的速度。

7.虚拟存储器:

    虚拟存储器是由主存储器和辅助存储器组成，通过必须的软件和硬件的支持，使得CPU可以访问的存储器具有近似于主存的速度和近似于辅存的容量。

8.快表:

    为了提高地址转换速度，缩短查表时间，采用一个小容量的、高速的相关存储部件，用来存放当前最经常用到的那一部分页表，采取按内容相联方式进行访问。这样，查页表的时间就相当于访问小容量的相关存储器的时间，从而大大地提高了速度，这个小容量相关存储器称为快表。

9.程序定位：

    把一个程序交给处理机运行，必须首先把这个程序的指令和数据装入到主存储器中。一般情况下，程序所分配到的主存物理空间与程序本身的逻辑地址空间是不同的，把指令和数据中的逻辑地址(相对地址)转变成主存物理地址(绝对地址)的过程称为程序定位。

10.延迟转移技术：

为了使指令流水线不断流，在转移指令之后插入一条不相关的有效的指令，而转移指令被延迟执行，这种技术称为延迟转移技术。

11.窗口重叠技术：

    为了能更简单、更直接地实现过程与过程之间的参数传递，大多数RISC机器的CPU中都设置有数量较大的寄存器组，让每个过程使用一个有限数量的寄存器窗口，并让各个过程的寄存器窗口部分重叠，这就是窗口重叠技术。

12.流水线技术：

    把一个重复的时序过程分成若干个子过程，每个子过程都可以有效地在其专用功能段上和其他子过程同时执行的一种技术，称为流水线技术。

13.动态流水线：

    动态流水线在同一时间内允许按多种不同运算的联结方式工作。

14.静态流水线：

    静态流水线在同一时间内只能按一种运算的联结方式工作。

15.线性流水线：

    线性流水线中，从输入到输出，每个功能段只允许经过一次，不存在反馈回路。

16.非线性流水线：

    非线性流水线存在反馈回路，从输入到输出过程中，某些功能段将数次通过流水线，这种流水线适合于进行线性递归的运算。

17.流水线的吞吐率：

    流水线单位时间完成的任务数。

18.超流水线计算机：

    超级流水线结构是把每一个流水线(一个周期)分成多个(例如3个)子流水线，而在每一个子流水线中取出的仍只有一条指令，但总的来看，在一个周期内取出了三条指令。即在一个时钟周期内能够分时发射多条指令的处理机。

19.向量的分段开采技术：

    当向量的长度大于向量寄存器的长度时，必须把长向量分成长度固定的段，采用循环结构处理这个长向量，这种技术称为向量循环开采技术，也称为向量分段开采技术。

20.基准测试程序：

为了能进行合理的评价，通常采用不同类型的程序进行测试，经过实践选择出的这些程序称为基准测试程序。

21.RAW

两条指令i，j，i在j前进入流水线，j执行要用到i的结果，但当其在流水线中重叠执行时，j可能在i写入其结果之前就先行对保存该结果的寄存器进行读操作，得到错误值。

22.WAR

    两条指令i，j，i在j前进入流水线，j可能在i读某个寄存器之前对该寄存器进行写操作，导致i读出数据错误。

23.WAW

   两条指令i，j，i在j前进入流水线，j、i的操作数一样，在流水线中重叠执行时，j可能在i写入其结果之前就先行对保存该结果的寄存器进行写操作，导致写错误。

24.失效开销

CPU向二级存储器发出访问请求到把这个数据调入一级存储器所需的时间。

25.强制性失效

当第一次访问一个块时，该块不在Cache中，需要从下一级存储器中调入Cache，这就是强制性失效。

27.容量失效

如果程序在执行时，所需要的块不能全部调入Cache中，则当某些块被替换后又重新被访问，就会产生失效，这种失效就称作容量失效。

27.冲突失效

   在组相联或直接映象Cache中，若太多的块映象到同一组（块）中，则会出现该组中某个块被别的块替换（即使别的组或块有空闲位置），然后又被重新访问的情况。

34.全相联映象

   主存中的任一块可以被放置到Cache中任意一个地方。

35.直接映象

   主存中的每一块只能被放置到Cache中唯一的一个地方。

36.组相联映象

   主存中的每一块可以放置到Cache中唯一的一组中任何一个地方（Cache分成若干组，每组由若干块构成）。

37.替换算法

    由于主存中的块比Cache中的块多，所以当要从主存中调一个块到Cache中时，会出现该块所映象到的一组（或一个）Cache块已全部被占用的情况。这时，需要被迫腾出其中的某一块，以接纳新调入的块。

38.相联度

在组相联中，每组Cache中的块数。

39.线路交换

   在线路交换中，源结点和目的结点之间的物理通路在整个数据传送期间一直保持连接。

35.分组交换

    把信息分割成许多组（又称为包），将它们分别送入互连网络。这些数据包可以通过不同的路径传送，到目的结点后再拼合出原来的数据，结点之间不存在固定连接的物理通路。

35.静态互连网络

   各结点之间有固定的连接通路、且在运行中不能改变的网络。

37.动态互连网络

    由交换开关构成、可按运行程序的要求动态地改变连接状态的网络。

三、简答题（每题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.计算机系统设计中经常使用的4个定量原理是什么？并说出它们的含义。

答：（1）以经常性事件为重点。在计算机系统的设计中，对经常发生的情况，赋予它优先的处理权和资源使用权，以得到更多的总体上的改进。（2）Amdahl定律。加快某部件执行速度所获得的系统性能加速比，受限于该部件在系统中所占的重要性。（3）CPU性能公式。执行一个程序所需的CPU时间 = IC ×CPI ×时钟周期时间。（4）程序的局部性原理。程序在执行时所访问地址的分布不是随机的，而是相对地簇聚。

15.试述页式管理虚拟存储器的工作过程。

答：页式管理是将主存空间与虚存空间按固定的大小划分成块，每块称为一页。页的大小和划分与程序的逻辑功能无关，由操作系统软件来执行。一般而言，一页的大小应该是512Bit的整数倍，因为辅助磁盘存储的物理块的大小为512Bit。虚页中的页称为虚页，实存中的各页称为实页，各虚页与实页之间按全相联方式映象，也就是虚页中的一页，可以存入主存中的任意一页的位置。当CPU给出所要访问的虚地址后，根据用户号访问基址寄存器，求得用户的页表首地址Pa，然后与虚地址中的虚页号P相加，得到该页的表目，由此表目中得到该页存入主存中的实页号为p，将该页号读出与页内地址组装即可得到主存的实际地址。

16.简述计算机系统结构用软件实现和用硬件实现各自的优缺点。

答：硬件实现:速度快、成本高；灵活性差、占用内存少。

  软件实现:速度低、复制费用低;灵活性好、占用内存多。

17.简述字节多路、数组多路和选择通道的数据传送方式。

答：

（1）字节多路通道：用于连接多台慢速外设，一般采用字节交叉传送数据的方式，即连接在通道上的各个设备轮流占用一个很短的时间片（通常小于100微秒）传输一个字节。

（2）选择通道：是指每一个通道连接一台高速外设，也可以连接多台相同的高速外设，但通道只能对各台外设串行服务。当某一设备工作时，则通道与该设备相连，一直到整个数组传送完后，才可能转向为其他设备服务。

（3）数组多路通道：数组多路通道是字节多路通道与选择通道工作方式的综合，是在数组传送的基础上，再分时为多个高速外设服务。它每次选择一个高速设备后传送一个数据块，并轮流为多台外围设备服务。每台高速外设，如磁盘，其工作时间有寻址时间与传送时间之分。而寻址时间很长，在这段时间中并不需要通道的控制，所以是通道空闲时间，那么通道可以为其他准备好的高速外设服务。

18.在指令编码中，缩短地址码的方法很多，请列出三种缩短地址码的方法，并说明理由。

答：缩短地址码长度的方法很多，如：

(1)用间接寻址方式缩短地址码长度。在主存储器的低端开辟出一个专门用来存储地址的区域，由于表示存储器低端部分的地址所需的地址码长度可以很短，将逻辑地址码存入这些单元，可以达到缩短地址码的目的。

(2)用变址寻址方式缩短地址码长度。由于程序局部性原理，在变址寻址方式中使用的地址偏移量可以比较短；因此，可以把比较长的基地址放在变址寄存器中，在指令的地址码中只需给出比较短的地址偏移量。

(3)用寄存器间接寻址方式缩短地址码长度。由于寄存器的数量比较少，表示一个寄存器的地址只需很少几位，而一个寄存器足可以放下一个逻辑地址。

19.指令流水线的中断处理有哪 2 种方法？各有何优缺点？

答：指令流水线的中断处理有不精确断点法和精确断点法 2 种方法。不精确断点法的

优点是实现简单，缺点是程序执行结果可能出错，且程序排错不方便。精确断点法的优点

是程序执行可靠，且有利于程序排错，缺点是需要设置大量的后援寄存器。

20. 流水线按级别分为哪几类？从处理对象对流水线的段的使用要求来看，线性流水线与非线性流水线的区别是什么？从对段的连接控制来看，静态流水线与动态流水线的区别是什么？

答：流水线按级别可分为部件级、处理机级和系统级 3 类。从处理对象对流水线的段的使用要求来看，线性流水线只允许处理对象对每一个段最多使用一次，非线性流水线允许处理对象对一个段使用多次。从对段的连接控制来看，静态流水线必须等流水线排空后才可以重新连接，动态流水线在一种功能的流水处理未全部完成之前就可重新进行另一种功能流水处理的段连接，但任何一个段只能同时在一个连接中。

21. 实现软件移植的途径有哪些？各受到什么限制？

答：软件移植的途径主要有：统一高级语言、系列机、模拟与仿真。统一高级语言只能解决高级语言软件的移植，而且，目前高级语言种类繁多，无法统一成一种高级语言，因此，只能相对地统一。系列机只能实现在结构相同或相近的机器之间的汇编语言应用软件的移植，由于系列机内各型号机器的结构变化不能太大，因此，一个系列机发展到一定程度就难以继续推出性能价格比更高的新型机。模拟用宿主机的机器指令来解释虚拟机的机器指令，当虚拟机同宿主机的机器指令语义差别大时，解释执行的速度慢。仿真用宿主机的微程序来解释目标机的机器指令，但由于微程序机器级的结构深深依赖于机器的系统结构，因此，当两种机器结构差别较大时，就很难依靠仿真来实现软件移植。

22.试用实例说明计算机系统结构、计算机组成与计算机实现之间的相互关系。

答：如在设计主存系统时，确定主存容量、编址方式、寻址范围等属于计算机系统结构。确定主存周期、逻辑上是否采用并行主存、逻辑设计等属于计算机组成。选择存储芯片类型、微组装技术、线路设计等属于计算机实现。

计算机组成是计算机系统结构的逻辑实现。计算机实现是计算机组成的物理实现。一种体系结构可以有多种组成。一种组成可以有多种实现。

23.简要说明提高计算机系统并行性的 3 种技术途径，并各举一例。

答：提高计算机系统并行性的 3 种技术途径分别是：时间交叉、资源重复和资源共享。

时间交叉使多个处理过程在时间上相互错开，交叉轮流地使用同一套硬件设备的各个

部分，提高硬件利用率，缩短执行时间，例如，指令流水线处理机。资源重复通过重复设置硬件资源来提高性能，例如，阵列处理机。资源共享利用软件方法让多个用户共享同一套资源，来提高系统资源利用率和系统性能，例如，多处理机系统、计算机网络和机群系统等。

24. CISC 的一条指令的功能在 RISC 中要用一串指令才能实现，为什么完成

相同功能的 CISC 目标程序比 RISC 目标程序的执行时间更长？

答：目标程序的执行时间主要用 CPU 时间来衡量，已知有

CPU 时间=IC×CPI×T

其中，IC 为目标程序被执行的指令条数，CPI 为指令平均周期数，T 是一个周期的时间长度。虽然相同功能的 CISC 目标程序的指令条数 IC 少于 RISC 目标程序的 IC，但是 CISC的 CPI 和 T 都大于 RISC 的 CPI 和 T，因此，CISC 目标程序比 RISC 目标程序的执行时间更长。

25.区别不同指令集结构的主要因素是什么？根据这个主要因素可将指令集结构分为哪3类？

答：区别不同指令集结构的主要因素是CPU中用来存储操作数的存储单元。据此可将指令系统结构分为堆栈结构、累加器结构和通用寄存器结构。

26.简述CISC指令集结构功能设计的主要目标。从当前的计算机技术观点来看，CISC指令集结构的计算机有什么缺点？

答：主要目标是增强指令功能，把越来越多的功能交由硬件来实现，并且指令的数量也是越来越多。

缺点： (1) CISC结构的指令集中，各种指令的使用频率相差悬殊。（2）CISC结构指令的复杂性带来了计算机体系结构的复杂性，这不仅增加了研制时间和成本，而且还容易造成设计错误。（3）CISC结构指令集的复杂性给VLSI设计增加了很大负担，不利于单片集成。（4）CISC结构的指令集中，许多复杂指令需要很复杂的操作，因而运行速度慢。 (5) 在CISC结构的指令集中，由于各条指令的功能不均衡性，不利于采用先进的计算机体系结构技术（如流水技术）来提高系统的性能。

27.简述先行控制的基本思想。

答：先行控制技术是把缓冲技术和预处理技术相结合。缓冲技术是在工作速度不固定的两个功能部件之间设置缓冲器，用以平滑它们的工作。预处理技术是指预取指令、对指令进行加工以及预取操作数等。

采用先行控制方式的处理机内部设置多个缓冲站，用于平滑主存、指令分析部件、运算器三者之间的工作。这样不仅使它们都能独立地工作，充分忙碌而不用相互等待，而且使指令分析部件和运算器分别能快速地取得指令和操作数，大幅度地提高指令的执行速度和部件的效率。这些缓冲站都按先进先出的方式工作，而且都是由一组若干个能快速访问的存储单元和相关的控制逻辑组成。

采用先行控制技术可以实现多条指令的重叠解释执行。

28. 减少流水线分支延迟的静态方法有哪些？

答：（1）预测分支失败：沿失败的分支继续处理指令，就好象什么都没发生似的。当确定分支是失败时，说明预测正确，流水线正常流动；当确定分支是成功时，流水线就把在分支指令之后取出的指令转化为空操作，并按分支目标地址重新取指令执行。

（2）预测分支成功：当流水线ID段检测到分支指令后，一旦计算出了分支目标地址，就开始从该目标地址取指令执行。

（3）延迟分支：主要思想是从逻辑上“延长”分支指令的执行时间。把延迟分支看成是由原来的分支指令和若干个延迟槽构成。不管分支是否成功，都要按顺序执行延迟槽中的指令。

3种方法的共同特点：它们对分支的处理方法在程序的执行过程中始终是不变的。它们要么总是预测分支成功，要么总是预测分支失败。

29.地址映象方法有哪几种？它们各有什么优缺点？

答：(1) 全相联映象。实现查找的机制复杂，代价高，速度慢。Cache空间的利用率较高，块冲突概率较低，因而Cache的失效率也低。（2）直接映象。实现查找的机制简单，速度快。Cache空间的利用率较低，块冲突概率较高，因而Cache的失效率也高。（3）组相联映象。组相联是直接映象和全相联的一种折衷。

30.简述虚拟存储器中的两级地址变换过程（要求附图说明）与地址变换的加速方法。

   首先是根据段号和当前进程的段表基地址（段表基地址+段号）

?从存在主存中的段表查表，获得该段的页表基地址（从段号到页表基地址的第一级变换）? 再用页号（页表基地址+页号）从页表中查出实页号，与页内地址拼装成完整的实地址（从页号到实页号的第二级变换）

地址加速：

工作过程

�首先通过TLB查表，如果TLB命中，则直接获得实页号，完成地址变换

�如果TLB未命中，则启动两级地址变换，获得实页号，并且将“段号页号-实页号”对应关系存入TLB（刷新TLBTLB）

地址变换的加速方法：压缩地址变换的级数：类似方案：虚页号-->实页号,利用程序的局部性特点，保存最近几次页面地址变换结果，构成”虚页－实页”转换表，以备重复使用，并用硬件实现快速检索，该机构称为地址转换后备缓冲TLB

31.简述实地址Cache在虚拟存储器中的工作过程及其加速作用。

访问过程：①查TLB，若命中则形成实地址，否则再进行查段表、页表形成实地址;②用实地址访问Cache，若命中则完成访问。否则启动主存进行Cache替换

实地址CacheCache支持下的两级地址变换过程：（加速作用）

用段表实地址查Cache，若命中则得到页表入口实地址，否则启动主存调段表部分内容送入Cache;用页表实地址查Cache，若命中则得到实页号，否则启动主存调段表部分内容送入Cache

实地址Cache的双重作用：①加速虚拟存贮器的访问②加速虚地址到实地址的转换

五、问答与计算题（每题15分）

1.  对于一台400MHz计算机执行标准测试程序，程序中指令类型，执行数量和平均时钟周期数如下：

求该计算机的有效CPI、MIPS和程序执行时间。

解：

        程序执行时间=（）／400=575ìs

2.计算机系统有三个部件可以改进，这三个部件的加速比如下：

  部件加速比1＝30；部件加速比2＝20；部件加速比3＝10；

(3) 如果部件1和部件2的可改进比例为30％，那么当部件3的可改进比例为多少时，系

    统的加速比才可以达到10？

(4) 如果三个部件的可改进比例为30％、30％和20％，三个部件同时改进，那么系统中不

    可加速部分的执行时间在总执行时间中占的比例是多少？

解：在多个部件可改进情况下Amdahl定理的扩展:

式中，fi为可加速部件i在未优化系统中所占的比例；Si是部件i的加速比。

3.假设某应用程序中有4类操作，通过改进，各操作获得不同的性能提高。具体数据如下表所示：

（1）改进后，各类操作的加速比分别是多少？

（2）各类操作单独改进后，程序获得的加速比分别是多少？

（3）4类操作均改进后，整个程序的加速比是多少？

解：根据Amdahl定律可得

4类操作均改进后，整个程序的加速比：

4.某机主存容量为512KB，Cache的容量为32KB，每块的大小为16个字（或字节）。划出全相联方式主、缓存的地址格式、目录表格式及其容量。

答：主存块数：512K/16＝32K＝2¹⁵；缓存块数：32K/16＝2K＝2¹¹；块内地址：16＝2⁴

5.主存容量为512KB，Cache的容量为32KB，每块为64个字（或字节），缓存共分128组。划出组相联方式主、缓存的地址格式、目录表格式及其容量。

答：主存区数：512K/32K＝16＝2⁴；缓存组数：128＝2⁷； 缓存块数：32K/64＝512＝2⁹；

组内块数：512/128＝4＝2²；   块内地址：64＝2⁶

6.在页式虚拟存储器中，一个程序由P1～P5共5个页面组成。在程序执行过程中依次访问的页面如下：P2，P3，P2，P1，P5，P2，P4，P5，P3，P2，P5，P2

假设系统分配给这个程序的主存有3个页面，分别采用FIFO、LFU和OPT三种页面替换算法对这3页主存进行调度。

（1）画出主存页面调入、替换和命中的情况表。

（2）统计三种页面替换算法的页命中率。

解：三种替换算法的替换过程：

7.一个有快表和慢表的页式虚拟存储器，最多有64个用户，每个用户最多要用1024个页面，每页4K字节，主存容量8M字节。

（1）写出多用户虚地址的格式，并标出各字段的长度。

（2）写出主存地址的格式，并标出各字段的长度。

（3）快表的字长为多少位？分几个字段？各字段的长度为多少位？

（4）慢表的容量是多少个存储字？每个存储字的长度为多少位？

答：用户号：64＝2⁶，虚页号：1024＝2¹⁰，页内地址：4K＝2¹²，主存页数：8M/4K＝2¹¹

（1）多用户虚地址：

         用户号（6位）＋虚页号（10位）＋页内地址（12位）   共28位

（2）主存地址：

         主存实页号（11位）＋页内地址（12位）                共23位

（3）快表字长27位；分3个字段：用户号6位，虚页号10位，实页号11位

（4）慢表容量为2^（6+10），每个存储字长为：主存页号＋1＝12位。

8.一个程序由五个虚页组成，采用LFU替换算法，在程序执行过程中依次访问的地址流如下：

4，5，3，2，5，1，3，2，3，5，1，3

（1）可能的最高页命中率是多少？

（2）至少要分配给该程序多少个主存页面才能获得最高的命中率。

（3）如果在程序执行过程中访问一个页面，平均要对该页面内的存储单元访问1024次，求访问存储单元的命中率。

解：（1）由于在页地址流中互不相同的页共有5页，因此最多分配5个主存页面就可获得最高页中命中率，可能的最高命中率为

（2）因为LFU替换算法为堆栈型换算法，即随着分配给该程序的主存页面数的减少，其命中率单调递减，所以为获得最高命中率H＝7/12，可采用逐步减少所分配的主存页数的方法来推算，若分配n个主存页面时可获得最高命中率，但分配n－1个页面时命中率却减少，则此时我们可以得出这样的结论：至少要分配给该程序n个主存页面才能获得最高的命中率。

由表可知，至少要分配给该程序4个主存页面才能获得最高的命中率。

（3）访问存储单元的命中率为

值得说明的是，在此例中，尽管LFU属于堆栈替换算法，但是分配的实际页数n也并不是越多越好，当命中率H达到饱和后，实际页数n的增加不仅不会提高命中率，反而会使实存的利用率下降。

9.假设一台模型计算机共有10种不同的操作码，如果采用固定长操作码需要4位。已知各种操作码在程序中出现的概率如下表所示，计算采用Huffman编码法的操作码平均长度，并计算固定长操作码和Huffman操作码的信息冗余量（假设最短平均长度H＝3.1位）。

答：构造Huffman树如下：

Huffman编码如下表：

Huffman编码的平均码长为：

  冗余量＝（3.15－3.10）/3.15＝1.59%

固定码长：log₂¹⁰＝4

冗余量＝（4－3.10）/4＝22.5%

10．一台模型机的各条指令的频度如下：

ADD（加）：43%                      SHR（右移）：1%

SUB（减）：13%                      CLL（循环左移）：2%

JOM（按页转移）：6%                 CLA（累加器清0）：22%

STO（存）：5%                       STP（停机）：1%

JMP（转移）：7％

  试设计这9条指令的哈夫曼编码的操作码表示以及2-4等长扩展操作码表示，并计算这两种表示的平均操作码长度。

答：构造Huffman树如下：

Huffman编码如下表：

Huffman编码的平均码长为：

2-4编码的平均码长为：

11．用一条4段浮点加法器流水线求8个浮点数的和: Z＝A＋B＋C＋D＋E＋F＋G＋H,求流水线的吞吐率、加速比和效率,其中△t1=△t2=△t3=△t4=△t。

答：

可对原式作一简单变化，得到：

   Z＝[（A＋B）＋（C＋D）]＋[（E＋F）＋（G＋H）]

7个加法8个数的流水线时空图如下：

从流水线的时空图中可以很清楚地看到，7个浮点加法共用了15个时钟周期。

流水线的吞吐率为：

流水线的加速比为：

流水线的效率为：

12.有一条静态多功能流水线由5段组成，加法用1、3、4、5段，乘法用1、2、5段，第3段的时间为2△t，其余各段的时间均为△t，而且流水线的输出可以直接返回输入端或

暂存于相应的流水寄存器中。现要在该流水线上计算             ，画出其时空图，并计算其吞吐率、加速比和效率。

解：首先，应选择适合于流水线工作的算法。对于本题，应先计算A₁＋B₁、A₂＋B₂、A₃＋B₃和A₄＋B₄；再计算(A₁＋B₁) ×(A₂＋B₂)和(A₃＋B₃) ×(A₄＋B₄)；然后求总的结果。

其次，画出完成该计算的时空图，如图所示，图中阴影部分表示该段在工作。

由图可见，它在18个△t时间中，给出了7个结果。所以吞吐率为：

如果不用流水线，由于一次求积需3△t，一次求和需5△t，则产生上述7个结果共需（4×5+3×3）△t =29△t。所以加速比为：

该流水线的效率可由阴影区的面积和5个段总时空区的面积的比值求得：

13.动态多功能流水线由6个功能段组成，如下图：

其中，S1、S4、S5、S6组成乘法流水线，S1、S2、S3、S6组成加法流水线，各个功能段时间均为50ns，假设该流水线的输出结果可以直接返回输入端，而且设置有足够的缓冲寄存器，若以最快的方式用该流水计算：

（3）画出时空图；

（4）计算实际的吞吐率、加速比和效率。

解：机器一共要做10次乘法，4次加法。

14.假设有一条长流水线，仅仅对条件转移指令使用分支目标缓冲。假设分支预测错误的开销为4个时钟周期，缓冲不命中的开销为3个时钟周期。假设：命中率为90%，预测精度为90%，分支频率为15%，没有分支的基本CPI为1。

（3）       求程序执行的CPI。

（4）       相对于采用固定的2个时钟周期延迟的分支处理，哪种方法程序执行速度更快？

解：（1）程序执行的CPI = 没有分支的基本CPI（1） + 分支带来的额外开销

分支带来的额外开销是指在分支指令中，缓冲命中但预测错误带来的开销与缓冲没有命中带来的开销之和。

分支带来的额外开销= 15% * (90%命中×10%预测错误×4 + 10％没命中×3)= 0.099

所以，程序执行的CPI ＝ 1 ＋ 0.099 = 1.099

（2）采用固定的2 个时钟周期延迟的分支处理CPI = 1 + 15%×2 = 1.3

由（1）（2）可知分支目标缓冲方法执行速度快。

15.什么是PM2I置换？写出PM2I置换函数的表达式，假设互联网有16个结点，请画出PM2I置换当i＝2时的输入端与输出端的连接关系。

答：PM2I是对输入端编号加减2的i次方后得到输出端的编号。其函数关系可表示为：

图略

16.在一个时钟频率 f 为 40MHz 的处理机上执行一个典型测试程序，该程序有 4 种类型指令，每种类型指令在程序中出现的条数和每种指令的 CPI 如表 1.1 所示。计算这个测试程序在该处理机上运行的 CPI 和相应的 MIPS。

表 1.1  指令在程序中出现的条数和每种指令的 CPI

17. 假设高速缓存 Cache 的工作速度为主存的 5 倍，且 Cache 被访问命中的

概率为 90%，那么，采用 Cache 后能使整个存储系统获得多高的加速比？

18.某个流水线由 4 个功能部件组成，每个功能部件的执行时间都为∆t。当连续输入 10 个数据后，停顿 5∆t，又连续输入 10 个数据，如此重复。画出时空图，计算流水线的实际吞吐率、加速比和效率。

、

19.某虚拟存储器采用页式管理，主存容量为 4 个页面，使用 LRU 替换算法。若程序访存的虚页地址流为：0，7，0，6，7，1，6，3，0，7，2，7，1，4，0，2

（1）画出该程序使用主存实页位置的过程。

（2）计算该程序对主存的命中率和缺失率。

20. 在页式虚拟存储器中，一个程序由 0~4 共 5 个虚页组成，在程序执行过程中，访存虚页地址流为：0，1，0，4，3，0，2，3，1，3

假设分配给这个程序的主存空间有 3 个实页，分别采用 FIFO、LRU 和 OPT 替换算法进行替换调度。

（1）分别画出 3 种替换算法对主存 3 个实页位置的使用过程。

（2）分别计算 3 种替换算法的主存命中率。