An Enhancement of Leveled DAG Prioritized Task Scheduling Algorithm in Distributed Computing Systems

EL-NATTAT, Amal; El-Bahnasawy, Nirmeen A.; EL-SAYED, Ayman

doi:10.21608/mjeer.2017.63443

An Enhancement of Leveled DAG Prioritized Task Scheduling Algorithm in Distributed Computing Systems

Document Type : Original Article

Authors

Dept. of Computer Science and Eng., Faculty of Elect., Eng., Menoufia University

10.21608/mjeer.2017.63443

Abstract

Task scheduling is an important issue in distributed systems that must be done efficiently to provide high system performance. In this paper, the problem of scheduling dependent tasks on homogeneous distributed systems is addressed. Two new static scheduling algorithms have been proposed to work on homogeneous distributed systems namely; Leveled DAG Prioritized Task (LDPT) and Enhanced Leveled DAG Prioritized Task (ELDPT). Both algorithms aim to minimizing the schedule length in order to improve the system performance.

References

"> [1] Journal of Theoretical and Applied Information Technology. (2011, April 9).
[Online]. Available: http://www.jatit.org/distributed-computing/grid-vsdistributed.htm.
[2] Topcuoglu, H., Hariri, S., Wu, M.Y. "Performance effective and low
complexity task scheduling for heterogonous computing", IEEE Trans. Parallel
Distributed Syst. 13(3), 2002.
[3] Luiz F. Bittencourt, RizosSakellariou. "DAG Scheduling Using a Look ahead
Variant of the Heterogeneous Earliest Finish Time Algorithm", 18th Euromicro
International Conference onParallel, Distributed and NetworkBasedProcessing(PDP), pp. 27-34, 2010.
[4] Eswari, R. and Nickolas, S. "Path-Based Heuristic Task Scheduling Algorithm
for Heterogeneous Distributed Computing Systems".Advances in Recent
Technologies in Communication and Computing (ARTCom), International
Conference on 2010. P: 30-34
[5] Rajak and Ranjit. "A Novel Approach for Task Scheduling in Multiprocessor
System".International Journal of Computer Applications (IJCA), Vol.44, No.
11, pp. 12-16.April 2012.
[6] Ahmad, S.G.; Munir, E.U. and Nisar, W. PEGA "A Performance Effective
Genetic Algorithm for Task Scheduling in Heterogeneous Systems".High
Performance Computing and Communication& 2012 IEEE 9th International
Conference on Embedded Software and Systems (HPCC-ICESS), IEEE 14th
International Conference on 2012. Pp. 1082-1087.
[7] Tang, X., et al., "List scheduling with duplication for heterogeneous computing
systems", Journal of Parallel and Distributed Computing (JPDC), Vol. 70,
No.4,pp. 323-329.2010.
[8] J. J. Hwang. Y.C. Chow. F. D. Anger and C.-Y. Lee. "Scheduling precedence
graphs In systems with interprocessor communication times." SLAM Journal of
Computing, vol. 18, no. 2. pp. 244-257. 1989.
[9] G.C. Slh and E. A. Lee. "A compile-time scheduling heuristic for
interconnection-constrained heterogeneous processor architectures." IEEE
Transactions on Parallel and Distributed Systems, vol. 4. no. 2, pp. 75-87, 1997.
[10] H. El-Rewini and T.G .Lewis, " Scheduling parallel programs onto arbitrary
target machines." Journal of Parallel and Distributed Computing, vol. 9. no. 2,
pp. 138-153, June 1990.
[11] Panos M. Pardalos, SanguthevarRajasekaran, José D. P. Rolim, "
Randomization Methods in Algorithm Design: DIMACS Workshop", vol. 43,
December 12-14, 1997.
[12] Ebrahimirad, V.; Rajabi, A.; Goudarzi, M., "Energy-aware scheduling algorithm
for precedence-constrained parallel tasks of network-intensive applications in a
distributed homogeneous environment". Computer and Knowledge Engineering
(ICCKE) 3th International Conference on 2013. Pp. 368 – 375.
[13] Zhuravlev, S., et al., Survey of energy-cognizant scheduling techniques. 99 (7),
Jan 2012.