Publication Details
GPU-Accelerated Synthesis of Probabilistic Programs
Češka Milan, doc. RNDr., Ph.D. (DITS)
Marcin Vladimír, Ing.
Vojnar Tomáš, prof. Ing., Ph.D. (DITS)
Markov models, probabilistic programs, graphical processing units
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.
@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"
}