Fifth International Conference on Grid and Cooperative Computing (GCC'06)
An Effective Scheduling Algorithm for Homogeneous System
Hunan, China
October 21-October 23
ISBN: 0-7695-2694-2
DOI Bookmark:
http://doi.ieeecomputersociety.org/10.1109/GCC.2006.26
Efficient application scheduling is critical for achieving high performance in homogeneous computing environment. The application scheduling problem has been shown to be NP-complete. However, because of its key importance, this problem has been extensively studied and various algorithms have been proposed in the literatures. In this paper we present a novel algorithm based on list-scheduling and taskduplication on a bounded number of fully connected homogeneous machines. The algorithm is called Fast Duplication based on Earliest Finish Time (FDEFT). In order to provide a robust and unbiased comparison with the related work, a parametric graph generator was designed to generate weighted directed acyclic graphs with various characteristics. The comparison study, based on both randomly generated graphs and the graphs of Gaussian Elimination, shows that our scheduling algorithm significantly outperform on average all other excellent algorithms.
Index Terms:
task scheduling, homogeneous, heuristic algorithm, task duplication
Citation:
Yipeng Zhou, Guangzhong Sun, Yunlian Jiang, Yinlong Xu, "An Effective Scheduling Algorithm for Homogeneous System," gcc, pp.71-77, Fifth International Conference on Grid and Cooperative Computing (GCC'06), 2006
Usage of this product signifies your acceptance of the
Terms of Use.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||