CFP last date
20 June 2024
Reseach Article

Task Scheduling Optimization in Heterogeneous Distributed Systems

by Aida A. Nasr, Nirmeen A. El-bahnasawy, Ayman El-Sayed
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 107 - Number 4
Year of Publication: 2014
Authors: Aida A. Nasr, Nirmeen A. El-bahnasawy, Ayman El-Sayed
10.5120/18737-9982

Aida A. Nasr, Nirmeen A. El-bahnasawy, Ayman El-Sayed . Task Scheduling Optimization in Heterogeneous Distributed Systems. International Journal of Computer Applications. 107, 4 ( December 2014), 5-12. DOI=10.5120/18737-9982

@article{ 10.5120/18737-9982,
author = { Aida A. Nasr, Nirmeen A. El-bahnasawy, Ayman El-Sayed },
title = { Task Scheduling Optimization in Heterogeneous Distributed Systems },
journal = { International Journal of Computer Applications },
issue_date = { December 2014 },
volume = { 107 },
number = { 4 },
month = { December },
year = { 2014 },
issn = { 0975-8887 },
pages = { 5-12 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume107/number4/18737-9982/ },
doi = { 10.5120/18737-9982 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:40:09.602103+05:30
%A Aida A. Nasr
%A Nirmeen A. El-bahnasawy
%A Ayman El-Sayed
%T Task Scheduling Optimization in Heterogeneous Distributed Systems
%J International Journal of Computer Applications
%@ 0975-8887
%V 107
%N 4
%P 5-12
%D 2014
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Efficient task scheduling is essential for obtaining high performance in heterogeneous distributed computing systems. Several algorithms are proposed for heterogeneous distributed computing systems. In this paper, a new static scheduling algorithm is proposed called Highest Communicated Path of Task (HCPT) algorithm to efficiently schedule tasks on the heterogeneous distributed computing systems. Our algorithm is based on the list-scheduling technique. The algorithm not only is focused on reducing the makespan, but also provides better performance than the other algorithms in terms of speedup and efficiency. It consists of three phases, level sorting phase, task-prioritizing phase and processor selection phase. From the theoretical analysis of the HCPT algorithm with other algorithms for a Directed A-cyclic Graph (DAG), the better performance is observed.

References
  1. E. Hesham and A. Mostafa, "Advanced Computer Architecture and Parallel Processing", (Wiley Series on Parallel and Distributed Computing), Wiley-Inter-science ©2005, ISBN 0-471-46740-5.
  2. R. Prodan and M. Wieczorek, "Bi-criteriaScheduling of Scientific Grid Workflows," IEEE Trans. on Automation Science and Engineering, vol. 7, no. 2, pp. 364 –376. April 2010
  3. HuiCheng, "A High Efficient Task Scheduling Algorithm Based on Heterogeneous Multi-Core Processor", IEEE,Second International Workshop on Database Technology and Application (DBTA), Pages 1-4, 27-28 November 2010,doi: 10. 1109/DBTA. 2010. 5659041.
  4. T. Hagras and J. Janecek, "A Near Lower-Bound Complexity Algorithm for Compile-Time Task-Scheduling in Heterogeneous Computing Systems", Third International Symposium on/Algorithms, Models and Tools for Parallel Computing on Heterogeneous Networks, and Third International Workshop onParallel and Distributed Computing, pp. 106-113, 5-7 July 2004 doi: 10. 1109/ISPDC. 2004. 3
  5. Junghwan Kim, Jungkyu Rho, Jeong-Ook Lee, and Myeong-Cheol Ko, "CPOC: Effective Static Task Scheduling for Grid Computing", in: Proceedings of the International Conference on High Performance Computing and Communications, Italy, 2005, pp. 477–486. DOI:10. 1007/11557654_56
  6. E. Ilavarasan and P. Thambidurai, "Low Complexity Performance Effective Task Scheduling Algorithm for Heterogeneous Computing Environments," Journal of Computer Sciences, Vol. 3, No. 2, PP. 94-103, 2007.
  7. H. Topcuoglu, S. Hariri, and M. Y. Wu, "Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing," IEEE Trans. Parallel and Distributed Systems (TPDS), Vol. 13, No. 3, pp. 260-274, March 2002.
  8. I. Ahmad, and Y. Kwok, "A New Approach to Scheduling Parallel Programs Using Task Duplication", Proc. International Conference of Parallel Processing",1994, Vol. 2, pp. 47-51, 15-19 august 1994, doi: 10. 1109/ICPP. 1994. 37
  9. Tarek Hagras and Jan Jane?cek, "A High Performance, Low Complexity Algorithm for Compile-Time Task Scheduling in Heterogeneous Systems",IEEE, 18th Internationalconference of Parallel and Distributed Processing Symposium, 2004,pp. 107-115, 26-30 April 2004, doi: 10. 1109/IPDPS. 2004. 1303056
  10. Nirmeen A. Bahnasawy, Fatma Omara, and Magdy Qotb, "A New Algorithm for Static Task Scheduling for Heterogeneous Distributed Computing Systems", African Journal of Mathematics and Computer Science Research Vol. 4(6),pp. 221-234,June 2011.
  11. Mohammad I. Daoud, Nawwaf Kharma, "A High Performance Algorithm For Static Task Scheduling in Heterogeneous Distributed Computing Systems," Journal of Parallel and Distributed Computing, Volume 68, Issue 4, PP. 399-409, April 2008, doi:10. 1016/j. jpdc. 2007. 05. 015.
  12. R. Eswari and S. Nickolas, "Path-based Heuristic Task Scheduling Algorithm for Heterogeneous Distributed Computing Systems", International Conference on Advances in Recent Technologies in Communication and Computing, PP. 30-34, 16-17 October 2010, DOI:10. 1109/ARTCom. 2010. 19
  13. R. Eswari and S. Nickolas, "Expected Completion Time Based Scheduling Algorithm for Heterogeneous Processors", in Proc. International Conf. Information Communication and Management(IPCSIT), vol. 16, pp. 72-77, January 2012,.
  14. V. A. F. Almeida, I. M. M Vasconcelos, J. N. C. Árabe and D. A. Menascé. "Using Random Task Graphs to Investigate the Potential Benefits of Heterogeneity in Parallel Systems", Proc. Supercomputing '92, pp. 683-691, 16-20 Nov. 1992. DOI:10. 1109/SUPERC. 1992. 236634
  15. T. Yang and A. Gerasoulis, "DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors", IEEE Transactionon Parallel and Distributed Systems, Vol. 5, No. 9, pp. 951-967, September 1994.
Index Terms

Computer Science
Information Sciences

Keywords

Static task scheduling heterogeneous distributed computing systems heuristic algorithm.