Prediction-Based Independent Task Scheduling for Heterogeneous Distributed Computing Systems

Abstract:

Independent task scheduling algorithms in distributed computing systems deal with three main conflicting factors including load balance, task execution time and scheduling cost. In this paper, the problem of scheduling tasks arriving at a low rate and with long execution time in heterogeneous computing systems is studied, and a new scheduling algorithm based on prediction is proposed. This algorithm evaluates the utility of task scheduling based on statistics and prediction to solve the influence of heterogeneous computing systems. The experimental results reveal that the proposed algorithm adequately balances the conflicting factors, and thus performs better than some classical algorithms such as MCT and MET when the parameters are well selected.

• Periodical: Advanced Materials Research (Volumes 457-458)
• Pages: 1039-1046
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.457-458.1039
• Online since: January 2012
• Authors: You Wei Lu, Zhen Zhen Xu, Feng Xia
• Keywords: Distributed Computing System, Heterogeneous System, Independent Task, Prediction, Task Scheduling

References

[1] Haluk Topcuogulu, Salim Hariri, Min-You Wu: Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing, IEEE Transactions on Parallel and Distributed Systems, 3rd ed., vol. 13, (2002), pp.260-274.

DOI: 10.1109/71.993206

[2] Ewa Deelman, Gurmeet Singh, Mei-Hui Su: Pegasus: A framework for mapping complex scientific workflows onto distributed systems, Scientific Programming, (2005). 3rd ed., vol. 13, pp.219-237.

DOI: 10.1155/2005/128026

[3] Etminani K. , Naghibzadeh M.: A Min-min Max-min selective algorithm for grid task scheduling, Internet, 2007. ICI 2007. 3rd IEEE/IFIP International Conference in Central Asia (2007), pp.26-28.

DOI: 10.1109/canet.2007.4401694

[4] Jinquan Zhang, Lina Ni, Changjun Jiang: A Heuristic Scheduling Strategy for Independent Tasks on Grid. Intelligent Systems, GCIS '09 (2009), 2nd ed, pp.35-38.

DOI: 10.1109/hpcasia.2005.5

[5] Michalas A, Louta M.: Adaptive Task Scheduling in Grid Computing Environments. Semantic Media Adaptation and Personalization, SMAP '09, (2009), pp.115-120.

DOI: 10.1109/smap.2009.25

[6] Chien-Min Wang, His-Min Chen, Chun-Chen Hsu: Online Metatask Scheduling Heuristics for a Bidding-based Distributed System, High Performance Computing and Communications (2009). pp.11-19.

DOI: 10.1109/hpcc.2009.91

[7] Abdulal W., Al Jadaan O., Jabas A., Ramachandram S. : Genetic algorithm for grid scheduling using best rank power, Nature & Biologically Inspired Computing (2009), 9th ed. vol. 11, pp.181-186.

DOI: 10.1109/nabic.2009.5393679

[8] Freund R. F., Gherrity M., Ambrosius S., Campbell M., Halderman M., Hensgen D. : Scheduling resources in multi-user heterogeneous computing environments with smartNet, Proceedings of the Seventh IEEE Heterogeneous Computing Workshop (1998).

DOI: 10.1109/hcw.1998.666558

[9] Armstrong R., Hensgen D., Kidd T. : The relative performance of various mapping algorithms is independent of sizable variances in run-time predications, Proceedings of the Seventh IEEE Heterogeneous Computing Workshop (1998).

DOI: 10.1109/hcw.1998.666547

[10] Muthucumaru M., Shoukat A., Howard J. S., Debra H., Richard F. F. : Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing system, Proceedings of the Eighth IEEE Heterogeneous Computing Workshop (1999).

DOI: 10.1109/hcw.1999.765094

[11] P. Tang, P.C. Yew, C. Zhu: Impact of self-scheduling on performance of multiprocessor systems, 3rd International Conference on Supercomputing (1988), pp.593-603.

DOI: 10.1145/55364.55422

[12] Liang Liang, Xue-Gong Zhou, Ying Wang, Cheng-Lian Peng: Online Hybrid Task Scheduling in Reconfigurable Systems, Computer Supported Cooperative Work in Design (2007), pp.1072-1077.

DOI: 10.1109/cscwd.2007.4281589