系统结构基本概念附原理

1、基本概念 ：1. 在 Cache 存贮器中， CPU 每次写 Cache 的同时，也写入主存，称这种更新主存块内容的 方法为写直达法。2. 进行仿真工作的机器称为宿主机，而被仿真的机器称为目标机。3. 不属于堆栈型替换算法的是 FIFO，而LRU OPT是属于堆栈型替换算法的。4. 因机器语言程序中邻近指令之间出现了关联，使它们不能同时解释的现象称为相关，它 可以有数相关及指令相关。5. 交换开关的四种开关状态是直连，交换，上播，下播。6. 提高计算机系统并行性的主要技术途径有时间重叠，资源重复，资源共享。7. 为解决多个处理机同时访问公用总线的冲突，所采用的总线仲裁算法有静态优先级，固 定时

2、间片，动态优先级，先来先服务。8. 在 SIMD 计算机中，无论是处理单元之间还是处理单元与存贮体之间，都要通过互连网 络实现信息交换。9. 指令的重叠解释，可以加快一段程序的解释，但不能加快单条指令的实现。10数据宽度是指 I/O 设备取得总线使用权后所传送数据的总量。11数组多路通道在每选择好一台设备后，要连续传送完固定个字节的成组数据后，才 释放总线 .12 .选择通道每选择一台设备，就让该设备独占通道，将n个字节全部传送完后，才释放通道总线，又去选择下一台设备，再传送它的全部字节数据。13. 等长操作码的意思是不管其指令的频度如何，都用同样长度的二进制码位数来对指令 操作码编码。14.

3、 若计算机系统的体系结构和硬件设计使编写程序时需要了解系统的结构细节，则对程 序设计而言，该计算机系统的体系结构不具有透明性。15. 在模m的并行主存系统中，主存实际频宽并不一定随模m值增大而线性提高。16 .在流水机器中，全局性相关是指由转移指令引起的相关。17 .块冲突概率最高的 Cache地址映象方式是直接映象方式。18 .当发生页面失效时，要从磁盘中调入一页到主存。19 .只有两种码长的扩展操作码编码，则需要对指令使用频度进行按大小分群。2 0 .在字节多路通道上，设备对通道要求的流量应是所挂全部设备的速率之和。基本原理1 .页面失效频率算法立足于堆栈型替换算法的特点，根据各道程序运行

4、中的主存页面失效率的高低， 由操作系统来动态调节分配给每道程序的实页数， 当主存页面失效率超过某个限 值时就自动增加给该道程序的主存页数来提高命中率，反之则减少给该道程序的主存页数。2 . 从计算机信息加工的各个步骤和阶段来看并行性等级可以分为四级：1) 存贮器操作并行：相联处理机2) 处理器操作步骤并行：流水线处理机3) 处理器操作并行：阵列处理机4) 指令、任务、作业并行：多处理机3 . 所谓透明就是看不到，不属于其管理的部分。若计算机系统的体系结构和硬件设计使编写程序时需要了解系统的结构细节， 则对程序设计而言， 该计算机系统的体系结构不具有 透明性。4 .硬件和软件在逻辑功能上是等效的

5、。在原理上，用软件实现的功能完全可以用硬件或固件(微程序解释 )来完成。用硬件实现的功能也可以通过用软件进行模拟来完成，只是反映在 速度、价格、实现的难易程度上，这两者是不同的。5 .影响主存命中率的主要因素：(1) 程序在执行过程中的页地址流分布情况。 (2) 所采用的页面替换算法。 (3) 页面大小。 (4) 程序所分配的主存容量。 (5) 所采用的页面调度算法。6 .设计RISC机器的基本技术：按设计RISC机器的一般原则来精选和优化设计指令系统；逻辑上采用硬联组合电路为主，适当辅以微程序控制；在CPU 内设置大量寄存器，采用重叠寄存器组的窗口； 指令采用重叠和流水的方式解释， 采用延迟

