《流水线技术》ppt课件

《《流水线技术》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章流水线技术3.5非线性流水线的调度非线性流水线因为段间设置有反馈回路，一个任务在流水的全过程中，可能会多次通过同一段或越过某些段。这样，如果每拍向流水线送入一个新的任务，将会发生多个任务争用同一功能段的使用冲突现象。究竟间隔几拍送入下一个任务，才既不发生功能段使用冲突，又能使流水线有较高的吞吐率和效率，是流水线调度要解决的问题。3.5非线性流水线的调度非线性单功能流水线的任务优化调度和控制方法①二维的预约表②延迟禁止表F(ForbiddenList)，如F={1,5,6,8}③冲突向量C(CollisonVector

2、)。如C=(10110001)④状态转移图⑤计算出每种调度方案的平均间隔拍数，从中找出其最小者3.5非线性流水线的调度预约表横向（向右）：时间（一般用时钟周期表示）纵向（向下）：流水线的段例：一个5功能段非线性流水线预约表如果在第n个时钟周期使用第k段，则在第k行和第n列的交叉处的格子里有一个√。3.5非线性流水线的调度根据预约表写出禁止表F禁止表F：一个由禁用启动距离构成的集合。具体方法对于预约表的每一行的任何一对√，用它们所在的列号相减（大的减小的），列出各种可能的差值，然后删除相同的，剩下的就是禁止表的元素。在上例中

3、第一行的差值只有一个：8；第二行的差值有3个：1，5，6；第3行只有一个√，没有差值；第4和第5行的差值都只有一个：1；其禁止表是：F={1，5，6，8}3.5非线性流水线的调度根据禁止表F写出初始冲突向量C0（进行从一个集合到一个二进制位串的变换）冲突向量C：一个N位的二进制位串。设C0=（cNcN-1…ci…c2c1），则：ci=0：允许间隔i个时钟周期后送入后续任务ci=1：不允许间隔i个时钟周期后送入后续任务对于上面的例子F={1，5，6，8}C0=（10110001）3.5非线性流水线的调度根据初始冲突向量C0画

4、出状态转换图当第一个任务流入流水线后，初始冲突向量C0决定了下一个任务需间隔多少个时钟周期才可以流入。在第二个任务流入后，新的冲突向量是怎样的呢？假设第二个任务是在与第一个任务间隔j个时钟周期流入，这时，由于第一个任务已经在流水线中前进了j个时钟周期，其相应的禁止表中各元素的值都应该减去j。对冲突向量来说，就是逻辑右移j位（左边补0）。在冲突向量上，就是对它们的冲突向量进行“或”运算。SHR(j)（C0）∨C0其中:SHR(j)表示逻辑右移j位3.5非线性流水线的调度推广到更一般的情况假设:Ck：当前的冲突向量j:允许的时

5、间间隔则新的冲突向量为：SHR(j)（Ck）∨C0对于所有允许的时间间隔都按上述步骤求出其新的冲突向量，并且把新的冲突向量作为当前冲突向量，反复使用上述步骤，直到不再产生新的冲突向量为止。3.5非线性流水线的调度从初始冲突向量C0出发，反复应用上述步骤，可以求得所有的冲突向量以及产生这些向量所对应的时间间隔。由此可以画出用冲突向量表示的流水线状态转移图。有向弧：表示状态转移的方向弧上的数字：表示引入后续任务（从而产生新的冲突向量）所用的时间间隔（时钟周期数）3.5非线性流水线的调度对于上面的例子（1）C0=（1011000

6、1）引入后续任务可用的时间间隔为：2、3、4、7个时钟周期如果采用2，则新的冲突向量为：（00101100）∨（10110001）=（10111101）如果采用3，则新的冲突向量为：（00010110）∨（10110001）=（10110111）如果采用4，则新的冲突向量为：（00001011）∨（10110001）=（10111011）如果采用7，则新的冲突向量为：（00000001）∨（10110001）=（10110001）3.5非线性流水线的调度（2）对于新向量（10111101），其可用的时间间隔为2个和7个时钟

7、周期。用类似上面的方法，可以求出其后续的冲突向量分别为10111101）和（10110001）。（3）对于其他新向量，也照此处理。（4）在此基础上，画出状态转移示意图。3.5非线性流水线的调度根据状态转换图写出最优调度方案根据流水线状态图，由初始状态出发，任何一个闭合回路即为一种调度方案。列出所有可能的调度方案，计算出每种方案的平均时间间隔，从中找出其最小者即为最优调度方案。上例中，各种调度方案及其平均间隔时间。3.5非线性流水线的调度最佳方案：（3，4）平均间隔时间：3.5个时钟周期（吞吐率最高）尽管（4，3）调度方案平

8、均间隔拍数也是3.5拍，但若实际流入任务数不是循环所需任务数的整数倍，则其实际吞吐率相对会低些，所以不作为最佳调度方案。方案（3，4）是一种不等时间间隔的调度方案，与等间隔的调度方案相比，在控制上要复杂得多。为了简化控制，也可以采用等间隔时间的调度方案，但吞吐率和效率往往会下降不少。在上述例子中，等时间