江西师范大学体系计算题.doc

《江西师范大学体系计算题.doc》由会员分享，可在线阅读，更多相关《江西师范大学体系计算题.doc（103页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date江西师范大学体系计算题江西师范大学体系计算题第 一 章1.49 有一台计算机，不同类型指令在理想Cache（无访问失败）与实际Cache（有访问失败）两种情况下的性能如下表。求理想Cache相对于实际Cache的加速比？指令类型 出现频率 理想CacheCPI 实际CacheCPI运算指令 40% 1 3取数指令 20% 2 8存数指令 15% 2 8控制指令 25%

2、 2 4解：理想Cache情况下指令的平均时钟周期数CPI为： CPI理想 = =140%+220%+215%+225% = 1.6实际Cache情况下指令的平均时钟周期数CPI为： CPI实际= =340%+820%+815%+425% = 5.0S = 实际CacheCPU执行时间/理想CacheCPU执行时间=（IC时钟周期CPI实际）/（IC时钟周期CPI理想）= CPI/CPIA = 5.0/1.6 = 3.121.45 用一台80MHz处理机执行标准测试程序，它包含的指令数和相应的平均时钟周期数如表1-10所示，求该处理机的有效CPI、MIPS和程序执行时间。表1-10 题1.46

3、的指令数和相应的平均周期数指令类型指令数平均周期数整数运算460001数据传输360002浮点运算140002控制指令90002解：该处理机指令的平均时钟周期数CPI为： CPI = =46/1051+36/1052+14/1052+9/1052 = 1.6 所以 MIPS = 时钟频率/（CPIB106）=（80106）/（1.6106）= 50 TCPU = IC/( MIPS106) = 105000/(50106) = 0.21(ms)1.44 某工作站采用时钟频率为15MHz、处理速率为10MIPS的处理机来执行一个测试程序。假定每次存储器存取为1个时钟周期，试问：(1)此计算机的有

4、效CPI是多少?(2)假定将处理机的时钟频率提高到30MHz，但存储器的工作速率不变，这样，每次存储器存取需要2个时钟周期。如果30指令每条只需要一次存储器存取操作，另外5指令每条需要二次存储器存取操作，假定测试程序的指令数不变，并与原工作站兼容，试求改进后的处理机的CPI。解：（1）由MIPS = 时钟频率/（CPI106），则有：CPIA =时钟频率/（MIPS106）= 1.5。 （2）当时钟频率为15MHZ时，假设不进行存储操作指令的CPI为x，则要进行一次存储操作指令的CPI为1+ x，要进行二次存储操作指令的CPI为2+ x，因此有： 1.5 = x65% + （1+ x）30%

5、+ （2+ x）5% 解得x = 1.1当时钟频率为30MHZ时，不进行存储操作指令的CPI不变为1.1，要进行一次存储操作指令的CPI为2+ x = 3.1，要进行二次存储操作指令的CPI为4+ x = 5.1，因此平均CPI为： CPIB = 1.165% + 3.130% + 5.15% = 1.9所以 MIPSB = 时钟频率/（CPIB106）=（30106）/（1.9106）= 15.8第 二 章 2.13 在一台单流水线多操作部件的处理机上执行下面的程序，每条指令的取指令、指令译码需要一个时钟周期，MOVE、ADD和MUL操作分别需要2个、3个和4个时钟周期，每个操作都在第一个时

6、钟周期从通用寄存器中读操作数，在最后一个时钟周期把运算结果写到通用寄存器中。k： MOVE R1，R0 ；R1 (R0)k+1： MUL R0，R2，R1 ；R0 (R2)(R1)k+2： ADD R0，R2，R3 ；R0 (R2)+(R3)(1)就程序本身而言，可能有哪几种数据相关?(2)在程序实际执行过程中，哪几种数据相关会引起流水线停顿?(3)画出指令执行过程的流水线时空图，并计算完成这3条指令共需要多少个时钟周期？解：（1）就程序本身而言，可能有三种数据相关。若3条指令顺序流动，则k指令对R1寄存器的写与k+1指令对R1寄存器的读形成的“先写后读”相关。若3条指令异步流动，则k指令对R

