系统结构复习

1、总 复 习第一章1. 计算机系统结构、组成、实现的基本概念和包含的内容；系统结构与软硬件功能划分的关系；计算机系统的多级层次结构；判断某项内容属于结构、组成、实现的哪一类；判断某项内容针对不同程序员的透明性。 2. 促进系统结构发展的因素（软件、应用、器件）。软件：实现软件可移植性的方法；系列机的概念；软件兼容的概念（向前、向后、向上、向下兼容）；模拟与仿真技术的概念；应用：应用对系统结构的要求。器件：系统结构下移的概念。3. 计算机系统的分型与分类的概念。Flynn分类法4. 系统结构设计的定量原理（Amdahl定理）；加速比的计算方法；5. 程序访问的局部性原理（时间局部性、空间局部性）；

2、判断系统结构中局部性原理的应用。6. 系统评价的指标（响应时间、CPU时间、MIPS、MFLOPS）；运用CPU性能公式、平均CPI比较系统性能。7. 并行性的概念；并行性的等级、粒度；并行性的开发策略（时间重叠、资源重复、资源共享）；8. 计算机系统的主要设计方法部分习题参考答案：1.6 解：（1）CPI (45000×175000×28000×41500×2) / 1295001.776（2）MIPS速率f/ CPI 400/1.776 225.225MIPS（3）程序执行时间= (45000×175000×28000×

3、41500×2)400×106=5.75×104s=0.575ms=575s1.8 解：（1）在多个部件可改进情况下，Amdahl定理的扩展：已知re130，re220，re310，Sp10，fe10.3，fe20.3，得：得fe30.36，即部件3的可改进比例为36%。（2）设系统改进前的执行时间为T，则3个部件改进前的执行时间为：（0.3+0.3+0.2）T = 0.8T，不可改进部分的执行时间为0.2T。已知3个部件改进后的加速比分别为S130，S220，S310，因此3个部件改进后的执行时间为： 改进后整个系统的执行时间为：Tn = 0.045T+0.2T

4、 = 0.245T那么系统中不可改进部分的执行时间在总执行时间中占的比例是：=82%1.9 解：（1）改进后，各类操作的加速比re分别是：操作类型各类操作的加速比re操作12/12操作220/151.33操作310/33.33操作44/14（2） 改进前系统总执行时间：10×2+30×20+35×10+15×41030 改进前各类操作时间在所有操作时间中所占的比例fe：操作类型改进前各类操作的执行时间在总的执行时间中所占的比例操作110×2/10300.01941.94%操作230×20/10300.582558.3%操作335

5、15;10/10300.339834%操作415×4/10300.05835.83%根据Amdahl定律可得各类操作单独改进后，程序获得的加速比分别是：操作类型改进前各类操作的执行时间在总的执行时间中所占的比例各类操作单独改进后，程序获得的加速比操作11.94%1.01操作258.3%1.17操作334%1.31操作45.83%1.05（3）在多个部件可改进情况下，Amdahl定理的扩展：4类操作均改进后，整个程序的加速比是：1/(1.94%/2+58.3%/1.33+34%/3.33+5.83%/4)1.78补充题1. 确定下列内容各属于哪方面的问题。（1）机器字长为32位。

6、60;          A.   B.    C.  （2）存储器最大容量为64MB。       A.   B.    C.  （3）存储器采用31路交叉存储方式。         A.   B.  

7、60; C.  （4）采用4M×4位的DRAM存储器芯片，组装在一块印刷电路板。  A.   B.    C. （5）存储器字长为32位，逻辑地址空间为4GB。   A.   B.    C.（6）主存储器的存储周期设计为200ns。                   

8、;   A.   B.    C.       答案中的符号的含义：A： 系统结构   B： 计算机组成    C： 计算机实现   答： AABCAB2. 判断下列哪些内容对机器语言（含汇编语言）程序员是透明的。1）指令寄存器                

9、            2）程序计数器3）数据通路的宽度                           4）浮点数据表示5）行波进位加法器         

10、;                 6）Cache7）控制存储器                                &

11、#160; 8）中断屏蔽触发器9）通用寄存器                                  10）硬盘11）只读存储器使用EPROM芯片    12）微地址寄存器答： 1、3、5、6、7、11、12第二章1. 指令系统的设计要求（

