计算机系统结构复习重点+课后习题解答顾一禾.docx
《计算机系统结构复习重点+课后习题解答顾一禾.docx》由会员分享，可在线阅读，更多相关《计算机系统结构复习重点+课后习题解答顾一禾.docx（32页珍藏版）》请在冰点文库上搜索。
计算机系统结构复习重点+课后习题解答顾一禾
总复习
第一章
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×10－4s=0.575ms=575μs
1.8解：
（1）在多个部件可改进情况下，Amdahl定理的扩展：
已知re1＝30，re2＝20，re3＝10，Sp＝10，fe1＝0.3，fe2＝0.3，得：
得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.045T+0.2T=0.245T
那么系统中不可改进部分的执行时间在总执行时间中占的比例是：
=82%
1.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
10×2/1030＝0.0194＝1.94%
操作2
30×20/1030＝0.5825＝58.3%
操作3
35×10/1030＝0.3398＝34%
操作4
15×4/1030＝0.0583＝5.83%
根据Amdahl定律
可得
各类操作单独改进后，程序获得的加速比分别是：
操作类型
改进前各类操作的执行时间
在总的执行时间中所占的比例
各类操作单独改进后，
程序获得的加速比
操作1
1.94%
1.01
操作2
58.3%
1.17
操作3
34%
1.31
操作4
5.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位。
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
使用频度pi
ADD
43%
SUB
13%
JMP
7%
JOM
6%
STO
5%
SHR
1%
CIL
2%
CLA
22%
STP
1%
写出这9条指令操作码的Huffman编码、3-4扩展编码、2-7扩展编码，并计算这3种编码的平均码长。
答：
两种Huffman编码方案
指令Ii
使用频度pi
Huffman编码1
Huffman
编码2
3－4编码
2－7
编码
ADD
43%
0
0
000
00
CLA
22%
10
100
001
01
SUB
13%
110
101
010
10
JMP
7%
11100
1100
0110
1100000
JOM
6%
11101
1101
0111
1100001
STO
5%
11110
1110
1000
1100010
CIL
2%
111110
11110
1001
1100011
SHR
1%
1111110
111110
1010
1100100
STP
1%
1111111
111111
1110
1100101
平均码长
2.42
2.42
3.22
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位
3位
3位
3位
操作码
地址码1
地址码2
地址码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）堆栈型
指令
取指字节数
取/存数字节数
PUSHa
3
8
PUSHb
3
8
ADD；（a+b）
1
12
PUSHc
3
8
PUSHd
3
8
ADD；（c+d）
1
12
MUL；（a+b）×（c+d）
1
12
PUSHf
3
8
PUSHg
3
8
SUB；（f-g）
1
12
DIV；（a+b）×（c+d）/（f-g）
1
12
POPX；X＝（a+b）×（c+d）/（f-g）
3
8
总字节数
26
116
（2）累加器型
指令
取指字节数
取/存数字节数
LOADa
3
4
ADDb
3
4
STOREh；h＝a＋b
3
4
LOADc
3
4
ADDd；c＋d
3
4
MULh；（a+b）×（c+d）
3
4
STOREh；h＝（a+b）×（c+d）
3
4
LOADf
3
4
SUBg；f-g
3
4
STOREi；i＝f-g
3
4
LOADh；读被除数h
3
4
DIVi；（a+b）×（c+d）/（f-g）
3
4
STOREX；X＝（a+b）×（c+d）/（f-g）
3
4
总字节数
39
52
（3）寄存器－寄存器型X＝（a+b）×（c+d）/（f-g）
指令
取指字节数
取/存数字节数
LOADR1，a
3
4
LOADR2，b
3
4
ADDR1，R2；R1＝a+b
1
0
LOADR2，c
3
4
LOADR3，d
3
4
ADDR2，R3；R2＝c+d
1
0
MULR1，R2；R1＝（a+b）×（c+d）
1
0
LOADR2，f
3
4
LOADR3，g
3
4
SUBR2，R3；R2＝f-g
1
0
DIVR1，R2；R1＝（a+b）×（c+d）/（f-g）
1
0
STOREX，R1；X＝（a+b）×（c+d）/（f-g）
3
4
总字节数
26
28
指令条数
取指字节数
取数/存数字节数
需传送总字节数
堆栈型
12
26
116
142
累加器型
13
39
52
91
寄存器－寄存器型
12
26
28
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];/*s1*/
c[i+1]=a[i]+d[i];/*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）；最后求总的结果。
完成该计算的时空图，图中阴影部分表示该段在工作。
由图可见，完成7个运算用了18个△t，吞吐率为：
如果不用流水线，由于一次求积需3△t，一次求和需5△t，则产生上述7个结果共需（4×5+3×3）△t=29△t。
所以加速比为：
该流水线的效率可由阴影区的面积和5个段总时空区的面积的比值求得：
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段的流水线，其预约表如下：
时间
功能段
T1
T2
T3
T4
T5
T6
T7
S1
∨
∨
S2
∨
∨
S3
∨
∨
S4
∨
∨
S5
∨
∨
1、试列出流水线的禁止表及原始冲突向量，画出流水线的状态图，并选择最佳的无冲突调度方案。
2、按所选择的调度方案，连续输入6个任务，画出流水线的时空图并求出流水线的最大吞吐率、实际吞吐率、加速比和效率。
答：
1、禁止表F＝{1，3，6}，原始冲突向量C＝（100101）
流水线状态图
调度方案
平均延迟时间
2，5
3.5
2，2，5
3
4，5
4.5
4
4
5
5
最佳的无冲突调度方案为2，2，5，
2、
S5
1
1
2
2
3
3
4
4
5
5
6
6
S4
1
2
1
3
2
3
4
5
4
6
5
6
S3
1
1
2
2
3
3
4
4
5
5
6
6
S2
1
2
1
3
2
3
4
5
4
6
5
6
S1
1
2
3
1
2
4
3
5
6
4
5
6
1
2
3
4
5
6
7
8
9
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中。
具体实现参考下图：
通过时间应该为前者（（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
第四章
1.指令级并行的基本概念。
2.开发指令级并行常用的方法
3.超标量、超流水、超长指令字的概念。
4.超长指令字的实现
5.循环展开和指令调度的基本方法
部分习题参考答案：
4.3分析：
产生结果指令
使用结果指令
延迟时钟周期数
浮点计算
另外的浮点计算
3
浮点计算
浮点数据存操作（SD）
2
浮点数据取操作（LD）
浮点计算
1
浮点数据取操作（LD）
浮点数据存操作（SD）
0
指令在流水线中执行时需要的延迟：
LOOP:
L.DF0,0（R1）
（空转）
MUL.DF0,F0,F2
L.DF4,0（R2）
（空转）
（空转）
ADD.DF0,F0,F4
（空转）
（空转）
S.DF0,0（R2）
DSUBIR1,R1,#8
DSUBIR2,R2,#8
BNEZR1,LOOP
（空转）
解：
将循环展开两次，进行指令调度，即可以消除延迟，其中增加寄存器F10、F14，对应一次循环中的F0和F4.
代码如下：
LOOP：
L.DF0，0（R1）
L.DF10，-8（R1）
MUL.DF0，F0，F2
MUL.DF10，F10，F2
L.DF4，0（R2）
L.DF14，-8（R2）
ADD.DF0，F0，F4
ADD.DF10，F10，F14
DSUBIR1，R1，#16
S.DF0，0（R2）
DSUBIR2，R2，#16
BNEZR1，LOOP
S.DF10，8（R2）
4.9解：
标量流水处理机的时空图：
执行完12条指令需T1＝14△t。
超标量流水处理机与超长指令字处理机的时空图：
超标量流水处理机中，每一个时钟周期同时启动4条指令。
执行完12条指令需T2＝5△t，相对于标量流水处理机的加速比为：
超长指令字处理机中，每4条指令组成一条长指令，共形成3条长指令。
执行完12条指令需T3＝5△t，相对于标量流水处理机的加速比为：
超流水处理机的时空图：
超流水处理机中，每1/4个时钟周期启动一条指令。
执行完12条指令需T4＝5.75△t，相对
升级会员 