A resource-aware scheduling algorithm with reduced task duplication on heterogeneous computing systems
A resource-aware scheduling algorithm with reduced task duplication on heterogeneous computing systems
复制标题
异构计算系统上减少任务重复的资源感知调度算法
DOI：
10.1007/s11227-014-1090-4
复制
发表时间：
2014-06-01
影响因子：
3.3
通讯作者：
Li, Keqin
中科院分区：
文献类型：
--
作者：
Mei, Jing;Li, Kenli;Li, Keqin
为了满足应用程序执行的高性能要求，人们提出了多种任务调度算法。其中，基于复制的调度算法实现了更高的性能相比，其他。然而，由于其贪婪的特点，他们复制每个任务的父，只要完成时间可以减少，这导致了资源的过度消耗。然而，大量的重复是不必要的，因为一些非关键任务的轻微延迟不会影响整体的完工时间。此外，这些冗余的重复会占用资源，延迟后续任务的执行，从而增加进度的完工时间。在本文中，我们提出了一种新的基于复制的算法，旨在克服上述缺点。所提出的算法是以最少的冗余重复调度任务。提出了一种优化方案，对算法生成的调度进行冗余搜索和去除。随机生成的有向无环图和两个现实世界的应用程序进行了测试，在我们的实验。实验结果表明，与其他算法相比，该算法最多可节省15. 59%的资源消耗。制造时间也有改善。
To satisfy the high-performance requirements of application executions, many kinds of task scheduling algorithms have been proposed. Among them, duplication-based scheduling algorithms achieve higher performance compared to others. However, because of their greedy feature, they duplicate parents of each task as long as the finish time can be reduced, which leads to a superfluous consumption of resource. However, a large amount of duplications are unnecessary because slight delay of some uncritical tasks does not affect the overall makespan. Moreover, these redundant duplications would occupy the resources, delay the execution of subsequent tasks, and increase the schedule makespan consequently. In this paper, we propose a novel duplication-based algorithm designed to overcome the above drawbacks. The proposed algorithm is to schedule tasks with the least redundant duplications. An optimizing scheme is introduced to search and remove redundancy for a schedule generated by the proposed algorithm further. Randomly generated directed acyclic graphs and two real-world applications are tested in our experiments. Experimental results show that the proposed algorithm can save up to 15.59 % resource consumption compared with the other algorithms. The makespan has improvement as well.