7、0寄存器的读与k+1指令对R0寄存器的写形成的“先读后写”相关，k+2指令对R0寄存器的写与k+1指令对R0寄存器的写形成的“写写”相关。（2）在程序实际执行过程中，二种数据相关会引起流水线停顿。一是“先写后读”相关，k指令对R1的写在程序执行开始后的第四个时钟；k+1指令对R1的读对指令本身是第三个时钟，但k+1指令比k指令晚一个时钟进入流水线，则在程序执行开始后的第四个时钟要读R1。不能在同一时钟周期内读写同一寄存器，因此k+1指令应推迟一个时钟进入流水线，产生了流水线停顿。二是“写写”相关，k+1指令对R0的写对指令本身是第六个时钟，而要求该指令进入流水线应在程序执行开始后的第三个时钟，

8、所以对R0的写是在程序执行开始后的第八个时钟。k+2指令对R0的写对指令本身是第五个时钟，而k+2指令比k+1指令晚一个时钟进入流水线，则在程序执行开始后的第四个时钟，所以对R0的写是在程序执行开始后的第八个时钟。不能在同一时钟周期内写写同一寄存器，因此k+2指令应推迟一个时钟进入流水线，产生了流水线停顿。另外，可分析“先读后写”相关不会产生流水线的停顿。 （3）由题意可认位该指令流水线由六个功能段取指、译码、取数、运一、运二和存数等组成，则程序指令执行过程的流水线时空图如下图所示。若3条指令顺序流动，共需要9个时钟周期。 空间存数 K存数 K+1存数 K+2存数 运二 K+1运二 运一 K+

9、1运一 K+2运一 取数 K取数 K+1取数 K+2取数 译码 K译码 K+1译码 K+2译码 取指 K取指 K+1取指 K+2取指 时间 0 1 2 3 4 5 6 7 8 92.23 有一条5个功能段的线性动态多功能流水线如图所示，其中1235功能段组成加法流水线，145功能段组成乘法流水线，设每个功能段的延迟时间均相等为t。用这条流水线计算F=，画出流水线时空图，并计算流水线的实际吞吐率、加速比和效率。S1S2S3S5S4XYZ解：由于该流水线为动态双功能流水线，计算要求先加后乘，因此应先设置加法功能，连续计算出（a1+b1）、（a2+b2）、（a3+b3）、（a4+b4）四个加法后；再

10、设置乘法功能，而且按(a1+b1)(a2+b2)(a3+b3)(a4+b4)顺序做3个乘法。因此可画出该流水线的时空图如图所示，图中A=a1+b1，B=a2+b2，C=a3+b3，D=a4+b4。空间S5S4S3S2S11234三一二一二一二1234ABCDAB CD(AB)(CD) t7t13a1b1a2b2a3b3a4b4ABCDABCD时间12341234三三由时空图可以看出，在总共12个t的时间内输出7个结果，所以有：TP = n/Tn = 7/12t而当用串行方法完成操作时，需要四次加法和三次乘法，完成一次加法需要4t，完成一次乘法需要3t，完成该运算总共需要时间为：T0 = 44t

11、+33t = 25t所以 S = T0/Tn = 2.08E = 有效时空区面积/全部时空区面积 = (44t+33t)/(512t) = 0.422.24 有一条3个功能段的流水线如下图所示，每个功能段的延迟时间均为t，但是，功能段S2的输出要返回到它自己的输入端循环执行一次。S1S2S3 输入 输出 t t t（1）如果每隔一个t向流水线连续输入任务，这条流水线会发生什么问题？（2）求这条流水线能够正常工作的实际吞吐率、加速比和效率。 （3）可用什么办法来提高流水线的吞吐率，画出改进后的流水线结构。解：（1）每个任务在段S2要反馈循环一次，执行时间为2t，其它各段的执行时间为t，因此应按瓶

