{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T09:44:45Z","timestamp":1753868685035,"version":"3.41.2"},"reference-count":63,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2020,10,8]],"date-time":"2020-10-08T00:00:00Z","timestamp":1602115200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Concurrency and Computation"],"published-print":{"date-parts":[[2021,2,25]]},"abstract":"<jats:title>Summary<\/jats:title><jats:p>In this work, we perform the feasibility analysis of a multi\u2010grained parallel version of the Zielonka Recursive (ZR) algorithm exploiting the coarse\u2010 and fine\u2010 grained concurrency. Coarse\u2010grained 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\u2010grained 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\u2010grained parallel algorithm running in a distributed and hybrid computing environment. Results confirm that while a fine\u2010grained parallelism have a clear performance limitation, the performance gain we can expect to get by employing a multilevel parallelism is significant.<\/jats:p>","DOI":"10.1002\/cpe.6043","type":"journal-article","created":{"date-parts":[[2020,10,9]],"date-time":"2020-10-09T06:13:07Z","timestamp":1602223987000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Toward a multilevel scalable parallel Zielonka's algorithm for solving parity games"],"prefix":"10.1002","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3379-0569","authenticated-orcid":false,"given":"Luisa","family":"D'Amore","sequence":"first","affiliation":[{"name":"University of Naples Federico II  Naples Italy"}]},{"given":"Aniello","family":"Murano","sequence":"additional","affiliation":[{"name":"University of Naples Federico II  Naples Italy"}]},{"given":"Loredana","family":"Sorrentino","sequence":"additional","affiliation":[{"name":"University of Naples Federico II  Naples Italy"}]},{"given":"Rossella","family":"Arcucci","sequence":"additional","affiliation":[{"name":"Data Science Institute Imperial College of London, South Kensington Campus  London UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0057-2573","authenticated-orcid":false,"given":"Giuliano","family":"Laccetti","sequence":"additional","affiliation":[{"name":"University of Naples Federico II  Naples Italy"}]}],"member":"311","published-online":{"date-parts":[[2020,10,8]]},"reference":[{"volume-title":"Model Checking","year":"2002","author":"Clarke EM","key":"e_1_2_7_2_1"},{"key":"e_1_2_7_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185392"},{"key":"e_1_2_7_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/333979.333987"},{"key":"e_1_2_7_5_1","unstructured":"AminofB MalvoneV MuranoA RubinS. Graded strategic logic: reasoning about uniqueness of Nash equilibria. Paper presented at: Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems Singapur;2016:698\u2010706."},{"key":"e_1_2_7_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2011.10.008"},{"key":"e_1_2_7_7_1","doi-asserted-by":"crossref","unstructured":"BerthonR MaubertB MuranoA RubinS VardiMY.Strategic logic with imperfect information. Paper presented at: Proceedings of the 32 Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS) Beijing (China);2017:1\u201012.","DOI":"10.1109\/LICS.2017.8005136"},{"key":"e_1_2_7_8_1","unstructured":"ChatterjeeK HenzingerTA JurdzinskiM. Mean\u2010payoff parity games. Paper presented at: Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science\u00a0LICS'05 Chicago IL;2005:178\u2010187; IEEE."},{"key":"e_1_2_7_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2017.09.011"},{"key":"e_1_2_7_10_1","first-page":"505","volume-title":"FSTTCS '10, Series LIPIcs 8","author":"Chatterjee K","year":"2010"},{"key":"e_1_2_7_11_1","first-page":"689","volume-title":"AAMAS '2016","author":"Malvone V","year":"2016"},{"key":"e_1_2_7_12_1","unstructured":"MogaveroF MuranoA PerelliG VardiMY. Reasoning about strategies: on the model\u2010checking problem; December 2011. arXiv:1112.6275."},{"issue":"1","key":"e_1_2_7_13_1","first-page":"1","article-title":"Reasoning about strategies: on the satisfiability problem","volume":"13","author":"Mogavero F","year":"2017","journal-title":"Log Methods Comput Sci"},{"key":"e_1_2_7_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2631917"},{"key":"e_1_2_7_15_1","doi-asserted-by":"crossref","unstructured":"MogaveroF MuranoA SauroL. On the boundaries of behavioral strategies. Paper presented at: Proceedings of the 2013 28th Annual ACM\/IEEE Symposium on Logic in Computer Science; June2013:263\u2010272.","DOI":"10.1109\/LICS.2013.32"},{"key":"e_1_2_7_16_1","first-page":"185","volume-title":"Principles and Practice of Multi\u2010Agent Systems, PRIMA, Lecture Notes in Computer Science","author":"Rubin S","year":"2015"},{"issue":"3","key":"e_1_2_7_17_1","first-page":"277","article-title":"On promptness in parity games","volume":"139","author":"Mogavero F","year":"2013","journal-title":"Fund Inform"},{"key":"e_1_2_7_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00150-1"},{"key":"e_1_2_7_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00009-7"},{"key":"e_1_2_7_20_1","doi-asserted-by":"crossref","unstructured":"JurdzinskiM. Small progress measures for solving parity games. Paper presented at: Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science; vol 1770 2000:290\u2010301; Springer Berlin Heidelberg.","DOI":"10.1007\/3-540-46541-3_24"},{"key":"e_1_2_7_21_1","doi-asserted-by":"crossref","unstructured":"V\u00f6geJ JurdzinskiM. A discrete strategy improvement algorithm for solving parity games. Paper presented at: Proceedings of the International Conference on Computer Aided Verification;2000:202\u2010215; Springer Berlin Heidelberg.","DOI":"10.1007\/10722167_18"},{"key":"e_1_2_7_22_1","doi-asserted-by":"crossref","unstructured":"ScheweS. Solving parity games in big steps. Paper presented at: Proceedings of the International Conference on Foundations of Software Technology and Theoretical Computer Science;2007:449\u2010460. Springer Berlin Heidelberg.","DOI":"10.1007\/978-3-540-77050-3_37"},{"key":"e_1_2_7_23_1","doi-asserted-by":"crossref","unstructured":"CaludeCS JainS KhoussainovB LiW StephanF. Deciding parity games in quasipolynomial time. Paper presented at: Proceedings of the 2017 Symposium on Theory of Computing;2017:252\u2010263; ACM New York NY.","DOI":"10.1145\/3055399.3055409"},{"key":"e_1_2_7_24_1","doi-asserted-by":"crossref","unstructured":"FriedmannO LangeM. Solving parity games in practice. Paper presented at: Proceedings of the International Symposium on Automated Technology for Verification and Analysis;2009:182\u2010196; Springer Berlin Heidelberg.","DOI":"10.1007\/978-3-642-04761-9_15"},{"volume-title":"The PGSolver Collection of Parity Game Solvers","year":"2009","author":"Friedmann O","key":"e_1_2_7_25_1"},{"key":"e_1_2_7_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2008.12.070"},{"key":"e_1_2_7_27_1","unstructured":"Di StasioA MuranoA PrignanoV SorrentinoL. Solving parity games in scala. Paper presented at: Proceedings of the 11th International Symposium Formal Aspects of Component Software FACS 2014 Bertinoro Italy September 10\u201012 2014 Revised Selected Papers;2014:8997 Springer New York NY."},{"key":"e_1_2_7_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2017.05.120"},{"key":"e_1_2_7_29_1","unstructured":"DijkTV. Parallel parity games: a multicore attractor for the Zielonka recursive algorithm. Paper presented at: Proceedings of the International Conference on Tools and Algorithms for the Construction and Analysis of Systems;2018:291\u2010308; Springer New York NY."},{"key":"e_1_2_7_30_1","doi-asserted-by":"crossref","unstructured":"KantG Van DePolJ. Generating and solving symbolic parity games;2014. arXiv preprint arXiv:1407.7928.","DOI":"10.4204\/EPTCS.159.2"},{"key":"e_1_2_7_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60761-7"},{"key":"e_1_2_7_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.10.009"},{"key":"e_1_2_7_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2008.11.011"},{"key":"e_1_2_7_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-02444-8_34"},{"key":"e_1_2_7_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63390-9_8"},{"key":"e_1_2_7_36_1","unstructured":"BerteroMBonettoPCarracciuoloLet al. MedIGrid: a medical imaging application for computational Grids. Paper presented at: Proceedings of the International Parallel and Distributed Processing Symposium IPDPS 2003 Nice (France);2003; IEEE."},{"key":"e_1_2_7_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-014-9824-2"},{"key":"e_1_2_7_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2013.05.290"},{"key":"e_1_2_7_39_1","unstructured":"D'AmoreL ArcucciR MarcellinoL MurliA. A parallel three\u2010dimensional variational data assimilation scheme numerical analysis and applied mathematics. Paper presented at: Proceedings of the International Conference on Numerical Analysis and Applied Mathematics Halkidiki (Greece); vol. 1389 2011:1829\u20101831; AIP Publishing."},{"key":"e_1_2_7_40_1","doi-asserted-by":"publisher","DOI":"10.3233\/ICA-2011-0382"},{"key":"e_1_2_7_41_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exp003"},{"key":"e_1_2_7_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36387-4"},{"issue":"1","key":"e_1_2_7_43_1","first-page":"67","article-title":"Towards a parallel component for imaging in PETSc programming environment: a case study in 3\u2010D echocardiography","volume":"32","author":"Carracciuolo L","year":"2006","journal-title":"Concurr Comput Pract Exp"},{"key":"e_1_2_7_44_1","doi-asserted-by":"crossref","unstructured":"PapadimitriouC. Algorithms games and the internet. Paper presented at: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing Hersonissos Greece;2001:749\u2010753:ACM.","DOI":"10.1145\/380752.380883"},{"key":"e_1_2_7_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90034-5"},{"key":"e_1_2_7_46_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-4(3:11)2008"},{"key":"e_1_2_7_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276748"},{"key":"e_1_2_7_48_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2011124"},{"key":"e_1_2_7_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(93)90036-D"},{"key":"e_1_2_7_50_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.1548"},{"issue":"1","key":"e_1_2_7_51_1","first-page":"228","article-title":"A parallel PDE\u2010based numerical algorithm for computing the optical flow in hybrid systems","volume":"22","author":"Cuomo S","year":"2016","journal-title":"J Comput Sci"},{"key":"e_1_2_7_52_1","doi-asserted-by":"crossref","unstructured":"AntonelliL CarracciuoloL CeccarelliM D'AmoreL MurliA. Total variation regularization for edge preserving 3D SPECT imaging in high performance computing environments. Paper presented at: Proceedings of the International Conference on Computational Science;2002:171\u2010180; Springer Berlin Heidelberg\/Germany.","DOI":"10.1007\/3-540-46080-2_18"},{"key":"e_1_2_7_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2234336.2234338"},{"key":"e_1_2_7_54_1","doi-asserted-by":"publisher","DOI":"10.31577\/cai_2019_4_817"},{"key":"e_1_2_7_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90046-1"},{"volume-title":"Structured Parallel Programming: Patterns for Efficient Computation","year":"2012","author":"McCool M","key":"e_1_2_7_56_1"},{"key":"e_1_2_7_57_1","doi-asserted-by":"crossref","unstructured":"AmdahlGM. Validity of the single processor approach to achieving large scale computing capabilities. Paper presented at: Proceedings of the AFIPS Spring Joint Computer Conference ATLANTIC CITY NJ;1967:56.","DOI":"10.1145\/1465482.1465560"},{"issue":"1","key":"e_1_2_7_58_1","first-page":"1","article-title":"Hyper\u2010threading technology architecture and microarchitecture","volume":"6","author":"Marr DT","year":"2002","journal-title":"Intel Technol J"},{"key":"e_1_2_7_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-016-0457-y"},{"issue":"1","key":"e_1_2_7_60_1","first-page":"8947","article-title":"Upton, hyper\u2010threading technology architecture and microarchitecture","volume":"6","author":"Marr DT","year":"2002","journal-title":"Intel Technol J"},{"key":"e_1_2_7_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55224-3_69"},{"key":"e_1_2_7_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-73659-4_25"},{"key":"e_1_2_7_63_1","doi-asserted-by":"publisher","DOI":"10.1088\/0266-5611\/18\/4\/315"},{"key":"e_1_2_7_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/225830.224449"}],"container-title":["Concurrency and Computation: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.6043","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/cpe.6043","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.6043","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,3]],"date-time":"2023-09-03T14:03:54Z","timestamp":1693749834000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.6043"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,8]]},"references-count":63,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,2,25]]}},"alternative-id":["10.1002\/cpe.6043"],"URL":"https:\/\/doi.org\/10.1002\/cpe.6043","archive":["Portico"],"relation":{},"ISSN":["1532-0626","1532-0634"],"issn-type":[{"type":"print","value":"1532-0626"},{"type":"electronic","value":"1532-0634"}],"subject":[],"published":{"date-parts":[[2020,10,8]]},"assertion":[{"value":"2020-02-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-10","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"e6043"}}