计算机系统结构复习材料(供参考)

1、这边整理的例题，老师说不会考原题！请配合PPT和课本使用，认真复习。如果到时候没有帮上很大的忙请不要怪我！一、填空题（每空1分，共20分）1 计算机系统多级层次结构含义P1 考6个机器级以及各自用什么实现。计算机多级层次结构由高到低分别为应用语言机器级、高级语言机器级、汇编语言机器级、操作系统机器级（前4者均用软件实现）、传统机器语言机器级（用微程序（固件）实现）和微程序机器级（用硬件实现）。2 弗林分类P26 可以写英文也可以写中文。1966年，弗林提出按指令流和数据流的多倍性对计算机系统分类。把计算机系统分成单指令流单数据流SISD、单指令流多数据流SIMD、多指令流单数据流MISD和多指

2、令流多数据流四大类MIMD。3 计算机系统持续性能评测，几种方式表达式，以及表达式中变量含义P10。 几何性能平均值不考。（1）算术性能平均值Am以速率评价： = 1/n(1/T1+1/T2+1/Tn)以时间评价: （2）调和性能平均值Hm = n/( T1+T2+Tn)（3）加权算术平均值Am 以上的式子，Ti和Ri分别是第i个程序的执行时间和执行速率，i是权值4 规格浮点数，P40表2-1。这题是这样考的：题目会给化出p=？，m=？，rm=？ 和某种条件，然后求该条件下的值。（以下那张图考试时不会给出），并要记补充那句。 * 表中特例是指rm为2的整数次幂时，用 =2m代入。补充：随着rm

3、越大，可表示数的范围增大、个数增多、精度单调下降，右移造成的精度损失降低，运算速度提高。5 尾数下溢处理方法，优缺点比较P44。（1） 截断法优点：实现容易，简单；不增加硬件，不需要处理时间；缺点：平均误差为负数，而且较大，无法调节；（2）舍入法优点：实现简单，增加的硬件很少，最大误差小，平均误差接近于0；缺点：处理速度慢，比较复杂；（3）恒置“1”法优点：实现最简单，不需增加硬件和处理时间，平均误差接近0；缺点：最大误差最大；（4）查表舍入法优点：查表速度快，平均误差接近0；缺点：硬件量大，成本较高6 存储体基本参数计算P73（1）存储器容量SM： SM =W×l×m （

4、2）存储器频宽Bm： 单体Bm=W/TM m个存储体并行Bm= W×m/ TM（3）存储价格（可以用总价格C或者每位价格c来表示）C=C1+C2 c=(C1×SM1+C2×SM2)/(SM1+SM2)7 多体单字模m低位交叉存储方式P75表3-1。 i mod m eg：若i =5， m =4，则值为1，即为1或者可以写M18 总线分类P84。 要会按什么分为什么（1）总线按在系统中的位置分为：芯片级总线、板级总线、系统级总线。（2）总线按数据传送方式分为：串行传输总线和并行传输总线。（3）总线按允许信息传送的方向分：单向传输和双向传输。（数据总线，地址总线，控制

5、总线）（4）总线按用法可以分：专用总线和非专用总线。9 总线控制方式P85 老师说是要考优先次序的确定方式(以下3个)（1）集中式串行链接方式（2）集中式定时查询方式（3）集中式独立请求方式10 页式虚拟存储器P109。全相联映像（有考的话，这就是答案了 O(_)O哈哈）11 页面替换算法有哪些P112页面替换算法有（1）随机算法（2）先进先出算法FIFO（3）近期最少使用算法LRU（4）最久没有使用算法（5）最优替换算法OPT（不考）12 标量流水机顺序流动、异步流动会出现的相关P165。顺序流动：“先写后读”相关异步流动：“先写后读”相关；“先读后写”相关；“写写”相关13 流水机中断处理

6、方式P171早期：采用“不精确断点”法。但不利于编程和程序的排错。后来：采用“精确断点”法。14 给出指令执行数量和平均时钟周期数计算CPI。假设系统共有n种指令，第i种指令的时钟周期数为，第i种指令在程序中出现的次数为，程序执行的总指令条数IC，则15 阵列处理机构形P193。两种：（1）具有分布式存储器的阵列处理机构型（2）具有集中式共享存储器的阵列处理机构型16 通道极限流量计算公式P95。（1）字节多路通道：（2）数组多路通道：（3）选择通道：17 各种互连网络的互连方式（给出入端，根据函数，求出端）P202开始。4个单级互连网络： （1） 立方体单级网络：函数：Cubei（Pn-1P

