计算机系统结构复习重点+课后习题解答顾一禾.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,相对