Data-centric Dynamic Partial Order Reduction

D 2018

Data-centric Dynamic Partial Order Reduction

CHALUPA, Marek, Krishnendu CHATTERJEE, Andreas PAVLOGIANNIS, Nishant SINHA, Kapil VAIDYA et. al.

Basic information

Original name

Data-centric Dynamic Partial Order Reduction

Authors

CHALUPA, Marek (203 Czech Republic, belonging to the institution), Krishnendu CHATTERJEE (356 India), Andreas PAVLOGIANNIS (300 Greece), Nishant SINHA (356 India) and Kapil VAIDYA (356 India)

Edition

New York, Proceedings of Symposium on Principles of Programming Languages 2018, p. 1-30, 30 pp. 2018

Publisher

ACM

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

printed version "print"

RIV identification code

RIV/00216224:14330/18:00100728

Organization unit

Faculty of Informatics

ISSN

DOI

http://dx.doi.org/10.1145/3158119

UT WoS

000688016900031

Keywords in English

Concurrency; Partial-order Reduction; Stateless model-checking

Abstract

V originále

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.

Links

GBP202/12/G061, research and development project

Name: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Acronym: CE-ITI)

Investor: Czech Science Foundation

MUNI/A/0854/2017, interní kód MU

Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VII.

Investor: Masaryk University, Category A

MUNI/A/1038/2017, interní kód MU

Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 18

Investor: Masaryk University, Category A

Citovat

CHALUPA, Marek, Krishnendu CHATTERJEE, Andreas PAVLOGIANNIS, Nishant SINHA and Kapil VAIDYA. Data-centric Dynamic Partial Order Reduction. In Proceedings of Symposium on Principles of Programming Languages 2018. New York: ACM, 2018, p. 1-30. ISSN 2475-1421. Available from: https://dx.doi.org/10.1145/3158119.

@inproceedings{1392167,
   author = {Chalupa, Marek and Chatterjee, Krishnendu and Pavlogiannis, Andreas and Sinha, Nishant and Vaidya, Kapil},
   address = {New York},
   booktitle = {Proceedings of Symposium on Principles of Programming Languages 2018},
   doi = {http://dx.doi.org/10.1145/3158119},
   keywords = {Concurrency; Partial-order Reduction; Stateless model-checking},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {New York},
   pages = {1-30},
   publisher = {ACM},
   title = {Data-centric Dynamic Partial Order Reduction},
   year = {2018}
}

TY  - JOUR
ID  - 1392167
AU  - Chalupa, Marek - Chatterjee, Krishnendu - Pavlogiannis, Andreas - Sinha, Nishant - Vaidya, Kapil
PY  - 2018
TI  - Data-centric Dynamic Partial Order Reduction
PB  - ACM
CY  - New York
KW  - Concurrency
KW  - Partial-order Reduction
KW  - Stateless model-checking
N2  - 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.
ER  -

CHALUPA, Marek, Krishnendu CHATTERJEE, Andreas PAVLOGIANNIS, Nishant SINHA and Kapil VAIDYA. Data-centric Dynamic Partial Order Reduction. In \textit{Proceedings of Symposium on Principles of Programming Languages 2018}. New York: ACM, 2018, p.~1-30. ISSN~2475-1421. Available from: https://dx.doi.org/10.1145/3158119.

Detailed Information on Publication Record