Fearnley, JS
(2017)
Efficient Parallel Strategy Improvement for Parity Games.
In: 29th International Conference on Computer Aided Verification CAV 2017, 2017-7-24 - 2017-7-28, Heidelberg, Germany.
Text
note.pdf - Author Accepted Manuscript Download (340kB) |
Abstract
We study strategy improvement algorithms for solving parity games. While these algorithms are known to solve parity games using a very small number of iterations, experimental studies have found that a high step complexity causes them to perform poorly in practice. In this paper we seek to address this situation. Every iteration of the algorithm must compute a best response, and while the standard way of doing this uses the Bellman-Ford algorithm, we give experimental results that show that one-player strategy improvement significantly outperforms this technique in practice. We then study the best way to implement one-player strategy improvement, and we develop an efficient parallel algorithm for carrying out this task, by reducing the problem to computing prefix sums on a linked list. We report experimental results for these algorithms, and we find that a GPU implementation of this algorithm shows a significant speedup over single-core and multi-core CPU implementations.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Additional Information: | Part of the Lecture Notes in Computer Science book series (LNCS, volume 10427) Also part of the Theoretical Computer Science and General Issues book sub series (LNTCS, volume 10427) |
Uncontrolled Keywords: | Parity Games, Strategy Improvement Algorithm, Bellman-Ford Algorithm, Switchable Edges, Pseudo Tree |
Depositing User: | Symplectic Admin |
Date Deposited: | 08 May 2017 06:31 |
Last Modified: | 19 Jan 2023 07:05 |
DOI: | 10.1007/978-3-319-63390-9_8 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3007272 |