《第3章流水线技术.ppt》由会员分享,可在线阅读,更多相关《第3章流水线技术.ppt(13页珍藏版)》请在三一文库上搜索。
1、第3章 流水线技术,3.5 非线性流水线的调度 非线性流水线因为段间设置有反馈回路,一个任务在流水的全过程中,可能会多次通过同一段或越过某些段。这样,如果每拍向流水线送入一个新的任务,将会发生多个任务争用同一功能段的使用冲突现象。 究竟间隔几拍送入下一个任务,才既不发生功能段使用冲突,又能使流水线有较高的吞吐率和效率,是流水线调度要解决的问题。,3.5 非线性流水线的调度,非线性单功能 流水线的任务优化调度和控制方法 二维的预约表 延迟禁止表F(ForbiddenList),如 F=1,5,6,8 冲突向量C (CollisonVector)。如C=(10110001) 状态转移图 计算出每种
2、调度方案的平均间隔拍数,从中找出其最小者,3.5 非线性流水线的调度,预约表 横向(向右):时间(一般用时钟周期表示) 纵向(向下):流水线的段,例:一个5功能段非线性流水线预约表,如果在第n个时钟周期使用第k段,则在第k行和第n列的交叉处的格子里有一个。,3.5 非线性流水线的调度,根据预约表写出禁止表F 禁止表F:一个由禁用启动距离构成的集合。 具体方法 对于预约表的每一行的任何一对,用它们所在的列号相减(大的减小的),列出各种可能的差值,然后删除相同的,剩下的就是禁止表的元素。 在上例中 第一行的差值只有一个:8; 第二行的差值有3个:1,5,6; 第3行只有一个,没有差值; 第4和第5
3、行的差值都只有一个:1; 其禁止表是:F= 1,5,6,8 ,3.5 非线性流水线的调度,根据禁止表F写出初始冲突向量C0 (进行从一个集合到一个二进制位串的变换 ) 冲突向量C:一个N位的二进制位串。 设C0=(cNcN-1cic2c1),则:,ci=0 :允许间隔i个时钟周期后送入后续任务 ci=1 :不允许间隔i个时钟周期后送入后续任务 对于上面的例子 F= 1,5,6,8 C0=(10110001),3.5 非线性流水线的调度,根据初始冲突向量C0画出状态转换图 当第一个任务流入流水线后,初始冲突向量C0决定了下一个任务需间隔多少个时钟周期才可以流入。 在第二个任务流入后,新的冲突向量
4、是怎样的呢? 假设第二个任务是在与第一个任务间隔j个时钟周期流入,这时,由于第一个任务已经在流水线中前进了j个时钟周期,其相应的禁止表中各元素的值都应该减去j。 对冲突向量来说,就是逻辑右移j位(左边补0)。 在冲突向量上,就是对它们的冲突向量进行“或”运算。 SHR(j)(C0)C0 其中:SHR(j)表示逻辑右移j位,3.5 非线性流水线的调度,推广到更一般的情况 假设: Ck:当前的冲突向量 j: 允许的时间间隔 则新的冲突向量为: SHR(j)(Ck)C0 对于所有允许的时间间隔都按上述步骤求出其新的冲突向量,并且把新的冲突向量作为当前冲突向量,反复使用上述步骤,直到不再产生新的冲突向
5、量为止。,3.5 非线性流水线的调度,从初始冲突向量C0出发,反复应用上述步骤,可以求得所有的冲突向量以及产生这些向量所对应的时间间隔。由此可以画出用冲突向量表示的流水线状态转移图。 有向弧:表示状态转移的方向 弧上的数字:表示引入后续任务(从而产生新的冲突向量)所用的时间间隔(时钟周期数),3.5 非线性流水线的调度,对于上面的例子 (1) C0=(10110001) 引入后续任务可用的时间间隔为:2、3、4、7个时钟周期 如果采用2,则新的冲突向量为: (00101100)(10110001)= (10111101) 如果采用3,则新的冲突向量为: (00010110)(10110001)
6、= (10110111) 如果采用4,则新的冲突向量为: (00001011)(10110001)= (10111011) 如果采用7,则新的冲突向量为: (00000001)(10110001)= (10110001),3.5 非线性流水线的调度,(2)对于新向量(10111101),其可用的时间间隔为2个和7个时钟周期。用类似上面的方法,可以求出其后续的冲突向量分别为10111101)和(10110001)。 (3)对于其他新向量,也照此处理。 (4)在此基础上,画出状态转移示意图。,3.5 非线性流水线的调度,根据状态转换图写出最优调度方案 根据流水线状态图,由初始状态出发,任何一个闭合
7、回路即为一种调度方案。 列出所有可能的调度方案,计算出每种方案的平均时间间隔,从中找出其最小者即为最优调度方案。 上例中,各种调度方案及其平均间隔时间。,3.5 非线性流水线的调度,最佳方案:(3,4) 平均间隔时间:3.5个时钟周期(吞吐率最高) 尽管(4,3)调度方案平均间隔拍数也是3.5拍,但若实际流入任务数不是循环所需任务数的整数倍,则其实际吞吐率相对会低些,所以不作为最佳调度方案。 方案(3,4)是一种不等时间间隔的调度方案,与等间隔的调度方案相比,在控制上要复杂得多。为了简化控制,也可以采用等间隔时间的调度方案,但吞吐率和效率往往会下降不少。 在上述例子中,等时间间隔的方案只有一个:(7),其吞吐率下降了一半。,3.5 非线性流水线的调度,例题:在一个4段的流水线处理机上需经7拍才能完成一个任务,其预约表如表所示。分别写出延迟禁止表F、冲突向量C;画出流水线状态转移图;求出最小平均延迟及流水线的最大吞吐率及其调度时的最佳方案。按此调度方案,输入6个任务,求实际的吞吐率。,
链接地址:https://www.31doc.com/p-2577426.html