Abstract:
In-Tree task graph can be used to represent a lot of issues of divide-and-conquer algorithms such as merge, summation, etc. Aiming at In-Tree task graph, a level scheduling algorithm is proposed. The algorithm stores scheduled tasks by using queues. In the same layer of scheduling, the task whose precursor is not null is prior scheduled to one of its precursor processors. Only tasks with null precursors are considered to be allocated a new processor. Experiment shows that compared with the former algorithms, the algorithm uses fewer processors in the case of approximate same length of scheduling.
Key words:
task scheduling,
In-Tree task graph,
length of scheduling
摘要: In-Tree任务图可用来表示归并、求和等分治算法的很多问题,该文针对这种任务图提出一种分层调度算法,利用队列存放被调度的任务,在同层任务调度中,优先把前驱不为空的任务调度到其一个前驱处理器上执行,只有前驱为空的任务才考虑是否分配新的处理器。实验表明,与以前的算法相比,该算法在调度长度相当的情况下,使用了更少的处理器。
关键词:
任务调度,
In-Tree任务图,
调度长度
CLC Number:
XU Hong-zhi; LI Ren-fa. Algorithm for Scheduling In-Tree Task Graph[J]. Computer Engineering, 2008, 34(23): 29-30,4.
徐洪智;李仁发. 一种调度In-Tree任务图的算法[J]. 计算机工程, 2008, 34(23): 29-30,4.