福建农林大学系统结构计算题

1、精选优质文档-倾情为你奉上题型一：（一）（五）（六）题型二：（二）（七）题型三：（三）（四）题型四：（八）（九）（十）（十一）（十二）（十三）（十四）（十五）题型五：（十六）（十七）（十八）题型六：（十九）（二二）（二三）（二五）（二六）（二七）（二八）其他题型考选择题：（二十）（二一）（二四）（二九）（三十）（一）【7-6】由霍纳法则给定的表达式如下：E=a(b+c(d+e(f+gh)利用减少树高的办法来加速运算，要求：（1） 画出树形流程图。（2） 确定TP、P、SP、EP的值。解：（1）若用单处理机处理，T1=7，改成E=ace(f+gh)+a(b+cd)，其计算的树形流程图如附图46所

2、示。 （2） P=3；TP=4；SP=T1/TP=7/4；EP=SP/P=7/12（二）【6-2】设向量长度均为64，在CRAY-1机上所用浮点功能部件的执行时间分别为：相加6拍，相乘7拍，求倒数近似值14拍；在存储器读数6拍，打入寄存器及启动功能部件各1拍。问下列各指令组内的哪些指令可以链接？哪些指令不可链接？不能链接的原因是什么？分别计算出各指令全部完成所需的拍数。（1） V0存储器 （2）V2V0V1V1V2+V3 V3存储器 V4V5V6 V4V0+ V3（3） V0存储器 （4）V0存储器 V2V0V1 V11/ V0V3V2+ V0 V3V1V2V5V3+ V4 V5V3+ V4解

3、：（1）三条全并行，完成时间为72拍 （2）一、二条并行，链接第三条，完成时间为80拍 （3）第一条链接第二条，与第三条串行，与第四条串行，完成时间为222拍 （4）全链接，完成时间为104拍（三）【例5-3】在一个4段的流水线处理机上需经7拍才能完成一个任务，其预约表如表5-2所示。 表5-2 7拍才能完成一个任务的预约表段 时间1234567 S1 S2 S3 S4分别写出延迟禁止表F、冲突向量C；画出流水线状态转移图；求出最小平均延迟及流水线的最大吞吐率及其调度时的最佳方案。按此调度方案，输入6个任务，求实际的吞吐率。解：此例可得延迟禁止表F=2,4,6。初始冲突向量C=（）。 状态转移

4、图如图5-29所示。各种调度方案及其相应的平均延迟如表5-3所示。 表5-3 调度方案及其相应的平均延迟 调度方案 平均延迟/拍 （1,7） 4 （3,5） 4 （5,3） 4 （5） 4由表5-3可知，最小平均延迟为4拍。此时流水线的最大吞吐率Tpmax=1/4（任务/拍）。最佳调度方案宜选其中按（1,7）周期性调度的方案。按（1,7）调度方案输入6个任务，全部完成的时间为1+7+1+7+1+7=24（拍），实际吞吐率Tp=6/24（任务/拍）。若按（3,5）调度方案输入6个任务，全部完成的时间为3+5+3+5+3+7=26（拍），实际吞吐率Tp=6/26（任务/拍）。若按（5,3）调度方案

5、输入6个任务，全部完成的时间为5+3+5+3+5+7=28（拍），实际吞吐率Tp=6/28（任务/拍）。可见，最佳的方案应为（1,7）调度方案，输入6个任务的实际吞吐率较之其他方案要更高些。（四）【5-11】在一个5段的流水线处理机上需经9拍才能完成一个任务，其预约表如表5-4所示。分别写出延迟禁止表F、冲突向量C；画出流水线状态转移图；求出最小平均延迟及流水线的最大吞吐率及其调度方案。按此流水线调度方案输入6个任务，求实际吞吐率。 表5-4 9拍才能完成一个任务的预约表段 时间 T0T1T2T3T4T5T6T7T8S1S2S3S4S5解：根据预约表中各个行中打“”的拍数求出差值，并将这些差值

6、汇集在一起，就可得到延迟禁止表F=1,3,4,8。由延迟禁止表F可转换得初始冲突向量C=（）。根据初始冲突向量可画出状态转换图如附图31所示。各种周期性调度方案列于附表15。由附表15可知最小平均延迟为3.5拍。此时，Tpmax=1/3.5（任务/拍）。最佳调度方案为（2,5）。附表15 周期性调度方案调度方案平均延迟/拍调度方案平均延迟/拍（2,5）3.5（6,7）6.5（2,7）4.5（7）7（5）5（5,2）3.5（6,5）5.5（6）6按（2,5）调度方案实际输入6个任务的时空图如附图32所示。实际吞吐率Tp=6/25（任务/拍）。（五）【例7-4】计算E1=a+bx+cxx+dxxx

7、。利用减少树高的办法来加速运算，要求：（1） 画出树形流程图。（2） 确定TP、P、SP、EP的值。解：（1）利用霍纳法可得到E1=a+x(b+x(c+x(d)。若用单处理机处理，T1=7，改成E1=a+x(b+x(c+x(d)。其计算的树形流程图如附图7-17（a）所示。（2） TP=4、P=3、SP=3/2、EP=1/2（六）【例7-6】表达式E2=a+b(c+def+g)+h。利用减少树高的办法来加速运算，要求：（1） 画出树形流程图。（2） 确定TP、P、SP、EP的值。解：P253-P254（七）【P201】设向量长度均为64，在CRAY-1机上所用浮点功能部件的执行时间分别为：相加

8、6拍，相乘7拍，求倒数近似值14拍；在存储器读数6拍，打入寄存器及启动功能部件各1拍。问下列指令组内的哪些指令可以链接？哪些指令不可链接？不能链接的原因是什么？分别计算出各指令全部完成所需的拍数。V3存储器V2V0+V1V4V2V3解：P201-P202（八）【5-3】有一个浮点乘流水线如图5-36（a）所示，其乘积可直接返回输入端或暂存于相应缓冲寄存器中，画出实现ABCD的时空图以及输入端的变化，并求出流水线的吞吐率和效率；当流水线改为图5-36（b）所示的形式实现同一计算时，求该流水线的效率及吞吐率。解：按图5-36（a）组织，实现ABCD的时空关系如附图16所示。吞吐率：Tp=3/13t

9、 ；效率：=（35t）/（313t）=5/13流水线按图5-36（b）组织，实现ABCD的时空关系如附图17所示。吞吐率：Tp=3/11t；效率：=（35t）/（311t）=5/11（九）【5-4】一个4段的双输入端规格化浮点加法流水线，每段经过时间为10ns，输出可直接返回输入或将结果暂存于相应缓存器中，问最少需要经多长时间才能求出10（i=1）Ai，并画出时空图。解：按（A1+A2）+（A3+A4）+（A9+A10）+（A5+A6）+（A7+A8）流水的时空图如附图18所示。（十）【5-5】为提高流水线效率可采用哪两种主要途径来克服速度瓶颈？现有3段流水线各经过时间依次为t、3t、t。 （

10、1）分别计算在连续输入3条指令和30条指令时的吞吐率和效率。 （2）按两种途径之一进行改进，画出流水线结构示意图，同时计算连续输入3条指令和30条指令时的吞吐率和效率。 （3）通过对（1）、（2）两小题的计算比较可得出什么结论？解：提高流水线效率，消除速度瓶颈主要有两种途径：将瓶颈段再细分；重复设置多个瓶颈段并联工作，给其轮流分配任务。（1） 在3段流水线各段经过时间依次为t、3t、t的情况下，连续流入3条指令时，将n=3，m=3，t1=t、t 2=3t、t3=t，tj=3t代入，可得吞吐率Tp和效率为（2） 若采取将2段细分成3个子段，每个子段均为t，构成流水线结构如附图10所示。若采取将3

11、个2段并联构成的流水线，其构成如附图20所示。（十一）【5-6】有一个双输入端的加-乘双功能静态流水线，由经过时间为t、2t、2t、t的1、2、3、4四个子过程构成。“加”按124连接，“乘”按134连接，流水线输出设有数据缓冲器，也可将数据直接返回输入。现要执行A（B+C（D+EF）+GH的运算，请调整计算顺序，画出能获得吞吐率尽量高的流水时空图，标出流水线入、出端数的变化情况，求出完成全部运算的时间及此期间流水线的效率。如对流水线瓶颈子过程再细分，最少需多长时间可完成全部运算？若子过程3不能再细分，只能用并联方法改进，则流水线的效率为多少？解：（十二）【5-7】有一个乘-加双功能静态流水线

12、，“乘”由1234完成，“加”由154完成，各段延时均为t，输出可直接返回输入或存入缓冲器缓冲。现要求计算长度均为8的A、B两个向量逐对元素求和的连乘积 S=8（i=1）（Ai+Bi）(1) 画出流水线完成此运算的时空图。(2) 完成全部运算所需多少t？此期间流水线的效率是多少？解：（十三）【5-8】带双输入端的加-乘双功能静态流水线有1、2、3、4四个子部件，延时分别为t、t、2t、t，“加”按124连接，“乘”按134连接，输出可直接返回输入或锁存，现欲执行4（i=1）（ai+bi）ci。（1） 画出此流水线时空图，标出流水线入端数据变化情况。（2） 计算运算全部完成所需时间及在此期间流水

13、线的效率。（3） 将瓶颈子部件再细分，画出解此题的时空图。（4） 求出按（3）解此题所需时间及在此期间流水线的效率。解：（1）（2）（3）（4）（十四）【5-9】现有长度为8的向量A和B，请分别画出下列4种结构的处理器上求点积AB的时空图，并求完成全部结果的最少时钟拍数。设处理器中每个部件的输出均可直接送到任何部件的输入或存入缓冲器中，其间的传送延时不计，指令和源操作数均能连续提供。（1） 处理器有个一乘法部件和一个加法部件，不能同时工作，部件内也只能以顺序方式工作，完成一次加法或乘法均需5拍。（2） 与（1）基本相同，只是乘法部件和加法部件可并行。（3） 处理器有一个乘-加双功能静态流水线，

14、乘、加均由5个流水线构成，各段经过时间要1拍。（4） 处理器有乘、加两条流水线，可同时工作，各由5段构成，每段经过时间为1拍。解：（十五）【5-2】流水线由4个功能部件组成，每个功能部件的延迟时间为t，当输入10个数据后间歇5t又输入10个数据，如此周期性地工作，求此时流水线的吞吐率，并画出其时空图。（十六）【例3-3】P89P91（十七）【3-5】设中断级屏蔽位“1”对应于开放，“0”对应于屏蔽，各级中断处理程序的中断级屏蔽设置如表3-6所示。 表3-6 习题3-5中的中断级屏蔽位设置中断处理程序级别 中断级屏蔽位第1级第2级第3级第4级第1级0000第2级1011第3级1000第4级101

15、0（1） 当中断相应优先次序为1234时，其中断处理次序是什么？（2） 设所有的中断处理都各需3个单位时间，中断响应和中断返回时间相对中断处理时间少得到多。当机器正在运行用户程序时，同时发生第2、3级中断请求，过两个单位时间后，又同时发生第1、4级中断请求，试画出程序运行过程示意图。解：（1）中断处理（完）的次序为1342。（2） CPU运行程序的过程示意图如附图4所示。在该图中，粗短线部分代表进行交换程序状态字的时间，t为1个单位时间。（十八）【3-6】若机机器共有5级中断请求，中断响应优先次序为12345，现要求其实际的中断处理次序为14523，回答下面问题：（1） 设计各级中断处理程序的

16、中断级屏蔽位（令“1”对应于屏蔽，“0”对应于开放）；（2） 若在运行用户程序时，同时出现第4、2级中断请求，而在处理第2级中断未完成时，又同时出现第1、3、5级中断请求，请画出此程序运行过程示意图。解：（1）（2）（十九）【例2-5】现假设某模型机共有n（n=7）条指令，使用频度如表2-4所示。若操作码用定长表示，需要3位。而按信息论观点，若各种指令的出现是互相独立的（实际并不都是如此），操作码的信息源熵（信息源所含平均信息量）H=-n（i=1）pi1bpi。由表2-4的数据可得H=-n（i=1）pi1bpi=2.17。说明表示这7种指令的操作码平均只需2.17位即可。现在用3位定长码表示，

17、信息冗余度为（3-2.17）/328%。冗余度相当大。指令使用频度（pi）指令使用频度（pi）I10.40I50.04I20.30I60.03I30.15I7 0.03I40.05-（1） 改用哈夫曼编码以及扩展的哈夫曼编码；（2） 构造哈夫曼数；解：（1）指令频度pi操作码OP使用哈夫曼编码OP长度li利用哈夫曼概念的扩展操作码OP长度liI10.4001002I20.30102012I30.151103102I40.0511100511004I50.0411101511014I60.0311110511104I70.0311111511114（2）（二十）【例2-6】P59（二一）【例2-

18、7】若某机要求有：三地址指令4条，单地址指令255条，零地址指令16条。设指令字长为12位，每个地址码长为3位。能否以扩展操作码为其编码？如果单地址指令改为254条呢？解：P60（二二）【例2-8】某模型机9条指令的使用频度如表2-7所示。要求有两种指令字长，都按双操作数指令格式编排，采用扩展操作码，并限制只能有两种操作码码长。设该机有若干通用寄存器，主存为16位宽，按字节编址，采用按整数边界存储，任何指令都在一个主存周期中取得，短指令为寄存器-寄存器型，长指令为寄存器-主存型，主存地址应能变址寻址。 表2-7 模型机指令指令使用频度指令使用频度指令使用频度ADD（加）STO（存）CIL（循环

19、左移）30%7%3%SUB（减）JMP（转移）CLA（清加）24%7%20%JOMSHR（右移）STP（停机）6%2%1%（1） 改用哈夫曼编码以及扩展的哈夫曼编码；（2） 构造哈夫曼数；（3） 计算平均码长解：（1）哈夫曼编码：ADD（加）30%01SUB（减）24%11CLA20%10JOM6%0001STO7%0011JMP7%0010SHR2%CIL3%00001STP1%00000扩展的操作码编码：ADD（加）30%00SUB（减）24%01CLA20%10JOM6%11000STO7%11001JMP7%11010SHR2%11011CIL3%11100STP1%11101（2）

20、哈夫曼树：（3） 平均码长：哈夫曼编码：2.61位；扩展码：2.78位。（二三）【2-4】设某机器阶值6位、尾数48位，阶符和数符不在其内，当尾数分别2、8、16为基时，在非负阶、正尾数、规格化情况下，求出其最小阶、最大阶、阶的个数、最小尾数值、最大尾数值、可表示的最小值和最大值及可表示数的个数。解：p=6，m=48时，在非负阶、规格化、正尾数的情况下，rm=2,8,16的各个参数的计算结果如附表1所示：（二四）【2-5】浮点数系统使用的阶基rp=2，阶值位数p=2，尾数基值rm=10，以rm为基的尾数m=1。（1） 试计算在非负阶、正尾数、规格化情况下的最小尾数值、最大尾数值、最大阶值、可表

21、示的最小值和最大值及可表示数的个数；（2） 对于rp=2，p=2，rm=4，m=2，重复以上计算。解：（1）在非负阶、正尾数、规格化情况下：（2）（二五）【2-6】由4位数（其中最低位为下溢处理的附加位）经ROM查表舍入法，下溢处理成3位结果，设计使下溢处理平均误差接近于0的ROM表，列出ROM编码表的地址与内容的对应关系。解：ROM下溢处理表16个单元的地址码为00001111，它与其内容（即下溢处理后的3位结果值）的对照关系如下表所示：地址00000001001000110100010101100111内容000001001010010011011100地址1000100110101011

22、1100110111101111内容100101101110110111111111（二六）【2-9】经统计，某机器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。分别求出用等长码、哈夫曼码、只有两种码长的扩展操作码等3种编码方式的操作码平均码长。解：14条指令的等长操作码的平均码长是4位。哈夫曼编码平均码长3.38位。只有两种码长的扩展操作码平均码长3.4位。（二七）【2-10】电文由AJ及空格字符组成，其字符出现频度依次为0.17,0.05,0.20,0.06,0.08,0.03,0.01,0.08,0.13,0.08，0.11。（1） 各字符用等长二进码编码，传送103个字符时，共需传送多少个二进制码码位？（2） 构造哈夫曼数，写出各字符的二进码码位数，计算字符的二进制位平均码长。（3） 用哈夫曼码传送103个字符，比定长码传送减少传送的二进制码码位数是多少？解：（1）共需传送4103位。（2） 哈夫曼树如附图2所示。字符码的二进制位平均码长为3.23位。（3） 可减少传送的二进制码码位数是（4-3.23）103=770位（二八）【