6、转移； 优化设计高质量的编 译程序。7 .数据表示是数据结构的组成元素，数据结构要通过软件映象变换成机器所具有的各种数据表示来实现。 不同的数据表示可为数据结构的实现提供不同的支持， 表现在实现效率和方 便性上不同。数据结构和数据表示是软件和硬件之间的交界面。确定和引入数据表示的基本原则：一是看系统效率有否提高，即是否减少了实现的时 间和存贮的空间，实现时间有否减少又主要看在主存和处理机之间传送的信息量有否减少； 二是看引入这种数据表示的通用性和利用率是否较高。8 .描述符数据表示在实现向量、 阵列数据元素的索引上要比用变址方法的方便，能更快地形成元素的地址，从而可以迅速进行访问，同时， 也有

7、利于检查程序中的向量、数组在使用 中是否越界。因此， 它为向量、 数组数据结构的实现提供了一定的支持，有利于简化编译中 的代码生成。但是， 描述符数据表示并没有向量、 数组的运算类指令， 也没有采用流水或处 理单元阵列形式的高速运算硬件， 没有时阵列中每个元素又是一个子阵列的相关型交叉阵列 进行处理的硬件。 也投有时大量元素是零的稀疏向量和数据进行压缩存贮、还原、 运算等指令和硬件。 因此，它对向量和数组的数据结构提供的支持不够强， 所以并不是向量数据表示。9 .流水线的时空图用于描述流水线的工作过程。在时空图中，横坐标表示时间，也就是输 入到流水线中的各个任务在流水线中所经过的时间。 当流水

8、线中的各个功能部件的执行时间 都相等时，横坐标被分割成相等长度的时间段。纵坐标表示空间，即流水线的各个子过程。 在时空图中，流水线的一个子过程通常称为“功能段” 。10 .硬件和软件在逻辑功能上是等效的。在原理上，用软件实现的功能完全可以用硬件或固件(微程序解释 )来完成。用硬件实现的功能也可以通过用软件进行模拟来完成，只是反映 在速度、价格、实现的难易程度上，这两者是不同的。11 . 寄存器寻址的原理是，指令的操作数地址码宇段给出存放操作数所用的寄存器号。可表示操作数的范围大小取决于存放操作数所用的寄存器的二进位位数。除取指外， 为获得操作数不用访存， 即访存 0 次。为指明操作数所占用指令

9、中的信息位数，只是寄存器编号所占的二进位位数，很短。例如， 16 个寄存器编号只需 4 位二进位。寄存器寻址简单，其取数 的时间要比访存的时间短很多。12 计算机系统结构、计算机组成、计算机实现互不相同，但又相互影响。(1 )计算机的系统结构相同，但可采用不同的组成。 (2)相同的组成可有多种不同的实现。( 3)计算机的系统结构不同，会使采用的组成技术不同，反之组成也会影响结构。综上所述，系 统结构的设计必须结合应用考虑，为软件和算法的实现提供更多更好的支持，同时要考 虑可能采用和准备采用的组成技术。13 .串行链接对通讯的可靠性，主要表现于“总线可用”线及其有关电路的失效会造成系统 整体瘫痪

10、的问题。一旦“总线可用”线出现断路或碰地，其高电压不能顺链往下传送，就会 使后面的部件在要求使用总线时，其请求无法得到响应。 为了提高可靠性，可以对“总线可 用”线及其相关电路，采取重复设置两套或多套的方法来解决。定时查询对通讯的可靠性要比串行链接的高。因为总线控制器通过计数，查询到某个出故障的部件时，故障部件不会给出“总线忙”信号。这样，不会影响控制器继续计数，去查询下一个部件，所以整个总线系统的工作不会瘫痪。一、 某机有10条指令，其使用频度分别为0.14, 0.12，0.12，0.03，0.05，0.06，0.04，0.13， 0.30 ， 0.01。要求：（a）画出Hafuman编码的

11、二叉树。（b）写出等长二进制编码，Hafuman编码，2-4扩展编码。（c） 计算三种编码的平均码长。I二进制编码Haffma n 码2-4扩展编码0.30000000000.140001010010.13001001110000.12001110010010.12010010110100.060101110010110.050110110111000.040111111011010.0310001111011100.011001111111111平均码长42.933.124 / 8.某报文由多个字符组成，其出现频度依次为0.17, 0.05, 0.20, 0.06, 0.08, 0.03,

