Efficient Parallel Strategy Improvement for Parity Games

Fearnley, JS
(2017) Efficient Parallel Strategy Improvement for Parity Games. In: 29th International Conference on Computer Aided Verification CAV 2017, 2017-07-24 - 2017-07-28, Heidelberg, Germany.

[img] Text
note.pdf - Accepted Version

Download (340kB)


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: 16 Aug 2022 03:10
DOI: 10.1007/978-3-319-63390-9_8
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3007272