1.计算机系统中有三个部件可以改进，这三个部件的部件加速比为:
部件加速比1=30 部件加速比2=20 部件加速比3=10； ；
(1) 如果部件1和部件2的可改进比例均为 30%，那么当部件3的可改进比例为多少时，系统加速
比才可以达到10 ？
(2)
如果三个部件的可改进比例分别为
30%、30%和20%，三个部件同时改进，那么系统中不可加
速部分的执行时间在总执行时间中占的比例是多少？
解：(1)在多个部件可改进情况下，
Sn
Amdahl定理的扩展:
(1
Fi)
Fi S
已知 S1 = 30 , S2 = 20 , S3= 10 , Sn = 10 , F1 = 0.3 , F2 = 0.3，得: 10
1-(0.3 0.3 F3) (0.3/30 0.3/20 F3/10)
得F3 = 0.36，即部件3的可改进比例为 36%。 (2 )设系统改进前的执行时间为 可改进部分的执行时间为 0.2T。
已知3个部件改进后的加速比分别为 Tn
T,则3个部件改进前的执行时间为： (0.3+0.3+0.2 ) T = 0.8T，不
S1 = 30 , S2 = 20 , S3 = 10 ,因此3个部件改进后的执行时间为:
0.3T 0.3T 0.2T 30
20
10
0.045T
改进后整个系统的执行时间为： Tn = 0.045T+0.2T = 0.245T 那么系统中不可改进部分的执行时间在总执行时间中占的比例是: 0.2T
0.82
0.245T
2.有一个5段流水线，各段执行时间均为△ t.其预约表如下 时间 Si S： 1 X 2 5 4 5 7 X X X 址 X X X
(1) 画出流水线任务调度的状态转移图。
(2) 分别求出允许不等时间间隔调度和等时间间隔调度的两种最优调度策略，以及这两种调度策略的流水线 最大吞吐率。
(3) 若连续输入10个任务，求这两种调度策略的流水线实际吞吐率和加速比。
解：(1)根据初始冲突向量的构成方法，对预约表各行中打“x”的拍数求出差值，除去重复的后汇集在- 起，即得到延迟禁止表为 F = {1, 3, 6}o由F可得到初始冲突向量为：
CO = (100101)
根据后继冲突向量的递推规则
Cj = SHR ( k) (Ci )V CO则可得出所有的后继状态，具体有:
C0三个后继状态： C1 =SHR( 2) (C0)V CO = 101101
C2 =SHR (4) ( C0)V C0 = 100111 C3 =SHR( 5) (C0)V C0 = 100101= C0
C1 二个后继状态： C4 =SHR( 2) ( C1)V C0 = 101111
C5 =SHR (5) (C1)V C0 = 100101=C0
C2二个后继状态： C6 =SHR( 4) ( C2)V C0 = 100111=C2
C7 =SHR( 5) ( C2)V C0 = 100101=C0
C4 一个后继状态： C8 =SHR( 5) ( C4)V C0 = 100101=C0
由后继状态和引起状态转移的时间间隔可得到状态有向图如上图所示。
调度策略 一个任务
(2, 5) 弧是一 (4, 5) 到平均
(5)
平均延迟时间
特别地，从C0出发的［4 , (4)］也是
(2+5)A t/2 = 3.5
△ t
调度策略，除第一条有向弧外，第二条有向
(4+5)^ t/2 = 4.5
△
个环路，该调度策略为(4)。从表中可以得 延迟时间最小的等间隔和不等间隔的调度策
t 5
△ t
(2+2+5)^ t/3 = 3 △ t
［4
, (4)］和(2, 2, 5),相应的最小平均 间为4△ t和3At，所以流水线的最大吞吐
略为 延迟时 4 , (4) 率为：
(2, 2, 5)
4
△ t
(2)由状态转移有向图可得到无冲突的任务调度策略及其平均延迟时间，如下表所示。 TPAmax = 1/ ( t) = 0.25/ △ t TPBmax = 1/ (3 △ t) = 0.33/ △ t (3) 按等间隔最优调度策略[4 , (4)]连续输入10个任务时，流水线的实际吞吐率为：
TP = 10/[ TP = 10/[
(4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 7 (2 + 2 + 5 + 2 + 2 + 5 + 2 + 2 + 5 + 7
) △ t] = 10/43 △ t ) △ t] = 5/17 △ t
按不等间隔最优调度策略(2, 2, 5)连续输入10个任务时，流水线的实际吞吐率为：
计算机体系结构期末考试试题及答案
