系统结构答案.docx
《系统结构答案.docx》由会员分享，可在线阅读，更多相关《系统结构答案.docx（45页珍藏版）》请在冰点文库上搜索。
系统结构答案
第一章
1.26假设高速缓存Cache工作速度为主存的5倍，且Cache被访问命中的概率为90％，那么，采用Cache后能使整个存储系统获得多高的加速比?
T01
解：
根据Amdahl定理有：
Sn==；结合题意：
Cache工作速度为
Tn（1–Fe）+Fe/Se
主存的5倍，相当于改进存储器后获得的加速比为5，即Se=5；Cache被访问命中的概率为90％，相当于访问存储器的时间有90％化在Cache上，即Fe=0.9。
所以Sn=1/[（1-0.9）+0.9/5]=3.57
1.27设计指令存储器有两种不同方案：
一种是采用价格较贵的高速存储器芯片，另一种是采用价格便宜的低速存储器芯片。
采用后一方案时，用同样的经费可使存储器总线带宽加倍，从而每隔2个时钟周期可取出2条指令（每条指令为单字长32位）。
而采用前一方案时，每一个时钟周期取出一条单字长指令。
由于访存局部性原理，当取出2个指令字时，通常这2个指令字都要使用，但仍有25％的时钟周期中，取出的2个指令字中仅有1个指令字是有用的。
试问采用这两种实现方案所构成的存储器带宽是多少？
解：
带宽是指单位时间内处理的二进制位数，相当于频率，用f表示。
采用方案A时，存取指令的CPIa=1时钟周期/指令字，即：
fa=1/CPIa×指令字长=1×32=32位/时钟周期。
采用方案B时，存取指令的CPIb=0.75×2/2+0.25×2/1=1.25时钟周期/指令字，即：
fa=1/CPIa×指令字长=0.8×32=25.6位/时钟周期。
1.28某工作站采用时钟频率为15MHz、处理速率为10MIPS的处理机来执行一个测试程序。
假定每次存储器存取为1个时钟周期，试问：
（1）此计算机的有效CPI是多少?
（2）假定将处理机的时钟频率提高到30MHz，但存储器的工作速率不变，这样，每次存储器存取需要2个时钟周期。
如果30％指令每条只需要一次存储器存取操作，另外5％指令每条需要二次存储器存取操作，假定测试程序的指令数不变，并与原工作站兼容，试求改进后的处理机CPI和MIPS。
解：
（1）由MIPS=时钟频率/（CPI×106），则有：
CPIA=时钟频率/（MIPS×106）=1.5。
（2）当时钟频率为15MHZ时，假设不进行存储操作指令的CPI为x，则要进行一次存储操作指令的CPI为1+x，要进行二次存储操作指令的CPI为2+x，因此有：
1.5=x×65%+（1+x）×30%+（2+x）×5%解得x=1.1
当时钟频率为30MHZ时，不进行存储操作指令的CPI不变为1.1，要进行一次存储操作指令的CPI为2+x=3.1，要进行二次存储操作指令的CPI为4+x=5.1，因此平均CPI为：
CPIB=1.1×65%+3.1×30%+5.1×5%=1.9
所以MIPSB=时钟频率/（CPIB×106）=（30×106）/（1.9×106）=15.8MIPS
1.29某计算机Cache能存放2000条指令。
假设10%的指令承担了90%时间的指令访问，而且这10%指令中每条指令的执行时间相同。
如果要执行的某程序共50000条指令，当计算机执行该程序时，在Cache中能访问到的指令的概率是多少？
解：
由题意可知：
45000条指令承担10%时间的指令访问，5000条指令承担90%时间的指令访问。
显然5000条指令被频繁使用，设平均使用次数为X；另外45000条指令仅使用一次。
则有：
45000:
0.1=5000X:
0.9解得X=81
所以该程序执行指令的条数为Y=45000+5000×81=450000
假设频繁使用的5000条指令均匀分布于程序之中，即每次调入Cache的2000条指令有200条是频繁使用的。
另假设每次调入Cache的2000条指令中的1800条均被使用了一次。
所以执行该程序时Cache中能访问到的指令的概率为:
（450000-50000/2000）÷450000≈100%
1.30有一台计算机，不同类型指令在理想Cache（无访问失败）与实际Cache（有访问失败）两种情况下的性能如下表。
求理想Cache相对于实际Cache的加速比？
指令类型出现频率理想CacheCPI实际CacheCPI
运算指令40%13
取数指令20%28
存数指令15%28
控制指令25%24
解：
理想Cache情况下指令的平均时钟周期数CPI为：
CPI理想=
=1×40%+2×20%+2×15%+2×25%=1.6
实际Cache情况下指令的平均时钟周期数CPI为：
CPI实际=
=3×40%+8×20%+8×15%+4×25%=5.0
S=实际CacheCPU执行时间/理想CacheCPU执行时间
=（IC×时钟周期×CPI实际）/（IC×时钟周期×CPI理想）=CPI/CPIA=5.0/1.6
=3.12
1.31假设在一台40MHz处理机上运行测试程序共有200000条指令，由4类指令组成。
已知指令的CPI和所各占比例如下表。
指令类型指令比例CPI
算逻运算60%1
Cache命中存取18%2
控制指令12%4
Cache末命中访主存10%8
（1）计算处理机运行该程序的平均CPI。
（2）根据
（1）所得CPI，计算相应的MIPS速率。
解:
（1）CPI=
=1×60%+2×18%+4×12%+8×10%=2.2
（2）MIPS=时钟频率/（CPI×106）=40×106/（2.2×106）=18.19
1.32已知4个程序在A、B、C三台计算机上的执行时间（秒）分别如下表，假设每个程序都有100×106条指令要执行，计算这3台计算机对每个程序的MIPS速率。
根据这些速率值，你能否得出这3台计算机相对性能的明确结论？
你能否找到一种将它们排序的方法？
试说明理由。
程序计算机A计算机B计算机C
程序111020
程序2100010020
程序3500100050
程序4100800100
解：
（1）由MIPS的定义有：
MIPS=Ic/（Tcpu×106）=100×106/（Tcpu×106）=100/Tcpu。
根据上表中列出的Tcpu则可计算出相应的MIPS如下表所示。
程序计算机A计算机B计算机C
程序1100105
程序20.115
程序30.20.12
程序410.1251
（2）由于MIPS与指令值、指令使用的频率等有关，在同一台机器上运行不同的程序，得出不同的速率MIPS，因此不能仅用MIPS来评价计算机性能的优劣。
而应用执行程序的算术平均Tcpu来评价比较好。
TcpuA=（1+1000+500+100）/4=400.25
TcpuB=（10+100+1000+800）/4=477.5
TcpuC=（20+20+50+100）/4=47.5
所以性能排序为：
C>A>B。
第二章
2.25浮点数系统使用的阶码基值re=2，阶值位数q=2，尾数基值rm=10，尾数位数p′=1，即按照使用的二进制位数来说，等价于p=4。
计算在非负阶、正尾数、规格化情况下的最小尾数值、最大尾数值、最大阶值、可表示的最小值和最大值及可表示数的个数。
解:
最小尾数值：
rm-1=10-1=0.1
最大尾数值：
1-rm-p′=1-10-1=0.9
最大阶值：
2q-1=3
可表示数的最小值：
1×rm-1=10-1=0.1
可表示数的最大值：
rm2q-1×（1-rm-p′）=103（1-10-1）=900
可表示数的个数：
2q×rmp′（rm-1）/rm=22×101（10-1）/10=36
2.26一个处理机有I1～I10共10条指令，经统计，各指令在程序中出现的概率如下：
I1：
0.25I2：
0.20I3：
0.15I4：
0.10I5：
0.08
I6：
0.08I7：
0.05I8：
0.04I9：
0.03I10：
0.02
（1）计算这10条指令的操作码最短平均长度。
（2）写出这10条指令的Huffman编码，并计算操作码编码的平均长度和信息冗余量。
（3）采用3/7扩展编码法和2/8扩展编码法编写这10条指令的操作码。
并分别计算编码的平均长度和信息冗余量。
说明哪一种扩展编码较好的理由。
解：
（1）∵操作码编码的最短平均长度为：
H=-
×log2pi
∴H=－（0.25log20.25＋0.20log20.20＋0.15log20.15＋0.10log20.10＋0.08log20.08
＋0.08log20.08＋0.05log20.05＋0.04log20.04＋0.03log20.03＋0.02log20.02）
=2.96（位）
（2）根据给出的使用频度，在构造Huffman树的过程中，有两个结点可供合并，因此可生成不同的Huffman树，其中给出一棵如图所示，相应的Huffman编码如表所示。
10
1010
I2I1
1010
10I410I3
10I610I5
I10I9I8I7
Ii
Pi
Huffman编码
Li
2-5编码（3/7）
Li
2-4编码（2/8）
Li
I1
0．25
00
2
00
2
00
2
I2
0．20
10
2
01
2
01
2
I3
0．15
010
3
10
2
1000
4
I4
0．10
110
3
11000
5
1001
4
I5
0．08
0110
4
11001
5
1010
4
I6
0．08
1110
4
11010
5
1011
4
I7
0．05
01110
5
11011
5
1100
4
I8
0．04
01111
5
11100
5
1001
4
I9
0．03
11110
5
11101
5
1110
4
I10
0．02
11111
5
11110
5
1111
4
∴Huffman编码的平均长度为：
l=
×li
l=0.25×2＋0.20×2＋0.15×3＋0.10×3＋0.08×4＋0.08×4＋0.05×5
＋0.04×5＋0.03×5＋0.02×5=2.99（位）
Huffman编码的信息冗余量为：
R=1-H/l=（1－2.96/2.99）×100%=1.0%
（3）3/7扩展编码和2/8扩展编码如表所示。
3/7扩展编码要求短码码点数为3，长码码点数为7。
所以短码长取2位，有码点22=4个，用一个作扩展标志；长码长取3位，有码点23=8个，有一个未被利用，即有一个余码点。
编码的平均长度为：
l=（0.25＋0.20＋0.15）×2＋（0.10＋0.08＋0.08＋0.05＋0.04＋0.03＋0.02）×5=3.2（位）
3/7扩展编码的信息冗余量为：
R=1－H/l=（1－2.96/3.2）×100%=7.5%
2/8扩展编码要求短码码点数为2，长码码点数为8。
所以短码长取2位，有码点22=4个，用二个作扩展标志；长码长取2位，有码点22×2=8个，码点全部被利用，即没有多余码点。
l=（0.25＋0.20）×2＋（0.15＋0.10＋0.08＋0.08＋0.05＋0.04＋0.03＋0.02）×4=3.1（位）
2/8扩展编码的信息冗余量为：
R=1－H/l=（1－2.96/3.1）×100%=4.5%
可见，2/8扩展编码优于3/7扩展编码。
2.27经统计，某种处理机14条指令的使用频度分别为：
0.01，0.15，0.12，0.03,0.02,0.04,0.02,0.04,0.01,0.13,0.15,0.14，0.11,0.03。
分别给出它们的定长码、Huffman编码、只能有两种码长且平均长度尽可能短的扩展编码，并分别计算三种编码的平均长度。
0.150.150.140.130.120.110.040.040.030.030.020.020.010.01
2.28用于文字处理的某专用机，每个文字符用4位十进制数字（0～9）编码表示，空格用︼表示。
在对传送的文字符和空格进行统计后，得出它们的使用频度如下：
︼：
0.200:
0.171:
0.062:
0.083:
0.114:
0.08
5:
0.056:
0.087:
0.138:
0.039:
0.01
（1）若对数字0～9和空格采用二进制编码，试设计编码平均长度最短的编码。
（2）若传送106个文字符号，且每个文字符号后均自动跟一个空格，按最短的编码，共需传送多少个二进制位？
若传送波特率为9600bPS，共需传送多少时间？
（3）若对数字0～9和空格采用4位定长码编码，重新计算问题
（2）。
解：
（1）∵操作码编码的平均长度最短为Huffman编码，生成的Huffman树，如图所示，相应的Huffman编码如表所示。
l=
×li=3.23（位）。
（2）根据题意，每个字符的二进制码的平均长度为：
3.23×（4＋1）=16.15（位）。
若要传输106个字符，则要传输二进制位数为：
106×16.15=1.615×107（位）
若波特率为56Kb/s，则传输时间为：
1.615×107/（56×103）=288（s）。
（3）当采用四位定长编码时，则需要传输二进制位数为：
106×4（4＋1）=2×107（位），传输时间为：
2×107/（56×103）=357（s）。
10
1010
︼
101010
370
51642
Ii
Pi
Huffman编码
Li
︼
0．20
10
2
0
0．17
000
3
7
0．13
010
3
3
0．11
110
3
2
0．08
0010
4
4
0．08
0011
4
6
0．08
0110
4
1
0．06
0111
4
5
0．05
1110
4
8
0．03
11110
5
9
0．01
11111
5
98
2.29一台模型机共有7条指令，各指令的使用频度分别为：
35%，25%，20%，10%，5%，3%，2%，有8个通用数据寄存器，2个变址寄存器。
（1）要求操作码的平均长度最短，请设计操作码的编码，并计算操作码编码的平均长度。
（2）设计8位字长的寄存器——寄存器型指令3条，16位字长的寄存器一存储器型变址寻址方式指令4条，变址范围不小于正、负127。
请设计指令格式，并给出指令各字段的长度和操作码的编码。
2.30一台模型机共有7条指令，各指令的使用频度分别为：
35%，25%，20%，10%，5%，3%，2%，有8个通用数据寄存器，2个变址寄存器。
（1）要求操作码的平均长度最短，请设计操作码的编码，并计算操作码编码的平均长度。
（2）设计8位字长的寄存器—寄存器型指令3条，16位字长的寄存器一存储器型变址寻址方式指令4条，变址范围不小于正、负127。
请设计指令格式，并给出指令各字段的长度和操作码的编码。
解：
（1）∵操作码编码的平均长度最短为Huffman编码，生成的Huffman树如图所示，相应的Huffman编码如表所示。
l=
×li=2.35（位）
Ii
Pi
Huffman编码
Li
2-4编码（3/4）
Li
I1
0．35
00
2
00
2
I2
0．25
01
2
01
2
I3
0．20
10
2
10
2
I4
0．10
110
3
1100
4
I5
0．05
1110
4
1101
4
I6
0．03
11110
5
1110
4
I7
0．02
11111
5
1111
4
（2）由于通用寄存器有8个，则指令中通用寄存器字段应为3位；操作码字段2位可有4个码点，用三个码点表示三条指令，另一个码点则作为扩展标志。
所以3条8位长的寄存器—寄存器型指令格式如下：
由于变址寄存器有2个，则指令中变址寄存器字段应为1位；变址范围-127～+127，则指令中相对位移字段应为8位；操作码字段前2位可有4个码点，用三个码点表示三条指令，另一个码点则作为扩展标志。
扩展2位正好可表示四条指令，操作码字段则为4位。
所以4条16位长的寄存器—存储器型指令格式如下：
特别地，当采用3/4扩展编码时，使用频度高的用短码表示，使用频度低的用长码表示，其相应的编码如表所示。
2.31某处理机的指令字长为16位，有二地址指令、一地址指令和零地址指令3类，每个地址字段的长度均为6位。
（1）如果二地址指令有15条，一地址指令和零地址指令的条数基本相等。
问一地址指令和零地址指令各有多少条？
并为这3类指令分配操作码。
（2）如果指令系统要求这3类指令条数的比例大致为1：
9：
9，问这3类指令各有多少条？
并为这3类指令分配操作码。
解：
（1）操作码字段取4位可有24=16个码点，用15个码点（0000～1110）表示15条二地址指令，另一个码点（1111）则作为扩展标志。
所以15条二地址指令格式如下：
由于要求一地址指令和零地址指令的条数基本相等。
所以地址码1字段6位扩展有266=64个码点，64个码点都用来表示零地址指令，共有64条。
（2）在一中指令条数的比例大约1：
4.2：
4.2，因此若使一地址指令和零地址指令加大一倍，则三类指令条数的比例大约1：
9：
9。
操作码字段取4位时的16个码点，用14个码点（0000～1101）表示14条二地址指令，另二个码点（1110与1111）则作为扩展标志。
2.32某模型机9条指令使用频度为：
ADD（加）30%SUB（减）24%JOM（按负转移）6%STO（存）7%
JMP（转移）7%SHR（右移）2%CIL（循环左移）3%CLA（清除）20%STP（停机）1%
要求有两种指令字长，都按双操作数指令格式编排，采用扩展操作码，并限制只能有两种操作码码长。
设该机有若干通用寄存器，主存为16位宽，按字节编址，采用按整数边界存储，任何指令都在一个主存周期中取得，短指令为寄存器--寄存器型，长指令为寄存器--主存型，主存地址应能变址寻址。
（1）仅根据使用频度，不考虑其它要求，设计出全Huffman操作码，计算其平均码长；
（2）考虑题目全部要求，设计优化实用的操作码形式，并计算其操作码的平均码长；
（3）该机允许使用多少可编址的通用寄存器？
（4）画出该机两种指令字格式，标出各字段之位数；
（5）指出访存操作数地址寻址的最大相对位移量为多少个字节？
解：
（1）根据给出的使用频度，在构造Huffman树的过程中，有两个结点可供合并，因此可生成不同的Huffman树，其中给出一棵如图所示，相应的Huffman编码如表所示。
∴Huffman编码的平均长度为：
l=
×li
l=0.3×2＋0.24×2＋0.2×2＋0.07×4＋0.07×4＋0.06×4＋0.03×5＋0.02×6＋0.01×6=2.61（位）
ADDCLASUB
J0MJMPSTO
CIL
指令
Ii
Pi
Huffman编码
Li
2-5编码（3/6）
Li
ADD
I1
0．30
01
2
00
2
SUB
I2
0．24
11
2
01
2
CLA
I3
0．20
10
2
10
2
STO
I4
0．07
0011
4
11001
5
JMP
I5
0．07
0010
4
11010
5
JOM
I6
0．06
0001
4
11011
5
CIL
I7
0．03
00001
5
11100
5
SHR
I8
0．02
000001
6
11101
5
STP
I9
0．01
000000
6
11110
5
STPSHR
（2）任何指令都在一个主存周期中取得，那么短指令字长为8位，长指令字长为16位。
又指令都是二地址指令，所以短指令寄存器--寄存器型的格式为：
长指令为寄存器--主存型的格式为：
由题意可知：
指令操作码采用扩展编码，且只能有两种码长。
从指令使用频度来看，ADD、SUB和CLA三条指令的使用频度与其它指令的使用频度相差较大，所以用两位操作码的三个码点来表示三条指令，一个码点作为扩展码点，且扩展三位来表示六条指令，即采用2--4扩展编码构成3/6编码，2--4扩展编码如表所示。
∴2--4扩展编码（3/6）的平均长度为：
l=
×li=2.78
（3）（4）由短指令寄存器--寄存器型的格式可知，寄存器号字段长度为3位，寄存器个数为8个。
则各字段长度如图格式所标识。
而对于长指令寄存器--主存型，一般变址寄存器是某通用寄存器，则变址寄存器号的字段长度为3位，则各字段长度如图格式所标识。
（5）由于相对位移字段长度为5位，因此访存地址寻址的最大相对位移量为25=32字节。
第三章习题
3.8在一台单流水线多操作部件的处理机上执行下面的程序，每条指令的取指令、指令译码需要一个时钟周期，MOVE、ADD和MUL操作分别需要2个、3个和4个时钟周期，每个操作都在第一个时钟周期从通用寄存器中读操作数，在最后一个时钟周期把运算结果写到通用寄存器中。
k：
MOVER1，R0；R1←（R0）
k+1：
MULR0，R2，R1；R0←（R2）×（R1）
k+2：
ADDR0，R2，R3；R0←（R2）+（R3）
（1）就程序本身而言，可能有哪几种数据相关?
（2）在程序实际执行过程中，哪几种数据相关会引起流水线停顿?
（3）画出指令执行过程的流水线时空图，并计算完成这3条指令共需要多少个时钟周期？
解：
（1）就程序本身而言，可能有三种数据相关。
若3条指令顺序流动，则k指令对R1寄存器的写与k+1指令对R1寄存器的读形成的“先写后读”相关。
若3条指令异步流动，则k指令对R0寄存器的读与k+1指令对R0寄存器的写形成的“先读后写”相关，k+2指令对R0寄存器的写与k+1指令对R0寄存器的写形成的“写—写”相关。
（2）在程序实际执行过程中，二种数据相关会引起流水线停顿。
一是“先写后读”相关，k指令对R1的写在程序执行开始后的第四个时钟；k+1指令对R1的读对指令本身是第三个时钟，但k+1指令比k指令晚一个时钟进入流水线，则在程序执行开始后的第四个时钟要读R1。
不能在同一时钟周期内读写同一寄存器，因此k+1指令应推迟一个时钟进入流水线，产生了流水线停顿。
二是“写—写”相关，k+1指令
升级会员 