We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A resource-aware scheduling algorithm with reduced task duplication on heterogeneous computing systems.
- Authors
Mei, Jing; Li, Kenli; Li, Keqin
- Abstract
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.
- Subjects
DIRECTED acyclic graphs; COMPUTER systems; HETEROGENEOUS computing; MATHEMATICAL mappings; MATHEMATICAL optimization
- Publication
Journal of Supercomputing, 2014, Vol 68, Issue 3, p1347
- ISSN
0920-8542
- Publication type
Article
- DOI
10.1007/s11227-014-1090-4