论文部分内容阅读
Petri网是一种可用于描述系统的并发性、冲突性、资源共享性等重要行为概念的基础理论,因为兼备数学化与图形化特点,因此在众多领域都有着广泛的应用。可达图可以反映Petri网的全部动态行为,可达图中所有标识组成的状态空间可以无死角的表达系统所有的状态演化,基于可达图的分析方法因直观、可靠等特点成为了Petri网模型最重要的研究手段之一。Petri网的可达图(状态空间)的大小规模受初始标识以及库所与变迁个数的影响,当这些影响因素发生变化时都会引起Petri网状态空间的规模产生急剧变化,当这些影响因素持续增大时,Petri网的状态空间大小会呈指数规模扩大,从而引发状态空间爆炸,这使得较大规模的Petri网状态空间的计算变得极其困难。传统的计算方法在计算较大规模Petri网的状态空间时,会遇到两个难题:计算时间过长和因为计算量过大引起的内存溢出。进入新世纪以来,CUDA等并行编程技术的快速发展为高性能计算提供了新的技术途径。这些新技术的出现也为Petri网状态空间的计算提供了新的思路。本文从并行计算的角度对Petri网状态空间的计算进行了研究。采用CUDA和MPI两种并行编程技术,设计了多种Petri网状态空间并行计算算法,并通过大量的实验进行了算法效率的测试。本文的主要工作如下:1.对传统的Petri网状态空间计算的算法做了分析与改进,在改进之后算法的基础上,基于CUDA设计了Petri网状态空间并行计算算法。因为该算法利用了GPU众核的优势,且在线程分配,内存管理,线程互斥等方面做了合理的处理,因此算法具有非常高的计算效率。2.基于MPI设计了多种Petri网状态空间并行计算算法,这几种算法的设计思路与并行程度均不相同,因此在计算效率上也有较大的差异。其中采用多个进程将状态空间分为多个部分分开存储的算法具有较高的计算效率,而且MPI可以在分布式存储系统上将各个进程的数据分别存储在多台独立的计算机上,因此该算法可以有效的解决单台计算机计算时出现的内存不足问题。3.基于Petri网状态空间并行计算算法设计了Petri网可达图中可达标识类别划分的算法。4.通过Petri网的实例模型对本文设计的算法进行了大量的对比测试。从初始标识的改变,Petri网库所、变迁个数变化等多个角度对文中算法计算效率的优劣进行了验证。