Expected Cost Based Greedy Scheduling Algorithm for Out-Tree Task Graphs

Abstract:

Effective task scheduling is crucial for achieving high performance in heterogeneous computing environments. Whiling scheduling Out-Tree task graphs, many previous heterogeneity based heuristic algorithms usually require high scheduling costs and may not deliver good quality schedules with lower costs. Aiming at the characteristics of Out-Tree task graphs and the features of heterogeneous environments and adopting the strategy based on expected costs and task duplications, this paper proposes a greedy scheduling algorithm, which, at each scheduling step, tries to guarantee not to increase the schedule length, schedules the current task onto the used processor which minimizes its execution finish time; meanwhile, takes load balances into account to economize the use of processors. The comparative experimental results show that the proposed algorithm has higher scheduling efficiency and robust performance, which could produce better schedule which has shorter schedule length and less number of used processors.

• Periodical: Applied Mechanics and Materials (Volumes 556-562)
• Pages: 3431-3437
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.556-562.3431
• Online since: May 2014
• Authors: Jian Jun Zhang*, Tian Hong Wang, Yu Zhuo Wang
• Keywords: Expected Cost, Heterogeneous Computing System, Out-Tree Task Graph, Schedule Length, Task Duplication, Task Scheduling

References

[1] Foad Lotfifar, Hadi Shahriar Shahhoseini, Complexity Task Scheduling Algorithm for Heterogeneous Computing Systems, Third Asia International Conference on Modelling & Simulation, , 2009, 5: 596-601.

DOI: 10.1109/ams.2009.77

[2] Jianjun Zhang, Yexin Song, Dengbin Huang, Task scheduling algorithm for Fork-Join task graghs in heterogeneous environment, Computer Engineering & Design, 2010, 31(3): 486-490, (In Chinese).

[3] Samantha Ranaweera, Dharma P Agrawal, A Task Duplication Based Scheduling Algorithm for Heterogeneous Systems, in Proc. 14th International Parallel and Distributed Processing Symposium, Florida, USA, 2000: 445-450.

DOI: 10.1109/ipdps.2000.846020

[4] H. Topcuoglu, S. Hariri and M.Y. Wu, Performance-effective and low-complexity task scheduling for heterogeneous computing, IEEE Trans. Parallel and Distributed Systems, 2002, 13(3): 260-274.

DOI: 10.1109/71.993206

[5] T. Hagras and J. Janecek, An approach to compile-time task scheduling in heterogeneous computing systems, in Proc. 33rd International Conf. on Parallel Processing Workshops, Canada, 2004: 182-189.

DOI: 10.1109/ipdps.2004.1303056

[6] Sang Cheol Kim, Sunggu Lee and Jaegyoon Hahm, Push-Pull: Deterministic Search-Based DAG Scheduling for Heterogeneous Cluster, IEEE Trans. Parallel and Distributed Systems, 2007, 18(11): 1489-1502.

DOI: 10.1109/tpds.2007.1106

[7] Fatma A. Omara, Mona M. Arafa, Genetic Algorithms for Task Scheduling Problem, Journal of Parallel and Distributed Computing, 2010, 70(1): 13-22.

DOI: 10.1016/j.jpdc.2009.09.009

[8] Jiadong Yang, Hua Xu, Peifa Jia, Task Scheduling for Heterogeneous Computing based on Bayesian Optimization Algorithm, 2009 International Conference on Computational Intelligence and Security, 2009: 112-117.

DOI: 10.1109/cis.2009.163