CHALUPA, Marek, Krishnendu CHATTERJEE, Andreas PAVLOGIANNIS, Nishant SINHA a Kapil VAIDYA. Data-centric Dynamic Partial Order Reduction. In Proceedings of Symposium on Principles of Programming Languages 2018. New York: ACM. s. 1-30. ISSN 2475-1421. doi:10.1145/3158119. 2018.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Data-centric Dynamic Partial Order Reduction
Autoři CHALUPA, Marek (203 Česká republika, domácí), Krishnendu CHATTERJEE (356 Indie), Andreas PAVLOGIANNIS (300 Řecko), Nishant SINHA (356 Indie) a Kapil VAIDYA (356 Indie).
Vydání New York, Proceedings of Symposium on Principles of Programming Languages 2018, od s. 1-30, 30 s. 2018.
Nakladatel ACM
Další údaje
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor 10201 Computer sciences, information science, bioinformatics
Stát vydavatele Spojené státy
Utajení není předmětem státního či obchodního tajemství
Forma vydání tištěná verze "print"
Kód RIV RIV/00216224:14330/18:00100728
Organizační jednotka Fakulta informatiky
ISSN 2475-1421
Doi http://dx.doi.org/10.1145/3158119
UT WoS 000688016900031
Klíčová slova anglicky Concurrency; Partial-order Reduction; Stateless model-checking
Štítky core_A, firank_1
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: RNDr. Pavel Šmerk, Ph.D., učo 3880. Změněno: 20. 9. 2022 11:14.
Anotace
We present a new dynamic partial-order reduction method for stateless model checking of concurrent programs. A common approach for exploring program behaviors relies on enumerating the traces of the program, without storing the visited states (aka stateless exploration). As the number of distinct traces grows exponentially, dynamic partial-order reduction (DPOR) techniques have been successfully used to partition the space of traces into equivalence classes (Mazurkiewicz partitioning), with the goal of exploring only few representative traces from each class. We introduce a new equivalence on traces under sequential consistency semantics, which we call the observation equivalence. Two traces are observationally equivalent if every read event observes the same write event in both traces. While the traditional Mazurkiewicz equivalence is control-centric, our new definition is data-centric. We show that our observation equivalence is coarser than the Mazurkiewicz equivalence, and in many cases even exponentially coarser. We devise a DPOR exploration of the trace space, called data-centric DPOR, based on the observation equivalence. For acyclic architectures, our algorithm is guaranteed to explore exactly one representative trace from each observation class, while spending polynomial time per class. Hence, our algorithm is optimal wrt the observation equivalence, and in several cases explores exponentially fewer traces than any enumerative method based on the Mazurkiewicz equivalence. For cyclic architectures, we consider an equivalence between traces which is finer than the observation equivalence; but coarser than the Mazurkiewicz equivalence, and in some cases is exponentially coarser. Our data-centric DPOR algorithm remains optimal under this trace equivalence. Finally, we perform a basic experimental comparison between the existing Mazurkiewicz-based DPOR and our data-centric DPOR on a set of academic benchmarks. Our results show a significant reduction in both running time and the number of explored equivalence classes.
Návaznosti
GBP202/12/G061, projekt VaVNázev: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Akronym: CE-ITI)
Investor: Grantová agentura ČR, Centrum excelence - Institut teoretické informatiky
MUNI/A/0854/2017, interní kód MUNázev: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VII.
Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VII., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/A/1038/2017, interní kód MUNázev: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 18
Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 18, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
VytisknoutZobrazeno: 28. 3. 2024 10:21