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. © 2020 John Wiley & Sons Ltd

Toward a multilevel scalable parallel Zielonka's algorithm for solving parity games / D'Amore, L.; Murano, A.; Sorrentino, L.; Arcucci, R.; Laccetti, G.. - In: CONCURRENCY AND COMPUTATION. - ISSN 1532-0626. - (2021). [10.1002/cpe.6043]

Toward a multilevel scalable parallel Zielonka's algorithm for solving parity games

D'Amore L.
;
Murano A.;Sorrentino L.;Arcucci R.;Laccetti G.
2021

Abstract

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. © 2020 John Wiley & Sons Ltd
2021
Toward a multilevel scalable parallel Zielonka's algorithm for solving parity games / D'Amore, L.; Murano, A.; Sorrentino, L.; Arcucci, R.; Laccetti, G.. - In: CONCURRENCY AND COMPUTATION. - ISSN 1532-0626. - (2021). [10.1002/cpe.6043]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11588/820182
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact