Treffer: Notation for mass parallel algorithms: computing Petri net state space on GPU case study

We introduce a novel notation for mass parallel algorithms, in particular, algorithms for GPU, which is based on graphical specification of the cube of threads combined with textual expressions, specifying a thread algorithm. We abstract from the peculiarities of a definite GPU preserving basic features of mass-parallel computations. As a case study for the notation, we developed, and implemented in CUDA, a reachability graph algorithm for Petri nets. Parallel hash tables have been introduced to reduce the time complexity. About a hundred time speed-up has been obtained, compared with the best known toolset Tina.