TY - GEN
T1 - Solving mean-payoff games on the GPU
AU - Meyer, Philipp J.
AU - Luttenberger, Michael
N1 - Publisher Copyright:
© Springer International Publishing AG 2016.
PY - 2016
Y1 - 2016
N2 - General purpose computation on graphics processing units (GPGPU) is a recent trend in areas which heavily depend on linear algebra, in particular solving large systems of linear equations. Many games, both qualitative (e.g. parity games) and quantitative (e.g. meanpayoff games) can be seen as systems of linear equations, too, albeit on more general algebraic structures. Building up on our GPU-based implementation of several solvers for parity games [8], we present in this paper a solver for mean-payoff games. Our implementation uses OpenCL which allows us to execute it without any changes on both the CPU and on the GPU allowing for direct comparison. We evaluate our implementation on several benchmarks (obtained via reduction from parity games and optimization of controllers for hybrid systems [10]) where we obtain a speedup of up to 10 on the GPU in cases of MPGs with 20 · 106 nodes and 60 · 106 edges.
AB - General purpose computation on graphics processing units (GPGPU) is a recent trend in areas which heavily depend on linear algebra, in particular solving large systems of linear equations. Many games, both qualitative (e.g. parity games) and quantitative (e.g. meanpayoff games) can be seen as systems of linear equations, too, albeit on more general algebraic structures. Building up on our GPU-based implementation of several solvers for parity games [8], we present in this paper a solver for mean-payoff games. Our implementation uses OpenCL which allows us to execute it without any changes on both the CPU and on the GPU allowing for direct comparison. We evaluate our implementation on several benchmarks (obtained via reduction from parity games and optimization of controllers for hybrid systems [10]) where we obtain a speedup of up to 10 on the GPU in cases of MPGs with 20 · 106 nodes and 60 · 106 edges.
UR - http://www.scopus.com/inward/record.url?scp=84992530890&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-46520-3_17
DO - 10.1007/978-3-319-46520-3_17
M3 - Conference contribution
AN - SCOPUS:84992530890
SN - 9783319465197
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 262
EP - 267
BT - Automated Technology for Verification and Analysis - 14th International Symposium, ATVA 2016, Proceedings
A2 - Artho, Cyrille
A2 - Peled, Doron
A2 - Legay, Axel
PB - Springer Verlag
T2 - 14th International Symposium on Automated Technology for Verification and Analysis, ATVA 2016
Y2 - 17 October 2016 through 20 October 2016
ER -