Detail publikačního výsledku

GPU-Accelerated Synthesis of Probabilistic Programs

ANDRIUSHCHENKO, R.; ČEŠKA, M.; MARCIN, V.; VOJNAR, T.

Originální název

GPU-Accelerated Synthesis of Probabilistic Programs

Anglický název

GPU-Accelerated Synthesis of Probabilistic Programs

Druh

Stať ve sborníku v databázi WoS či Scopus

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

Markov models, probabilistic programs, graphical processing units

Klíčová slova v angličtině

Markov models, probabilistic programs, graphical processing units

Autoři

ANDRIUSHCHENKO, R.; ČEŠKA, M.; MARCIN, V.; VOJNAR, T.

Rok RIV

2025

Vydáno

30.06.2022

Nakladatel

Springer Nature Switzerland AG

Místo

Cham

ISBN

978-3-031-25312-6

Kniha

International Conference on Computer Aided Systems Theory (EUROCAST'22)

Edice

Lecture Notes in Computer Science

Strany od

256

Strany do

266

Strany počet

11

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"
}