General scheduling framework in computational Grid based on Petri net

Abstract

A general scheduling framework (GSF) for independent tasks in computational Grid is proposed in this paper, which modeled by Petri net and located on the layer of Grid scheduler. Furthermore, a new mapping algorithm aimed at time and cost is designed on the basis of this framework. The algorithm uses weighted average fuzzy applicability to express the matching degree between available machines and independent tasks. Some existent heuristic algorithms are tested in GSF, and the results of simulation and comparison not only show good flexibility and adaptability of GSF, but also prove that, given a certain aim, the new algorithm can consider the factors of time and cost as a whole and its performance is higher than those mentioned algorithms.

Keywords

general scheduling framework / Meta-tasks / computational Grid / Petri net / algorithm

References

[1] RamanR, LivnyM, SolomonM. Matchmaking: distributed resource management for high throughput computing[A]. Proceedings of the Seventh IEEE International Symposium on High Performance Distributed Computing [C], 1998, DC, IEEE Computer Society Press: 140-146

[2] WU Min-you, SHU Wei. Segmented Min-Min: a static mapping algorithm for meta-tasks on heterogeneous computing systems[A]. Proceedings of 9th Heterogeneous Computing Workshop (HCW 2000)[C]. 2000. 375–385.

[3] HuZhi-gang, ZhongJue. Research on theory and method in parallel designing environment based on coupling[J]. Journal of CSUT, 2002, 9(2): 123-127

[4] BraunT D, SiegelH J, et al.. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing system [J]. Journal of Parallel and Distributed Computing, 2001, 6: 810-837

[5] Armstrong R, Hensgen D, Kidd T. The relative performance of various mapping algorithms is independent of sizable variances in run-time predictions[A]. Proceedings of 7th IEEE Heterogeneous Computing Workshop (HCW ’98)[C]. 1998. 79–87.

[6] Tracy D. Braun A. Comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems[A]. Proceedings of the Eighth Heterogeneous Computing Workshop[C]. 1999. 19–29.

[7] MurataT.. Petri nets: Properties, analysis and applications. Proceedings of the IEEE, 1989, 77(4): 541-580

[8] HU Zhi-gang, MA Hao, WANG Guo-jun. A reliable routing algorithm in mobile ad hoc networks using fuzzy petri net[A]. Proceeding of IEEE Communications Society Globecom 2004 Workshops[C]. 2004. 80–84.

[9] ChenS M, KeJ S, ChangJ F. Knowledge representation using fuzzy Petri nets[J]. IEEE Transactions on Knowledge and Data Engineering, 1990, 2(3): 311-319

[10] JinHai, ChenGang, ZhaoMei-ping. Research on a job scheduling model for fault tolerant computational grid[J]. Journal of Compu Ter Research and Development, 2004, 41(8): 1382-1388(in Chinese)

[11] ZuberekW M. Timed petri nets: definitions, properties and applications[J]. Microelectronics and Reliability, 1991, 32(4): 627-644

[12] Zhuo L U, Alexander H L. A colored petri net model of distributed tactical decision making[A]. Proceedings of 1991 IEEE/SMC International Conference on Systems[C]. 1991. 2035–2040.

[13] Beaven M, Marinescu D, Stansifer R. Critical path analysis of concurrent ada programs using colored petri nets: rewrite rules[A]. Proceedings of ISCAS 1991, Intl. Symp. Circuits and Systems[C]. 1991. 144–152.

[14] Miner A S. Computing response time distributions using stochastic petri nets and matrix diagrams[A]. Proceedings of 10th International Workshop on Petri Nets and Performance Models (PNPM 2003) [C]. 2003. 10–19.

[15] HAN Yao-jun, JIANG Chang-jun, et al. Resource scheduling algorithms for grid computing and its modeling and analysis using petri net[A]. Proceedings of GCC (2)[C]. 2003. 73–80.

[16] YanJia-jie. Fuzzy applicability and weighted average applicability of F sets[J]. Journal of Zhengzhou Institute of Technology, 1994, 15(2): 89-91(in Chinese)