Earlier Version

Data-centric dynamic partial order reduction

1 Anonymous, 2 Anonymous, 3 Anonymous, 4 Anonymous, Data-Centric Dynamic Partial Order Reduction, IST Austria, 2016.

Download
OA IST-2016-620-v1+1_main.pdf 538.88 KB
Restricted authornames.txt
Technical Report | Published | English
Author
Anonymous, 1; Anonymous, 2; Anonymous, 3; Anonymous, 4
Series Title
IST Austria Technical Report
Abstract
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. 1. 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. 2. 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.
Publishing Year
Date Published
2016-07-15
Page
20
ISSN
IST-REx-ID

Cite this

Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. Data-Centric Dynamic Partial Order Reduction. IST Austria; 2016.
Anonymous, 1, Anonymous, 2, Anonymous, 3, & Anonymous, 4. (2016). Data-centric dynamic partial order reduction. IST Austria.
Anonymous, 1, 2 Anonymous, 3 Anonymous, and 4 Anonymous. Data-Centric Dynamic Partial Order Reduction. IST Austria, 2016.
1 Anonymous, 2 Anonymous, 3 Anonymous, and 4 Anonymous, Data-centric dynamic partial order reduction. IST Austria, 2016.
Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. 2016. Data-centric dynamic partial order reduction, IST Austria, 20p.
Anonymous, 1, et al. Data-Centric Dynamic Partial Order Reduction. IST Austria, 2016.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2018-12-12
MD5 Checksum
1d69252d66bcdf782615ddfb911d2957
File Name
authornames.txt 121 bytes
Access Level
Restricted Closed Access
Date Uploaded
2019-05-10
MD5 Checksum
deabb0eb8f237cae4f9542b28b0b6eb2


Material in IST:
Later Version

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1610.01188

Search this title in

Google Scholar