Abstract
This paper proposes OMP-RACER, a dynamic apparent data race detector for OpenMP programs. Apparent data races are those races that manifest in a program considering the logical series-parallel relations of the execution. By identifying apparent races, OMP-RACER can detect races that occur not only in the observed schedule but also in other schedules for a given input. Our key contribution is a data structure to capture series-parallel relations between various fragments of an OpenMP program with both structured and unstructured parallelism directives, which we call the Enhanced OpenMP Series-Parallel Graph (EOSPG). OMP-RACER maintains information about previous accesses with each memory access and uses the EOSPG to check if they can logically execute in parallel. OMP-RACER detects more races with similar overheads when compared to existing state-of-the-art race detectors for OpenMP programs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Agrawal, K., Devietti, J., Fineman, J.T., Lee, I.T.A., Utterback, R., Xu, C.: Race detection and reachability in nearly series-parallel dags. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, p. 156–171. SODA 2018 (2018)
Atzeni, S., et al.: Archer: effectively spotting data races in large OpenMP applications. In: 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 53–62. IPDPS 2016 (2016)
Basupalli, V., et al.: ompVerify: polyhedral analysis for the OpenMP programmer. In: Chapman, B.M., Gropp, W.D., Kumaran, K., Müller, M.S. (eds.) IWOMP 2011. LNCS, vol. 6665, pp. 37–53. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21487-5_4
Boushehrinejadmoradi, N., Yoga, A., Nagarakatte, S.: A parallelism profiler with what-if analyses for OpenMP programs. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis, pp. 16:1–16:14. SC 2018 (2018)
Boushehrinejadmoradi, N., Yoga, A., Nagarakatte, S.: Omp-racer data race detector (2020). https://github.com/rutgers-apl/omprace
Burckhardt, S., Kothari, P., Musuvathi, M., Nagarakatte, S.: A randomized scheduler with probabilistic guarantees of finding bugs. In: Proceedings of the 15th International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 167–178. ASPLOS (2010)
Chatarasi, P., Shirako, J., Kong, M., Sarkar, V.: An extended polyhedral model for SPMD programs and its use in static data race detection. In: Ding, C., Criswell, J., Wu, P. (eds.) LCPC 2016. LNCS, vol. 10136, pp. 106–120. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-52709-3_10
Cheng, G.I., Feng, M., Leiserson, C.E., Randall, K.H., Stark, A.F.: Detecting data races in cilk programs that use locks. In: Proceedings of the 10th ACM Symposium on Parallel Algorithms and Architectures, pp. 298–309. SPAA (1998)
Feng, M., Leiserson, C.E.: Efficient detection of determinacy races in cilk programs. In: Proceedings of the 9th ACM Symposium on Parallel Algorithms and Architectures, pp. 1–11. SPAA (1997)
Flanagan, C., Freund, S.N.: Fasttrack: efficient and precise dynamic race detection. In: Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 121–133 (2009)
Gu, Y., Mellor-Crummey, J.: Dynamic data race detection for OpenMP programs. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis, pp. 61:1–61:12. SC 2018 (2018)
Jannesari, A., Bao, K., Pankratius, V., Tichy, W.: Helgrind+: an efficient dynamic race detector. In: 2009 IEEE International Symposium on Parallel Distributed Processing, pp. 1–13 (2009)
Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Commun. ACM, pp. 558–565 (1978)
Liao, C., Lin, P.H., Asplund, J., Schordan, M., Karlin, I.: Dataracebench: a benchmark suite for systematic evaluation of data race detection tools. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 11:1–11:14. SC 2017 (2017)
Mellor-Crummey, J.: On-the-fly detection of data races for programs with nested fork-join parallelism. In: Proceedings of the 1991 ACM/IEEE Conference on Supercomputing, pp. 24–33. Supercomputing (1991)
Nagarakatte, S., Burckhardt, S., Martin, M.M., Musuvathi, M.: Multicore acceleration of priority-based schedulers for concurrency bug detection. In: Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 543–554. PLDI (2012)
Netzer, R.H.B., Miller, B.P.: What are race conditions?: Some issues and formalizations. ACM Lett. Program. Lang. Syst. pp. 74–88 (1992)
Nudler, I., Rudolph, L.: Tools for the efficient development of efficient parallel programs. In: Proceedings of the 1st Israeli conference on computer system engineering (1988)
OpenMP Architecture Review Board: Openmp 5.0 complete specification, November 2017. https://www.openmp.org/wp-content/uploads/OpenMP-API-Specification-5.0.pdf
Pozniansky, E., Schuster, A.: Efficient on-the-fly data race detection in multithreaded c++ programs. In: Proceedings of the Ninth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 179–190. PPoPP (2003)
Raman, R., Zhao, J., Sarkar, V., Vechev, M., Yahav, E.: Efficient data race detection for Async-finish parallelism. In: Proceedings of the 1st International Conference on Runtime Verification, pp. 368–383. RV (2010)
Raman, R., Zhao, J., Sarkar, V., Vechev, M., Yahav, E.: Scalable and precise dynamic datarace detection for structured parallelism. In: Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 531–542. PLDI (2012)
Savage, S., Burrows, M., Nelson, G., Sobalvarro, P., Anderson, T.: Eraser: a dynamic data race detector for multi-threaded programs. In: Proceedings of the 16th ACM Symposium on Operating Systems Principles, pp. 27–37. SOSP (1997)
Serebryany, K., Iskhodzhanov, T.: Threadsanitizer: Data race detection in practice. In: Proceedings of the Workshop on Binary Instrumentation and Applications, pp. 62–71. WBIA (2009)
Utterback, R., Agrawal, K., Fineman, J.T., Lee, I.T.A.: Provably good and practically efficient parallel race detection for fork-join programs. In: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures. SPAA 2016 (2016)
Ye, F., Schordan, M., Liao, C., Lin, P.H., Karlin, I., Sarkar, V.: Using polyhedral analysis to verify OpenMP applications are data race free. In: 2018 IEEE/ACM 2nd International Workshop on Software Correctness for HPC Applications (Correctness), pp. 42–50 (2018)
Yoga, A., Nagarakatte, S.: Atomicity violation checker for task parallel programs. In: Proceedings of the 2016 International Symposium on Code Generation and Optimization, pp. 239–249. CGO (2016)
Yoga, A., Nagarakatte, S.: A fast causal profiler for task parallel programs. In: Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering, pp. 15–26. ESEC/FSE 2017 (2017)
Yoga, A., Nagarakatte, S.: Parallelism-centric what-if and differential analyses. In: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, p. 485–501. PLDI 2019 (2019)
Yoga, A., Nagarakatte, S., Gupta, A.: Parallel data race detection for task parallel programs with locks. In: Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, pp. 833–845. FSE (2016)
Acknowledgments
We thank the reviewers for their feedback. This paper is based on work supported in part by NSF CAREER Award CCF–1453086, NSF Award CCF-1908798, and NSF Award CCF-1917897.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Boushehrinejadmoradi, N., Yoga, A., Nagarakatte, S. (2020). On-the-fly Data Race Detection with the Enhanced OpenMP Series-Parallel Graph. In: Milfeld, K., de Supinski, B., Koesterke, L., Klinkenberg, J. (eds) OpenMP: Portable Multi-Level Parallelism on Modern Systems. IWOMP 2020. Lecture Notes in Computer Science(), vol 12295. Springer, Cham. https://doi.org/10.1007/978-3-030-58144-2_10
Download citation
DOI: https://doi.org/10.1007/978-3-030-58144-2_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-58143-5
Online ISBN: 978-3-030-58144-2
eBook Packages: Computer ScienceComputer Science (R0)