Publication Details

GPU-Accelerated Synthesis of Probabilistic Programs

ANDRIUSHCHENKO, R.; ČEŠKA, M.; MARCIN, V.; VOJNAR, T. GPU-Accelerated Synthesis of Probabilistic Programs. In International Conference on Computer Aided Systems Theory (EUROCAST'22). Lecture Notes in Computer Science. Cham: Springer Nature Switzerland AG, 2022. p. 256-266. ISBN: 978-3-031-25312-6.
Czech title
GPU akcelerovaná syntéza pravděpodobnostních programů
Type
conference paper
Language
English
Authors
Keywords

Markov models, probabilistic programs, graphical processing units

Abstract

We consider automated synthesis methods for finite-state probabilistic programs
satisfying a given temporal specification. Our goal is to accelerate the
synthesis process using massively parallel graphical processing units (GPUs). The
involved analysis of families of candidate programs is the main computational
bottleneck of the process. We thus propose a state-level GPU-parallelisation of
the model-checking algorithms for Markov chains and Markov decision processes
that leverages the related but distinct topology of the candidate programs. For
structurally complex families, we achieve a speedup of the analysis over one
order of magnitude. This already leads to a considerable acceleration of the
overall synthesis process and paves the way for further improvements.

Published
2022
Pages
256–266
Proceedings
International Conference on Computer Aided Systems Theory (EUROCAST'22)
Series
Lecture Notes in Computer Science
Conference
Eurocast 2022 -- 18th International Conference on Computer Aided Systems Theory, Las Palmas de Gran Canaria, Canary Islands, ES
ISBN
978-3-031-25312-6
Publisher
Springer Nature Switzerland AG
Place
Cham
EID Scopus
BibTeX
@inproceedings{BUT178306,
  author="Roman {Andriushchenko} and Milan {Češka} and Vladimír {Marcin} and Tomáš {Vojnar}",
  title="GPU-Accelerated Synthesis of Probabilistic Programs",
  booktitle="International Conference on Computer Aided Systems Theory (EUROCAST'22)",
  year="2022",
  series="Lecture Notes in Computer Science",
  pages="256--266",
  publisher="Springer Nature Switzerland AG",
  address="Cham",
  isbn="978-3-031-25312-6"
}
Back to top