A Pipeline Virtual Service Pre-Scheduling Pattern and its Application in Astronomy Data Processing

Abstract

Based on Open Grid Services Architecture (OGSA), the concept and the formal model of Pipeline Virtual Service (PVS) are proposed and presented in this paper. PVS is used to model a special type of grid workflow composed of a group of services that can be executed as a pipeline. A PVS Pre-Scheduling Pattern is described in detail, which can overlap the execution time of a PVS with the time of generating and optimizing the scheduling solution pool. The Pattern includes two independent components, the solution generating component (GenFunc) and the solution execution component (ExeFunc). GenFunc can take advantage of the powerful computing potential of grid environment to find the optimal or a near optimal scheduling solution, while ExeFunc can select a suitable scheduling solution and put a PVS into running as soon as possible. Two corresponding algorithms, SODGen and SODExe, are also developed. The analytic and simulation results show that the PVS Pre-Scheduling Pattern can not only balance the scheduling cost and scheduling precision, save the scheduling time greatly, but also reduce the execution time through selecting the optimized solution. A prototype is designed and implemented for a large scale astronomy data processing center. The early engineering evaluation experiments show that the PVS Pre-Scheduling Pattern is feasible, efficient, and flexible in real astronomy data processing.

Keywords

Grid computing workflow pipeline pre-scheduling MetaService

Get full access to this article

View all access options for this article.

References

Mandal, A. , K. Kennedy , C. Koelbel , G. Marin , J. Mellor-Crummey , B. Liu , and L. Johnsson. 2005. Scheduling strategies for mapping application workflows onto the grid. In Proceedings of High Performance Distributed Computing, 2005. 14th IEEE International Symposium, 24—27 July, pp. 125—34.

Deelman, E. , J. Blythe , Y. Gil , C. Kesselman , G. Mehta , K. Vahi , K. Blackburn , A. Lazzarini , A. Arbree , R. Cavanaugh , and S. Koranda. 2003. Mapping abstract complex workflows onto grid environments. Journal of Grid Computing 1(1):25—39.

Sakellariou, R. , and H. Zhao , 2004. A low-cost rescheduling policy for efficient mapping of workflows on grid systems. Scientific Programming 12(4):253—62.

Blythe, J. , S. Jain , E. Deelman , Y. Gil , K. Vahi , A. Mandal , and K. Kennedy. 2005. Task scheduling strategies for workflow-based applications in grids. In Proceedings of Cluster Computing and the Grid, 2005. IEEE International Symposium, Vol. 2, pp. 759— 67.

Foster, I. , C. Kesselman , J. Nick , and S. Tuecke. 2002. The physiology of the grid: an open grid services architecture for distributed systems integration. <http://www.Globus.org/research/papers/ogsa.pdf>.

Dong, F. , and S.G. Akl. 2006, Scheduling algorithms for grid computing: state of the art and open problems. Technical Report, Queen's University School of Computing, Kingston, Ontario .

Du, Z. , C. M. Lau Francis , C. Wang , W. Lam , C. He , X. Wang , Y. Chen , and S. Li . 2004. Design of an OGSA-based MetaService architecture. Grid and Cooperative Computing-GCC2004 , LNCS 3251, pp. 167—74.

Xu, Z. , and W. Li . 2002. Research on VEGA grid architecture. Journal of Computer Research and Development, 39(8): 923—929.

Frey, J. 2002. Condor DAGMan: Handling Inter-Job Dependencies . :<http//www.bo.infn.it/calcolo/condor/dagman/>

10.

Cao, J. , S.A. Jarvis , S. Saini , and G.R. Nudd. 2003. GridFlow: workflow management for grid computing. In Proceedings of Cluster Computing and the Grid. 3rd IEEE/ACM International Symposium, 12—15 May, pp.198—205.

11.

Wieczorek, M. , R. Prodan , and T. Fahringer. 2005. Scheduling of scientific workflows in the ASKALON grid environment, ACM SIGMOD Record , 34(3):56—62.

12.

Deelman, E. , et al. 2004. Pegasus: Mapping scientific workflow onto the grid. In Proceedings of the Across Grids Conference 2004, Nicosia, Cyprus.

13.

Cgsp. 2005. <www.chinagrid.edu.cn/cgsp/ >

14.

Chen, Y. , and W.-T. Tsai. 2006. Introduction to programming languages: Programming in C, C++, Scheme, Prolog, C#, and SOA, 2nd edition, Iowa: Kendall/Hunt Publishing Company.

15.

Yu, J. , and R. Buyya. 2005. A taxonomy of workflow management systems for grid computing. Technical Report, GRIDS-TR-2005-1. Melbourne, Australia: Grid Computing and Distributed Systems Laboratory, University of Melbourne.

16.

Garey, M.R. , and D.S. Johnson , 1979.Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman and Company.

17.

Braun, T.D. , H.J. Siegel , N. Beck , L.L. Bölöni , M. Maheswaran , A.I. Reuther , J.P. Robertson , M.D. Theys , B. Yao , D. Hensgen , and R.F. Freund. 2001. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. Journal of Parallel and Distributed Computing 61:810—37.

18.

Chen, Y. , H. Huang , and W.-T. Tsai. 2005. Scheduling simulation in a distributed wireless embedded system, Simulation Journal 81(6):425—36.

19.

Thain, D. , T. Tannenbaum , and M. Livny. 2003. Condor and the Grid. In Grid Computing: Making the Global Infrastructure a Reality. New Jersey, USA: John Wiley & Sons, pp. 299—336.

20.

Shepard, T. , and J.A. Martin Gagné. 1991. A pre-run-time scheduling algorithm for hard real-time systems. Software Engineering, IEEE Transactions 17(7):669—77.

21.

Liu, J. , S. Zhang , and J. Hu. 2002. A workflow model supporting pre-dispatching of tasks. Systems, Man and Cybernetics, IEEE International Conference, October 6—9, Vol.e 7, pp. 6.