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

1、-. z.题型一：一五六题型二：二七题型三：三四题型四：八九十十一十二十三十四十五题型五：十六十七十八题型六：十九二二二三二五二六二七二八其他题型考选择题：二十二一二四二九三十一【7-6】由霍纳法则给定的表达式如下：E=a(b+c(d+e(f+gh)利用减少树高的方法来加速运算，要求：画出树形流程图。确定TP、P、SP、EP的值。解：1假设用单处理机处理，T1=7，改成E=ace(f+gh)+a(b+cd)，其计算的树形流程图如附图46所示。P=3；TP=4；SP=T1/TP=7/4；EP=SP/P=7/12二【6-2】设向量长度均为64，在CRAY-1机上所用浮点功能部件的执行时间分别为：相

2、加6拍，相乘7拍，求倒数近似值14拍；在存储器读数6拍，打入存放器及启动功能部件各1拍。问以下各指令组的哪些指令可以？哪些指令不可？不能的原因是什么？分别计算出各指令全部完成所需的拍数。V0存储器2V2V0V1V1V2+V3 V3存储器V4V5V6 V4V0+ V3V0存储器4V0存储器V2V0V1 V11/ V0V3V2+ V0 V3V1V2V5V3+ V4 V5V3+ V4解：1三条全并行，完成时间为72拍2一、二条并行，第三条，完成时间为80拍3第一条第二条，与第三条串行，与第四条串行，完成时间为222拍4全，完成时间为104拍三【例5-3】在一个4段的流水线处理机上需经7拍才能完成一个

3、任务，其预约表如表5-2所示。表5-2 7拍才能完成一个任务的预约表段时间1234567 S1 S2 S3 S4分别写出延迟制止表F、冲突向量C；画出流水线状态转移图；求出最小平均延迟及流水线的最大吞吐率及其调度时的最正确方案。按此调度方案，输入6个任务，际的吞吐率。解：此例可得延迟制止表F=2,4,6。初始冲突向量C=101010。状态转移图如图5-29所示。各种调度方案及其相应的平均延迟如表5-3所示。表5-3 调度方案及其相应的平均延迟调度方案平均延迟/拍1,7 43,5 45,3 45 4由表5-3可知，最小平均延迟为4拍。此时流水线的最大吞吐率Tpma*=1/4任务/拍。最正确调度方

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调度方案输入6个任务，全部完成的时间为5+3+5+3+5+7=28拍，实际吞吐率Tp=6/28任务/拍。可见，最正确的方案应为1,7调度方案，输入6个任务的实际吞吐率较之其他方案要更高些。四【5-11】在一个5段的流水线处理机上需经9拍才能完成一个任务，其预约表如表5-4所示。分别写出延迟制止表F、冲突向量C；画出流水线状

5、态转移图；求出最小平均延迟及流水线的最大吞吐率及其调度方案。按此流水线调度方案输入6个任务，际吞吐率。表5-4 9拍才能完成一个任务的预约表段时间 T0T1T2T3T4T5T6T7T8S1S2S3S4S5解：根据预约表中各个行中打的拍数求出差值，并将这些差值聚集在一起，就可得到延迟制止表F=1,3,4,8。由延迟制止表F可转换得初始冲突向量C=10001101。根据初始冲突向量可画出状态转换图如附图31所示。各种周期性调度方案列于附表15。由附表15可知最小平均延迟为3.5拍。此时，Tpma*=1/3.5任务/拍。最正确调度方案为2,5。附表15 周期性调度方案调度方案平均延迟/拍调度方案平均

6、延迟/拍2,53.56,76.52,74.577555,23.56,55.566按2,5调度方案实际输入6个任务的时空图如附图32所示。实际吞吐率Tp=6/25任务/拍。五【例7-4】计算E1=a+b*+c*+d*。利用减少树高的方法来加速运算，要求：画出树形流程图。确定TP、P、SP、EP的值。解：1利用霍纳法可得到E1=a+*(b+*(c+*(d)。假设用单处理机处理，T1=7，改成E1=a+*(b+*(c+*(d)。其计算的树形流程图如附图7-17a所示。TP=4、P=3、SP=3/2、EP=1/2六【例7-6】表达式E2=a+b(c+def+g)+h。利用减少树高的方法来加速运算，要求

7、：画出树形流程图。确定TP、P、SP、EP的值。解：P253-P254七【P201】设向量长度均为64，在CRAY-1机上所用浮点功能部件的执行时间分别为：相加6拍，相乘7拍，求倒数近似值14拍；在存储器读数6拍，打入存放器及启动功能部件各1拍。问以下指令组的哪些指令可以？哪些指令不可？不能的原因是什么？分别计算出各指令全部完成所需的拍数。V3存储器V2V0+V1V4V2V3解：P201-P202八【5-3】有一个浮点乘流水线如图5-36a所示，其乘积可直接返回输入端或暂存于相应缓冲存放器中，画出实现ABCD的时空图以及输入端的变化，并求出流水线的吞吐率和效率；当流水线改为图5-36b所示的形

8、式实现同一计算时，求该流水线的效率及吞吐率。解：按图5-36a组织，实现ABCD的时空关系如附图16所示。吞吐率：Tp=3/13t ；效率：=35t/313t=5/13流水线按图5-36b组织，实现ABCD的时空关系如附图17所示。吞吐率：Tp=3/11t；效率：=35t/311t=5/11九【5-4】一个4段的双输入端规格化浮点加法流水线，每段经过时间为10ns，输出可直接返回输入或将结果暂存于相应缓存器中，问最少需要经多长时间才能求出10i=1Ai，并画出时空图。解：按A1+A2+A3+A4+A9+A10+A5+A6+A7+A8流水的时空图如附图18所示。十【5-5】为提高流水线效率可采用

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

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

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

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

13、解：十五【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级1010当中断相应优先次序为1234时，其中断处理次序是什么？设所有的中断处理都各需3个单位时间，中断响应和中断返回时间相对中断处理时间少得到多。当机器正在

14、运行用户程序时，同时发生第2、3级中断请求，过两个单位时间后，又同时发生第1、4级中断请求，试画出程序运行过程示意图。解：1中断处理完的次序为1342。CPU运行程序的过程示意图如附图4所示。在该图中，粗短线局部代表进展交换程序状态字的时间，t为1个单位时间。十八【3-6】假设机机器共有5级中断请求，中断响应优先次序为12345，现要求其实际的中断处理次序为14523，答复下面问题：设计各级中断处理程序的中断级屏蔽位令1对应于屏蔽，0对应于开放；假设在运行用户程序时，同时出现第4、2级中断请求，而在处理第2级中断未完成时，又同时出现第1、3、5级中断请求，请画出此程序运行过程示意图。解：12十

15、九【例2-5】现假设*模型机共有nn=7条指令，使用频度如表2-4所示。假设操作码用定长表示，需要3位。而按信息论观点，假设各种指令的出现是互相独立的实际并不都是如此，操作码的信息源熵信息源所含平均信息量H=-ni=1pi1bpi。由表2-4的数据可得H=-ni=1pi1bpi=2.17。说明表示这7种指令的操作码平均只需2.17位即可。现在用3位定长码表示，信息冗余度为3-2.17/328%。冗余度相当大。指令使用频度pi指令使用频度piI10.40I50.04I20.30I60.03I30.15I70.03I40.05-改用哈夫曼编码以及扩展的哈夫曼编码；构造哈夫曼数；解：1指令频度pi操

16、作码OP使用哈夫曼编码OP长度li利用哈夫曼概念的扩展操作码OP长度liI10.4001002I20.30102012I30.151103102I40.0511100511004I50.0411101511014I60.0311110511104I70.03111115111142二十【例2-6】P59二一【例2-7】假设*机要求有：三地址指令4条，单地址指令255条，零地址指令16条。设指令字长为12位，每个地址码长为3位。能否以扩展操作码为其编码？如果单地址指令改为254条呢？解：P60二二【例2-8】*模型机9条指令的使用频度如表2-7所示。要求有两种指令字长，都按双操作数指令格式编排，

17、采用扩展操作码，并限制只能有两种操作码码长。设该机有假设干通用存放器，主存为16位宽，按字节编址，采用按整数边界存储，任何指令都在一个主存周期中取得，短指令为存放器-存放器型，长指令为存放器-主存型，主存地址应能变址寻址。表2-7 模型机指令指令使用频度指令使用频度指令使用频度ADD加STO存CIL循环左移30%7%3%SUB减JMP转移CLA清加24%7%20%JOMSHR右移STP停机6%2%1%改用哈夫曼编码以及扩展的哈夫曼编码；构造哈夫曼数；计算平均码长解：1哈夫曼编码：ADD加30%01SUB减24%11CLA20%10JOM6%0001STO7%0011JMP7%0010SHR2%

18、000001CIL3%00001STP1%00000扩展的操作码编码：ADD加30%00SUB减24%01CLA20%10JOM6%11000STO7%11001JMP7%11010SHR2%11011CIL3%11100STP1%11101哈夫曼树：平均码长：哈夫曼编码：2.61位；扩展码：2.78位。二三【2-4】设*机器阶值6位、尾数48位，阶符和数符不在其，当尾数分别2、8、16为基时，在非负阶、正尾数、规格化情况下，求出其最小阶、最大阶、阶的个数、最小尾数值、最大尾数值、可表示的最小值和最大值及可表示数的个数。解：p=6，m=48时，在非负阶、规格化、正尾数的情况下，rm=2,8,1

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

20、结果值的对照关系如下表所示：地址00000001001000110100010101100111容000001001010010011011100地址10001001101010111100110111101111容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位。哈夫曼编码平均

21、码长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。各字符用等长二进码编码，传送103个字符时，共需传送多少个二进制码码位？构造哈夫曼数，写出各字符的二进码码位数，计算字符的二进制位平均码长。用哈夫曼码传送103个字符，比定长码传送减少传送的二进制码码位数是多少？解：1共需传送4103位。哈夫曼树如附图2所示。字符码的二进制位平均码长为3.23位。可减少传送的二进制码码位数是4-3.23103=770位二八【2-11】用于文字处理的*专用机，每