Effcient Parallel GPU Algorithms For The Reachability Graph Of Petri Net Based On BDD

With the continuous development of the social digital economy,more and more industrial embedded software and internet infrastructure adopt the distributed concurrent system's organizational structure.Such complex systems often cause deadlock problems due to improper order of concurrent access to shared resources,which reduces productivity and sometimes even leads to the collapse of the entire system.To avoid the deadlock phenomenon,process analysis and state prediction of the system-operation have become critical factors in designing this type of system.As a standard mathematical tool for analyzing processes,Petri nets can accurately model a class of concurrent systems,which have shared resource behaviors and are driven by events.In related theories of Petri nets,a type of digraph called reachability graph is proposed to realize the analysis of model behavior and state,which is an essential basis for predicting and avoiding deadlock.However,given a Petri net,the scale of its reachability graph will increase exponentially with the increase of the network structure's complexity and the length of the initial identification model,which may cause problem of state explosion may occur.This thesis conducts research on the reachability graph calculation of Petri nets,and mainly does the following work:1.As the basis of the reachable graph of parallel computing,it analyzes standard parallel modes such as loop decoupling,derivation/collection,and divide-and-conquer.It summarizes the reconstruction principle of serial computing parallelization.Based on CUDA(compute unified device architecture),it is proposed that a parallel computing method with GPU(graphics processing unit)as the primary computing platform.In order to maximize the computing performance,the hardware structure of the basic unit of GPU(SM,stream multiprocessor)is used as the research starting point,and the implementation of the programming model such as thread organization and memory management are summarized.2.Differentiate the serial algorithm steps for calculating the reachability graph of Petri nets and study in-depth the key links such as the transition enabling transmission and the addition of new legal signs in each iteration.The detailed contents include: a)Decouple the serial loop for this crucial link and propose a parallel algorithm for reachable graphs of linked list insertion hash.When the index organizes multithreading to perform state transition calculations to prevent the coupling between threads from causing parallel operations to degenerate into serial operations,this thesis stores the identifiers based on hash values.However,this parallel algorithm has problems such as fierce thread competition and high time and space complexity.b)In order to solve the problem of thread competition and time complexity,we propose a parallel computing method that reduces the probability of conflicts between threads and improve the search speed,which uses the Cuckoo hash with multiple location selection sets and eviction characteristics as the mainframe.It includes a self-balancing binary search tree(i.e.,a red-black tree)that stores the upper limit of eviction elements.c)Aiming at the memory overflow problem caused by the high complexity of the running space,the Boolean function based on BDD(binary decision diagram)can be optimized to express properties of a new reachable state.This thesis proposes an algorithm to add ROBDD(restrict ordered binary decision diagram)nodes under the hash bucket.The compressed form of the reachable state reduces the memory usage of the GPU.To compare the absolute speedup and the upper limit of the number of reachable states of the three parallel algorithms from multiple perspectives,this thesis calculates the reachability graphs of Petri nets of different sizes,and confirms the expected results,and analyzes the calculation results for subsequent research for reference.