BlockRace: A Big Data Approach to Dynamic Block-based Data Race Detection for Multithreaded Programs
Pages 71 - 80
Abstract
The advent of multicore systems and distributed frameworks enables distributed strategies to address challenges in large-scale divisible problems by decomposing them into small ones, processing the corresponding sub-solutions and aggregating these sub-solutions into the final result. However, dynamic online detection of data races in execution traces of multithreaded programs is challenging to be parallelized due to their inherent historic event sensitivity and incremental inference of happens-before transitive closure To examine the extent of such detection to be transformed into parallel versions, in this paper, we present BlockRace, a novel dynamic block-based data race detection technique, which precisely detects data races in such traces and checks pairs of events blocks in parallel using its novel strategy. We evaluate BlockRace on 18 programs, and the results show that BlockRace achieves 1.96x to 5.5x speedups compared to its sequential counterparts. To the best of our knowledge, BlockRace is the first technique to detect races in block parrs where these block pairs can be run in parallel on Big Data frameworks.
References
[1]
Rapid, https://github.com/umangm/rapid
[2]
Apache Hadoop, https://hadoop.apache.org/
[3]
Apache Spark, https://spark.apache.org/
[4]
Kryo, https://github.com/EsotericSoftware/kryo
[5]
RVPredict, https://runtimeverification.com/predict/
[6]
F. Sorrentino, A. Farzan, and P. Madhusudan, "PENELOPE: Weaving Threads to Expose Atomicity Violations," in Proceedings of the Eighteenth ACM SIGSOFT International Symposium on Foundations of Software Engineering, New York, NY, USA, 2010, pp. 37--46.
[7]
K. Veeraraghavan, D. Lee, B. Wester, J. Ouyang, P. M. Chen, J. Flinn, and S. Narayanasamy. DoublePlay: Parallelizing sequential logging and replay. In Proc. 2011 International Conference on Architectural Support for Programming Languages and Operating Systems, pages 15--26.
[8]
B. Wester, D. Devecsery, P. M. Chen, J. Flinn, and S. Narayanasamy, "Parallelizing Data Race Detection," in Proceedings of the Eighteenth International Conference on Architectural Support for Programming Languages and Operating Systems, New York, NY, USA, 2013, pp. 27--38.
[9]
Y. Sakurai, Y. Arahori, and K. Gondow, "POL Skew-Aware Parallel Race Detection," in Proceedings of IEEE 18th International Working Conference on Source Code Analysis and Manipulation (SCAM), 2018, pp. 215--224.
[10]
Y. W. Song and Y.-H. Lee, "A Parallel FastTrack Data Race Detector on Multicore Systems," in Proceedings of IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2017, pp. 387--396.
[11]
Y. Cai, J. Zhang, L. Cao, and J. Liu, "A deployable sampling strategy for data race detection," in In Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, 2016, pp. 810--821.
[12]
S. Wu, C. Yang, and W. K. Chan, "ASR: Abstraction Subspace Reduction for Exposing Atomicity Violation Bugs in Multithreaded Programs," in 2015 IEEE International Conference on Software Quality, Reliability and Security, 2015, pp. 272--281.
[13]
Y. Cai and W. K. Chan, "Magiclock: Scalable Detection of Potential Deadlocks in Large-Scale Multithreaded Programs," IEEE Transactions on Software Engineering, vol. 40, no. 3, pp. 266--281, Mar. 2014.
[14]
J. W. Voung, R. Jhala, and S. Lerner, "RELAY: Static Race Detection on Millions of Lines of Code," in Proceedings of the the 6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on The Foundations of Software Engineering, New York, NY, USA, 2007, pp. 205--214.
[15]
B. P. Wood, M. Cao, M. D. Bond, and D. Grossman, "Instrumentation Bias for Dynamic Data Race Detection," Proc. ACM Program. Lang., vol. 1, no. OOPSLA, pp. 69:1--69:31, Oct. 2017.
[16]
J. Yang, C. Yang, and W. K. Chan, "HistLock: Efficient and Sound Hybrid Detection of Hidden Predictive Data Races with Functional Contexts," in 2016 IEEE International Conference on Software Quality, Reliability and Security (QRS), 2016, pp. 13--24.
[17]
D. Marino, M. Musuvathi, and S. Narayanasamy, "LiteRace: Effective Sampling for Lightweight Data-Race Detection," In ACM Sigplan notices (Vol. 44, No. 6). ACM. pp. 134--143.
[18]
E. Vlachos et al., "ParaLog: Enabling and Accelerating Online Parallel Monitoring of Multithreaded Applications," in Proceedings of the Fifteenth Edition of ASPLOS on Architectural Support for Programming Languages and Operating Systems, New York, NY, USA, 2010, pp. 271--284.
[19]
T. Zhang, C. Jung, and D. Lee, "ProRace: Practical Data Race Detection for Production Use," in ACM SIGOPS Operating Systems Review51, no. 2, 2017, pp. 149--162.
[20]
C. Flanagan and S. N. Freund, FastTrack: efficient and precise dynamic race detection. In Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '09). ACM, New York, NY, USA, 121--133.
[21]
Y. Smaragdakis, J. Evans, C. Sadowski, J. Yi, and C. Flanagan, "Sound Predictive Race Detection in Polynomial Time," in Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, New York, NY, USA, 2012, pp. 387--400.
[22]
D. Kini, U. Mathur, and M. Viswanathan, "Dynamic Race Prediction in Linear Time," in ACM SIGPLAN Notices, vol. 52, no. 6, Jun. 2017, pp. 157--170.
[23]
A. Pavlogiannis, "Fast, Sound and Effectively Complete Dynamic Race Detection," arXiv:1901.08857 [cs], Jan. 2019.
[24]
S. Lu, J. Tucek, F. Qin, and Y. Zhou, "AVIO: Detecting Atomicity Violations via Access-Interleaving Invariants," IEEE Micro, vol. 27, no. 1, pp. 26--35, Jan. 2007.
[25]
S. Lu, S. Park, E. Seo, and Y. Zhou, "Learning from Mistakes: A Comprehensive Study on Real World Concurrency Bug Characteristics," in Proceedings of the 13th International Conference on Architectural Support for Programming Languages and Operating Systems, New York, NY, USA, 2008, pp. 329--339.
[26]
S. Biswas, M. Zhang, M. D. Bond, and B. Lucia, "Valor: efficient, software-only region conflict exceptions," in ACM SIGPLAN Notices, vol. 50, no. 10, 2015, pp. 241--259.
[27]
S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. E. Anderson. "Eraser: A dynamic data race detector for multi-threaded programs. " In ACM Transactions on Computer Systems (TOCS) 15, no. 4, 1997, pp. 391--411.
Index Terms
- BlockRace: A Big Data Approach to Dynamic Block-based Data Race Detection for Multithreaded Programs
Recommendations
Applying transactional memory to concurrency bugs
ASPLOS XVII: Proceedings of the seventeenth international conference on Architectural Support for Programming Languages and Operating SystemsMultithreaded programs often suffer from synchronization bugs such as atomicity violations and deadlocks. These bugs arise from complicated locking strategies and ad hoc synchronization methods to avoid the use of locks. A survey of the bug databases of ...
Applying transactional memory to concurrency bugs
ASPLOS '12Multithreaded programs often suffer from synchronization bugs such as atomicity violations and deadlocks. These bugs arise from complicated locking strategies and ad hoc synchronization methods to avoid the use of locks. A survey of the bug databases of ...
Applying transactional memory to concurrency bugs
ASPLOS '12Multithreaded programs often suffer from synchronization bugs such as atomicity violations and deadlocks. These bugs arise from complicated locking strategies and ad hoc synchronization methods to avoid the use of locks. A survey of the bug databases of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2020
122 pages
ISBN:9781450379571
DOI:10.1145/3387903
Copyright © 2020 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 07 October 2020
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
AST '20
Sponsor:
AST '20: IEEE/ACM 15nd International Conference on Automation of Software Test
October 7 - 8, 2020
Seoul, Republic of Korea
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 75Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)1
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in