Call for Paper - April 2021 Edition
IJCA solicits original research papers for the April 2021 Edition. Last date of manuscript submission is March 22, 2021. Read More

MAHEFT-based Adaptive Grid Workflow Scheduling Approach

Print
PDF
International Journal of Computer Applications
© 2011 by IJCA Journal
Volume 35 - Number 7
Year of Publication: 2011
Authors:
Ahmed A. Ghanem
Ahmed I. Saleh
Hesham A. Ali
10.5120/4414-6133

Ahmed A Ghanem, Ahmed I Saleh and Hesham A Ali. Article: MAHEFT-based Adaptive Grid Workflow Scheduling Approach. International Journal of Computer Applications 35(7):22-31, December 2011. Full text available. BibTeX

@article{key:article,
	author = {Ahmed A. Ghanem and Ahmed I. Saleh and Hesham A. Ali},
	title = {Article: MAHEFT-based Adaptive Grid Workflow Scheduling Approach},
	journal = {International Journal of Computer Applications},
	year = {2011},
	volume = {35},
	number = {7},
	pages = {22-31},
	month = {December},
	note = {Full text available}
}

Abstract

The Grid Workflow scheduling is considered an important issue in Workflow management. Workflow scheduling is a process of assigning workflow tasks to suitable computational resources. Workflow scheduling significantly affects the performance and the execution time of the workflow. A Workflow scheduling approach falls in one of three categories: static, dynamic or adaptive. Grid environment is a highly changing environment in which static approaches performance is questioned. Effective workflow scheduling approaches are essential to make use of the Grid heterogeneous resource capabilities. The main objective of this paper is to introduce an adaptive heuristic list scheduling approach which utilizes the MAHEFT algorithm. MAHEFT algorithm considers the new changes in the Grid environment in order to minimize the total execution time (makespan) and to increase the speedup. The improvement rate in makespan of MAHEFT algorithm ranges between 2% to 21%. With respect to Speedup, MAHEFT is faster than both static HEFT and adaptive AHEFT algorithms with speedup values between 2.08 and 4.16.

References

  • I. Taylor, E. Deelman, D. Gannon, and M. Shields. Workflows for e-Science: Scientific Workflows for Grids. Springer, 2006.
  • I. Foster and C. Kesselman. Computational Grids in The Grid: Blueprint for a New Computing Infrastructure. Springer, ch. 2, 1999.
  • J. Yu and R. Buyya. A Taxonomy of Workflow Management Systems for Grid Computing. Journal of Grid Computing, Springer, Sept. 2005.
  • M. Wieczorek, R. Prodan, A. Hoheisel, M. Wieczorek , R. Prodan, and A. Hoheisel. Taxonomies of the Multi-criteria Grid Workflow Scheduling Problem. Grid Middleware and Services Book. p 237-264. Springer US, 2008.
  • J. Cao, S. Jarvis, S. Saini, and G. Nudd. GridFlow: Workflow Management for Grid Computing. In 3rd International Symposium on Cluster Computing and the Grid (CCGrid), Tokyo, Japan, IEEE Computer Society Press, Los Alamitos, May 12-15, 2003.
  • I. Brandic, S. Pllana, and S. Benkner. Amadeus: A Holistic Service-oriented Environment for Grid Workflows. International Workshop on Workflow Systems in Grid Environments (WSGE06). China, October 2006.
  • J. Frey and et al., Condor-g: A computation management agent for multi-institutional grids. Cluster Computing Journal, 237–246, July 2002.
  • T. Oinn and et al., Taverna: A tool for the composition and enactment of bioinformatics workflows. Bioinfomatics, 3045–3054, 2004.
  • E. Deelman, G. Singh, M.-H. Su, J. Blythe, Y. Gil, C. Kesselman, et al. Pegasus: a Framework for Mapping Complex Scientific Workflows onto Distributed Systems. Scientific Programming Journal, Nov. 2005.
  • Z. Yu and W. Shi. An Adaptive Rescheduling Strategy for Grid Workflow Applications. In Proceedings of the 21st IPDPS, 2007.
  • H. Topcuouglu, S. Hariri, and M.-Y. Wu. Performance effective and low-complexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distribution Systems, 260–274, 2002.
  • J. D. Ullman, NP-complete Scheduling Problems, Journal of Computer and System Sciences, 384-393, 1975.
  • M. Maheswaran, S. Ali, H. Siegel, D. Hensgen, and R. Freund. Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computng Systems. In 8th Heterogeneous Computing Workshop (HCW’99), Apr. 1999.
  • Iverson, M., F. Ozguner and G. Follen. Parallelizing existing applications in a distributed heterogeneous environments. Proc. Heterogeneous Computing Workshop, 93-100, 1995.
  • E. Deelman, J. Blythe, Y. Gil, and C. Kesselman. Workflow Management in GriPhyN. Grid Resource Management, State of the Art and Future Trends, 99–116, 2004.
  • R. Sakellariou and H. Zhao. A low-cost rescheduling policy for efficient mapping of workflows on grid systems. Scientific Programming, 253–262, 2004.
  • K. Lee, N. W. Paton, R. Sakellariou, A. Fernandes. Utility Driven Adaptive Workflow Execution. In the Proceedings of the 2009 9th IEEE/ACM International Symposium on Cluster Computing and the Grid, 220-227, 2009.
  • J. Blythe, S. Jain, E. Deelman, Y. Gil, K. Vahi, A. Mandal and K. Kennedy. Task Scheduling Strategies for Workflow-based Applications in Grids. IEEE International Symposium on Cluster Computing and Grid (CCGrid), 2005.
  • STG, http://www.kasahara.elec.waseda.ac.jp/schedule/index.html, visited June 2011.
  • V. Almeida, I. Vasconcelos, J. Á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, 1992.
  • T. Yang and A. Gerasoulis, "DSC : Scheduling Parallel Tasks on an Unbounded Number of Processors," IEEE Trans. Parallel and Distributed Systems, Vol.5, No.9, pp. 951-967, 1994.
  • T. Adam, K. Chandy and J. Dickson, "A Comparison of List Schedules for Parallel Processing Systems", Communications of the ACM, Vol.17, No.12, pp. 685-690, 1974.
  • U. H¨onig and W. Schiffmann. A comprehensive test bench for the evaluation of scheduling heuristics. In roc. of PDCS 2004.