基于多核机群的Petri网并行算法的研究与实现

目前，并行算法被广泛应用于大量数值问题的求解。但是，对存在并发功能问题的并行算法研究成果缺乏。为此，我们根据Petri网系统具有并发功能的特点，对Petri网并行算法进行研究，具有非常重要的意义。首先对Petri网系统的结构、行为、功能进行静态分析，同时对多核PC和多核机群的多线程、多进程并行设计方法进行研究，提出新的并行模型和编程模式。然后，根据库所不变量技术对Petri网系统进行并行化研究，提出P/T网并行化功能划分的策略、条件、原则和完备性性质；再对P/T网系统的进程内和进程间的并行性进行研究，提出P/T网系统并行化模型。在此基础上，结合多核机群的并行新方法，提出多核PC和多核机群的Petri并行算法；最后，以自动物料处理车间的Petri柔性制造系统为例，对多核PC和多核机群的并行算法编程实现，模拟自动物料处理Petri网系统的实际运行过程，验证并行算法的可行性和有有效性。

项目针对功能并行算法研究成果缺乏的问题，结合Petri网、并行、代数等理论，系统地探讨了以下几方面内容：(1)各种Petri网转换成P/T网的方法、数学表示及形式化过程的研究。系统地分析了原型网、P/T网、颜色网、谓词/变迁等各种Petri网模型的原理及其内在关系，提出并论述了P/T网是各种Petri网并行化最理想的模型。将各种Petri网转换成P/T网，分别给出了结构模型转换方法和代数模型转换方法及其形式化过程；（2）多核PC和机群的新型并行模型研究。结合多线程与软事务内存(STM)共享数据的优势，提出了多核PC的OpenMP+STM并行模型和基于多核机群的MPI+OpenMP+STM三级并行编程模型，并应用到Petri网等多个领域；（3）用库所不变量技术对大规模P/T网进行并行化的数学表示、功能划分策、划分条件及完备性研究。从库所和变迁不同角度，提出基于库所不变量和变迁图两种划分策略，利用库所不变量与齐次线性方程组理论，建立并论证了P-不变量的求解方法；依据库所不变量解集，提出了P/T网并行功能划分公式、判定定理，对存在多种划分情形，进行完备性研究与证明，建立了P/T网的并行划分理论；根据P/T网划分理论，设计出P/T网并行功能划分算法并编程验证；（4）对进程内部和进程间变迁行为的并行机理分析，提出P/T网并行模型的研究。从多核PC和机群不同的体系结构，分析功能划分后变迁的并发、冲突、共享等行为的并行性，建立了多核PC和多核机群的两种P/T网并行模型；（5）将多核PC和多核机群的新型并行模型应用于P/T网的并行算法设计。将OpenMP+STM并行模型、MPI+OpenMP+STM并行编程模型与P/T网并行模型相结合，分别设计出基于多核PC的Petri网并行算法和基于多核机群的Petri网并行算法；（6）两个新算法的实例仿真。以某食用油企业食用调和油自动生产系统为例，研制出基于多核PC和多核机群三级并行模型的Petri网自动物料处理仿真两个系统，有效地模拟自动物料处理系统的实际运行过程，这两个软件已获国家软件著作权登记。项目的研究成果丰富了Petri网、并行计算的理论和应用。