j计算机体系结构第三章习题(2)

（2）

C0四个后继状态：C1 =SHR（C0）∨C0 = 10111101 7 （3）

C2 =SHR（C0）∨C0 = 10110111 10110001 C0 （4）

C3 =SHR（C0）∨C0 = 10111011 3 2 （7）

C4 =SHR（C0）∨C0 = 10110001=C0 7 4 7 （2）

C1二个后继状态：C5 =SHR（C1）∨C0 = 10111111 10110111 C2 10111101 C1 （7）

C6 =SHR（C1）∨C0 = 10110001=C0 7 （4）

C2二个后继状态：C7 =SHR（C2）∨C0 = 10111011=C3 3 4 7 2 （7）

C8 =SHR（C2）∨C0 = 10110001=C0

（3）10111011 C3 10111111 C5 C3二个后继状态：C9 =SHR（C3）∨C0 = 10110111=C2 （7）

C10=SHR（C3）∨C0 = 10110001=C0

（7）

C5一个后继状态：C11=SHR（C5）∨C0 = 10110001=C0

由后继状态和引起状态转移的时间间隔可得到状态有向图如上图所示。

（3）由状态转移有向图可得到无冲突的任务调度策略及其平均延迟时间，如下表所示。

调度策略 平均延迟时间 特别地，从C0出发的[3，（4，3）]也是一个 （2，2，7） （2+2+7）△t/3 = 3.67△t 任务调度策略，除第一条有向弧外，第二、三条 （2，7） （2+7）△t/2 = 4.5△t 有向组成一个环路，该调度策略为（4，3）。从表 （3，4，7） （3+4+7）△t/3 = 4.67△t 中可以得到平均延迟时间最小的调度策略为（4， （3，7） （3+7）△t/2 = 5△t 3），该调度策略则为最优调度策略，相应的最小

（4，3，7） （4+3+7）△t/3 = 4.67△t 平均延迟时间为3.5△t，所以流水线的最大吞吐 （4，7） （4+7）△t/2 = 5.5△t 率为：

（7） 7△t TPmax = 1/（3.5△t）= 0.286/△t 3，（4，3） （4+3）△t/2 = 3.5△t

（4）按最优调度策略[3，（4，3）]连续输入8个任务时，流水线的实际吞吐率为： TP = 8/[（3 + 4 + 3 + 4 + 3 + 4 + 3 + 9）△t] = 0.24/△t

3.17 有一个5段流水线的预约表如下：

(1)画出流水线调度状态有向图。

(2)分别求出允许不等间隔调度和等间隔调度的最优调度策略以及这两种调度策略的最大吞吐率。 (3)若连续输入10个任务，求这两种调度策略的实际吞吐率。 时间 1 2 3 4 5 6 7 流水段

S1 × ×

S2 × ×

S3 × ×

S4 × ×

S5 × × 解：（1）根据初始冲突向量的构成方法，对预约表各行中打“×”的拍数求出差值，除去重复的后汇集在一起，即得到延迟禁止表为F =｛1，3，6｝。由F可得到初始冲突向量为： C0 =（100101）

（k）

根据后继冲突向量的递推规则Cj = SHR（Ci）∨C0则可得出所有的后继状态，具体有：

（2）

C0三个后继状态：C1 =SHR（C0）∨C0 = 101101 5 （4）

C2 =SHR（C0）∨C0 = 100111 100101 C0 （5）

C3 =SHR（C0）∨C0 = 100101= C0 4 2 5 5 C1二个后继状态：C4 =SHR（C1）∨C0 = 101111 100111 C2 101101 C1 （5）

C5 =SHR（C1）∨C0 = 100101=C0 5 （4）

C2二个后继状态：C6 =SHR（C2）∨C0 = 100111=C2 4 2 （5）

C7 =SHR（C2）∨C0 = 100101=C0

（5）101111 C4 C4一个后继状态：C8 =SHR（C4）∨C0 = 100101=C0

由后继状态和引起状态转移的时间间隔可得到状态有向图如上图所示。

（2）由状态转移有向图可得到无冲突的任务调度策略及其平均延迟时间，如下表所示。

（2）

调度策略 平均延迟时间 特别地，从C0出发的[4，（4）]也是一个任务 （2，5） （2+5）△t/2 = 3.5△t 调度策略，除第一条有向弧外，第二条有向弧是一 （4，5） （4+5）△t/2 = 4.5△t 个环路，该调度策略为（4）。从表中可以得到平均 （5） 5△t 延迟时间最小的等间隔和不等间隔的调度策略为 （2，2，5） （2+2+5）△t/3 = 3△t [4，（4）]和（2，2，5），相应的最小平均延迟时

4，（4） 4△t 间为4△t和3△t，所以流水线的最大吞吐率为：

TPAmax = 1/（4△t）= 0.25/△t TPBmax = 1/（3△t）= 0.33/△t （3）按等间隔最优调度策略[4，（4）]连续输入10个任务时，流水线的实际吞吐率为： TP = 10/[（4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 7）△t] = 10/43△t 按不等间隔最优调度策略（2，2，5）连续输入10个任务时，流水线的实际吞吐率为： TP = 10/[（2 + 2 + 5 + 2 + 2 + 5 + 2 + 2 + 5 + 7）△t] = 5/17△t