计算机科学 ›› 2017, Vol. 44 ›› Issue (Z11): 586-591, 595.doi: 10.11896/j.issn.1002-137X.2017.11A.126

• 综合、交叉与应用 • 上一篇    下一篇

基于三层混合编程模型的Petri网并行算法研究

周杰,李文敬   

  1. 广西师范学院计算机与信息工程学院 南宁530023,广西师范学院科学计算与智能信息处理高校重点实验室 南宁530023;广西师范学院物流管理与工程学院 南宁530299
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受国家自然科学基金(61363037,4,61163012),广西自然科学基金(2016GXNSFAA380243),广西自然科学基金重点项目(2014GXNSFDA118037)资助

Research on Parallel Algorithm of Petri Net Based on Three-layer Mixed Programming Model

ZHOU Jie and LI Wen-jing   

  • Online:2018-12-01 Published:2018-12-01

摘要: 为解决多核机群Petri网并行化过程中,运用MPI+OPenMP混合编程实现同步会出现死锁的问题,提出了基于三层混合编程模型的Petri网并行算法。首先,根据事务内存的同步优势,在多核机群环境下构建MPI+OPenMP+STM的三层编程模型;然后,对Petri网的几何模型与代数模型的并行化进行分析,建立MPI+OPenMP+STM三层结构的Petri网并行模型,并对三层混合编程模型的Petri网并行算法进行设计与分析;最后,通过示例进行编程验证,该算法的运行效率明显优于其他编程模式,而且Petri网的规模越大,其并行计算的效果就越明显。因此,该算法是多核机群环境下模拟Petri网并行运行的一种高效且可行的算法。

关键词: Petri网,MPI+OPenMP+STM编程,Petri网并行化,Petri网并行模型,并行算法

Abstract: In order to solve the deadlocks in the synchronization realized by using the MPI+OPenMP mixed programming during the parallelization of Petri nets based on the multi core cluster,the paper proposed the Petri net parallel algorithm based on a three layer mixed programming model.Firstly,it builds a three layer programming model of MPI+OPenMP+STM in the multi-core cluster environment according to the synchronous advantage of the transactional memory.Then,it analyzes the parallelization of the geometric model and the algebraic model of the Petri net.It also builds the Petri net parallel model with a three-layer structure of MPI+OPenMP+STM as well as designing and analyzing the Petri net parallel algorithm of the three-layer programming model.Finally,the paper validates the programming through examples and proves that the operating efficiency of this algorithm is much better than those of other programming modes.In addition,the larger the size of the Petri net is,the better effect of the parallel computing it has.Therefore,the algorithm is an efficient and applicable algorithm for the simulated parallel operation of the Petri net in the multi-core cluster environment.

Key words: Petri net,MPI+OPenMP+STM programming,Petri net parallelization,Petri net parallel model,Parallel algorithm

[1] 李文敬,王汝凉,廖伟志.基于P-不变量的Petri网并行化方法的研究[J].计算机工程与设计,2009,0(16):3758-3770.
[2] SHARMA R,KANUNGO P.Performance evaluation of MPIand hybrid MPI+OpenMP programming paradigms on multi-core processors cluster[C]∥International Conference on Recent Trends in Information Systems.2011:137-140.
[3] RABENSEIFNER R,HAGER G,JOST G.Hybrid MPI/Open-MP Parallel Programming on Clusters of Multi-Core SMP Nodes[C]∥Euromicro International Conference on Parallel.2009:427-436.
[4] 赵永华,迟学斌.基于SMP集群的MPI+OpenMP混合编程模型及有效实现[J].微电子学与计算机,2005,2(10):7-11.
[5] 潘卫,陈燎原,张锦华,等.基于SMP集群的MPI+OpenMP混合编程模型研究[J].计算机应用研究,2009,6(12):4592-4594.
[6] 陈辉,孙雷鸣,李录明,等.基于MPI+OpenMP的多层次并行偏移算法研究[J].成都理工大学学报(自然科学版),2010,7(5):528-534.
[7] 吴长莉.基于MPI和OpenMP的三维FDTD并行算法的研究[D].武汉:华中科技大学,2009:10-12.
[8] 李文敬,廖伟志,王汝凉.Petri网系统的功能划分及其并行算法[J].计算机工程,2009,5(21):48-50,53.
[9] 李文敬,廖伟志,元昌安,等.高级Petri网并行化预处理方法的研究[J].广西大学学报(自然科学版),2013(5):1100-1107.
[10] 柯琦,钟诚,陈清媛,等.多核机群上通信高效的整数序列并行排序方法[J].计算机应用,2013,3(3):821-824.
[11] LIN C,SNYDER L.Princilples of Parallel Programming[M].Pearson Education,Inc.,publishing as Addison Wesley.2009:180-220.
[12] LI W J,LI S,YUAN C A,et al.Research on Soft-ware Transa-ctional Memory Parallel Programming Model Based on Multi-core Cluster[J].Journal of Chinese Computer Systems,2014,35(8):1732-1737.
[13] Gilbert Fridgen,Christian Stepanek,Thomas Wolf.Investigation of exogenous shocks in complex supply networks-a modular Petri Netapproach[J].International Journal of Production Research,2015,3(5):1387-1408.
[14] SOURAVLAS S I,ROUMELIOTIS M.Petri net modeling and simulation of pipelined redistributions for a deadlock-free system[J].Cogent Engineering,2015,2(1):1057427.
[15] WANG R Z,AGARWAL S,DAGLI C H.Executable System of Systems Architecture Using OPM in Conjunction with Colored Petri Net:A Module for Flexible Intelligent and Learning Architect-ures for System of systems[J].Incose International symposium,2014,4(s1):581-596.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[2] 夏庆勋,庄毅. 一种基于局部性原理的远程验证机制[J]. 计算机科学, 2018, 45(4): 148 -151, 162 .
[3] 厉柏伸,李领治,孙涌,朱艳琴. 基于伪梯度提升决策树的内网防御算法[J]. 计算机科学, 2018, 45(4): 157 -162 .
[4] 王欢,张云峰,张艳. 一种基于CFDs规则的修复序列快速判定方法[J]. 计算机科学, 2018, 45(3): 311 -316 .
[5] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[6] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[7] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[8] 刘琴. 计算机取证过程中基于约束的数据质量问题研究[J]. 计算机科学, 2018, 45(4): 169 -172 .
[9] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .
[10] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99, 116 .