7、iP1 P0）= Pn-1P1 P0 式中，0in-1，Pi为入端号二进制码的第i位。 例如：给出N=8，则n=3（n为维数，决定P0到P2），给i=0，则Cube0= P2P1 给i=1，则Cube1= P2P0 给i=2，则Cube2= P1P0（2）PM2I单级网络：式中，0jN-1, 0in-1, n=log2N。 例如：给出i和j的值，并告诉N=? 代入上式即可求得PM2+i 和PM2-i （3）混洗交换单级网络：互连函数：式中，n=log2N，Pn-1Pn-2P1P0为入端编号的二进制码。 类似（1）（4）蝶形单级网络：互连函数：butterfly类似（1）2个多级互连网络：（1）

8、多级立方体网络：例如：给出入端号0，1，2，3，4，5，6，7和级控制信号，如：级控制信号为101，入端号为0的出端号为5，图中右下角就是所要求的出端。 207页的图例如：给出以下入端号，01234567和部分级控制信号，（以部分级控制信号第1列为例，第6章48幻灯片有该动态过程），图中右下角就是所要求的出端。 208页的图（2）多级混洗交换网络 二、简答题（每题5分，共20分）1 分别阐述CISC、RISC含义，优、缺点。优缺点来自百度，仅供参考CISC 复杂指令系统计算机(Complex Instruction Set Computer) 优点：指令越多功能越强，强调代码效率，容易和高级语

9、言接轨。可以对存储器直接操作，实现从存储器到存储器的数据转移，可加入DSP指令。缺点：指令太多不易记忆；CPU内部结构复杂造成频率不高；指令执行速度慢。RISC 精简指令系统计算机(Reduced Instruction Set Computer)优点：指令少容易记忆，尽量将操作码和操作数用1个16位数或32位数表示，指令整齐。CPU时钟频率可以做得很高，指令执行速度快。缺点：同样功能的程序，产生的代码量比较大；不能对存储器直接访问，不能实现存储器到存储器的数据转移。2 从计算机处理数据的并行性来看，并行性等级可分为哪几级并行性等级从低到高可以分为4级： 位串字串同时只对一个字的一位进行处理，

10、这通常是指传统的串行单处理机，没有并行性。 位并字串同时对一个字的全部位进行处理，这通常是指传统的并行单处理机，开始出现并行性。 位片串字并同时对许多字的同一位（称位片）进行处理，开始进入并行处理领域。 全并行同时对许多字的全部或者部分位组进行处理。3 给出中断处理次序，给出中断出现情况，画出运行情况示意图。（两张图都要画，第一张图2分，第二张3分）例题：假设系统有4个中断级，相应地每一级中断处理程序的现行PSW中都有4位中断级屏蔽位。如果中断级屏蔽位为“1”，则表示对该级中断开放，允许其进入中断响应排队器；如果中断级屏蔽位为“0”，则对该级中断屏蔽，不让其进入中断响应排队器。若中断处理次序1

11、432，就需如下表设置好各级中断处理程序现行程序状态字中的中断级屏蔽位即可。4 给出冲突向量，画出状态转移图。PPT第五章66幻灯片点进去，有详细动态过程。解释：给出冲突向量10110001，图中的9+不要管它，不必标出。2，3，4，7是看所给的冲突向量中哪几位为0（从右到左18数起），然后所给的冲突向量10110001逻辑右移2位变成00101100，再与所给的冲突向量10110001进行或运算5给出在CRAY-1机上的指令问是否可以链接执行，并分析其所需最少执 行拍数。例：在CRAY-1机上，设向量的长度均为64；所用浮点功能部件的执行时间分别为：相加需6拍，相乘需7拍，从存储器读数需6拍

12、，存入寄存器及启动功能部件各需1拍。问下列各指令组中，组内哪些指令可以链接？哪些指令不可以链接？不能链接的原因是什么？并分别计算出下列各指令组全部完成所需要的拍数。（1）V2¬V0*V1V3¬存储器 V4¬V3+V5（2）V0¬存储器V1¬V2+V3 V4¬V5*V6（3）V0¬存储器V2¬V0*V1 V3¬V0+V4解:(1)第三条向量指令与第二条向量指令有源目向量相关，可以链接执行；第一条向量指令与第二、三条向量指令无关，可以与它们并行执行。6画出某种多级互连网络（多级立方体或omega）。以下是N=

