计算机组织结构第三章重要练习题详解

考查：线性流水线和时空图

题目1： 有一指令流水线如下所示
计算机组织结构第三章重要练习题详解
（1）求连续输入10条指令，该流水线的实际吞吐率和效率；
（2）该流水线的“瓶颈”在哪一段？请采取两种不同的措施消除此“瓶颈”。对于你所给出的两种新的流水线，连续输入10条指令时，其实际吞吐率和效率各是多少？

解：
（1）线性流水线解题，先画出时空图
计算机组织结构第三章重要练习题详解
$TP=\frac{10}{200*10+50*4}=\frac{1}{220}$

$E=\frac{200*10+100*10+50*20}{2200*4}=\frac{4000}{8800}=\frac{5}{11}$

（2）瓶颈在S3和S4，
方法一：
把S3和S4分开拆为几步。
计算机组织结构第三章重要练习题详解

方法二：
计算机组织结构第三章重要练习题详解
由时空图可知，两者的实际吞吐率和效率一致的。

$TP=\frac{10}{17*50}=\frac{1}{85}$

$E=\frac{1}{17}$

考查：非线性流水线和流水线调度问题

题目2： 在一个5 段流水线处理机上，各段执行时间均为Δt，需经9Δt 才能完成一个任务，其预约表如表3.8所示：
计算机组织结构第三章重要练习题详解
（1）画出流水线任务调度的状态转移图。
（2）求流水线的最优调度策略和最大吞吐率。
（3）按最优调度策略连续输入6 个任务，求流水线的实际吞吐率是多少。

解：
（1）我们解题的逻辑是：
预约表 $\rightarrow$ 禁止表 $\rightarrow$ 初始冲突标量 $\rightarrow$ 所有冲突变量 $\rightarrow$ 状态机

$S_1$ : 8
$S_2$ : 1
$S_3$ : 3,4
$S_4$ : 1

先写出禁止表： $F=\{8,4,3,1\}$

然后二进制位元化得到初始冲突变量： $C_0=10001101$
根据 $newC_0=shr^j\lor C_0$ 计算出所有的冲突变量

第一轮：
$F_1=\{7,6,5,2\}$

$J=2 \rightarrow C_{1A}=10101111$
$J=5 \rightarrow C_1=10001101=C_0$
$J=6 \rightarrow C_{1B}=10001111$
$J=7 \rightarrow C_1=10001101=C_0$

第二轮：
（1） $C_{1A}=10101111$

$F_2=\{7,5\}$
$J=7 \rightarrow C_{2}=10001101=C_{0}$
$J=5 \rightarrow C_{2}=10001101=C_{0}$

（2） $C_{1B}=10001111$

$F_2=\{7,6,5\}$
$J=7 \rightarrow C_{2}=10001101=C_{0}$
$J=6 \rightarrow C_{2}=10001111=C_{1B}$
$J=5 \rightarrow C_{2}=10001101=C_{0}$

画出状态机：
计算机组织结构第三章重要练习题详解
（2）先找出所有的调度策略：（先写一个的，再写两个的，再写三个的，有条理的写）
枚举出所有的量：2，5，6，7

（5） AVG=5
（7） AVG=7
（2，5） AVG=3.5
（2，7） AVG=4.5
（6，5） AVG=5.5
（6，7） AVG=6.5
（6，6，7） AVG=9.5
（6，6，5） AVG=8.5

最小是（2，5），所以最优策略是（2，5）

因为最小的延迟是3.5
最大吞吐率 $TP_{max}=\frac{1}{3.5 \Delta t}$

（3）
按最优调度策略画出时空图，才能计算各种性能标准：
计算机组织结构第三章重要练习题详解
总共需要到25个 $\Delta t$ ， $TP=\frac{6}{25\Delta t}$ （实际吞吐率就是算完成每个任务所消耗的单位时间）

计算机组织结构 第三章重要练习题详解

相关推荐

计算机组织结构第三章重要练习题详解