计算机综合体系结构期末复习题答案.doc

《计算机体系结构》期末复习题答案
系别 _________ 班级 _________ 姓名__________ 学号__________
一、 填空题（每空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种通信模式是（单播模式，选播模式，广播模式和会议模式）。
13.传统冯•诺依曼计算机是以控制驱动方法工作，以数据驱动方法工作经典计算机是（数据流计算机），以需求驱动方法工作经典计算机是（归约机），以模式匹配驱动方法工作经典计算机是（人工智能计算机）。
二、名词解释（每题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/16＝32K＝215；缓存块数：32K/16＝2K＝211；块内地址：16＝24
容量：和缓冲块数量相同即211＝2048(或32K/16＝2048)。
主存块号Bi 块内地址
18 4 3 0
主存地址
缓存块号Bi 块内地址
14 4 3 0
缓存地址
主存块地址 缓存块地址 有效位
26 12 11 1 0
目录表

2. 主存容量为512KB，Cache容量为32KB，每块为64个字（或字节），缓存共分128组。划出组相联方法主、缓存地址格式、目录表格式及其容量。
答：主存区数：512K/32K＝16＝24；缓存组数：128＝27； 缓存块数：32K/64＝512＝29；
组内块数：512/128＝4＝22； 块内地址：64＝26

容量：和缓冲块数量相同即29＝512(或32K/64＝512)。
区号 块号 缓存块号 有效位
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立方置换函数：
1000
1001
1010
1011
1100
1101
1110
1111
1000
1001
1010
1011
1100
1101
1110
1111
0000
0001
0010
0011
0100
0101
0110
0111
0000
0001
0010
0011
0100
0101
0110
0111

C1立方置换函数：
0000
0000

0001
0010
0011
0100
0101
0110
0111
0001
0010
0011
0100
0101
0110
0111

1001
1010
1011
1100
1101
1110
1111
1001
1010
1011
1100
1101
1110
1111
1000
1000

C2立方置换函数：
1000
1001
1010
1011
1100
1101
1110
1111
1000
1001
1010
1011
1100
1101
1110
1111
0000
0001
0010
0011
0100
0101
0110
0111
0000
0001
0010
0011
0100
0101
0110
0111

C3立方置换函数：
1000
1001
1010
1011
1100
1101
1110
1111
1000
1001
1010
1011
1100
1101
1110
1111
0000
0001
0010
0011
0100
0101
0110
0111
0000
0001
0010
0011
0100
0101
0110
0111

4. 在页式虚拟存放器中，一个程序由P1～P5共5个页面组成。在程序实施过程中依次访问页面以下：P2，P3，P2，P1，P5，P2，P4，P5，P3，P2，P5，P2
假设系统分配给这个程序主存有3个页面，分别采取FIFO、LFU和OPT三种页面替换算法对这3页主存进行调度。
（1）画出主存页面调入、替换和命中情况表。
（2）统计三种页面替换算法页命中率。
解：三种替换算法替换过程：

页地址流
2
3
2
1
5
2
4
5
3
2
5
2

FIFO
命中3次
2
2
3
2
3
2*
3
1
5
3*
1
5
2
1*
5*
2
4
5*
2
4
3
2*
4
3
2*
4
3
5
4*
3*
5
2
调
进
调
进
命
中
调
进
替
换
替
换
替
换
命
中
替
换
命
中
替
换
替
换

LRU
命中5次

2
2
3
2
3
1
2
3*
5
1
2*
2
5
1*
4
2
5*
5
4
2*
3
5
4*
2
3
5*
5
2
3*
2
5
3*
调
进
调
进
命
中
调
进
替
换
命
中
替
换
命
中
替
换
替
换
命
中
命
中

OPT
命中6次
2
2
3
2
3
2
3
1*
2
3*
5
2*
3
5
4*
3
5
4*
3
5
4*
3
5
2
3*
5
2
3
5
2
3
5
调
进
调
进
命
中
调
进
替
换
命
中
替
换
命
中
命
中
替
换
命
中
命
中

5. 一个有快表和慢表页式虚拟存放器，最多有64个用户，每个用户最多要用1024个页面，每页4K字节，主存容量8M字节。
（1）写出多用户虚地址格式，并标出各字段长度。
（2）写出主存地址格式，并标出各字段长度。
（3）快表字长为多少位？分多个字段？各字段长度为多少位？
（4）慢表容量是多少个存放字？每个存放字长度为多少位？
答：用户号：64＝26，虚页号：1024＝210，页内地址：4K＝212，主存页数：8M/4K＝211
（1）多用户虚地址：
用户号（6位）＋虚页号（10位）＋页内地址（12位） 共28位
（2）主存地址：
主存实页号（11位）＋页内地址（12位） 共23位
（3）快表字长27位；分3个字段：用户号6位，虚页号10位，实页号11位
（4）慢表容量为2（6+10），每个存放字长为：主存页号＋1＝12位。