12、0.01,0.08, 0.13, 0.08, 0.11。完成以下要求：若各字符用等长二进制编码，传送200个字符时，需传送多少位二进制码？画出哈夫曼树,写出各字符的二进制码位数。按哈夫曼编码，计算字符的平均码长。解：共需传送4X 200 = 800 位。哈夫曼树如下图：11哈夫曼编码的平均码长为'、 pi li =3.23位i 4三.在Cache存贮器中，块的大小为512字，主存分8块，Cache分为4块，采用组相联映象（组间直接、组内相联），每组2块，替换算法为LRU。设主存块地址流为1、2、4、1、3、7、0、1、2、5、4、6、4、7、2,从Cache为空开始，列出 Cache中

13、各块随时间的使 用状况，求Cache的命中率。答：Cache中各块随时间的使用状况如下表：主存块地址1241370125464720111*1111*111*44444Cache 块144*4*4*00*0*55*5*5*5*5*22222*7777*7*7*666*2333*3*3*2222*2*77*命中情况失失失H失替替H替替替替H替替根据上表 Cache的块命中率为 3/15 = 0.2四.有一个 Cache主存层次：主存分 8块（07）, Cache为4块（03）,块大小为1KB。 采用组相联映象，组内块数为2块。已知页面地址流为 2, 7, 4, 2, 0, 1 , 5, 4, 1

14、,2, 6, 5 , 6 , 0 , 2。试用LRU和OPT替换算法，分别画出替换示意图、求出命中率H。* （假设Cache已先后访问并预取进了主存的第5、1、3、7块,）*用LRU替换算法时：A2742015412656020组444*11*44*4*4*555*5*00*55*1111*1*001组22*2*2H222222 H2*2*2*2*2H777*7*7*7*7*7*7*666H66*4命中率为：H= 用OPT替换算法时:A2742015412656020组444444*H1*1*1*1*1*000*1*5*55555H55*5*1组2222H222222H2*2*222H7*7*

15、7*7*7*7*7*7*7*666*H6*6*命中率为:615H=四.设一个4段流水线的预约表如下，要求：(1) 写出禁止等待时间和初始冲突向量C。(2) 画出调度该流水线的状态变换图，。段号(1)S1禁止时间S2禁止时间S3禁止时间 禁止时间2，3,1234561VVV2VV3V4| V |V3. 5 2225允许时间1，4拍 号6 / 8初始冲突向量 C0=10110五.已知算术表达式E=a-b(c-de+f-g)+h，现用3个处理机的并行系统处理。要求:试压缩树高来开发该式并行性。求出P、Tp、Sp、Ep。deT 串=7 Tp = 4P= 3Sp= T 串/ Tp=7/4Ep= Sp/p

16、=7/12六.设向量A和B各有4个元素在下图所示的静态双功能流水线上计4算向量点积A B=X aD，其中1宀2宀3宀5组成加法流水线，1i T-4-5组成乘法流水线。若假定流水线的各段所经过的时间均为 t=2.5，流水线输出可直接送回输入或暂存于相应缓冲寄存器 中，其延迟时间和功能切换所需的时间都可忽略。求出吞吐率和 加速比。z实际吞吐率为=-18.7%15 过 15 疋 2.5因顺序方式所需时间为 4 3 ：t 3 4：t=24：.t ,因此加速比 Sp=24 . t/15 ：t=1.6七.某程序共有5个虚页，页地址流为3, 2, 0, 2, 4, 3, 4,2, 1, 3, 2, 0在主存

17、分配的页面数为 3,且主存开始为空的条 件下使用LRU , OPT, FIFO三种页面替换算法，要求画出各种 算法的页面替换过程并求出各种算法的命中率。320243421320LRU算法333*3*444H44*333*222H22*2*2 H22*2H2000*333*111*0OPT算法333333*H3*333H33222H2*222H222H20*0*444H4*1*1*10FIFO 算法333*3*444H4*1111222H2*3333*3*H3*00000*0*2222H2*LRU算法的命中率 H=4/12=33.3% OPT算法的命中率H=6/12=50%FIFO算法的命中率 H=4/12=33.3%八机器共有 5级中断，中断响应