Abstract:
Out-Tree task graph is one of basic structurs in task scheduling, and the problem of wasting processors is revealed when many previous algorithms work on it, which results in poor schedule efficiency. This paper proposes a new heuristic algorithm with task duplication based on mean value, which tries to get the shortest schedule length and takes load balances into account to economize the used processors. Experimental results show that the proposed scheduling algorithm can produce better schedule which has less number of used processors and higher efficiency.
Key words:
Out-Tree task graph,
Heterogeneous Computing System(HCS),
task duplication,
scheduling length,
standard efficiency,
mean value
摘要： Out-Tree任务图是任务调度问题中的基本结构，现有的多数算法在调度该任务图时凸显出处理器浪费的问题，从而导致算法调度效果欠佳。针对该问题，结合任务复制的调度策略，提出一种基于平均值的启发式算法。该算法在不增加算法调度长度的情况下，尽可能将任务调度至已有的处理器中执行，注重平衡处理器的负载，达到减少使用处理器的目的。实验结果表明，与TDS算法相比，该算法使用的处理器个数较少，且效率较高。
关键词:
Out-Tree任务图,
异构计算系统,
任务复制,
调度长度,
标准效率,
平均值
CLC Number: