Research On Parallel Computing Of Petri Net State Space Based On CUDA And MPI

Petri nets are basic theory that can be used to describe concurrency,conflict,resource sharing and other important behavioral concepts of systems.With the characteristics of mathematically and graphically,it is widely applied in many fields.Reachability graph can reflect all dynamic behaviors of Petri nets.The state space composed of all markings in graph-based can express all the evolutions of the system without dead ends.The reachable graph-based analysis method has become one of the most powerful and signifacate research methods in Petri net works for its intuitionistic and authoritative characteristics.The size of a reachable graph(state space)of a Petri net will be affected by the initial marking and the number of transitions and places.When these factors change,the scale of the state space will change dramatically.When these factors continue to increase,the size of the Petri space will expand exponentially,leading to the explosion of state space,which makes the computation of state space in Petri net becomes extremely difficult.When calculating the state space of large scale Petri net,the traditional computing methods will face two problems: too long computation time and memory overflow due to excessive computation.Since the beginning of the new century,the rapid development of the parallel programming technology such as CUDA has provided a new technical approach for highperformance computing.The emergence of CUDA also provides a new way of computing the state space of Petri nets.In this paper,two parallel programming techniques,CUDA and MPI,are adopted,and a variety of Petri net state space parallel computing algorithms are proposed.A large number of experiments are carried out to test the efficiency of the algorithm.The main work of this paper is as follows:1.The traditional algorithm for computing state space of Petri nets is improved.Based on the improved algorithm,a parallel algorithm is developed based on CUDA.Because the algorithm uses the characteristics of GPU multi cores,and has handled ingeniously in the aspects of thread allocation,memory management,memory exclusion and so on,so the algorithm has distinct computational efficiency.2.Based on MPI,a variety of parallel computing algorithms for Petri net state space are designed.These algorithms have different design ideas and parallelism,so there are also great differences in computation efficiency.Among them,multiple processes divide the state space into many parts,and separate storage algorithm has higher computational efficiency.Moreover,MPI can store data from different processes on separate computers in distributed storage system.Therefore,the algorithm can effectively solve the lack of memory when the computation is performed on a single computers.3.Based on the state space parallel computing algorithm,an algorithm to identify different types of states in reachability graphs of Petri nets is established.4.By the example of Petri nets,a lot of comparative tests are carried out on the algorithm designed in this paper.The efficiency of the algorithm is verified by the change of initial identification,Petri Net Library and the number of transitions.