总 复 习
第一章
1. 计算机系统结构、组成、实现的基本概念和包含的内容；系统结构与软硬件功能划分的关系；计算机系统
的多级层次结构；判断某项内容属于结构、组成、实现的哪一类；判断某项内容针对不同程序员的透明性。 2. 促进系统结构发展的因素（软件、应用、器件）。
软件：实现软件可移植性的方法；系列机的概念；软件兼容的概念（向前、向后、向上、向下兼容）；模拟与仿真技术的概念；
应用：应用对系统结构的要求。 器件：系统结构下移的概念。
3. 计算机系统的分型与分类的概念。Flynn分类法 4. 系统结构设计的定量原理（Amdahl定理）；加速比的计算方法； 5. 程序访问的局部性原理（时间局部性、空间局部性）；判断系统结构中局部性原理的应用。 6. 系统评价的指标（响应时间、CPU时间、MIPS、MFLOPS）；运用CPU性能公式、平均CPI比较系统性
能。
7. 并行性的概念；并行性的等级、粒度；并行性的开发策略（时间重叠、资源重复、资源共享）； 8. 计算机系统的主要设计方法 部分习题参考答案： 1.6 解：（1）CPI ＝(45000×1＋75000×2＋8000×4＋1500×2) / 129500＝1.776
（2）MIPS速率＝f/ CPI ＝400/1.776 ＝225.225MIPS
（3）程序执行时间= (45000×1＋75000×2＋8000×4＋1500×2)／400×106
－
=5.75×104s=0.575ms=575μs
1.8 解：（1）在多个部件可改进情况下，Amdahl定理的扩展：
Sp?1f(1??fei)??eirei
已知re1＝30，re2＝20，re3＝10，Sp＝10，fe1＝0.3，fe2＝0.3，得：
1 10?1（-0.3?0.3?F3）?（0.3/30?0.3/20?F3/10）得fe3＝0.36，即部件3的可改进比例为36%。
（2）设系统改进前的执行时间为T，则3个部件改进前的执行时间为：（0.3+0.3+0.2）T = 0.8T，不可改进部分的执行时间为0.2T。
已知3个部件改进后的加速比分别为S1＝30，S2＝20，S3＝10，因此3个部件改进后的执行时间为：
'Tn?0.3T0.3T0.2T???0.045T 302010 改进后整个系统的执行时间为：Tn = 0.045T+0.2T = 0.245T
那么系统中不可改进部分的执行时间在总执行时间中占的比例是：
0.2T?0.82=82%
0.245T1.9 解：
（1）改进后，各类操作的加速比re分别是： 操作类型 各类操作的加速比re 操作1 2/1＝2 操作2 20/15＝1.33 操作3 10/3＝3.33 操作4 4/1＝4 （2）∵ 改进前系统总执行时间：10×2+30×20+35×10+15×4＝1030 ∴ 改进前各类操作时间在所有操作时间中所占的比例fe： 操作类型 操作1 操作2 操作3 操作4 根据Amdahl定律Sp?改进前各类操作的执行时间 在总的执行时间中所占的比例 10×2/1030＝0.0194＝1.94% 30×20/1030＝0.5825＝58.3% 35×10/1030＝0.3398＝34% 15×4/1030＝0.0583＝5.83% 可得
1f(1?fe)?ere各类操作单独改进后，程序获得的加速比分别是： 操作类型 操作1 操作2 操作3 操作4 改进前各类操作的执行时间 在总的执行时间中所占的比例 1.94% 58.3% 34% 5.83% 各类操作单独改进后， 程序获得的加速比 1.01 1.17 1.31 1.05 （3）在多个部件可改进情况下，Amdahl定理的扩展：
Sp?1f(1??fei)??eirei
4类操作均改进后，整个程序的加速比是：1/(1.94%/2+58.3%/1.33+34%/3.33+5.83%/4)≈1.78
补充题
1. 确定下列内容各属于哪方面的问题。
（1）机器字长为32位。 A. B. C. （2）存储器最大容量为64MB。 A. B. C. （3）存储器采用31路交叉存储方式。 A. B. C. （4）采用4M×4位的DRAM存储器芯片，组装在一块印刷电路板。 A. B. C. （5）存储器字长为32位，逻辑地址空间为4GB。 A. B. C. （6）主存储器的存储周期设计为200ns。 A. B. C. 答案中的符号的含义：A： 系统结构 B： 计算机组成 C： 计算机实现 答： AABCAB
2. 判断下列哪些内容对机器语言（含汇编语言）程序员是透明的。 1）指令寄存器 2）程序计数器 3）数据通路的宽度 4）浮点数据表示 5）行波进位加法器 6）Cache
7）控制存储器 8）中断屏蔽触发器
9）通用寄存器 10）硬盘
11）只读存储器使用EPROM芯片 12）微地址寄存器 答： 1、3、5、6、7、11、12
第二章
1. 指令系统的设计要求（完备性、有效性、兼容性、规整性、对称性、可扩充性、正交性、有利于编译）。 2. 指令系统的分类（堆栈型、累加器型、通用寄存器型）；通用寄存器型指令的特点（R－R型、R－M型、
M－M型）。
3. 操作数访问方式（按地址访问、按内容访问）；
按地址访问的编址问题：字编址、字节编址、位编址；按字节编址时的大端排序与小端排序。编址规定中的访存越界问题及其解决方法。
按内容访问：联想存储器的工作过程。
4. 指令格式的设计准则；操作码的优化方法（霍夫曼编码、扩展霍夫曼编码）。 5. 指令系统的两种设计风格CISC和RISC。
CISC风格的特点；RISC风格的特点。
RISC风格指令系统的实现技术：窗口寄存器重叠技术、优化转移技术。
6. 数据类型、数据表示、数据结构的概念和关系；引入数据表示的原则（减少程序执行时间和存储容量、较
好的通用性和较高的效率）；数据表示与系统结构的关系。
7. 向量数据表示的形式；采用向量数据表示时，向量指令中应给出的内容。 8. 自定义数据表示：带标志符数据表示、数据描述符表示。 部分习题参考答案： 补充题
一、 某模型机的9条指令在程序中的使用频度经统计如下表所示。 指令Ii ADD SUB JMP JOM STO SHR CIL CLA STP 使用频度pi 43% 13% 7% 6% 5% 1% 2% 22% 1% 写出这9条指令操作码的Huffman编码、3-4扩展编码、2-7扩展编码，并计算这3种编码的平均码长。 答：两种Huffman编码方案
指令Ii ADD CLA SUB JMP JOM STO CIL SHR STP 平均码长 使用频度pi 43% 22% 13% 7% 6% 5% 2% 1% 1% Huffman编码1 0 10 110 11100 11101 11110 111110 1111110 1111111 2.42 Huffman 编码2 0 100 101 1100 1101 1110 11110 111110 111111 2.42 3－4编码 000 001 010 0110 0111 1000 1001 1010 1110 3.22 2－7 编码 00 01 10 1100000 1100001 1100010 1100011 1100100 1100101 3.1 Huffman编码1的平均码长：
H＝0.43×1＋0.22×2＋0.13×3＋(0.07＋0.06＋0.05)×5＋0.02×6＋(0.01＋0.01)×7＝2.42 Huffman编码2的平均码长：
H＝0.43×1＋(0.22＋0.13)×3＋(0.07＋0.06＋0.05)×4＋0.02×5＋(0.01＋0.01)×6＝2.42 3－4编码的平均码长：
H＝(0.43＋0.22＋0.13)×3＋(0.07＋0.06＋0.05＋0.02＋0.01＋0.01)×4＝3.22 2－7编码的平均码长：
H＝(0.43＋0.22＋0.13)×2＋(0.07＋0.06＋0.05＋0.02＋0.01＋0.01)×7＝3.1
二、某处理机的指令系统的指令字长为12位，每个地址码的长度为3位，现要求该指令系统中有：三地址指令4条、单地址指令255条、零地址指令16条。问能否用扩展编码的方式为其操作码编码？如果要求单地址指令
为254条，能否对其操作码用扩展编码？说明理由。 答：三地址指令格式：
3位 操作码
（1）3位操作码，可以表示8条三地址指令，现只需4条，剩余4个码点。设没有二地址指令，则单地址指令可以使用6位地址码作为扩展操作码，共可有4×64＝256条指令，但要求有16条零地址指令，需要单地址指令留出2个码点，256－2＝254，不能满足单地址指令的需要，所以不能用扩展编码的方式为该方案的操作码编码。
（2）如果要求单地址指令为254条，则可以满足单地址指令的需要，可以用扩展编码的方式为该方案的操作码编码。
三、设需要计算X＝(a+b)×(c+d)/(f-g)，其中a、b、c、d、f、g均事先存放在存储器中，X为存放结果的存储器单元。请用堆栈型、累加器型、寄存器－寄存器型指令编写完成同样功能的汇编语言程序。设寄存器－寄存器型指令为二地址指令，指令格式中第一操作数为目的操作数，第二操作数为源操作数，指令的操作码占一字节（包含指令中使用的寄存器），存储器地址占二字节，操作数占四字节。请根据所编写的汇编语言程序回答下列问题：
⑴ 计算三种指令代码序列从存储器取指所需的总字节数。 ⑵ 计算三种指令代码序列取数或存数所需的总字节数。 ⑶ 比较三种结构所需的指令字节数和需传送的总字节数。
说明：减法为目的操作数减去源操作数、除法为目的操作数除以源操作数。 答：（1）堆栈型
指令 PUSH a PUSH b ADD ；(a+b) PUSH c PUSH d ADD ；(c+d) MUL ；(a+b)×(c+d) PUSH f PUSH g SUB ；(f-g) DIV ；(a+b)×(c+d) /(f-g) POP X ；X＝(a+b)×(c+d)/(f-g) 总字节数 （2）累加器型 指令 LOAD a ADD b STORE h ； h＝a＋b LOAD c ADD d ； c＋d MUL h ；(a+b)×(c+d) STORE h ； h＝(a+b)×(c+d) LOAD f SUB g ；f-g STORE i ； i＝f-g 3 3 3 3 3 3 3 3 3 3 取指字节数 4 4 4 4 4 4 4 4 4 4 取/存数字节数 取指字节数 3 3 1 3 3 1 1 3 3 1 1 3 26 取/存数字节数 8 8 12 8 8 12 12 8 8 12 12 8 116 3位 地址码1 3位 地址码2 3位 地址码3 LOAD h ；读被除数h DIV i ；(a+b)×(c+d)/(f-g) STORE X ； X＝(a+b)×(c+d)/(f-g) 总字节数
（3）寄存器－寄存器型X＝(a+b)×(c+d)/(f-g)
指令 LOAD R1 ，a LOAD R2，b ADD R1 ，R2 ；R1＝a +b LOAD R2 ，c LOAD R3，d ADD R2 ，R3 ；R2＝c +d MUL R1 ，R2 ；R1＝(a+b)×(c+d) LOAD R2 ，f LOAD R3，g SUB R2 ，R3 ；R2＝f-g 3 3 3 39 4 4 4 52 取指字节数 3 3 1 3 3 1 1 3 3 1 1 3 26 指令条数 12 13 12 取指字节数 26 39 26 取/存数字节数 4 4 0 4 4 0 0 4 4 0 0 4 28 DIV R1 ，R2 ；R1＝(a+b)×(c+d) /(f-g) STORE X，R1 ；X＝(a+b)×(c+d)/(f-g) 总字节数
堆栈型 累加器型 寄存器－寄存器型
取数/存数字节数 116 52 28 需传送总字节数 142 91 54 第三章
1. 标量流水的基本概念和分类；先行控制的概念。会计算采用顺序方式和不同的重叠方式执行指令时的指令
执行时间。
2. 利用时空图进行标量流水线的性能分析（吞吐率、加速比、效率） 3. 非线性流水线的调度方法（基本调度方法和优化调度方法）。
4. 掌握流水线操作中全局相关（转移指令引起的相关）和局部相关（数据读写引起的相关）问题的解决方法。
几种解决全局相关的预测算法的原理及实现。
5. 向量流水线的特点。向量处理方式（横向、纵向、纵横向加工）。
6. 增强向量处理性能的方法（并行处理技术、链接技术）的应用及向量程序的时间计算。 7. 向量编队的方法，根据向量编队计算性能参数的方法。 8. 向量访问步长，解决向量机的访存冲突的方法。
9. 向量处理性能的评估参数（Tvp、 R∞、n1/2、nv等）的定义。 部分习题参考答案： 3.9 解：
for (i=2; i<100; i=i+1) a[i]=b[i]+a[i] c[i+1]=a[i]+d[i]
;/* s1 */
; /* s2 */
a[i-1]=2*b[i] ; /* s3 */
b[i+1]=2*b[i] ;/* s4 */
（1）在一次循环中存在的相关：
真数据相关：
S1&S2：a[i] a[i] = b[i] + a[i]与c[i+1] = a[i] + d[i] 先写后读 没有输出相关和反相关
（2）展开循环后，可发现由于循环存在的相关： 展开循环两次：
a[i] = b[i] + a[i] ; /* s1 */ c[i+1] = a[i] + d[i] ; /* s2 */ a[i-1] = 2 * b[i] ; /* s3 */ b[i+1] = 2 * b[i] ; /* s4 */ a[i+1] = b[i+1] + a[i+1] ; /* s1＇*/ c[i+2] = a[i+1] + d[i+1] ; /* s2＇*/ a[i] = 2 * b[i+1] ; /* s3＇*/ b[i+2] = 2 * b[i+1] ; /* s4＇*/ 存在的相关：
真数据相关（先写后读）：
S1&S2：a[i]： a[i] = b[i] + a[i] 与 c[i+1] = a[i] + d[i] S1’&S2’：a[i]： a[i] = b[i] + a[i] 与 c[i+1] = a[i] + d[i] S4& S1’： b[i+1]；b[i+1] = 2 * b[i] 与 a[i+1] = b[i+1] + a[i+1] S4& S3’： b[i+1]：b[i+1] = 2 * b[i] 与 a[i] = 2 * b[i+1] S4&S4’： b[i+1]；b[i+1] = 2 * b[i] 与 b[i+2] = 2 * b[i+1] 反相关（先读后写）：
S1&S3’：a[i]： a[i] = b[i] + a[i] 与a[i] = 2 * b[i+1] S2&S3’：a[i]：：c[i+1] = a[i] + d[i] 与a[i] = 2 * b[i+1] 输出相关（先写后写）：
S1&S3’： a[i]： a[i] = b[i] + a[i] 与a[i] = 2 * b[i+1]
3.14 解：适合于流水线工作的算法：先计算A1＋B1、A2＋B2、A3＋B3和A4＋B4；再计算(A1＋B1)×(A2＋B2)和(A3＋B3)×(A4＋B4)；最后求总的结果。
完成该计算的时空图，图中阴影部分表示该段在工作。
段 5 4 3 2 1 A B C D A×B C×D A×B×C×D A=A1＋B1 B=A2＋B2 C=A3＋B3 D=A4＋B4 输0 1 2 3 入4 5 6 7 8 9 A1 A2 A3 A4 B1 B2 B3 B4 10 11 12 13 14 15 16 17 18 A×B A C B D C×D 时间
由图可见，完成7个运算用了18个△t，吞吐率为：
7 TP?
18?t如果不用流水线，由于一次求积需3△t，一次求和需5△t，则产生上述7个结果共需（4×5+3×3）△t =29△t。所以加速比为：
2 9 ? t
S??1.6118?t
该流水线的效率可由阴影区的面积和5个段总时空区的面积的比值求得： 4 ? ? 53 ? 3E??0.3225?18
3.17解：没有控制相关时，流水线的平均CPI＝1
存在控制相关时：
∵无条件分支在第二个时钟周期结束时就被解析出来，∴需要插入1个额外的stall； ∵条件分支要到第3个时钟周期结束时才能被解析出来，∴需要插入2个额外的stall。 根据采用减少分支延迟的方法不同，所得的加速比不同。
（1）采用排空流水线的策略时，对无条件分支，有1个额外的stall；对于条件分支，有2个额外的stall：
CPIA = 1+20%×2+5%×1 = 1.45 加速比S=CPIA/1 = 1.45
（2）采用预测分支成功策略时，对无条件分支和成功的条件分支，有1个额外的stall，对于失败的条件分
支，有2个额外的stall（需作废预取的成功分支指令）： CPIA = 1+20%×(60%×1+40%×2) +5%×1 = 1.33 加速比S= CPIA /1 = 1.33
（3）采用预测分支失败策略时，对无条件分支，有1个额外的stall，对于成功的条件分支，有2个额外的
stall，（需作废预取的失败分支指令）；对失败的条件分支，由于预测失败分支，因此分支指令相当于一条普通指令，其目标地址已经由PC给出，流水线正常流动，不必等待，所以不需要延迟： CPIA = 1+20%×(60%×2 + 40%×0) +5%×1 = 1.29 加速比S= CPIA /1 = 1.29
补充题
已知有一个5段的流水线，其预约表如下：
时间 功能段 S1 S2 S3 S4 S5 T1 ∨ ∨ T2 ∨ T3 ∨ ∨ T4 ∨ ∨ T5 ∨ T6 T7 ∨ ∨
1、试列出流水线的禁止表及原始冲突向量，画出流水线的状态图，并选择最佳的无冲突调度方案。
2、按所选择的调度方案，连续输入6个任务，画出流水线的时空图并求出流水线的最大吞吐率、实际吞吐率、加速比和效率。
答：1、 禁止表 F＝{1，3，6}，原始冲突向量 C＝（100101） 流水线状态图
5 100101 5 4 2 5 100111 4 101101 2 101111 5 调度方案 2，5 2，2，5 4，5 4 5 最佳的无冲突调度方案为 2，2，5， 2、
S5 S4 S3 S2 1 平均延迟时间 3.5 3 4.5 4 5 1 2 3 1 1 2 2 3 6 2 1 3 2 1 7 2 3 3 2 3 8 3 4 3 4 3 4 5 4 4 5 4 5 4 6 4 5 5 6 5 4 6 5 4 5 6 6 6 5 6 5 6 6 6 1 1 2 2 1 4 1 2 3 2 9 S1 1 3 5 10 11 12 13 14 15 16 17 18 19 20 设每个功能段的时间为△t 流水线的最大吞吐率 Tpmax＝1/3△t
流水线的实际吞吐率 Tp＝6/20△t≈0.3/△t 流水线的加速比：Sp＝6×7△t/20△t≈2. 1 流水线的效率：E＝6×10/5*20＝3/5＝0.6=60%
3.19 解：（1）设A＋B的中间结果放在V6中，（A＋B）×C的最后结果放在V7中，D＋E的中间结果放在V8中，（D＋E）×F的最后结果放在V9中。具体实现参考下图：
V0AV1BV6V2CV7向量加向量乘V3DV4EV8V5FV9 通过时间应该为前者（（A＋B）×C）通过的时间：
T通过= (1+2+1)+(1+3+1) =9（拍）
（2）在做完（A＋B）×C之后，作（C＋D）×E就不需要通过时间了。
V6←A＋B V7←V6×C
V8←D＋E
V9←V8×F
T?T通过＋（8－1）?8?24（拍）?1200(ns)32TP??26.67MFLOPST
第四章
1. 指令级并行的基本概念。 2. 开发指令级并行常用的方法
3. 超标量、超流水、超长指令字的概念。 4. 超长指令字的实现
5. 循环展开和指令调度的基本方法 部分习题参考答案： 4.3分析：
产生结果指令 浮点计算 浮点计算 使用结果指令 另外的浮点计算 浮点数据存操作（SD） 浮点计算 延迟时钟周期数 3 2 1 0 浮点数据取操作（LD） 浮点数据取操作（LD） 浮点数据存操作（SD） 指令在流水线中执行时需要的延迟：
LOOP: L.D F0,0(R1) （空转） MUL.D F0,F0,F2 L.D F4,0(R2)
（空转） （空转）
ADD.D F0,F0,F4
（空转） （空转）
S.D F0,0(R2) DSUBI R1,R1,#8 DSUBI R2,R2,#8 BNEZ R1,LOOP
（空转）
解：将循环展开两次，进行指令调度，即可以消除延迟，其中增加寄存器F10、F14，对应一次循环中的F0和F4.
代码如下： LOOP： L.D F0，0（R1）
L.D F10，-8（R1） MUL.D F0，F0，F2 MUL.D F10，F10，F2 L.D F4，0（R2） L.D F14，-8（R2） ADD.D F0，F0，F4
ADD.D DSUBI S.D DSUBI BNEZ S.D F10，F10，F14 R1，R1，#16 F0，0(R2) R2，R2，#16 R1，LOOP F10，8(R2)
4.9 解：标量流水处理机的时空图：
执行 1 2 3 4 5 6 7 8 9 10 11 12 分析 1 2 3 4 5 6 7 8 9 10 11 12 取指 1 2 3 4 5 6 7 8 9 10 11 12 14 时间 执行完12条指令需T1＝14△t。
超标量流水处理机与超长指令字处理机的时空图：
4 8 12 执行 3 7 11 2 6 10 1 5 9 4 8 12 4 8 12 执行 3 7 11 2 6 10 1 5 9 1 5 9 分析 3 7 11 2 6 10 1 5 9 4 8 12 分析 取指 1 5 9 5 时间 取指 3 7 11 2 6 10 1 5 9 超长指令字处理机时空图 5 时间 超标量处理机时空图
超标量流水处理机中，每一个时钟周期同时启动4条指令。执行完12条指令需T2＝5△t，相对于标量流水处理机的加速比为：
T14?tS2?1??2.8
T25?t超长指令字处理机中，每4条指令组成一条长指令，共形成3条长指令。执行完12条指令需T3＝5△t，相
对于标量流水处理机的加速比为：
T14?tS3?1??2.8
T35?t超流水处理机的时空图：
4 8 12 7 11 6 10 执行 1 4 3 2 1 4 3 2 5 9 8 12 7 11 分析 6 10 5 9 8 12 取指 3 2 1 7 11 6 10 5 9 4 5 5.75 时间
超流水处理机中，每1/4个时钟周期启动一条指令。执行完12条指令需T4＝5.75△t，相对于标量流水处理机的加速比为：
T14?tS4?1??2.435
T45.75?t
补充题
设系统中有多个加法器，不存在加法器的资源冲突，有3条连续指令构成的程序代码段： ADD R1，R2，R4 ADD R2，R1，1 SUB R1，R4，R5 请回答：
(1) 分析代码段中的存在的数据相关；
(2) 采用何种硬件技术可以解决这些数据相关？要求加以说明。 答：
I1 ADD R1，R2，R4 I2 ADD R2，R1，1 I3 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，R4 I2 ADD R2′，R1，1 I3 SUB R1′，R4，R5
第五章
1. 存储器层次结构的概念；采用存储器层次结构的目的；程序局部性在存储器层次结构中的应用。
2. 设置Cache—主存层次、主存—辅存层次的目的；Cache—主存层次、主存—辅存层次实现手段的不同之处。
3. 命中率（失效率）、平均访问时间的概念和计算方法；如何利用速度、容量、价格的关系设计存储器层次结
构各级的参数。
4. Cache的基本概念；主存—Cache的三种地址映象方式及实现方法。能够根据给定条件分析设计不同地址
映象方式下，主存、Cache的地址和块的映像关系。
5. 各种替换算法的特点和实现方法；Cache的取算法和更新策略；Cache写不命中时的调块策略。 6. 程序的执行时间与Cache的性能的关系
7. Cache的性能分析，失效率与块大小、相联度、容量之间的关系
8. 提高主存带宽的方法；并行存储器的特点；高位交叉存取和低位交叉存取的特点和实现方法。能够通过计
算分析采用多体交叉技术后增加的存储器带宽和计算机性能的提高情况。 部分习题参考答案： 补充题
某采用组相联映像方式的Cache存储系统中，主存由M0～M7共8块组成，Cache由C0～C3共4块组成。Cache分为2组，每组2块。设在某程序的执行过程中，访存的主存块地址流为：M6、M2、M4、M1、M4、M6、M3、M4、M0、M5、M3、M7，主存中的内容在程序开始时未装入Cache。设Cache采用LRU替换算法。
(1) 列表写出程序执行过程中Cache中各块的调入、替换和命中情况。 (2) 计算该程序执行过程中访问Cache的命中率。
答：主存块M0、M2、M4、M6映射到Cache的0组中的C0、C1上
主存块M1、M3、M5、M7映射到Cache的1组中的C2、C3上 采用LRU替换算法时Cache中各块使用情况：
时刻 C0 C1 C2 C3 1 6 调入 2 6* 2 调入 3 4 2* 替换 4 4 2* 1 调入 5 4 2* 1 命中 6 4* 6 1 替换 7 4* 6 1* 3 调入 8 4 6* 1* 3 命中 9 4* 0 1* 3 替换 10 4* 0 5 3* 替换 11 4* 0 5* 3 命中 12 4* 0 7* 3 替换 主存块号 M6 M2 M4 M1 M4 M6 M3 M4 M0 M5 M3 M7 Cache的命中率：H＝3/12＝1/4＝0.25
5.10 解：（1）根据题意，约75%的访存为取指令。
因此，分离Cache的总体失效率为：（75%×0.39%）＋（25%×4.82%）＝1.4975%； 容量为64KB的混合Cache的失效率略低一些，只有1.35%。 （2）平均访存时间公式可以分为指令访问和数据访问两部分：
平均访存时间＝指令所占的百分比×（读命中时间＋读失效率×失效开销）＋数据所占的百分比×（数据命中时间＋数据失效率×失效开销）
所以，两种结构的平均访存时间分别为：
分离Cache的平均访存时间＝75%×（1＋0.39%×50）＋25%×（1＋4.82%×50） ＝（75%×1.195）＋（25%×3.41）＝0.89625+0.8525＝1.74875
混合Cache的平均访存时间＝75%×（1＋1.35%×50）＋25%×（1＋1＋1.35%×50） ＝（75%×1.675）＋（25%×2.675）＝1.25625＋0.66875＝1.925
因此，尽管分离Cache的实际失效率比混合Cache的高，但其平均访存时间反而较低。分离Cache提供了两个端口，消除了结构相关。
5.11 解：平均访问时间＝命中时间＋失效率×失效开销
平均访问时间1-路=2.0+1.4% *80=3.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.344IC CPU time 2-way=IC(2.2*2+1.2*0.01*80)＝5.36IC 相对性能比：
CPUtime?2wayCPUtime?1way?5.36/5.344=1.003
和平均访存时间的比较结果相反，从CPU时间的角度看，直接映像Cache的平均性能好一些。
5.12解：（1）写直达cache访问命中，有两种情况：
读命中，不访问主存；
写命中，更新cache和主存，访问主存1次（∵主存每次只能读或写一个字）。 访问失效，有两种情况：
读失效，将主存中的块调入cache中，访问主存2次（∵一个主存块为两个字）；
写失效，采用按写分配，即当Cache写不命中时，先把所写单元所在的块从主存调入Cache，然后再写入Cache。
访问主存次数：将所写的块调入cache，访问主存2次，∵写直达，∴写入Cache的同时要将修改的数据写入主存，再访问主存1次，共3次。
∵写直达，cache与主存信息一致，∴主存块调入cache时，不用考虑块的写回。 根据上述分析，各操作占总读写操作的比例和访存次数如下表：
访问命中 Y Y N N
访问类型 读 写 读 写 某操作占总读写操作的比例 95%×75%＝71.25% （75%是读操作） 95%×25%＝23.75% （25%是写操作） 5%×75%＝3.75% 5%×25%＝1.25% 访存次数 0 1 2 3 根据上表可得一次访存请求后，真正的平均访存次数：
平均访存次数＝(71.25%×0)+( 23.75%×1)+( 3.75%×2)+ (1.25%×3) ＝0.35次
CPU发出访存请求的速率为109字/s，即带宽为109字/s，其中真正访存的次数是0.35×109次， ∴ 已用带宽所占的比例＝0.35×109/109 ＝35.0% （2）写回法cache访问命中，有两种情况：
读命中，不访问主存； 写命中，不访问主存。
写回法cache访问失效，无论读写，均需从主存调块，同时要考虑被修改过的块被替换时，需要写回主存，存在两种情况：
读失效，将主存中的块调入cache中，同时要考虑Cache块被替换时写回主存的情况： 读失效的概率：5%×75%=3.75%，
∵在任何时候，Cache中有30％的块被修改过，∴70%块没有被修改过，是干净的。 替换时，对于70%的干净块，直接调块，访存2次；
对于30%的脏块，需将cache块写回主存后，再调块，访存4次。
写失效：采用按写分配，即当Cache写不命中时，先把所写单元所在的块从主存调入Cache，然后再写入Cache。
写失效的概率：5%×25%=1.25%，
替换时，对于70%的干净块，从主存直接调块，访存2次；
对于30%的脏块，脏cache块写回主存访存2次，再从主存调块，访存2次，共访存4次。
根据上述分析，访问Cache不命中时各操作占总读写操作的比例和访存次数如下表： 访问命中 访问类型 块为脏 某操作占总读写操作的比例 访存次数 Y Y N N N N
读 写 读 读 写 写 X X N（干净） Y（脏） N（干净） Y（脏） 95%×75%＝71.25% （75%是读操作） 95%×25%＝23.75% （25%是写操作） 5%×75%×70%＝2.625% 5%×75%×30%＝1.125% 5%×25%×70%＝0.875% 5%×25%×30%＝0.375% 0 0 2 4 2 4 根据上表可得一次访存请求后，真正的平均访存次数：
平均访存次数＝71.25％×0＋23.75%×0＋2.625%×2＋1.125%×4＋0.875%×2+0.375%×4
＝0.13次
∴ 已用带宽所占的比例＝0.13×109/109 ＝13.0%
第六章
1. I/O系统的特点；I/O系统对计算机系统性能的影响，利用加速比进行量化比较。 2. 通道的概念；带有通道的I/O系统的结构；通道的工作过程。
字节多路通道、选择通道、数组多路通道的特点；根据给定条件进行通道流量分析和主存频率计算。 部分习题参考答案：
6.5解：本题要求计算通道的吞吐率，而且机器有一个多路通道，这就有两种可能：字节多路通道和数组多路通道。因为如果将多路通道组织成数组多路通道，某个时刻通道只能为一台设备传送数据，所以它的传输率是所有设备的传输率的最大值，而如果将它组织成字节多路通道，该通道的最大传输率就是所有设备的传输率之和。 所以在本题中，从性能上考虑，应组织成字节多路通道形式。 所以此类通道的最大传输率为：
（1）fBYTE＝∑fi＝f打印机传输率×2＋f读卡机传输率×2＋f终端传输率×10＝25.6KBps （i＝1..14）
（2）两个选择通道连接的设备相同，所以只要计算其中一个通道的传输率既可。因为磁盘机的传输率大于磁带机。所以此类通道的传输率为：
max{800，200}＝800KBps
所以本系统的最大数据传输率为： f系统＝2×800＋25.6＝1625.6KBps。
6.8解：（1）通道实际流量为
fbyte??fi?50?50?40?25?25?10?200B/ms
i?16（2）由于通道的最大流量等于实际工作流量，即有
1fmax?byte??200B/ms
TS?TD可得，通道的工作周期Ts+TD = 5μs。
补充题
有8台外设的数据传输率分别如下表所示。 设备号 数据传输速率（B/ms） 1 500 2 240 3 100 4 75 5 50 6 40 7 14 8 10 现要设计一种通道，其设备选择时间TS＝2μs，数据传输时间TD＝2μs。请回答： （1） 如果按字节多路通道设计，该通道的最大流量是多少？如果希望从8台设备中至少选择4台外设同时连
接到该通道上，而且尽可能多连接速率高的设备，那么应选择哪些设备连接到该通道上？
（2） 如果按数组多路通道设计，且一次传送定长数据块的大小为512B，则该通道的最大流量是多少？从8
台设备中可以选择哪些设备连接到该通道上？
答：
（1）如果按字节多路通道设计，该通道的最大流量是 11f???250KB/s?设备流量之和maxbyte
TS?TD2?s?2?
为满足字节多路通道的流量设计要求，可选择3、4、5、7、8同时连接到该通道上。 （2）如果按数组多路通道设计，该通道的最大流量是
11f???0.499B/?s?499KB/s maxselectTS2?s?TD?2
n512
为满足数组多路通道的流量设计要求，除1以外，所有设备均可同时连接到该通道上。
第七章
1． 阵列机的基本结构与主要特点。
2． 计算机系统互连网络及互连函数；互连网络的主要性能参数（网络规模、结点度、连接数、网络距离、对
称性、等分宽度等），
3． 常见的静态互连网络的拓扑结构及其参数。
4． 互连网络设计时应考虑的因素（定时方式、控制策略、交换方式、网络拓扑）。
5． 常用的单级互连网络及互连函数（交换、混洗、蝶式、反位序、移数、PM2I、混洗交换）；会根据互连函
数分析输入结点与输出结点的关联关系。
6． 常用的多级互连网络（多级混洗交换网络、多级立方体网络）；会设计画出多级互连网络的网络结构，根据
输入结点与输出结点的关联关系分析给出各开关的控制信号，分析网络的冲突情况。 部分习题参考答案： 7.3 解：（1）共有32个处理机，表示处理机号的二进制地址应为5位。
E2（12）＝E2（01100）＝01000（8） S（8）＝S（01000）＝10000（16） B（9）＝B（01001）＝11000（24） PM2I+3（28）＝28＋23 mod32 ＝4 E0（S（4））＝E0（S（00100））＝01001（9） S（E0（18））＝S（E0（10010））＝S（10011）＝00111（7）
（2）2n个结点的均匀洗牌交换网的网络直径为2n-1，32个结点的均匀洗牌交换网的网络直径为9。 从5号处理机发送数据到7号处理机，最短路径要经过6步： 00101→00100→01000→01001→10010→10011→00111
（3）网络直径是3，结点度是9，与2号处理机距离最远的是13、15、21、23号处理机。
7.6 解：（1）N个输入的不同排列数为N！。
（2）N个输入端、输出端的Omega网络有n＝log2N级开关级，每级开关级有N/2个2×2的4功能开关，总共有（N/2）log2N个开关。置换连接是指网络的输入端与输出端的一对一连接，故只考虑2×2开关的2个功能状态，即直送与交叉。网络采用单元控制，因此，每个开关都根据连接要求处于2个功能状态中的一种状态，所以，由（N/2）log2N个开关组成的Omega网络的开关状态的种数为：
（N/2）log2N2?NN/2
一种网络开关状态实现Omega网络的一种无冲突的置换连接，所以，一次使用Omega网络可以实现的无冲突的置换连接有NN/2种。
（3）若N=8，则一次通过能实现的置换数占全部排列的百分比为： NN/2844096???10.16% N!8!40320
7.7 解：Omega网络使用的2×2开关有4种状态：直送、交叉、上播、下播。分别画出实现P6播送给P0~P4、 P3播送给P5~P7要求使用的开关状态，可见它们的播送要求没有冲突，因此它们的播送可以同时实现。同时实现的Omega网络开关状态图如下所示。
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7