13、8的情况，如果N=16就要多出第3级了，以两图中最上面3个框为例，大家会想，为什么是01，02，04呢？那么，是这样的，根据级别，分别应该相差20，21，22，所以是01，02，04，根据该规律大致就可以理解为什么是那些数据了，最后完成全为0的相连，1，2，3，4，5，6，7也一样。（1）多级立方体 N=8 多级立方体互连网络 （2）omega（又称多级混洗交换网络） N=8多级混洗交换网络 3、 计算题（每题15分，共60分）1假设一条指令的执行过程分为“取指令”、“分析”和“执行”三段，每段的时间分别为t，t和3t。在下列情况下，分别写出连续执行n条指令所需要的时间表达式。 (必考) （1

14、）顺序执行方式顺序执行时每条指令用时=t + t + 3t = 5t，因此n条指令所需要的时间T = 5nt。（2）“取指令”和“执行”重叠“取指令”和“执行”重叠，即一次重叠执行方式，我们假设第n+1条指令的“取指令”和第n条指令的“执行”同时结束，那么所需要的时间为 T = 5t + （n - 1）（t + 3t）= 4nt + t。（3）“取指令”、“分析”和“执行”重叠 第一条指令完成时间 = t + t + 3t = 5t 由于后面的指令的“取指令”、“分析”和上一条指令的执行阶段重叠，故每3t完成一条指令，余下（n-1）条指令用时3t（n-1），因此，n条指令所需要的时间T = 5

15、t + 3t（n-1）= （3n+2）t。（4）说说顺序执行方式和重叠方式的优缺点。顺序执行方式：优点：控制简单，转入下一条指令的时间易于控制。缺点：上一步操作未完成，下一步操作便不能开始，机器各部件利用率低。重叠方式：优点：指令运行时间缩短，功能部件利用率提高。 缺点：需要增加硬件，控制过程复杂。2哈夫曼编码以及扩展码P51 例题（小测过的题目）：某模型机7条指令使用频度分别为23%，15%，35%，9%，7%，5%，6%，求其哈夫曼编码（画出哈夫曼树，并根据左小右大，左0右1（考试时候也是这么规定）的方式编码），并求其平均码长。并设计某种可行的扩展码，写出编码，求平均码长。解答： 哈夫曼树

16、： 哈夫曼编码：I1 = 0 I5 = 11110 I2 = 10 I6 = 111110I3 = 110 I7 = 111111I4 = 1110编码平均码长l： =1×0.35+0.65×0.23+0.05×0.11=2.63扩展码： I1 = 00 I5 = 1101 I2 = 01 I6 = 1110I3 = 10 I7 = 1111I4 = 1100正确：3页式虚拟存储器给出页地址流,n=3 如P114116(1) 分别画出LRU，FIFO，OPT算法的页面替换状态图（用*号标注下一次应当被替换出去的页面），以及各自的命中率。命中率：5/12命中率：1/

17、4命中率：1/2（2）画出LRU的堆栈处理变化过程，并计算当n为4，5，6时的命中率。PPT第4章第49个幻灯片，点击去，有动态详细过程。该题考试需要画。1,2,4,5,7因为页面数发生改变了，故一定不命中（看图中这5列是空着的）。4给出向量运算,分别画出在动态双功能流水线和静态双功能流水线上的运行时空图，并分别计算其实际吞吐率和效率。如P163 ，P159（1）动态双功能流水线上的运行时空图例题：用一条4段浮点加法器流水线求8个浮点数的和：ZABCDEFGH分析：1、线性流水线，输入任务不连续2、存在数据相关，如只有A+B的运算结果出来之后才能做加C的运算3、如果这样，与顺序执行方式完全一样4、如果作如下变换：Z = (A+B) + (C+D) + (E+F) + (G+H)小括号内的操作之间，没有数据相关，可以连续输入到流水线中。实际吞吐率： 助记：其实用上图的指令条数7除以总时间长 15就可以了。效率： 助记：上图中含有数字的格子总数除以总空间（2）静态双功能流水线上的运行时空图 书上163-164页有相关例题。5.Cache存储器结构、工作原理，地址映像变换、替换算法实现等P124P134。老师说以上四方面都给出描述就可以了。不需要画出存储器结构