12、完备性、有效性、兼容性、规整性、对称性、可扩充性、正交性、有利于编译）。2. 指令系统的分类（堆栈型、累加器型、通用寄存器型）；通用寄存器型指令的特点（RR型、RM型、MM型）。3. 操作数访问方式（按地址访问、按内容访问）；按地址访问的编址问题：字编址、字节编址、位编址；按字节编址时的大端排序与小端排序。编址规定中的访存越界问题及其解决方法。按内容访问：联想存储器的工作过程。4. 指令格式的设计准则；操作码的优化方法（霍夫曼编码、扩展霍夫曼编码）。5. 指令系统的两种设计风格CISC和RISC。CISC风格的特点；RISC风格的特点。RISC风格指令系统的实现技术：窗口寄存器重叠技术、优化转

13、移技术。6. 数据类型、数据表示、数据结构的概念和关系；引入数据表示的原则（减少程序执行时间和存储容量、较好的通用性和较高的效率）；数据表示与系统结构的关系。7. 向量数据表示的形式；采用向量数据表示时，向量指令中应给出的内容。8. 自定义数据表示：带标志符数据表示、数据描述符表示。部分习题参考答案：补充题一、 某模型机的9条指令在程序中的使用频度经统计如下表所示。指令Ii使用频度piADD43%SUB13%JMP7%JOM6%STO5%SHR1%CIL2%CLA22%STP1%写出这9条指令操作码的Huffman编码、3-4扩展编码、2-7扩展编码，并计算这3种编码的平均码长。答：两种Huf

14、fman编码方案指令Ii使用频度piHuffman编码1Huffman编码234编码27编码ADD43%0000000CLA22%1010000101SUB13%11010101010JMP7%11100110001101100000JOM6%11101110101111100001STO5%11110111010001100010CIL2%1111101111010011100011SHR1%111111011111010101100100STP1%111111111111111101100101平均码长2.422.423.223.1Huffman编码1的平均码长：H0.43×10

15、.22×20.13×3(0.070.060.05)×50.02×6(0.010.01)×72.42Huffman编码2的平均码长：H0.43×1(0.220.13)×3(0.070.060.05)×40.02×5(0.010.01)×62.4234编码的平均码长：H(0.430.220.13)×3(0.070.060.050.020.010.01)×43.2227编码的平均码长：H(0.430.220.13)×2(0.070.060.050.020.010.01)&

16、#215;73.1二、某处理机的指令系统的指令字长为12位，每个地址码的长度为3位，现要求该指令系统中有：三地址指令4条、单地址指令255条、零地址指令16条。问能否用扩展编码的方式为其操作码编码？如果要求单地址指令为254条，能否对其操作码用扩展编码？说明理由。答：三地址指令格式：3位3位3位3位操作码地址码1地址码2地址码3（1）3位操作码，可以表示8条三地址指令，现只需4条，剩余4个码点。设没有二地址指令，则单地址指令可以使用6位地址码作为扩展操作码，共可有4×64256条指令，但要求有16条零地址指令，需要单地址指令留出2个码点，2562254，不能满足单地址指令的需要，所以

17、不能用扩展编码的方式为该方案的操作码编码。（2）如果要求单地址指令为254条，则可以满足单地址指令的需要，可以用扩展编码的方式为该方案的操作码编码。第三章1. 标量流水的基本概念和分类；先行控制的概念。会计算采用顺序方式和不同的重叠方式执行指令时的指令执行时间。2. 利用时空图进行标量流水线的性能分析（吞吐率、加速比、效率）3. 非线性流水线的调度方法（基本调度方法和优化调度方法）。4. 掌握流水线操作中全局相关（转移指令引起的相关）和局部相关（数据读写引起的相关）问题的解决方法。几种解决全局相关的预测算法的原理及实现。5. 向量流水线的特点。向量处理方式（横向、纵向、纵横向加工）。6. 增强

18、向量处理性能的方法（并行处理技术、链接技术）的应用及向量程序的时间计算。7. 向量编队的方法，根据向量编队计算性能参数的方法。8. 向量访问步长，解决向量机的访存冲突的方法。9. 向量处理性能的评估参数（Tvp、 R、n1/2、nv等）的定义。部分习题参考答案：3.9列举出下面循环中的所有相关，包括输出相关、反相关、真相关。for (i=2; i<100; i=i+1)ai=bi+ai;/* s1 */ci+1=ai+di; /* s2 */ai-1=2*bi; /* s3 */bi+1=2*bi;/* s4 */解：展开循环两次：ai = bi + ai; /* s1 */ci+1 =

