Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Toward a multilevel scalable parallel Zielonka's algorithm for solving parity games
Ist Teil von
Concurrency and computation, 2021-02, Vol.33 (4), p.n/a
Ort / Verlag
Hoboken: Wiley Subscription Services, Inc
Erscheinungsjahr
2021
Link zum Volltext
Quelle
Wiley Online Library Journals Frontfile Complete
Beschreibungen/Notizen
Summary
In this work, we perform the feasibility analysis of a multi‐grained parallel version of the Zielonka Recursive (ZR) algorithm exploiting the coarse‐ and fine‐ grained concurrency. Coarse‐grained parallelism relies on a suitable splitting of the problem, that is, a graph decomposition based on its Strongly Connected Components (SCC) or a splitting of the formula generating the game, while fine‐grained parallelism is introduced inside the Attractor which is the most intensive computational kernel. This configuration is new and addressed for the first time in this article. Innovation goes from the introduction of properly defined metrics for the strong and weak scaling of the algorithm. These metrics conduct to an analysis of the values of these metrics for the fine grained algorithm, we can infer the expected performance of the multi‐grained parallel algorithm running in a distributed and hybrid computing environment. Results confirm that while a fine‐grained parallelism have a clear performance limitation, the performance gain we can expect to get by employing a multilevel parallelism is significant.