CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Task Scheduling Algorithm for High Performance Heterogeneous Distributed Computing Systems

by Aida A. Nasr, Nirmeen A. El-bahnasawy, Ayman El-sayed
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 110 - Number 16
Year of Publication: 2015
Authors: Aida A. Nasr, Nirmeen A. El-bahnasawy, Ayman El-sayed
10.5120/19402-1070

Aida A. Nasr, Nirmeen A. El-bahnasawy, Ayman El-sayed . Task Scheduling Algorithm for High Performance Heterogeneous Distributed Computing Systems. International Journal of Computer Applications. 110, 16 ( January 2015), 23-29. DOI=10.5120/19402-1070

@article{ 10.5120/19402-1070,
author = { Aida A. Nasr, Nirmeen A. El-bahnasawy, Ayman El-sayed },
title = { Task Scheduling Algorithm for High Performance Heterogeneous Distributed Computing Systems },
journal = { International Journal of Computer Applications },
issue_date = { January 2015 },
volume = { 110 },
number = { 16 },
month = { January },
year = { 2015 },
issn = { 0975-8887 },
pages = { 23-29 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume110/number16/19402-1070/ },
doi = { 10.5120/19402-1070 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:46:33.625576+05:30
%A Aida A. Nasr
%A Nirmeen A. El-bahnasawy
%A Ayman El-sayed
%T Task Scheduling Algorithm for High Performance Heterogeneous Distributed Computing Systems
%J International Journal of Computer Applications
%@ 0975-8887
%V 110
%N 16
%P 23-29
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The main objective of task scheduling is to assign tasks onto available processors with the aim of producing minimum schedule length and without violating the precedence constraints. Several algorithms have been proposed for solving task-scheduling problem. The most of them doesn't take into account the average communication of parents and data ready time. In this paper, a new static scheduling algorithm is proposed called Communication Leveled DAG with Duplication (CLDD) algorithm to efficiently schedule tasks on the heterogeneous distributed computing systems. It solves most limitations of existing algorithms. The algorithm not only focuses on reducing the makespan, but also provides better performance than the other algorithms in terms of speedup, efficiency and time complexity. It consists of three phases, level sorting phase, task-prioritizing phase and processor selection phase. We evaluate the performance of our algorithm by applying it on random DAGs. According to the evolved results, it has been found that our algorithm outperform the others.

References
  1. G. Coulouris, J. Dollimore, T. Kindberg, "Distributed Systems Concepts and Design", Publishing as Addison-Wesley Longman Publication CO., Inc. Boston, MA, USA, Copyright © 2001.
  2. P. Krzyzanowski, "Lectures on Distributed Systems: A Taxonomy of distributed Systems"(pdf) Rutgers University –CS 417: Distributed Systems, 2003, URL: https://www.cs.rutgers.edu/~pxk/rutgers/notes/content/01-intro.pdf
  3. H. El-Rewini, T. G. Lewis, H. H. Ali, "Task Schedulimg in Parallel and Distributed Systems", Prentice-Hall International Editions, 1994.
  4. Yu. Kwok, "High Performance Algorithms for Compile-time Scheduling of Parallel Processors", Ph.D. Thesis, Hong Kong University, 1997.
  5. M. I. Daoud, N. Kharma, "A High Performance Algorithm for Static Task Scheduling in Heterogeneous Distributed Computing Systems", Journal of Parallel and Distributed Computing, pp. 399-409, 2007.
  6. N. A. Bahnasawy, F. Omara, and M. 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.
  7. Y. Kwok, I. Ahmad, "Static Scheduling Algorithm for Allocating Directed Task Graphs to Multiprocessors", ACM Comput. Suv. 31 (1999), 406-471.
  8. D. I. Amalarethinam, G. J. Mary, ”A New DAG Based Dynamic Task Scheduling Algorithm (DYTAS) for Multiprocessor Systems”, International Journal of Computer Applications (0975 – 8887) Volume 19– No.8, 2011.
  9. 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, 2010.
  10. H. Arabnejad, J. Barbosa, " List Scheduling Algorithm for Heterogeneous Systems by an Optimistic Cost Table", IEEE Transactions on Parallel & Distributed Systems, Vol. 25, PP. 682-694, March 2013.
  11. H.Topcuoglu, S. Hariri, and M.Y.Wu, "Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing", IEEE Trans. Parallel and Distributed Systems,March 2002, Vol. 13, No.3, pp. 260-274.
  12. M. Jing and L. Kenli, "Energy-Aware Scheduling Algorithm with Duplication on Heterogeneous Computing Systems," Publish in: Grid Computing (GRID), ACM/IEEE 13th International Conference, Page: 122 -129, Sept. 2012.
  13. S. Ranaweera and D. P. Agrawal. "A Task Duplication Based Scheduling Algorithm for Heterogeneous Systems". In 14th International Parallel and Distributed Processing Symposium, pages 445–450, Washington -Brussels- Tokyo, IEEE, May 2000.
  14. S. Darbha and D. P. Agrawal, "A Task Duplication Based Scalable Scheduling Algorithm for Distributed Memory Systems". J. Parallel Distrib. Comput, Vol. 46, PP. 15-27, 1997.
  15. Baskiyar S. and SaiRanga P. C., "Scheduling Directed A-cyclic Task Graphs on Heterogeneous Network of Workstations to Minimize schedule length", International Conference on Parallel Processing Workshops, pp. 97-103, Oct. 2003.
  16. E. Illavarasan and P. Thambidurai, "Low Complexity Performance Effective Task Scheduling Algorithm for Heterogeneous Computing Environments", Journal of Computer Sciences, PP. 94-103, 2007
  17. 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 2011, pp.72-77.
  18. URL: http://www.kasahara.elec.waseda.ac.jp/schedule/making_e.html
  19. V. Almeida, I. Vasconcelos, J. Árabe and D. Menascé. " Using Random Task Graphs to Investigate the Potential Benefits of Heterogeneity in Parallel Systems", Proc. Supercomputing '92, pp. 683-691 (1992).
  20. 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.

Powered by PhDFocusTM