12、颈段的执行时间2t流入任务，才不会发生冲突现象，否则会发生流水线的阻塞。 （2）若连续输入n个任务，则流水线的实际吞吐率、加速比和效率分别为： TP = n/（4t +2（n1）t）= n/2（n + 1）t 1/2tS = 4nt/（4t +2（n1）t）= 2n/（n + 1）2 E = 4nt/3（4t +2（n1）t）= 2n/3（n + 1）2/3（3）为提高流水线的吞吐率，可重复设置段S2，并使两个段S2串连在一起，从而消除瓶颈段S2，而且各段执行时间相等为t，流水线的段数为4。流水线的结构如下图所示。S3S2S2S1 输入 输出 t t t t2.25 在一个5段的流水线处理机上

13、需经9t才能完成一个任务，其预约表为： 时间 1 2 3 4 5 6 7 8 9流水段S1 S2 S3 S4 S5 延迟D2 （1）写出流水线的初始冲突向量。（2）画出流水线任务调度的状态有向图。（3）求出流水线的最优调度策略及最小平均延迟时间和流水线的最大吞吐率。（4）按最优调度策略连续输入8个任务时，流水线的实际吞吐率是多少? 解：（1）根据初始冲突向量的构成方法，对预约表各行中打“”的拍数求出差值，除去重复的后汇集在一起，即得到延迟禁止表为F =1，5，6，8。由F可得到初始冲突向量为： C =（10110001） （2）根据后继冲突向量的递推规则Cj = SHR（k）（Ci）C0则可得

14、出所有的后继状态，具体有：10110001 C0C0四个后继状态：C1 =SHR（2）（C0）C0 = 10111101 7 C2 =SHR（3）（C0）C0 = 10110111 C3 =SHR（4）（C0）C0 = 10111011 3 2C4 =SHR（7）（C0）C0 = 10110001=C0 7 4 710111101 C110110111 C2C1二个后继状态：C5 =SHR（2）（C1）C0 = 10111111 C6 =SHR（7）（C1）C0 = 10110001=C0 7C2二个后继状态：C7 =SHR（4）（C2）C0 = 10111011=C3 3 4 7 21011

15、1011 C310111111 C5C8 =SHR（7）（C2）C0 = 10110001=C0C3二个后继状态：C9 =SHR（3）（C3）C0 = 10110111=C2C10=SHR（7）（C3）C0 = 10110001=C0C5一个后继状态：C11=SHR（7）（C5）C0 = 10110001=C0 由后继状态和引起状态转移的时间间隔可得到状态有向图如上图所示。 （3）由状态转移有向图可得到无冲突的任务调度策略及其平均延迟时间，如下表所示。调度策略 平均延迟时间 特别地，从C0出发的3，（4，3）也是一个（2，2，7） （2+2+7）t/3 = 3.67t 任务调度策略，除第一条有

16、向弧外，第二、三条 （2，7） （2+7）t/2 = 4.5t 有向组成一个环路，该调度策略为（4，3）。从表 （3，4，7） （3+4+7）t/3 = 4.67t 中可以得到平均延迟时间最小的调度策略为（4， （3，7） （3+7）t/2 = 5t 3），该调度策略则为最优调度策略，相应的最小（4，3，7） （4+3+7）t/3 = 4.67t 平均延迟时间为3.5t，所以流水线的最大吞吐（4，7） （4+7）t/2 = 5.5t 率为：（7） 7t TPmax = 1/（3.5t）= 0.286/t3，（4，3） （4+3）t/2 = 3.5t （4）按最优调度策略3，（4，3）连续输入8

