Premium
Toward a multilevel scalable parallel Zielonka's algorithm for solving parity games
Author(s) -
D'Amore Luisa,
Murano Aniello,
Sorrentino Loredana,
Arcucci Rossella,
Laccetti Giuliano
Publication year - 2020
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.6043
Subject(s) - computer science , parallel computing , concurrency , scalability , parallelism (grammar) , algorithm , parallel algorithm , scaling , kernel (algebra) , theoretical computer science , distributed computing , mathematics , geometry , combinatorics , database
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.