Toward a multilevel scalable parallel Zielonka's algorithm for solving parity games. (8th October 2020)

• Record Type: Journal Article
• Authors: D'Amore, Luisa; Murano, Aniello; Sorrentino, Loredana; Arcucci, Rossella; Laccetti, Giuliano
• Other Names: Jeon Gwanggil guestEditor.; Abdellah Chehri guestEditor.; Cuomo Salvatore guestEditor.; Din Sadia guestEditor.; Jabbar Sohail guestEditor.; Kosta Sokol guestEditor.; Laccetti Giuliano guestEditor.; Lapegna Marco guestEditor.; Mele Valeria guestEditor.; Montella Raffaele guestEditor.
• Is Part Of: Concurrency and computation. Volume 33:Number 4(2021)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2020-10-08
• Subjects: hybrid architectures -- multilevel parallelism -- parity games -- performance analysis -- Zielonka algorithm; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.6043
• Languages: English
• ISSNs: 1532-0626

Abstract

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.