计算机系统结构——非线性流水线调度
非线性流水线调度
回顾:线性流水线的调度
非线性流水线因为段间设置有反馈回路,一个任务在流水的全过程中,可能会多次通过同一段或越过某些段。这样,如果每拍向流水线送入一个新的任务,将会发生多个任务争用同一功能段的使用冲突现象。
流水线调度要解决的问题: 究竟间隔几拍送入下一个任务,才既不发生功能段使用冲突,又能使流水线有较高的吞吐率和效率
非线性单功能流水线的任务优化调度和控制方法
- ①二维的预约表(什么时候要用到这个功能段)
K:流水线的段数(有几个功能段)
n:每完成一个任务需要多少拍
若第n拍要用到第k个功能段,就在相应的交点✔ - ②延迟禁止表F(ForbiddenList)(隔多长时间不能送入指令)
计算方式:第一段,在第1拍和第0拍被使用,中间间隔8拍。
所以的每个功能段每两个✔相减,得到数字,取出重复的,得到的集合。上例F={1,5,6,8} - ③冲突向量C (CollisonVector)。(位数拍数-1)
用二进制表示(二进制的第一位为1), 延迟禁止表中出现数字对应位用1表示,其他用0表示。如C=(10110001); - ④状态转移图
第一条指令和第二条指令进行或运算得到新的冲突向量。
具体运算方法:
什么时候不算:算到和初始一样
画状态转移图
- ⑤计算出每种调度方案的平均间隔拍数,从中找出最小平均间隔拍数的方案。
若时间一样,采用前面那个数字小的(不确定)