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

Journal article


Zaitsev, D., Zhang, Z., Liu, D. and Shmeleva, T. R. 2024. Notation for mass parallel algorithms: computing Petri net state space on GPU case study. International Journal of Parallel, Emergent and Distributed Systems . pp. 1-15. https://doi.org/10.1080/17445760.2024.2431545
AuthorsZaitsev, D., Zhang, Z., Liu, D. and Shmeleva, T. R.
Abstract

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.

KeywordsMass parallel algorithm; Petri net; reachability graph
Year2024
JournalInternational Journal of Parallel, Emergent and Distributed Systems
Journal citationpp. 1-15
PublisherTaylor & Francis (Routledge)
ISSN1744-5779
Digital Object Identifier (DOI)https://doi.org/10.1080/17445760.2024.2431545
Web address (URL)https://www.tandfonline.com/doi/full/10.1080/17445760.2024.2431545
Publisher's version
License
File Access Level
Open
Output statusPublished
Publication dates
Online22 Nov 2024
Publication process dates
Deposited28 Nov 2024
Permalink -

https://repository.derby.ac.uk/item/qv26w/notation-for-mass-parallel-algorithms-computing-petri-net-state-space-on-gpu-case-study

Download files

  • 21
    total views
  • 7
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as

Related outputs

Verification of MPI programs via compilation into Petri nets
Guliak, R.N., Shmeleva, T.R. and Zaitsev, D. 2025. Verification of MPI programs via compilation into Petri nets. in: Raj, P., Dutta, P. K., Chong, P. H. J., Song, H. and Zaitsev, D. A. (ed.) Applied Graph Data Science : Graph Algorithms and Platforms, Knowledge Graphs, Neural Networks, and Applied Use Cases Morgan Kaufmann; Elsevier Inc.. pp. 245-269
Analysis of Bitcoin fork by colored Petri nets
Zhou, Z., Liu, D., Shmeleva, T.R. and Zaitsev, D. 2024. Analysis of Bitcoin fork by colored Petri nets. 2024 IEEE International Conference on Systems, Man, and Cybernetics (SMC). IEEE. https://doi.org/10.1109/SMC54092.2024.10831492
Sleptsov net based reliable embedded system design on microcontrollers and FPGAs
Xu, R., Zhang, S., Liu, D. and Zaitsev, D. 2024. Sleptsov net based reliable embedded system design on microcontrollers and FPGAs. 2024 IEEE International Conference on Embedded Software and Systems (ICESS). IEEE. https://doi.org/10.1109/ICESS64277.2024.00011