6. 一个程序由五个虚页组成，采取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个主存页面才能取得最高命中率。

页地址流
4
5
3
2
5
1
3
2
2
5
1
3
S(1)
堆 S(2)
栈 S(3)
内 S(4)
容 S(5)
S(6)
4
5
4
3
5
4
2
3
5
4
5
2
3
4
1
5
2
3
4
3
1
5
2
4
2
3
1
5
4
2
3
1
5
4
5
2
3
1
4
1
5
2
3
4
3
1
5
2
4
n=1
实 n=2
页 n=3
数 n=4
n>=5

H
H
H

H
H

H
H
H
H
H
H
H

H
H

H
H

H
H

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

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

7. 假设一台模型计算机共有10种不一样操作码，假如采取固定长操作码需要4位。已知多种操作码在程序中出现概率以下表所表示，计算采取Huffman编码法操作码平均长度，并计算固定长操作码和Huffman操作码信息冗余量（假设最短平均长度H＝3.1位）。
指令序号
指令使用频度Pi
指令序号
指令使用频度Pi
I1
0.17
I6
0.09
I2
0.15
I7
0.08
I3
0.15
I8
0.07
I4
0.13
I9
0.03
I5
0.12
I10
0.01

答：结构Huffman树以下：

Huffman编码以下表：
指令号
指令使
用频度Pi
Huffman
编码
码长
指令号
指令使
用频度Pi
Huffman
码
码长
I1
0.17
10
2
I6
0.09
0110
4
I2
0.15
000
3
I7
0.08
0111
4
I3
0.15
001
3
I8
0.07
1110
4
I4
0.13
010
3
I9
0.03
11110
5
I5
0.12
110
3
I10
0.01
11111
5

Huffman编码平均码长为：
冗余量＝（3.15－3.10）/3.15＝1.59%
固定码长：log210＝4
冗余量＝（4－3.10）/4＝22.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编码以下表：
指令
指令使
用频度Pi
Huffman
编码
码长
2-4扩展
码
码长
ADD
0.43
0
1
00
2
CLA
0.22
100
3
01
2
SUB
0.13
101
3
1000
4
JMP
0.07
1100
4
1001
4
JOM
0.06
1101
4
1010
4
STO
0.05
1110
4
1011
4
CLL
0.02
11110
5
1100
4
SHR
0.01
111110
6
1101
4
STP
0.01
111111
6
1110
4

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

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

S1

S2

S3

S4

输出

△
t
1

△
t
2

△
t
3

△
t
4

答：可对原式作一简单改变，得到：
Z＝[（A＋B）＋（C＋D）]＋[（E＋F）＋（G＋H）]
7个加法8个数流水线时空图以下：

从流水线时空图中能够很清楚地看到，7个浮点加法共用了15个时钟周期。
流水线吞吐率为：

流水线加速比为：

流水线效率为：

9．设有两个向量A，B，各有4个元素，若在图所表示静态双功效流水线上，计算向量点积：

其中，1→2→3→5组成加法流水线，1→4→5组成乘法流水线。
又设每个流水线所经过时间均为△t，而且流水线输出结果能够直接返回到输入或暂存于对应缓冲寄存器中，其延迟时间和功效切换所需时间全部能够忽略不计。请使用合理算法，能使完成向量点积A*B所用时间最短，并求出流水线在此期间实际吞吐率TP和效率E。
解：首先，应选择适合于静态流水线工作算法。对于本题，应先连续计算al*bl、a2*b2、a3*b3和a4*b4共4次乘法，然后功效切换，按((albl+a2b2)+(a3b3+a4b4))经3次加法来求得最终结果。按此算法可画出流水线工作时时空图。
由图可见，总共在15个△t时间内流出7个结果，所以在这段时间里，流水线实际吞吐率TP为7/15△t。
若不用流水线，因为一次求积需3△t,产生上述结果就需要4´3△t+3´4△t=24△t。所以,加速比为S=24△t/(15△t)=1.6。
该流水线效率可用阴影区面积和全部5个段总时空图面积之比求得，即