17、个任务时，流水线的实际吞吐率为： TP = 8/（3 + 4 + 3 + 4 + 3 + 4 + 3 + 9）t = 0.24/t第 三 章3.26 设16个处理器编号分别为0，1，15，要用单级互连网络，当互连函数分别为：（1）Cube3（Cube1） （5）Butterfly（Butterfly） （8） （9） （13）时，第13号处理器分别与哪一个处理器相连?解：（1）因为Cube3（Cube1(X3X2X1X0)）= Cube3(X3X2X1X0)= X3X2X1X0所以13 Cube3（Cube1(1101)）= 0100 4 （5）因为Butterfly（Butterfly(X3

18、X2X1X0)）=Butterfly（X0X2X1X3）=X3X2X1X0所以13 Butterfly（Butterfly (1101)）= 1101 13 （8）因为(X3X2X1X0)= X0X3X2X1 所以13 (1101)= 1110 14 （9）因为(X3X2X1X0)= X3X2X0X1 所以13 (1101)= 1110 14 （13）因为(X3X2X1X0)= X1X2X3X0 所以13 (1101)= 0111 73.30 在有16个处理器的均匀洗牌网络中，若要使第0号处理器与第15号处理器相连，需要经过多少次均匀洗牌和交换置换。解：0（0000B）号处理器与15（1111

19、B）号处理器相连要对四位取反。交换置换一次只能对一位取反，所以要四次交换置换。交换置换每次取反只对最低位，要有三次移位，所以要四次均匀洗牌置换。即变换为0000(E) 0001() 0010(E) 0011() 0110(E) 0111()1110(E) 1111。3.34 在编号分别为0，1，2，9的16个处理器之间，要求按下列配对通信：(B、1)，(8、2)，(7、D)，(6、C)，(E、4)，(A、0)，(9、3)，(5、F)。试选择所用互连网络类型、控制方式，并画出该互连网络的拓扑结构和各级的交换开关状态图。解：16个处理机通过N = 16的互连网络互联，通信配对连接的二进制编号为：(

20、0、A)：0000-1010 (8、2)：1000-0010(1、B)：0001-1011 (9、3)：1001-0011(2、8)：0010-1000 (A、0)：1010-0000(3、9)：0011-1001 (B、1)：1011-0001(4、E)：0100-1110 (C、6)：1100-0110(5、F)：0101-1111 (D、7)：1101-0111(6、C)：0110-1100 (E、4)：1110-0100(7、D)：0111-1101 (F、5)：1111-0101显然要求互连网络实现的互联函数为f（X3X2X1X0）= X3X2X1X0，为多重方体置换。N = 16的

21、STARAN网络在级控方式下实现的是方体置换，且当级控信号为F = f3f2f1f0 = 1010时，实现的互联函数是Cube3（Cube1（X3X2X1X0）= X3X2X1X0。所以采用N = 16的STARAN网络在级控方式且级控信号F = 1010时，可实现要求配对通信。0123456789ABCDEF0123456789ABCDEF3.41 写出N=8的蝶式置换的互连函数，如采用Omega网络，则需几次通过才能完成此变换？画出Omega网络实现此变换的控制状态图。 解：（1）N=8的蝶式置换的互连函数为：（X2X1X0）= X0X1X2（2）根据Omega网络采用单元控制终端标记法寻

22、径方法，蝶式交换的连接关系及用N=8的Omega网络实现该连接的开关要求如下表所示。 S D d2 d1 d0 K2级开关 K1级开关 K0级开关 0 0 0 0 0 与K21上输出端连接 与K11上输出端连接 与K01上输出端连接 1 4 1 0 0 与K22下输出端连接 与K14上输出端连接 与K03上输出端连接 2 2 0 1 0 与K23上输出端连接 与K11下输出端连接 与K02上输出端连接 3 6 1 1 0 与K24下输出端连接 与K14下输出端连接 与K04上输出端连接 4 1 0 0 1 与K21上输出端连接 与K11上输出端连接 与K01下输出端连接 5 5 1 0 1 与

23、K22下输出端连接 与K14上输出端连接 与K03下输出端连接 6 3 0 1 1 与K23上输出端连接 与K11下输出端连接 与K02下输出端连接 7 7 1 1 1 与K24下输出端连接 与K14下输出端连接 与K04下输出端连接 由表可见，当实现八个结点对连接时，对K2级开关的要求将发生下列争用开关输出端的冲突： 0 0 和 4 1 争用开关K21上输出端 1 4 和 5 5 争用开关K22下输出端 2 2 和 6 3 争用开关K23上输出端 3 6 和 7 7 争用开关K24下输出端因此，为避免K2级开关输出端的冲突，八个结点对连接分两次实现。第一次实现：0 0、1 4、2 2、3 6

