|
列表调度算法的主要步骤如下:
(1) Current_Step:= 1; -- Current_Step代表当前控制步
(2) 为当前控制步建立就绪队列,并按优先级函数排序;
(3) 在满足硬件资源约束的条件下,将具有最高优先级的操作调度到当前控制步(Current_Step);
(4) 修改就绪操作队列;
(5) 在满足硬件资源约束的条件下,若还有操作可以被调度转(3);否则进入下一步;
(6) Current_Step:= Current_Step + 1;
(7) 若还有操作尚未被调度,转(2);
(8) 结束。
仍以diffeq为例,设总控制步数为7,对其执行列表调度算法。假定硬件资源为2个非流水线乘法器(*),1个减法器(-),1个加法和比较单元(+,<
)。假定优先级函数为路径长度。调度过程如下:
第1控制步:
就绪队列:操作3,4,5,6,1。
调度结果:操作3,4,1。
第2控制步:
就绪队列:操作5,6,2。
调度结果:操作2。
第3控制步:
就绪队列:操作7,5,6。
调度结果:操作7,5。
第4控制步:
就绪队列:操作6。
调度结果:无(缺少硬件资源)。
第5控制步:
就绪队列:操作8,6,10。
调度结果:操作8,6,10。
第6控制步:
就绪队列:空。
调度结果:无。
第7控制步:
就绪队列:操作11,9。
调度结果:操作11,9。
调度结果示于图5.18。调度完成后,即可得到操作调度的有限状态机(FSM)描述。本例的有限状态机描述示于图5.19,其中FSM的每一个状态对应于一个控制步,在状态的旁边标记着该控制步所要执行的操作。图中状态s4和s6是空状态,因为乘法操作是多周期操作,状态s4和s6下乘法操作正在执行。
|