|
AN EFFICIENT SCHEDULING ALGORITHM FOR DIRECTED ACYCLIC GRAPHS IN A HETEROGENEOUS MULTIPROCESSOR SYSTEM
1
Author(s):
JUGMENDRA SINGH
Vol - 6, Issue- 10 ,
Page(s) : 3 - 18
(2015 )
DOI : https://doi.org/10.32804/BBSSES
Abstract
ABSTRACT
Parallel processing is one of the important processing types of applications that are used to execute multiple tasks on different number of processors at the same time. To utilize the processors in optimized manner, various scheduling algorithms are used. In multiprocessor scheduling algorithms,
- J. Blythe, S. Jain, E. Deelman, Y. Gil, K. Vahi, A. Mandal and K. Kennedy, “Task scheduling strategies for workflow-based applications in grids”, In CCGRID, pp. 759-767, 2005.
- M. Iverson, F. Ozguner and G. Follen, “Parallelizing existing applications in a distributed heterogeneous environments”, Proceedings of Heterogeneous Computing Workshop, pp. 93-100, 1995.
- S.J. Kim and Browne, “A general approach to mapping of parallel computations upon multiprocessor architectures”, Proceeding of International Conference on Parallel Processing, Vol. 3, pp. 1-8, August 1998.
- Y.K. Kwok and I. Ahmad, “Dynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors”, IEEE Transactions on Parallel & Distributed Systems, Vol. 7, No. 5, pp. 506-521, 1996.
- Y.K. Kwok and I. Ahmad, “Benchmarking and comparison of the task graph scheduling algorithms”, Journal of Parallel & Distributed Computing, Vol. 59, No. 3, pp. 381-422, 1999.
- Y.K. Kwok and I. Ahmad, “Static scheduling algorithms for allocating directed task graphs to multiprocessors”, ACM Computer Survey, Vol. 31, No. 4, pp. 406-471, 1999.
- J. Liou and M.A. Falls, “An efficient clustering heuristic for scheduling DAGs on multiprocessors”, In Proceedings of Symposium Parallel and Distributed Processing, 1996.
- G.Q. Liu, K.L. Poh, and M. Xie, “Iterative list scheduling for heterogeneous computing”, Journal of Parallel & Distributed Computing, Vol. 65, No. 5, pp. 654-665, 2005.
- A. Radulescu and A.J.C. Van Gemund, “Fast and effective task scheduling in heterogeneous systems”, Proceedings of the 9th Heterogeneous Computing Workshop, Washington, DC, USA, IEEE Computer Society, pp 229-239, 2000.
- H.EI-Rewini and T.G. Lewis, “Scheduling parallel program tasks onto arbitrary target machines,” Journal of Parallel & Distributed Computing, Vol. 9, pp.138-153, 1990.
- H. El-Rewini, T. G. Lewis and H. H. Ali, “Task scheduling in parallel and distributed systems”, Prentice Hall, Englewood Cliffs, 1994.
- R. Sakellariou and H. Zhao, “A hybrid heuristic for DAG scheduling on heterogeneous systems”, In Proceedings of 13th Heterogeneous Computing Workshop, Santa Fe, NM, April 2004.
- G.C. Sih and E.A. Lee, “A compile-time scheduling heuristic for interconnection constrained heterogeneous processor architectures”, IEEE Transactions on Parallel & Distributed Systems, Vol. 4, No. 2, pp. 175-187, 1993.
- H. Topcuglou, S. Hariri and M.Y. Wu, “Performance effective and low-complexity task scheduling for heterogeneous computing”, IEEE Transactions on Parallel & Distributed Systems, Vol. 13, No. 3, February 2002.
- M.Y. Wu and D.D. Gajski. “Hypertool: a programming aid for message-passing systems”, IEEE Transactions on Parallel & Distributed Systems, Vol. 1, No. 3, pp. 330-343, 1990.
- P.K. Yadav, M.P. Singh and H. Kumar, “Scheduling algorithm: tasks scheduling algorithm for multiple processors with dynamic re-assignment”, International Conference on Stochastic Process and Applications held from July 16-21, 2007 at IISC Bangalore.
- T. Yang and A. Gerasoulis, “DSC: Scheduling parallel tasks on an unbounded number of processors”, IEEE Transactions on Parallel & Distributed Systems, Vol. 5, No. 9, pp. 951-967, 1994.
- H. Zhao and R. Sakellariou, “An experimental investigation into the rank functions of the heterogeneous earliest finish time scheduling algorithm”, In Proceedings of 9th International Euro-Par Conference. Springer-Verlag, 2003.
|