24、；第二次实现：4 1、5 5、6 3、7 7。分两次实现连接也避免K1级开关K11和K14输出端的冲突，K0级四个开关没有输出端的冲突。（3）Omega网络分2次连接的开关状态如下图。0123456701234567 第一次0123456701234567 第二次3.55 对于4方体网络见图3-65，从结点0000到结点1111，有多少条最短路径？为什么？用E立方维序寻径算法找出其中一条最短路径。 解：（1）当源节点与目的节点的海明距离为h，则有h!条最短路径。结点0000到结点1111的海明距离为4，所以有1234=24条最短路径。 （2）方向位向量R = SD = 00001111 = 1

25、111，V = S = 0000（源节点）r1=1，V = V2i-1 = 00000001 = 0001；r2=1，V = V2i-1 = 00010010 = 0011；r3=1，V = V2i-1 = 00110100 = 0111；r4=1，V = V2i-1 = 01111000 = 1111（目的结点）。所以，0000与1111有一条最短路径为：S=00000001001101111111=D。第 四 章4.52 浮点数系统使用的阶码基值re=2，阶值位数q=2，尾数基值rm=10，尾数位数p=1，即按照使用的二进制位数来说，等价于p=4。计算在非负阶、正尾数、规格化情况下的最小尾

26、数值、最大尾数值、最大阶值、可表示的最小值和最大值及可表示数的个数。解: 最小尾数值：rm-1 = 10-1 = 0.1最大尾数值：1- rm-p =1-10-1 = 0.9最大阶值：2q-1=3可表示数的最小值：1rm-1 = 10-1 = 0.1可表示数的最大值：rm2q-1（1- rm-p）=103（1-10-1）= 900可表示数的个数：2qrmp（rm-1）/rm = 22101（10-1）/10 = 364.53 一台机器要求浮点数的字长的精度不低于10-7.2，表数的范围正数不小于1038，且正负对称。尾数用原码、纯小数表示，阶码用移码、整数表示。设计这种浮点数的格式。解 依题意

27、，取表数范围N =1038，表数精度=10-7.2。由式（4-4）得： = 6.99，上取整，得到阶码字长q=7。由式（4-5）得：，上取整，得到尾数字长p=24。从而加上一个尾数符号位和一个阶码符号位，浮点数的总字长为：p+q+2=24+7+2=33。实际浮点数总字长应为8的倍数，故取浮点数总字长为40位。多出的7位可以加到尾数字长p中用于提高浮点数的表数精度，也可以加到阶码字长q中来扩大浮点数的表数范围。暂且让p增加6位，q增加1位，即p=30，q=8。如图4-8所示是设计出来的浮点数格式。长度 1 p=30 1 q=8位序 39 38 9 8 7 0尾符S 尾数M 阶符F 阶码E图4-8

28、 例4.2浮点数的设计格式4.58 用于文字处理的某专用机，每个文字符用4位十进制数字（09）编码表示，空格用表示。在对传送的文字符和空格进行统计后，得出它们的使用频度如下：0.20 0:0.17 1:0.06 2:0.08 3:0.11 4:0.085: 0.05 6:0.08 7:0.13 8:0.03 9:0.01（1）若对数字09和空格采用二进制编码，试设计编码平均长度最短的编码。（2）若传送106个文字符号，且每个文字符号后均自动跟一个空格，按最短的编码，共需传送多少个二进制位？若传送波特率为9600bPS，共需传送多少时间？（3）若对数字09和空格采用4位定长码编码，重新计算问题（

