第3讲流水线技术.pptVIP

第3章 流水线技术 3.5 非线性流水线的调度 非线性流水线因为段间设置有反馈回路，一个任务在流水的全过程中，可能会多次通过同一段或越过某些段。这样，如果每拍向流水线送入一个新的任务，将会发生多个任务争用同一功能段的使用冲突现象。 究竟间隔几拍送入下一个任务，才既不发生功能段使用冲突，又能使流水线有较高的吞吐率和效率，是流水线调度要解决的问题。 3.5 非线性流水线的调度 非线性单功能 流水线的任务优化调度和控制方法 ①二维的预约表 ②延迟禁止表F(ForbiddenList)，如 F={1,5,6,8} ③冲突向量C (CollisonVector)。如C= ④ 状态转移图 ⑤ 计算出每种调度方案的平均间隔拍数，从中找出其最小者 3.5 非线性流水线的调度 预约表 横向（向右）：时间（一般用时钟周期表示） 纵向（向下）：流水线的段 例：一个5功能段非线性流水线预约表 如果在第n个时钟周期使用第k段，则在第k行和第n列的交叉处的格子里有一个√。 3.5 非线性流水线的调度 根据预约表写出禁止表F 禁止表F：一个由禁用启动距离构成的集合。 具体方法 对于预约表的每一行的任何一对√，用它们所在的列号相减（大的减小的），列出各种可能的差值，然后删除相同的，剩下的就是禁止表的元素。 在上例中 第一行的差值只有一个：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= 3.5 非线性流水线的调度 根据初始冲突向量C0画出状态转换图 当第一个任务流入流水线后，初始冲突向量C0决定了下一个任务需间隔多少个时钟周期才可以流入。 在第二个任务流入后，新的冲突向量是怎样的呢？ 假设第二个任务是在与第一个任务间隔j个时钟周期流入，这时，由于第一个任务已经在流水线中前进了j个时钟周期，其相应的禁止表中各元素的值都应该减去j。 对冲突向量来说，就是逻辑右移j位（左边补0）。 在冲突向量上，就是对它们的冲突向量进行“或”运算。 SHR(j)（C0）∨C0 其中:SHR(j)表示逻辑右移j位 3.5 非线性流水线的调度 推广到更一般的情况 假设: Ck：当前的冲突向量 j: 允许的时间间隔 则新的冲突向量为： SHR(j)（Ck）∨C0 对于所有允许的时间间隔都按上述步骤求出其新的冲突向量，并且把新的冲突向量作为当前冲突向量，反复使用上述步骤，直到不再产生新的冲突向量为止。 3.5 非线性流水线的调度 从初始冲突向量C0出发，反复应用上述步骤，可以求得所有的冲突向量以及产生这些向量所对应的时间间隔。由此可以画出用冲突向量表示的流水线状态转移图。 有向弧：表示状态转移的方向 弧上的数字：表示引入后续任务（从而产生新的冲突向量）所用的时间间隔（时钟周期数） 3.5 非线性流水线的调度 对于上面的例子 （1） C0= 引入后续任务可用的时间间隔为：2、3、4、7个时钟周期 如果采用2，则新的冲突向量为： ∨= 如果采用3，则新的冲突向量为： ∨= 如果采用4，则新的冲突向量为： ∨= 如果采用7，则新的冲突向量为： ∨= 3.5 非线性流水线的调度 （2）对于新向量，其可用的时间间隔为2个和7个时钟周期。用类似上面的方法，可以求出其后续的冲突向量分别和。 （3）对于其他新向量，也照此处理。 （4）在此基础上，画出状态转移示意