题型一：（一）（五）（六） 题型二：（二）（七） 题型三：（三）（四）
题型四：（八）（九）（十）（十一）（十二）（十三）（十四）（十五） 题型五：（十六）（十七）（十八）
题型六：（十九）（二二）（二三）（二五）（二六）（二七）（二八） 其他题型考选择题：（二十）（二一）（二四）（二九）（三十） （一）【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×V1
V1←V2+V3 V3←存储器
V4←V5×V6 V4←V0+ V3
（3） V0←存储器 （4）V0←存储器
V2←V0×V1 V1←1/ V0 V3←V2+ V0 V3←V1×V2 V5←V3+ V4 V5←V3+ V4
解：（1）三条全并行，完成时间为72拍
（2）一、二条并行，链接第三条，完成时间为80拍
（3）第一条链接第二条，与第三条串行，与第四条串行，完成时间为222拍
（4）全链接，完成时间为104拍
（三）【例5-3】在一个4段的流水线处理机上需经7拍才能完成一个任务，其预约表如表5-2所示。
表5-2 7拍才能完成一个任务的预约表 段 时间 1 2 3
4 5 6 7
S1 S2 S3 S4 √ √ √ √ √ √ √ √ 分别写出延迟禁止表F、冲突向量C；画出流水线状态转移图；求出最小平均延迟及流水线的最大吞吐率及其调度时的最佳方案。按此调度方案，输入6个任务，求实际的吞吐率。 解：此例可得延迟禁止表F={2,4,6}。
初始冲突向量C=（101010）。 状态转移图如图5-29所示。
各种调度方案及其相应的平均延迟如表5-3所示。 表5-3 调度方案及其相应的平均延迟 调度方案 （1,7） （3,5） 平均延迟/拍 4 4
（5,3） （5） 4 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-4 9拍才能完成一个任务的预约表 段 时间 T0 S1 S2 √ T1 √ T2 √ T3
T4 T5 T6 T7 T8 √
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） （2,7） （5） 平均延迟/拍 3.5 4.5 5 调度方案 （6,7） （7） （5,2）
平均延迟/拍 6.5 7 3.5
福建农林大学系统结构计算题
