题型一:(一)(五)(六) 题型二:(二)(七) 题型三:(三)(四)
题型四:(八)(九)(十)(十一)(十二)(十三)(十四)(十五) 题型五:(十六)(十七)(十八)
题型六:(十九)(二二)(二三)(二五)(二六)(二七)(二八) 其他题型考选择题:(二十)(二一)(二四)(二九)(三十) (一)【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
福建农林大学系统结构计算题
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)