A Heterogeneity Based Greedy Algorithm for Scheduling Out-Tree Task Graphs

Abstract:

The scheduling of Out-Tree task graphs is one of the critical factors in implementing the compilers of parallel languages and improving the performance of parallel computing. When applied to Out-Tree task graphs, many previous classical heterogeneity based algorithms always ignored the economization on processors and the minimization of the schedule length, which led to low efficiency in real applications. This paper proposes a heterogeneity based greedy algorithm for scheduling Out-Tree task graphs, which is based on list and task duplication, tries to find the best point between balancing loads and shortening the schedule length and improves the schedule performance without increasing the time complexity of the algorithm. The comparative experimental results demonstrate that the proposed algorithm could achieve shorter schedule length while using less number of processors.

• Periodical: Applied Mechanics and Materials (Volumes 475-476)
• Pages: 972-977
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.475-476.972
• Online since: December 2013
• Authors: Jian Jun Zhang, Yong Qu, Dan Mei
• Keywords: Heterogeneous Computing System, List Scheduling, Out-Tree Task Graph, Parallel Distributed Computing, 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, 5, pp.596-601, (2009).

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, 31(3), pp.486-490, 2010 (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, pp.445-450, (2000).

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, 13(3), pp.260-274, (2002).

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, pp.182-189, (2004).

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, 18(11), pp.1489-1502, (2007).

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, 70(1), pp.13-22, (2010).

DOI: 10.1016/j.jpdc.2009.09.009