19、 ai + di; /* s2 */ai-1 = 2 * bi; /* s3 */bi+1 = 2 * bi; /* s4 */ai+1 = bi+1 + ai+1; /* s1*/ci+2 = ai+1 + di+1; /* s2*/ai = 2 * bi+1; /* s3*/bi+2 = 2 * bi+1; /* s4*/在一次循环中：输出相关：无；反相关：无；S1&S2：ai真相关 ai = bi + ai与ci+1 = ai + di 展开循环后可见，由于循环引入的相关：S4&S4 bi+1：真相关；bi+1 = 2 * bi与bi+2 = 2 * bi+1 S4&am

20、p; S1 bi+1：真相关；bi+1 = 2 * bi与ai+1 = bi+1 + ai+1 S4& S3 bi+1：真相关；bi+1 = 2 * bi与ai = 2 * bi+1 S1&S3 ai：输出相关：ai = bi + ai 与ai = 2 * bi+1 反相关：ai = bi + ai 与ai = 2 * bi+1 S2&S3 ai：反相关：ci+1 = ai + di 与ai = 2 * bi+1 3.14 解：适合于流水线工作的算法：先计算A1B1、A2B2、A3B3和A4B4；再计算(A1B1)×(A2B2)和(A3B3)×(A4

21、B4)；最后求总的结果。完成该计算的时空图，图中阴影部分表示该段在工作。由图可见，完成7个运算用了18个t，吞吐率为： 如果不用流水线，由于一次求积需3t，一次求和需5t，则产生上述7个结果共需（4×5+3×3）t =29t。所以加速比为： 该流水线的效率可由阴影区的面积和5个段总时空区的面积的比值求得： 3.17 解：没有控制相关时流水线的平均CPI1存在控制相关时：由于无条件分支在第二个时钟周期结束时就被解析出来，而条件分支要到第3个时钟周期结束时才能被解析出来。所以：（1）若使用排空流水线的策略，则对于条件分支，有两个额外的stall，对无条件分支，有一个额外的sta

22、ll：CPI = 1+20%*2+5%*1 = 1.45 加速比S=CPI/1 = 1.45（2） 若使用预测分支成功策略，则对于不成功的条件分支，有两个额外的stall，对无条件分支和成功的条件分支，有一个额外的stall 1：CPI = 1+20%*(60%*1+40%*2) +5%*1 = 1.33 加速比S=CPI/1 = 1.33（3）若使用预测分支失败策略，则对于成功的条件分支，有两个额外的stall；对无条件分支，有一个额外的stall；对不成功的条件分支，其目标地址已经由PC 值给出，不必等待，所以无延迟：CPI = 1+20%*(60%*2 + 40%*0) +5%*1 =

23、1.29 加速比S=CPI/1 = 1.29补充题1已知有一个5段的流水线，其预约表如下：              时间功能段T1T2T3T4T5T6T7S1S2S3S4S51、试列出流水线的禁止表及原始冲突向量，画出流水线的状态图，并选择最佳的无冲突调度方案。2、按所选择的调度方案，连续输入6个任务，画出流水线的时空图并求出流水线的最大吞吐率、实际吞吐率、加速比和效率。3、如果采用非计算延迟功能段，按最小启动距离进行调度，请画出采用了预留非计算延迟功能段的预约表

24、，并判断此时该流水线的最大吞吐率是多少？在按最小启动距离进行调度时，连续输入6个任务，画出流水线的时空图并求出流水线的最大吞吐率、实际吞吐率、加速比和效率。答：1、 禁止表 F1，3，6，原始冲突向量 C（100101）流水线状态图调度方案平均延迟时间2，53.52，2，534，54.54455最佳的无冲突调度方案为 2，2，5，2、 S5112233445566S4121323454656S3112233445566S2121323454656S11231243564561234567891011121314151617181920设每个功能段的时间为t流水线的最大吞吐率 Tpmax1/3t

25、流水线的实际吞吐率 Tp6/20t0.3/t流水线的加速比：Sp6×7t/20t2. 1流水线的效率：E6×10/5*203/50.6=60%3、 最小启动距离为2，插入非计算延迟线D 时间功能段T1T2T3T4T5T6T7T8S1S2S3S4S5DD123456S5112233445566S4121324354656S3112233445566S2121324354656S1123415263456123456789101112131415161718按最小启动距离进行调度时，流水线的最大吞吐率 Tpmax1/2t 流水线的实际吞吐率 Tp6/18t1/3t0.333/t

