非线性流水线调度算法.pptx

Company LogoCompany Logo1 非非线性流水性流水线的冲突的冲突问题：向非：向非线性流水性流水线仍每隔一拍送入一个新任仍每隔一拍送入一个新任务，会会发生什么生什么现象？象？流水流水线的冲突：几个任的冲突：几个任务争用同一个流水段争用同一个流水段流水流水线的启的启动距离：向流水距离：向流水线连续输入两个任入两个任务之之间的的时间间隔隔Company LogoCompany Logo2预约表表Company LogoCompany Logo3Company LogoCompany Logo4无冲突无冲突调度方法度方法 非非线性流水性流水线的的禁止向量禁止向量：预约表中每一行任意两个表中每一行任意两个“”之之间的距离都的距离都计算出来，去掉算出来，去掉重复的。相重复的。相邻的两个任的两个任务进入流水入流水线引起冲突的引起冲突的间隔拍数。隔拍数。例如，如例如，如图所示的所示的预约表的禁止向量表的禁止向量为（3 3，4 4，6 6）由禁止向量得到由禁止向量得到冲突向量冲突向量：C（CnCn-1C2C1）其中：其中：n是是禁止向量中的最大禁止向量中的最大值。Cn总为1 如果如果i在禁止向量中，在禁止向量中，则Ci1，否，否则Ci0。例如：例如：对于上面的于上面的预约表，表，C C（101100101100）。）。Company LogoCompany Logo5由冲突向量构造状态图：由冲突向量构造状态图：把冲突向量送入一个把冲突向量送入一个n位逻辑右移移位器；如果移位器移出位逻辑右移移位器；如果移位器移出0 0，用移位，用移位器中的值与初始冲突向量作器中的值与初始冲突向量作“按位或按位或”运算，得到一个新的冲突向量；否运算，得到一个新的冲突向量；否则不作任何处理；如此重复则不作任何处理；如此重复n次。次。对于中间形成的每一个新的冲突向量，也要按照这一方法进行处理。对于中间形成的每一个新的冲突向量，也要按照这一方法进行处理。在初始冲突向量和所有的新形成的冲突向量之间用带箭头的线连接，在初始冲突向量和所有的新形成的冲突向量之间用带箭头的线连接，当新形成的冲突向量出现重复时可以合并到一起。当新形成的冲突向量出现重复时可以合并到一起。初始冲突向量：初始冲突向量：101010101010禁止向量禁止向量为：（：（2 2，4 4，6 6）Company LogoCompany Logo预约表表对应唯一冲突向量唯一冲突向量 -对应唯一状唯一状态图。不同的不同的预约表也可能有相同的状表也可能有相同的状态图。初始冲突向量决定初始冲突向量决定调度。度。单纯由由图的角度分析最佳的角度分析最佳调度：度：无限无限长路径中平均路径中平均边权最小的路径最小的路径状状态图中平均中平均边权最小的循最小的循环6Company LogoCompany Logo7采用状态图中任何一个闭合回路来进行调度，都不会冲突。最小的平均间隔拍数为最佳调度。最佳调度为（1，7）和（3，5）。平均启平均启动距离距离为 4 4。启启动距离最小的等距离最小的等间隔调度（5 5）。）。Company LogoCompany Logo8Company LogoCompany Logo9Company LogoCompany LogoThank you