关于非线性流水线启动算法及进展的学习
1. 非线性流水线简介
1.1. 流水线处理
所谓流水线处理是指将一个大的计算任务分成若干个子任务，是每个子任务在一个专门的硬件站上执行，一个任务需顺序地经过流水线中多个站的处理才能完成。因此，可使用流水线处理的计算任务必须可分，而且子任务处理时间越平均，流水线的效率越高。 1.2. 流水线分类及区别
按照流水线中各硬件站之间是否有反馈回路，可将流水线分成线性流水线和非线性流水线两大类。在线性流水线中，各硬件站串行连接，其特点是：从输入端开始，每一站只顺序使用一次，便可从输出流出一个结果。
非线性流水线除了串行连接的通路外，还有反馈回路，其结构比较复杂。使用非线性流水线处理的任务的特点：从输入到输出的一次流水过程中并不是每个站顺序只使用一次，而是有的站可能使用多次。要解决此问题就需要增加重复硬件站把非线性流水线做成线性流水线，或增加反馈回路，重复利用某一站。
线性流水线的调度比较简单，因为对各任务而言，每站只顺序使用一次，不会在某时刻出现两个任务争用一个硬件站的情况，只需每个时钟节拍输入一个任务即不会出现冲突问题。然而在非线性流水线中，由于一个站可能被多次使用，如果仍按线性流水线输入方法就可能在某个时刻有两个或多个任务共同争用一个硬件站，即产生冲突，使流水线不能通畅。所以在非线性流水线中就存在在什么时刻输入任务不会冲突的问题，也就是调度问题。
2. 流水线调度问题
2.1. 非线性流水线无冲突调度的目标
非线性流水线调度是找出平均允许启动距离最小的启动循环。按照这样的启动循环向流水线的输入端输入任务．所有功能段在任何时刻都没有冲突，而且流水线的工作效率最高。 2.2. 基本解决方法
目前有两种方法解决调度问题：
第一种是构造冲突向量，利用冲突向量生成状态图：在状态图中找一个平均等待时间最小的有圈子图，由有圈子图可生成调度序列。
第二种方法是通过插入时间延迟段改造流水线的时间关系，使得给定的恒定循环调度不会产生冲突，从而达到优化的目的。
3. 几种常见的调度方法
3.1. 不插入时间延迟段的恒定循环调度方案
基本思想是：找出一个最小时间间隔并按此时间间隔进行调度，使多个任务输入流水线，并在处理过程中不会出现它们争用某硬件站的情况。
表1.预约表
S1 S2 S3 S4 t1 × × t2 × t3 × t4 × t5 × t6 t7 × 如果Si行有两个相距d时钟周期站使用，则相距d时钟周期输入一个新任务一定会存在某个时刻争用Si的情况。所以，我们可以构造一个禁止集合F。如表一，S1的禁止时钟周期为6，S2禁止时钟周期为4，S3禁止时钟周期为1，S4无
禁止时钟周期，故禁止集合F={1,4,6}。也就是说，任意两任务的间隔D不能属于F。设输入第T（T>1）个任务，每个任务间隔为d时钟周期，那么(T-1)d,(T-2)d,(T-3)d……3d,2d,1d都不属于禁止集合F。如表1，可求出d为5和7，取最小的5作为时间间隔不会产生冲突。 3.2. 迭加原理生成状态图调度方案
虽然恒定等待时间调度方案简单，控制容易，但多数情况下恒定等待时间调度不能使流水线达到最高效率。因而还需要寻求其它途径进行调度，使流水线的效率提高，这就是下面要讨论的非均匀调度。
经分析的，到底在哪个时刻输入新任务与当时流水线上各任务的推进情况有关。因此，我们可以用禁止集合来表示冲突，集合中记录产生冲突的时间间隔，如表1，禁止集合F={1,4,6}，意思是：任务2可以在间隔时钟周期2,3,5输入。假设，任务2间隔时钟周期2输入，即在t3时刻输入，那么t1，t2时刻是绝对不会冲突的，此时任务1的禁止集合可以减2忽略t1,t2时刻，增加t8,t9时刻的监视，t3为逻辑上的t1时刻，记任务1的禁止集合为f1={2,4},同样任务2的禁止集合f2={1,4,6}。f1∪f2即为任务3等待输入时流水线里的禁止集合，f3=｛1，2，4，6｝，即任务3可以间隔时钟周期3,5输入。在新的禁止集合的基础上，按同样的方法可以再生成后续禁止集合，此过程一直进行到没有不同新的禁止产生为止。此时会形成以禁止集合为顶点，时钟间隔为边的状态转移图，且存在多条闭合回路，按任意条闭合回路调度流水线都不会产生冲突，只需选取一组平均间隔最小，效率最高的组合作为调度方案即可。
3.3. 计算最小平均等待时间MAL，插入时间延迟段优化恒定循环时间达到下限 恒定等待时间调度方案简单，容易控制，但一般不能使流水线达到最大效率；有圈子图方案虽效率有所提高，但操作复杂，而且还有优化空间，所以提出两套方案结合的方案。
给定的恒定循环时间有个下限，最小平均等待时间MAL的下限是预约表任一行中格子内符号的最大个数。该方案的目标就是以恒定等待时间启动且该恒定等待时间达到MAL下限。
具体步骤是先使用有圈子图方法求出MAL，若该MAL等于预约表任一行中格子内符号的最大个数，即已经达到下限，则不需要优化，否则使用插入时间延迟段方法优化MAL。插入非计算延迟段D，使预约表中每一行任意符号之间的间隔都不为MAL下限及下限的倍数，构成新预约表。这样就使得MAL等于预约表任一行中格子内符号的最大个数．即最优的MAL。
举例：
表2
根据有圈子图方案求的MAL=4，其中一个等待循环为（5，3），得时空运行表3：
表3
S1 S2 S3 S4 1 #1 2 #1 3 #1 4 #1 5 #1 6 #2 #1 7 #1 #2 8 #2 9 #3 #2 10 #3 #2 11 #2 #3 12 #2 #3 添加时间延迟段得新预约表4：
表4
S1 S2 S3 S4 D1 1 # 2 # 3 # 4 #
5 # 6 # 7 # # 新预约表可以以优化后的MAL=2恒定时间循环启动，时空运行表5如下：
表5
S1 S2 S3 S4 D1
1 #1 2 #1 3 #2 #1 4 #2 #1 5 #3 #2 #1 6 #3 #1 #2 7 #1 #3 #2 8 #1 #2 #3 9 #2 #3 10 #2 #3 11 #3 12 #3
