非线性流水线调度

非线性流水线的调度张长明[e-mail]：ncepubd非线性流水线的表示一条非线性流水线一般需要一个各流水段之间的连接图和一张预约表共同来表示。非线性流水线的冲突向一条非线性流水线的输入端连续输入两个任务之间的时间间隔称为非线性流水线的启动距离或等待时间。启动距离通常用时钟周期数来表示，它是一个正整数。当以某一个启动距离向一条非线性流水线连续输入任务时，可能在某一个流水段，或某几个流水段中发生有几个任务同时争用同一个流水段的情况，这种情况就是非线性流水线中的冲突。非线性流水线中的冲突举例启动距离为3的流水线冲突情况禁止启动距离引起非线性流水线流水段冲突的启动距离称为禁止启动距离。如上例中启动距离3是禁止启动距离禁止表要正确地调度一条非线性流水线，首先要找出流水线的所有禁止启动距离。把一条非线性流水线的所有禁止启动距离组合在一起就形成一个集合，通常把这个集合称为非线性流水线的禁止表。由预约表得到禁止表的方法很简单，只要把预约表的每一行中任意两个“×”之间的距离都计算出来，去掉重复的，由这种数组成的一个集合就是这条非线性流水线的禁止表。禁止表如对于前例的预约表第1行的第1列与第4列的两个“×”之间的距离为3；第1列与第7列的两个“×”之间的距离为6；第4列与第7列的两个“×”之间的距离也为3；第2行的第2列与第5列的两个“×”之间的距离也为3；第3行的第2列与第6列的两个“×”之间的距离为4。因此，对应的非线性流水线的禁止表为（3，4，6）。启动循环有些启动距离在非线性流水线的所有功能段，在任何时间都不会发生冲突。如前例中启动距离为5时，其预约表如下：启动循环非线性流水线中，不发生冲突的启动距离不一定仅仅是一个常数，在一般情况下是一个循环数列。例如，前例中采用1、7、1、7、…交替的启动距离时，任何一个时钟周期也不会发生冲突。启动循环使非线性流水线的任何一个流水段在任何一个时钟周期都不发生冲突的循环数列称为非线性流水线的启动循环。只有一个启动距离的启动循环又称为恒定循环。把一个启动循环内的所有启动距离相加再除以这个启动循环内的启动距离个数就得到这个启动循环的平均启动距离。无冲突调度方法非线性流水线无冲突调度的主要目标是要找出具有最小平均启动距离的启动循环，按照这样的启动循环向非线性流水线的输入端输入任务，流水线的工作速度最快，而且所有流水段在任何时间都没有冲突。基本步骤(1)写出流水线的禁止表和初始冲突向量。(2)画出调度流水线的状态图。(3)求出流水线的各种启动循环和对应的平均启动距离。(4)找出平均启动距离最小的启动循环。禁止表和冲突向量冲突向量用二进制数表示，其长度是禁止表中的最大距离，每一位在向量中的位置i，对应于i个时钟周期的启动距离，若该启动距离是禁止启动距离，则该位为1，否则为0。例如：禁止表F=（6，4，2），则：冲突向量C＝（C6C5C4C3C2C1），由于禁止表是（6，4，2），得到C6＝C4＝C2＝1，其余位为0，因此，冲突向量为C＝（101010）。由冲突向量构造状态图把上面得到的冲突向量C作为初始冲突向量送入一个逻辑右移移位器：当从移位器移出的位为0时，用移位器中的值与初始冲突向量作“按位或”运算，得到一个新的冲突向量；若移位器移出的位为1，不作任何处理；移位器继续右移，如此重复。对于中间形成的每一个新的冲突向量，也要按照这一方法进行处理。在初始冲突向量和所有的新形成的冲突向量之间用带箭头的线连接，表示各种状态之间的转换关系。当新形成的冲突向量出现重复时可以合并到一起。无冲突调度方法下面通过一个具体的例子来说明非线性流水线的调度方法。一条有4个流水段的非线性流水线，每个流水段的延迟时间都相等，其预约表如下：流水线的禁止表和初始冲突向量对于S1，禁止启动距离是7-1=6；对于S2，禁止启动距离是6-2=4；对于S3，禁止启动距离是5-3=2；所以：禁止表F=（6,4,2）冲突向量C=（101010）流水线的状态图及各简单启动循环简单循环平均启动距离（1，7）4（3，7）5（5，7）6（3，5，7）5（5，3，7）5（3，5）4（5）5（7）7