26、流水线的加速比：Sp6×7t/18t7 /32.33流水线的效率：E6×10/5×182 /366.7%3.19 解：（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就不需要通过时间了。V6AB V7V6×C V8DE V9V8×F第四章1. 指令级并行的基本概

27、念。2. 开发指令级并行常用的方法3. 超标量、超流水、超长指令字的概念。4. 超长指令字的实现5. 循环展开和指令调度的基本方法部分习题参考答案：4.3分析：产生结果指令使用结果指令延迟时钟周期数浮点计算另外的浮点计算3浮点计算浮点数据存操作（SD）2浮点数据取操作（LD）浮点计算1浮点数据取操作（LD）浮点数据存操作（SD）0指令在流水线中执行时需要的延迟：LOOP:L.DF0,0(R1) （空转）MUL.DF0,F0,F2L.DF4,0(R2)（空转）（空转）ADD.DF0,F0,F4（空转）（空转）S.DF0,0(R2)DSUBIR1,R1,#8DSUBIR2,R2,#8BNEZR1,

28、LOOP（空转）解：将循环展开两次，进行指令调度，即可以消除延迟，其中增加寄存器F10、F14，对应一次循环中的F0和F4.代码如下：LOOP： L.D F0，0（R1）L.D F10，-8（R1）MUL.D F0，F0，F2MUL.D F10，F10，F2L.D F4，0（R2）L.DF14，-8（R2）ADD.D F0，F0，F4ADD.DF10，F10，F14DSUBI R1，R1，#16S.D F0，0(R2)DSUBI R2，R2，#16BNEZ R1，LOOPS.D F10，8(R2)4.9 解：标量流水处理机的时空图：执行完12条指令需T114t。超标量流水处理机与超长指令字处理

29、机的时空图：超标量流水处理机中，每一个时钟周期同时启动4条指令。执行完12条指令需T25t，相对于标量流水处理机的加速比为：超长指令字处理机中，每4条指令组成一条长指令，共形成3条长指令。执行完12条指令需T35t，相对于标量流水处理机的加速比为：超流水处理机的时空图：超流水处理机中，每1/4个时钟周期启动一条指令。执行完12条指令需T45.75t，相对于标量流水处理机的加速比为：补充题设系统中有多个加法器，不存在加法器的资源冲突，有3条连续指令构成的程序代码段： ADD R1，R2，R4 ADD R2，R1，1 SUB R1，R4，R5请回答：(1) 分析代码段中的存在的数据相关；(2) 采

30、用何种硬件技术可以解决这些数据相关？要求加以说明。答：I1 ADD R1，R2，R4I2 ADD R2，R1，1I3 SUB R1，R4，R5真数据相关RAW：I1与I2（R1） 先写后读名相关WAW：I1与I3（R1） 先写后写 反相关WAR：I1与I2（R2）；I2与I3（R1） 先读后写解决方法：（1）I1与I2关于R1的RAW相关，可以用定向技术解决。（2）I1与I3关于R1的WAW相关，I1与I2（R2）；I2与I3（R1）的WAR，可以用寄存器换名技术解决。将R2，R1换名为R2，R1.解决结果：I1 ADD R1，R2，R4I2 ADD R2，R1，1I3 SUB R1，R4，R

31、5第五章1. 存储器层次结构的概念；采用存储器层次结构的目的；程序局部性在存储器层次结构中的应用。2. 设置Cache主存层次、主存辅存层次的目的；Cache主存层次、主存辅存层次实现手段的不同之处。3. 命中率（失效率）、平均访问时间的概念和计算方法；如何利用速度、容量、价格的关系设计存储器层次结构各级的参数。4. Cache的基本概念；主存Cache的三种地址映象方式及实现方法。能够根据给定条件分析设计不同地址映象方式下，主存、Cache的地址和块的映像关系。5. 各种替换算法的特点和实现方法；Cache的取算法和更新策略；Cache写不命中时的调块策略。6. 程序的执行时间与Cache的

