@inproceedings{10.1007/978-3-319-63390-9_8,
    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.},
    Address = {Cham},
    Author = {Fearnley, John},
    BookTitle = {Computer Aided Verification},
    Editor = {Majumdar, Rupak and Kun{\v{c}}ak, Viktor},
    ISBN = {978-3-319-63390-9},
    Pages = {137--154},
    Publisher = {Springer International Publishing},
    Title = {Efficient Parallel Strategy Improvement for Parity Games},
    Year = {2017},
    date-added = {2019-04-12 08:05:31 +0200},
    date-modified = {2019-04-12 08:05:31 +0200},
    doi = {10.1007/978-3-319-63390-9_8}
}

@inproceedings{10.1007/978-3-319-63390-9_8, 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.}, Address = {Cham}, Author = {Fearnley, John}, BookTitle = {Computer Aided Verification}, Editor = {Majumdar, Rupak and Kun{\v{c}}ak, Viktor}, ISBN = {978-3-319-63390-9}, Pages = {137--154}, Publisher = {Springer International Publishing}, Title = {Efficient Parallel Strategy Improvement for Parity Games}, Year = {2017}, date-added = {2019-04-12 08:05:31 +0200}, date-modified = {2019-04-12 08:05:31 +0200}, doi = {10.1007/978-3-319-63390-9_8} }