An Efficient Dual Objective Grid Workflow Scheduling Algorithm
|
10.5120/3983-5625 |
D.I.George Amalarethinam and F.Kurus Malai Selvi. Article: An Efficient Dual Objective Grid Workflow Scheduling Algorithm. International Journal of Computer Applications 33(1):7-12, November 2011. Full text available. BibTeX
@article{key:article,
author = {D.I.George Amalarethinam and F.Kurus Malai Selvi},
title = {Article: An Efficient Dual Objective Grid Workflow Scheduling Algorithm},
journal = {International Journal of Computer Applications},
year = {2011},
volume = {33},
number = {1},
pages = {7-12},
month = {November},
note = {Full text available}
}
Abstract
Grid computing is a mainstream technology to integrate large scale distributed sharing resources. To achieve the promising potentials of tremendous distributed resources, effective and efficient scheduling algorithms are fundamentally important. Most of the applications in grid computing fall into interdependent task model called workflow application. Task scheduling is a fundamental issue in achieving high performance in grid computing systems. It is well known that the complexity of a general scheduling problem is NP-Complete [1]. The grid workflow task scheduling problem is described by a Directed Acyclic Graph (DAG) or task graph. The graph represents the dependency among tasks, their computation time and communication time between them. In the management of workflow execution scheduling, the key issues that impact on the performance of the system is based on proper scheduling. In this paper, a new algorithm, named Efficient Dual Objective Scheduling (EDOS) is proposed to maximize the resource utilization in a grid and to minimize makespan by reserving the resources in advance and schedule the task on priority. The proposed algorithm has been implemented for arbitrary task graphs in a simulated environment. Finally, the results are compared with the well known Min-Min and HEFT scheduling algorithms and showing that the proposed algorithm is yielding better results, that is, minimizing makespan and higher utilization of resources.
Reference
- H. El-Rewini, T. Lewis, and H..Ali, Task Scheduling in Parallel and Distributed Systems, ISBN: 0130992356, PTR Prentice Hall, 1994
- Yves Robert, Frederic Vivien, “Algorithms and Theory of computation Hand Book”, Chapman and Hall CRC, pp.29.29, November, 2009
- María M. López, Elisa Heymann, Miquel A. Senar,” Analysis of Dynamic Heuristics for Workflow Scheduling on Grid Systems” The Fifth International Symposium on Parallel and Distributed Computing(ISPDC’06), pp .199-207, July 2006
- Y.-K. Kwok and I. Ahmad. Static Scheduling Algorithms for Allocating Directed Task Graphs. ACM Computing Surveys, 31(4):pp. 406-471, 1999
- R.Sakellariou and H. Zhao. A Hybrid Heuristic for DAG Scheduling on Heterogeneous Systems. In Proceedings of 13th Heterogeneous Computing Workshop (HCW 2004), Santa Fe, New Mexico, USA ,pp. 26-30, April 2004
- H. Topcuoglu, S. Hariri, and M. Wu. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems, 13(3):pp. 260–274, March 2002
- Henan Zhao and Rizos Sakellariou, “Advance Reservation Policies for Workflows”, E. Frachtenberg and U. Schwiegelshohn (Eds.): JSSPP 2006, LNCS 4376, Springer-Verlag Berlin Heidelberg, pp. 47–67, 2007
- Jia Yu and Rajkumar Buyya, “Workflow Scheduling Algorithms for Grid Computing”, Studies in Computational Intelligence, Meta-heuristics for scheduling in Distributed Computing Environments, Vol.146,pp. 173-214, 2008
- W. Smith, I. Foster, and V.Taylor.Scheduling with Advanced Reservations. In Proceedings of International Parallel and Distributed Processing Symposium (IPDPS), pp. 127-132, May 2000
- Muthucumaru Maheswaran, Shoukat Ali, Howard Jay Siegel, Debra Hensgen and Richard.F.Freund, “Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems”, Heterogeneous Computing Workshop(HCW’99), pp. 30-44, 1999
- Y.-K. Kwok and I. Ahmad, “Benchmarking and comparison of the task graph scheduling algorithms, ” Journal of Parallel and Distributed Computing, vol. 59, no. 3, pp. 381-422, 1999
- Fangpeng Dong and Selim G. Akl, “PFAS: A Resource-Performance-Fluctuation-Aware Workflow Scheduling Algorithm for Grid Computing”, IEEE, pp.1-9, 2007
- Young Choon Lee, Riky Subrata, and Albert Y. Zomaya, “On the Performance of a Dual-Objective Optimization Model for Workflow Applications on Grid Platforms”, IEEE Transactions on Parallel and Distributed Systems, Vol. 20, No. 9, pp. 1273-1284, 2009
- Sheng Di, Cho-Li Wang, “Dual- Phase Just –in –time Workflow Scheduling in P2P Grid Systems”,39th International Conference on Parallel Processing , pp. 238-247, 2010
- Joerg Decker, Joerg Schneider, “Heuristic Scheduling of Grid Workflows Supporting Co-Allocation and Advance Reservation”, Seventh IEEE International Symposium on Cluster Computing and the Grid (CCGrid07), pp. 335-342, 2007