流水线技术.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,第,3,章 流水线技术,3.5,非线性流水线的调度,非线性流水线因为段间设置有反馈回路，一个任务在流水的全过程中，可能会多次通过同一段或越过某些段。这样，如果每拍向流水线送入一个新的任务，将会发生多个任务争用同一功能段的使用冲突现象。,究竟间隔几拍送入下一个任务，才既不发生功能段使用冲突，又能使流水线有较高的吞吐率和效率，是流水线调度要解决的问题,。,3.5,非线性流水线的调度,非线性单功能 流水线的任务优化调度和控制方法,二维的预约表,延迟禁止表,F,(ForbiddenList),，如,F,=1,5,6,8,冲突向量,C(CollisonVector),。如,C=,(10110001),状态转移图,计算出每种调度方案的平均间隔拍数，从中找出其最小者,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,写出初始冲突向量,C,0,（进行从一个集合到一个二进制位串的变换）,冲突向量,C,：一个,N,位的二进制位串。,设,C,0,=,（,c,N,c,N-1,c,i,c,2,c,1,）,，则：,c,i,=0,：允许间隔,i,个时钟周期后送入后续任务,c,i,=1,：不允许间隔,i,个时钟周期后送入后续任务,对于上面的例子,F=1,，,5,，,6,，,8,C,0,=,（,10110001,）,3.5,非线性流水线的调度,根据初始冲突向量,C,0,画出状态转换图,当第一个任务流入流水线后，初始冲突向量,C,0,决定了下一个任务需间隔多少个时钟周期才可以流入。,在第二个任务流入后，,新的冲突向量是怎样的呢？,假设第二个任务是在与第一个任务间隔,j,个时钟周期流入，这时，由于第一个任务已经在流水线中前进了,j,个时钟周期，其相应的禁止表中各元素的值都应该减去,j,。,对冲突向量来说，就是,逻辑右移,j,位,（左边补,0,）。,在冲突向量上，就是对它们的冲突向量进行,“或”运算,。,SHR,(j),（,C,0,C,0,其中,:,SHR,(j),表示逻辑右移,j,位,3.5,非线性流水线的调度,推广到更一般的情况,假设,:,C,k,：当前的冲突向量,j,:,允许的时间间隔,则新的冲突向量为：,SHR,(j),（,C,k,）,C,0,对于所有允许的时间间隔都按上述步骤求出其新的冲突向量，并且把新的冲突向量作为当前冲突向量，反复使用上述步骤，直到不再产生新的冲突向量为止。,3.5,非线性流水线的调度,从初始冲突向量,C,0,出发，反复应用上述步骤，可以求得所有的冲突向量以及产生这些向量所对应的时间间隔。由此可以画出用冲突向量表示的,流水线状态转移图,。,有向弧,：表示状态转移的方向,弧上的数字,：表示引入后续任务（从而产生新的冲突向量）所用的时间间隔（时钟周期数）,3.5,非线性流水线的调度,对于上面的例子,（,1,）,C,0,=,（,10110001,）,引入后续任务可用的时间间隔为：,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,个,时钟周期。用类似上面的方法，可以求出其后续的冲突向量分别为,10111101,）,和,（,10110001,）,。,（,3,）对于其他新向量，也照此处理。,（,4,）在此基础上，画出状态转移示意图。,3.5,非线性流水线的调度,根据状态转换图写出最优调度方案,根据流水线状态图，由初始状态出发，任何一个闭合回路即为一种调度方案。,列出所有可能的调度方案，计算出每种方案的平均时间间隔，从中找出其最小者即为最优调度方案。,上例中，各种调度方案及其平均间隔时间。,3.5,非线性流水线的调度,最佳方案：,（,3,，,4,）,平均间隔时间：,3.5,个时钟周期（吞吐率最高）,尽管（,4,，,3,）调度方案平均间隔拍数也是,3.5,拍，但若实际流入任务数不是循环所需任务数的整数倍，则其实际吞吐率相对会低些，所以不作为最佳调度方案。,方案,（,3,，,4,）,是一种,不等时间间隔的调度方案,，与,等间隔的调度方案,相比，在控制上要复杂得多。为了简化控制，也可以采用等间隔时间的调度方案，但吞吐率和效率往往会下降不少。,在上述例子中，等时间间隔的方案只有一个：,（,7,）,，其吞吐率下降了一半。,3.5,非线性流水线的调度,例题：在一个,4,段的流水线处理机上需经,7,拍才能完成一个任务，其预约表如表所示。,分别写出延迟禁止表,F,、冲突向量,C,;,画出流水线状态转移图；求出最小平均延迟及流水线的最大吞吐率及其调度时的最佳方案。按此调度方案，输入,6,个任务，求实际的吞吐率。,时间,段,1,2,3,4,5,6,7,S1,S2,S3,S4,