Research on Petri Net System Parallel Subnet Partitioning Completeness Theory and Algorithm
LI Wenjing1,2, LI Songzhao3, LU Jianbo21. School of Logistics Management and Engineering, Nanning Normal University, Nanning 530299, Guangxi, China; 2. Guangxi Higher-Education Key Laboratory of Scientific Computing and Intelligent Information Processing, Nanning Normal University, Nanning 530299, Guangxi, China; 3. College of Computer and Information Engineering, Nanning Normal University, Nanning 530299, Guangxi, China
In order to solve the parallel algorithm of Petri net system with concurrent function, so as to achieve the parallel control and simulation operation of this system, this paper proposes the function partition completeness theory and algorithms of Petri net parallelization, thereby providing the theoretical support for the realization of Petri parallel algorithms. Firstly, according to the con-current characteristics of Petri net model, we analyze the parallelism of Petri net system; then, by giving the solving process of place invariants and the function partitioning of Petri net, we propose the function partitioning conditions and determination theorem of Petri net parallelization, and conduct its theoretical proof and practical verification. On this basis, we conduct the theoretical study and analysis on the situation that Petri net system has several kinds of parallel function partitioning, propose the completeness theorem of parallelism function partitioning in Petri net system, and verify it. Finally, we give the algorithms, application examples and simulation experiment results of parallel function partitioning of Petri net systems based on place invariant. The theoretical proof and experimental results show that the function partitioning conditions and completeness theory of Petri net parallelization based on place invariant are correct, and the parallel algorithms under such theoretical basis are also correct and effective.
 Finkel A. The minimal cover ability graph for Petri nets [J]. Lecture Notes in Computer Science, 1993, 674: 210-243.
 Kaim W E, Kordon F. An integrated framework for rapid system prototyping and automatic code distribution[C]// 5th IEEE International Workshop on Rapid System Prototyping. Piscataway: IEEE, 1994:52-61.
 Colom J M, Silva M. Convex geometry and semi flows in P/T nets. A comparative study of algorithms for computation of minimal P-semi flows [J]. Lecture Notes in Computer Science, 1991, 483:79-112.
 Zaitsev D A, Dmitry A. Toward the minimal universal Petri net [J]. IEEE Transactions on Systems, Man, and Cybernet-ics: Systems, 2013, 44(1): 47-58.
 Sine V B, Thomas S J, Jon J, et al. Interval abstraction re-finement for model checking of timed-arc Petri nets [C]// 12th International Conference on Formal Modeling and Analysis of Timed Systems. Heidelberg: Springer-Verlag, 2014: 237-251.
 Darondeau P, Koutny M, Pietkiewicz-Koutny M, et al. Syn-thesis of nets with step firing policies [C]// Proceedings of the 29th Petri Nets. Heidelberg: Springer-Verlag, 2008: 112-131.
 Jantzen M, Zetzsche G. Labeled step sequences in Petri nets [C]// Proceedings of the 29th Petri Nets. Heidelberg: Springer-Verlag, 2008: 270-287.
 Lawrence C, Michael H, David M. Renew 2.5–Towards a comprehensive integrated development environment for Petri net-based applications [C]// International Conference on Application and Theory of Petri Nets and Concurrency. Heidelberg: Springer-Verlag, 2016: 101-112.
 Souravlas S I, Roumeliotis M. Petri net modeling and simu-lation of pipelined redistributions for a deadlock-free system [J]. Cogent Engineering, 2015, 2(1): 1057427.
 Wu Z H. Petri Nets Introduction [M]. Beijing: China Machine Press, 2006(Ch).
 Girault C, Valk R. Petri Nets for Systems Engineering: A Guide to Modeling, Verification, and Applications [M]. Berlin: Springer-Verlag, 2003.
 Li W J, Yang W, Li S, et al. Research on methods of trans-formation of Petri nets systems into the Place Transition Nets [C]// 2012 Third Global Congress on Intelligent Systems. Piscataway: IEEE, 2012: 233-236.
 Hao K G, Ding J J. Hierarchical Petri nets [J]. Journal of Frontiers of Computer Science and Technology, 2008, 2(2): 123-130.
 Couvreur J M, Poitrenaud D, Weil P. Branching processes of general Petri nets [C]// 32nd International Conference on Application and Theory of Petri Nets and Concurrency. Heidelberg: Springer-Verlag, 2011: 129-148.
 Khomenko V, Mokhov A. An Algorithm for direct con-struction of complete merged processes [C]// 32nd Interna-tional Conference. Piscataway: IEEE, 2011: 89-108.
 Kocí R, Janoušek V. Towards design method based on for-malisms of Petri nets, DEVS, and UML [C]// The 6th In-ternational Conference on Software Engineering Advances. Wilmington: IARIA XPS Press, 2011: 299-304.
 Kocí R, Janoušek V. Simulation based design of control systems using DEVS and Petri nets [J]. Lecture Notes in Computer Science, 2009, 5717: 849-856.
 Wang C, Feng X J, Li X, et al. Colored Petri net model with automatic parallelization on real-time multicore architectures [J]. Journal of Systems Architecture, 2014, 60(I3): 293-304.
 Huang B, Zhou M C, Zhang G X. Synthesis of Petri net supervisors for FMS via redundant constraint elimination [J]. Automatica, 2015, 61(6): 156-163.
 Li Z W, Zhou M C. Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 2004, 34(1): 38-51.
 Li S Y, Li Z W. Solving siphons with the minimal cardinality in Petri nets and its applications to deadlock control [J]. International Journal of Production Research, 2012, 50(22): 6203-6218.
 Liu J F, Chen K, Wang Z S. Fault analysis for flight control system using weighted fuzzy Petri nets [J]. Journal of Convergence Information Technology, 2011, 6(3):146-155.
 Sun L M, Meng C, Yang S, et al. A method for fault diagnosis in missile based on fuzzy Petri net [C]// International Conference on Industrial Control and Electronics Engi-neering. Piscataway: IEEE, 2012: 1911-1913.
 Rozinat A, Mans R S, Song M, et al. Discovering colored Petri nets from event logs [J]. International Journal on Software Tools for Technology Transfer, 2008, 10(1): 57- 74.
 Du Y Y, Ning Y H, Qi L. Reachability analysis of logic Petri nets using incidence matrix [J]. Enterprise Information Systems, 2014, 8(6): 630-647.
 Chen Z X, Li Z L, Cao S, et al. Schedule refinement for homogeneous multi-core processors in the presence of manufacturing-caused heterogeneity [J]. Frontiers of In-formation Technology & Electronic Engineering, 2015, 16(12): 1018-1033.
 Hu W, Liu G M, Li Q, et al. Storage wall for exascale su-percomputing [J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(11): 1154-1175.
 Friederike W. Organizational dynamics in adaptive distributed search processes: Effects on performance and the role of complexity [J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(4): 283- 295.
 Chen T M, Sanchez-Aarnoutse J C, Bufora J. Petri net modeling of cyber-physical attacks on smart grid [J]. IEEE Transactions on Smart Grid, 2011, 2(4): 741-749.
 Pournaras E, Warnier M, Brazier F M T. Adaptive self-organization in distributed tree topologies [J]. Interna-tional Journal of Distributed Systems and Technologies, 2014, 5(1): 24-57.
 Verma A, Pattanaik K K. Failure detector of perfect P class for synchronous hierarchical distributed systems [J]. International Journal of Distributed Systems and Technologies, 2016, 7(2): 57-74.