On State Space Of Petri Nets Through GPU Parallel Computing In MATLAB

Petri nets were originally designed as the models and analysis method to describe asynchronous concurrent computer communication protocol systems.After more than sixty years of development,Petri nets have been widely used in software design,fault diagnosis,data analysis,and other fields.The reachability graph can reflect a Petri net's dynamic behavior;the analysis methods based on reachability graphs are the most reliable and widely applicable ones.For example,reachability graphs is used to analyze the reachability of the Petri net models.Hence,the important properties in the systems modeled by Petri nets,such as boundedness,liveness,and safety,can be analyzed for certain.However,the size of a reachability graph,i.e.,the Petri net's state space,is related to its structure and initial marking.When the scale of these influencing factors increases,the scale of the state space will increase exponentially.Traditional serial programs often take a long time to calculate a large-scale state space.It is even impossible to obtain a complete reachability graph in an acceptable time or computing cost.With the continuous development of computer technology today,parallel computing has emerged to solve large-scale problems and complex systems.After decades of development,parallel computing technology has been successfully applied in various fields and for computing the state space of large-scale Petri nets.GPU has hundreds of cores;these cores form a single hardware unit in a special way that can run thousands of concurrent hardware threads.Due to such structural characteristics,GPU has great advantages in dealing with large-scale intensive data and data-parallel problems;with the general parallel architecture CUDA,the usage of GPU is are becoming more and more popular in the field of general computing.MATLAB's parallel computing toolbox can more easily call and operate GPU to accelerate programs to solve computational and data-intensive problems more efficiently.This thesis' s main work is to use GPU to compute Petri nets' state space in parallel in a MATLAB environment to solve the problem of long time-consuming calculations of traditional serial programs.(1)Analyze the previous state-space-computing serial program,from which some serial proceduces can be changed to a parallel style.Based on the advanced parallel structure provided in the MATLAB Parallel Computing Toolbox,this work first proposes a Petri net state-space parallel algorithm that does not use GPU.This algorithm achieves the parallel purpose by executing the 1) loop in parallel.Compared with the serial program,the improved one can significantly improve calculation efficiency.Furthermore,vectorization is used to replace the 1) loop in the above program,and the data is transferred to the GPU.A parallel program for solving the state space of the Petri net using GPU is obtained.The data in MATLAB is vectorized to accelerate the code operation.By verifying examples,it can be known that its operation efficiency is much higher than that of serial and parallel program that do not use GPU.(2)By imposing constraints on the enabled transitions,a Petri net subclass and its state space solution algorithm is obtained.This algorithm only changes the enabled transitions' judgment criterion and does not change the main algorithm of the state space;that is,it only needs rewriting the criterion of the firing rule of transitions and then brings it into the above-mentioned parallel algorithm.(3)In addition to the above contents,this work also proposes a solution algorithm for the basic markings in the labeled Petri net models for fault diagnosis,which provides calculation support for the analysis method based on the basic markings.This work conducts digital experiments through several Petri net examples.It verifies that using GPU for parallel computing is a powerful means to improve the efficiency of solving large-scale Petri net state space.