29、2）。解：（1）操作码编码的平均长度最短为Huffman编码，生成的Huffman树，如图所示，相应的Huffman编码如表所示。l=li = 3.23（位）。（2）根据题意，每个字符的二进制码的平均长度为：3.23（41）=16.15（位）。若要传输106个字符，则要传输二进制位数为：10616.15 =1.615107（位）若波特率为56Kb/s，则传输时间为：1.615107/（56103）=288（s）。1.000.010.040.090.200.400.030.050.110.200.080.060.140.270.600.160.080.130.330.170.08（3）当采用四位

30、定长编码时，则需要传输二进制位数为：1064（41）=2107（位），传输时间为：2107/（56103）=357（s）。 1 0 1 0 1 0 1 0 1 0 1 0 3 7 0 5 1 6 4 2IiPiHuffman编码Li02010200170003701301033011110320080010440080011460080110410060111450051110480031111059001111115 9 84.60 一台模型机共有7条指令，各指令的使用频度分别为：35%，25%，20%，10%，5%，3%，2%，有8个通用数据寄存器，2个变址寄存器。（1）要求操作码的平均长

31、度最短，请设计操作码的编码，并计算操作码编码的平均长度。（2）设计8位字长的寄存器寄存器型指令3条，16位字长的寄存器一存储器型变址寻址方式指令4条，变址范围不小于正、负127。请设计指令格式，并给出指令各字段的长度和操作码的编码。解：（1）操作码编码的平均长度最短为Huffman编码，生成的Huffman树如图所示，相应的Huffman编码如表所示。l=li = 2.35（位）1.000.020.050.100.200.400.030.050.100.200.250.600.35IiPiHuffman编码Li2-4编码（3/4）LiI1035002002I2025012012I3020102

32、102I4010110311004I50051110411014I600311110511104I700211111511114（2）由于通用寄存器有8个，则指令中通用寄存器字段应为3位；操作码字段2位可有4个码点，用三个码点表示三条指令，另一个码点则作为扩展标志。所以3条8位长的寄存器寄存器型指令格式如下：操作码（2位）寄存器1（3位）寄存器2（3位）由于变址寄存器有2个，则指令中变址寄存器字段应为1位；变址范围-127+127，则指令中相对位移字段应为8位；操作码字段前2位可有4个码点，用三个码点表示三条指令，另一个码点则作为扩展标志。扩展2位正好可表示四条指令，操作码字段则为4位。所以4

33、条16位长的寄存器存储器型指令格式如下：操作码（4位）寄存器（3位）变址寄存器（1位）相对位移（8位）特别地，当采用3/4扩展编码时，使用频度高的用短码表示，使用频度低的用长码表示，其相应的编码如表所示。4.65 某模型机9条指令使用频度为：ADD（加） 30% SUB（减） 24% JOM（按负转移）6% STO（存） 7%JMP（转移）7% SHR（右移）2% CIL（循环左移）3% CLA（清除）20%STP（停机）1%要求有两种指令字长，都按双操作数指令格式编排，采用扩展操作码，并限制只能有两种操作码码长。设该机有若干通用寄存器，主存为16位宽，按字节编址，采用按整数边界存储，任何指令

34、都在一个主存周期中取得，短指令为寄存器-寄存器型，长指令为寄存器-主存型，主存地址应能变址寻址。（1）仅根据使用频度，不考虑其它要求，设计出全Huffman操作码，计算其平均码长；（2）考虑题目全部要求，设计优化实用的操作码形式，并计算其操作码的平均码长；（3）该机允许使用多少可编址的通用寄存器？（4）画出该机两种指令字格式，标出各字段之位数；（5）指出访存操作数地址寻址的最大相对位移量为多少个字节？解：（1）根据给出的使用频度，在构造Huffman树的过程中，有两个结点可供合并，因此可生成不同的Huffman树，其中给出一棵如图所示，相应的Huffman编码如表所示。 Huffman编码的平均长度为：l=lil=0.320.2420.220.0740.0740.0640.0350.0260.016=2.61（位）0.560.010.030.060.120.260.020.030.060.070.141.000.200.070.440.240.30 ADD CLA SUB J0M JMP STO