32、性能的关系7. Cache的性能分析，失效率与块大小、相联度、容量之间的关系8. 提高主存带宽的方法；并行存储器的特点；高位交叉存取和低位交叉存取的特点和实现方法。能够通过计算分析采用多体交叉技术后增加的存储器带宽和计算机性能的提高情况。部分习题参考答案：补充题 某采用组相联映像方式的Cache存储系统中，主存由M0M7共8块组成，Cache由C0C3共4块组成。Cache分为2组，每组2块。设在某程序的执行过程中，访存的主存块地址流为：M6、M2、M4、M1、M4、M6、M3、M4、M0、M5、M3、M7，主存中的内容在程序开始时未装入Cache。设Cache采用LRU替换算法。(1) 列表

33、写出程序执行过程中Cache中各块的调入、替换和命中情况。(2) 计算该程序执行过程中访问Cache的命中率。答：主存块M0、M2、M4、M6映射到Cache的0组中的C0、C1上主存块M1、M3、M5、M7映射到Cache的1组中的C2、C3上 采用LRU替换算法时Cache中各块使用情况：时刻123456789101112主存块号M6M2M4M1M4M6M3M4M0M5M3M7C066*4444*4*44*4*4*4*C122*2*2*666*0000C21111*1*1*55*7*C33333*33调入调入替换调入命中替换调入命中替换替换命中替换Cache的命中率：H3/121/40.2

34、5 5.10 解：（1）根据题意，约75%的访存为取指令。因此，分离Cache的总体失效率为：（75%×0.39%）（25%×4.82%）1.4975%； 容量为64KB的混合Cache的失效率略低一些，只有1.35%。 （2）平均访存时间公式可以分为指令访问和数据访问两部分： 平均访存时间指令所占的百分比×（读命中时间读失效率×失效开销）数据所占的百分比×（数据命中时间数据失效率×失效开销） 所以，两种结构的平均访存时间分别为： 分离Cache的平均访存时间75%×（10.39%×50）25%×（14.

35、82%×50）（75%×1.195）（25%×3.41）0.89625+0.85251.74875 混合Cache的平均访存时间75%×（11.35%×50）25%×（111.35%×50）（75%×1.675）（25%×2.675）1.256250.668751.925因此，尽管分离Cache的实际失效率比混合Cache的高，但其平均访存时间反而较低。分离Cache提供了两个端口，消除了结构相关。5.11 解：平均访问时间命中时间失效率×失效开销平均访问时间1-路=2.0+1.4% *80=3

36、.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和平均访存时间的比较结果相反，从CPU时间的角度看，直接映

37、像Cache的平均性能好一些。5.12解：采用按写分配（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

38、)+(1.3%*3)0.35次已用带宽=0.35×109/109 =35.0%（2）写回法cache访问命中,有两种情况：读命中，不访问主存；写命中，不访问主存。采用写回法，只有当修改的cache块被换出时，才写入主存；无论读写，若访问失效，则有一个块将被换出，这也有两种情况：读失效：概率5%*75%=3.75%，70%块是干净的，没有被修改过，直接调块，访存2次，30%块为脏，cache块写回后，再调块，访存4次。写失效：概率 5%×25%=1.25%，采用按写分配法：调块后写入Cache。70%块是干净的，没有被修改过，直接调块，访存2次，30%块为脏，cache块写回

39、后，再调块，访存4次。总结：如果被替换的块没有修改过，将主存中的块调入cache块中，访问主存2次；如果被替换的块修改过，则首先将修改的块写入主存，需要访问主存2次；然后将主存中的块调入cache块中，需要访问主存2次，共4次访问主存。访问命中块为脏频率访存次数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.13×10 9/10 913%第六章1. I/O系统的特点；I/O系统对计算机系统性能的

40、影响，利用加速比进行量化比较。2. 通道的概念；带有通道的I/O系统的结构；通道的工作过程。字节多路通道、选择通道、数组多路通道的特点；根据给定条件进行通道流量分析和主存频率计算。部分习题参考答案：6.8解：（1）通道实际流量为（2）由于通道的最大流量等于实际工作流量，即有可得，通道的工作周期Ts+TD = 5s。补充题有8台外设的数据传输率分别如下表所示。设备号12345678数据传输速率（B/ms）5002401007550401410现要设计一种通道，其设备选择时间TS2µs，数据传输时间TD2µs。请回答：（1） 如果按字节多路通道设计，该通道的最大流量是多少？如果希望从8台设