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

题型一：（一）（五）（六）题型二：（二）（七）题型三：（三）（四）题型四：（八）（九）（十）（十一）（十二）（十三）（十四）（十五）题型五：（十六）（十七）（十八）题型六：（十九）（二二）（二三）（二五）（二六）（二七）（二八）其他题型考选择题：（二十）（二一）（二四）（二九）（三十）（一）【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）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）V2←V0×V1V1←V2+V3V3←存储器V4←V5×V6V4←V0+V3（3）V0←存储器（4）V0←存储器V2←V0×V1V1←1/V0V3←V2+V0V3←V1×V2V5←V3+V4V5←V3+V4解：（1）三条全并行，完成时间为72拍（2）一、二条并行，链接第三条，完成时间为80拍（3）第一条链接第二条，与第三条串行，与第四条串行，完成时间为222拍（4）全链接，完成时间为104拍（三）【例5-3】在一个4段的流水线处理机上需经7拍才能完成一个任务，其预约表如表5-2所示。表5-27拍才能完成一个任务的预约表段时间1234567S1√√√S2√√S3√S4√√分别写出延迟禁止表F、冲突向量C；画出流水线状态转移图；求出最小平均延迟及流水线的最大吞吐率及其调度时的最佳方案。按此调度方案，输入6个任务，求实际的吞吐率。解：此例可得延迟禁止表F={2,4,6}。初始冲突向量C=（101010）。状态转移图如图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）调度方案输入6个任务，全部完成的时间为5+3+5+3+5+7=28（拍），实际吞吐率Tp=6/28（任务/拍）。可见，最佳的方案应为（1,7）调度方案，输入6个任务的实际吞吐率较之其他方案要更高些。（四）【5-11】在一个5段的流水线处理机上需经9拍才能完成一个任务，其预约表如表5-4所示。分别写出延迟禁止表F、冲突向量C；画出流水线状态转移图；求出最小平均延迟及流水线的最大吞吐率及其调度方案。按此流水线调度方案输入6个任务，求实际吞吐率。表5-49拍才能完成一个任务的预约表段时间T0T1T2T3T4T5T6T7T8S1√√S2√√S3√√√S4√√S5√√解：根据预约表中各个行中打“√”的拍数求出差值，并将这些差值汇集在一起，就可得到延迟禁止表F={1,3,4,8}。由延迟禁止表F可转换得初始冲突向量C=（10001101）。根据初始冲突向量可画出状态转换图如附图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。利用减少树高的办法来加速运算，要求：（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机上所用浮点功能部件的执行时间分别为：相加6拍，相乘7拍，求倒数近似值14拍；在存储器读数6拍，打入寄存器及启动功能部件各1拍。问下列指令组内的哪些指令可以链接？哪些指令不可链接？不能链接的原因是什么？分别计算出各指令全部完成所需的拍数。V3←存储器V2←V0+V1V4←V2×V3解：P201-P202（八）【5-3】有一个浮点乘流水线如图5-36（a）所示，其乘积可直接返回输入端或暂存于相应缓冲寄存器中，画出实现A×B×C×D的时空图以及输入端的变化，并求出流水线的吞吐率和效率；当流水线改为图5-36（b）所示的形式实现同一计算时，求该流水线的效率及吞吐率。解：按图5-36（a）组织，实现A×B×C×D的时空关系如附图16所示。吞吐率：Tp=3/13△t；效率：η=（3×5△t）/（3×13△t）=5/13流水线按图5-36（b）组织，实现A×B×C×D的时空关系如附图17所示。吞吐率：Tp=3/11△t；效率：η=（3×5△t）/（3×11△t）=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、3△t、△t。（1）分别计算在连续输入3条指令和30条指令时的吞吐率和效率。（2）按两种途径之一进行改进，画出流水线结构示意图，同时计算连续输入3条指令和30条指令时的吞吐率和效率。（3）通过对（1）、（2）两小题的计算比较可得出什么结论？解：提高流水线效率，消除速度瓶颈主要有两种途径：①将瓶颈段再细分；②重复设置多个瓶颈段并联工作，给其轮流分配任务。（1）在3段流水线各段经过时间依次为△t、3△t、△t的情况下，连续流入3条指令时，将n=3，m=3，△t1=△t、△t2=3△t、△t3=△t，△tj=3△t代入，可得吞吐率Tp和效率η为（2）若采取将2段细分成3个子段，每个子段均为△t，构成流水线结构如附图10所示。若采取将3个2段并联构成的流水线，其构成如附图20所示。（十一）【5-6】有一个双输入端的加---乘双功能静态流水线，由经过时间为△t、2△t、2△t、△t的1、2、3、4四个子过程构成。“加”按1→2→4连接，“乘”按1→3→4连接，流水线输出设有数据缓冲器，也可将数据直接返回输入。现要执行A×（B+C×（D+E×F））+G×H的运算，请调整计算顺序，画出能获得吞吐率尽量高的流水时空图，标出流水线入、出端数的变化情况，求出完成全部运算的时间及此期间流水线的效率。如对流水线瓶颈子过程再细分，最少需多长时间可完成全部运算？若子过程3不能再细分，只能用并联方法改进，则流水线的效率为多少？解：（十二）【5-7】有一个乘---加双功能静态流水线，“乘”由1→2→3→4完成，“加”由1→5→4完成，各段延时均为△t，输出可直接返回输入或存入缓冲器缓冲。现要求计算长度均为8的A、B两个向量逐对元素求和的连乘积S=Π8（i=1）（Ai+Bi）(1)画出流水线完成此运算的时空图。(2)完成全部运算所需多少△t？此期间流水线的效率是多少？解：（十三）【5-8】带双输入端的加---乘双功能静态流水线有1、2、3、4四个子部件，延时分别为△t、△t、2△t、△t，“加”按1→2→4连接，“乘”按1→3→4连接，输出可直接返回输入或锁存，现欲执行Σ4（i=1）[（ai+bi）×ci]。（1）画出此流水线时空图，标出流水线入端数据变化情况。（2）计算运算全部完成所需时间及在此期间流水线的效率。（3）将瓶颈子部件再细分，画出解此题的时空图。（4）求出按（3）解此题所需时间及在此期间流水线的效率。解：（1）（2）（3）（4）（十四）【5-9】现有长度为8的向量A和B，请分别画出下列4种结构的处理器上求点积A·B的时空图，并求完成全部结果的最少时钟拍数。设处理器中每个部件的输出均可直接送到任何部件的输入或存入缓冲器中，其间的传送延时不计，指令和源操作数均能连续提供。（1）处理器有个一乘法部件和一个加法部件，不能同时工作，部件内也只能以顺序方式工作，完成一次加法或乘法均需5拍。（2）与（1）基本相同，只是乘法部件和加法部件可并行。（3）处理器有一个乘---加双功能静态流水线，乘、加均由5个流水线构成，各段经过时间要1拍。（4）处理器有乘、加两条流水线，可同时工作，各由5段构成，每段经过时间为1拍。解：（十五）【5-2】流水线由4个功能部件组成，每个功能部件的延迟时间为△t，当输入10个数据后间歇5△t又输入10个数据，如此周期性地工作，求此时流水线的吞吐率，并画出其时空图。（十六）【例3-3】P89~P91（十七）【3-5】设中断级屏蔽位“1”对应于开放，“0”对应于屏蔽，各级中断处理程序的中断级屏蔽设置如表3-6所示。表3-6习题3-5中的中断级屏蔽位设置中断处理程序级别中断级屏蔽位第1级第2级第3级第4级第1级0000第2级1011第3级1000第4级1010（1）当中断相应优先次序为1→2→3→4时，其中断处理次序是什么？（2）设所有的中断处理都各需3个单位时间，中断响应和中断返回时间相对中断处理时间少得到多。当机器正在运行用户程序时，同时发生第2、3级中断请求，过两个单位时间后，又同时发生第1、4级中断请求，试画出程序运行过程示意图。解：（1）中断处理（完）的次序为1→3→4→2。（2）CPU运行程序的过程示意图如附图4所示。在该图中，粗短线部分代表进行交换程序状态字的时间，△t为1个单位时间。（十八）【3-6】若机机器共有5级中断请求，中断响应优先次序为1→2→3→4→5，现要求其实际的中断处理次序为1→4→5→2→3，回答下面问题：（1）设计各级中断处理程序的中断级屏蔽位（令“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位定长码表示，信息冗余度为（3-2.17）/3≈28%。冗余度相当大。指令使用频度（pi）指令使用频度（pi）I10.40I50.04I20.30I60.03I30.15I70.03I40.05--（1）改用哈夫曼编码以及扩展的哈夫曼编码；（