流水线时空图

流水线要经过装入、充满、排空三个阶段。

静态流水线

定义：在同一时段内，只有一种任务。

例子：A*B = a1b1 + a2b2 + a3b3 + a4b4

前面四个任务是乘法，后面三个任务是加法。我们看到乘法并没有交织到加法，而是等加法执行完，再执行。

动态流水线

定义：在同一时段内，多种任务在执行（如乘法和加法同时运行）。

例子：A*B = a1b1 + a2b2 + a3b3 + a4b4

第一个黄色任务表示a1b1+a2b2，由于第二个黄色任务a3b3+a4b4需要a4b4结束后再进行，所以没有紧跟着前一个黄色任务。同理，最后一个加法，要在前两个加法结束后才能进行。

吞吐率（TP）

定义：单位时间完成的指令数（或任务数，这个任务有可能是浮点加法）。

例子：

这个例子中各功能段用时不同，受S2的制约，出现了如上图所示的空隙，最终TP计算式为：

其中tj为各段时间中最长的一段时间。

加速比

定义：串行用时与流水用时之比。

下面是加速比趋于无穷的情况，看来加速比是有上限的，且这个值接近于功能段数。

效率

定义：因为要完成每个功能段需要多个设备共同工作，在整个流水过程中，这些设备并不是一直都工作，我们让所有设备实际工作时间之和与假定整个流水过程中所有设备一直工作的时间总和之比称为效率（有点摸不着头脑，看下面的例子）。

效率计算式为：

分母m*T表示时空图中m段与T（流水时间）围成的面积，分子m*n*t0表示n个任务实际占用面积之和。

如果各段时间不相等（这个例子可以参见上面的例子）：

非线性流水线的调度

对于一个任务，在它的节拍中，存在至少两个节拍使用的是同一功能段，则称它为非线性流水，如果不注意前后两个任务相隔的节拍数，很有可能发生功能段争用（如在上面吞吐量部分的时空图中，我们就不能前后两个任务相隔1拍或2拍）。为了找出这些不能使用的节拍间隔，我们引入了预约表，正如名字所示，一个任务说它在什么时候要使用哪一段，我预约了。随之而来的一些重要概念有：

• 禁止表F：{1,5,6,8}，相邻两个任务的间隔拍数不能为1，5，6，8。扫描每一行，该行星星之间的距离种类，如本例中第二行，星星之间相隔1、5或6，所以得出间隔拍数不能为1、5和6。
• 初始冲突向量：第i位的状态用以表示与当时相隔i拍给流水线送入后继任务是否会发生功能段的使用冲突。如不发生，0，否则，1。C=(10110001)。
• 状态转换图：由初始冲突向量而来。将C放到一个6位逻辑右移移位器，当从移位器移出0，用移位器中的值与初始冲突向量做“按位或”，得到一个新的冲突向量。当移位器移出1，不做任何处理。重复这个步骤。对产生的每一个新的冲突向量做同样处理。在初始冲突向量和所有形成的冲突向量之间，箭头连接。

• 接下来是简单循环：状态图中的环（带方向）。像（3,5）因为终止于5处有自环，所以也是简单循环。

简单循环	平均启动距离
（1，7）	4
（3，5）	4
（5，7）	6
（3，5，7）	5
（5，3，7）	5
（5）	5

最小循环为（1，7）、（3，5）
最小恒定循环为（5）

恒定启动循环（5）的流水线工作状态：