Joachim Protze
ABSTRACT
With greater adoption of various high-level parallel programming models to harness on-node parallelism, accurate data race detection has become more crucial than ever. However, existing tools have great difficulty spotting data races through these high-level models, as they primarily target low-level concurrent execution models (e.g., concurrency expressed at the level of POSIX threads). In this paper, we propose a novel technique to accurately detect those data races that can occur at higher levels of concurrent execution. The core idea of our technique is to introduce the general concept of Thread-Local Concurrency (TLC) as a new way to translate the concurrency expressed by a high-level programming paradigm into the low execution level understood by the existing tools. Specifically, we extend the definition of vector clocks to allow the existing state-of-the-art race detectors to recognize those races that occur at the higher level of concurrency with minor modifications to these tools. Our evaluation with our prototype implemented within ThreadSanitizer shows that TLC can allow the existing tool to detect these races accurately with only small additional analysis overheads.
- Documentation of OpenMPI on Valgrind usage, https://www.open-mpi.org/faq/?category=debugging#valgrind_clean.Google Scholar
- OpenMP: Support for the OpenMP language, http://openmp.llvm.org.Google Scholar
- TLC implementation. https://github.com/PRUNERS/compiler-rt (branch tlc) and https://github.com/PRUNERS/openmp (branch archer-tlc).Google Scholar
- Simone Atzeni, Ganesh Gopalakrishnan, Zvonimir Rakamaric, Dong H. Ahn, Ignacio Laguna, Martin Schulz, Gregory L. Lee, Joachim Protze, and Matthias S. Müller. ARCHER: Effectively Spotting Data Races in Large OpenMP Applications. In 2016 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2016, Chicago, IL, USA, May 23--27, 2016, pages 53--62, 2016.Google Scholar
- D. Bailey, J. Barton, T. Lasinski, and H. Simon. The NAS Parallel Benchmarks. RNR-91-002, NASA Ames Research Center, August 1991.Google Scholar
- Mingdong Feng and Charles E. Leiserson. Efficient detection of determinacy races in cilk programs. In SPAA, pages 1--11, 1997. Google ScholarDigital Library
- Cormac Flanagan and Stephen N. Freund. Fasttrack: efficient and precise dynamic race detection. In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2009, Dublin, Ireland, June 15--21, 2009, pages 121--133, 2009. Google ScholarDigital Library
- Ok-Kyoon Ha and Yong-Kee Jun. An efficient algorithm for on-the-fly data race detection using an epoch-based technique. Scientific Programming, 2015:205827:1--205827:14, 2015. Google ScholarDigital Library
- Ali Jannesari, Kaibin Bao, Victor Pankratius, and Walter F. Tichy. Helgrind+: An efficient dynamic race detector. In 23rd IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2009, Rome, Italy, May 23--29, 2009, pages 1--13, 2009. Google ScholarDigital Library
- Young-Joo Kim, Sejun Song, and Yong-Kee Jun. VORD: A Versatile On-the-fly Race Detection Tool in OpenMP Programs. International Journal of Parallel Programming, 42(6):900--930, 2014. Google ScholarDigital Library
- Leslie Lamport. Time, clocks and the ordering of events in a distributed system, pages 558--565, July 1978. Google ScholarDigital Library
- John Mellor-Crummey. On-the-fly Detection of Data Races for Programs with Nested Fork-join Parallelism. In Proceedings of the 1991 ACM/IEEE Conference on Supercomputing, Supercomputing '91, pages 24--33, New York, NY, USA, 1991. ACM. Google ScholarDigital Library
- Matthias S. Müller, John Baron, William C. Brantley, Huiyu Feng, Daniel Hackenberg, Robert Henschel, Gabriele Jost, Daniel Molka, Chris Parrott, Joe Robichaux, Pavel Shelepugin, G. Matthijs van Waveren, Brian Whitney, and Kalyan Kumaran. SPEC OMP2012 - an application benchmark suite for parallel systems using openmp. In OpenMP in a Heterogeneous World - 8th International Workshop on OpenMP, IWOMP 2012, Rome, Italy, June 11--13, 2012. Proceedings, pages 223--236, 2012. Google ScholarDigital Library
- Jan Felix Münchhalfen, Tobias Hilbrich, Joachim Protze, Christian Terboven, and Matthias S. Müller. Classification of Common Errors in OpenMP Applications. In Using and Improving OpenMP for Devices, Tasks, and More - 10th International Workshop on OpenMP, IWOMP 2014, Salvador, Brazil, September 28--30, 2014. Proceedings, pages 58--72, 2014.Google Scholar
- Robert H. B. Netzer and Barton P. Miller. What are race conditions?: Some issues and formalizations. LOPLAS, pages 74--88, 1992. Google ScholarDigital Library
- OpenMP Architecture Review Board. TR6: OpenMP Version 5.0 Preview 2. http://www.openmp.org/wp-content/uploads/openmp-tr6.pdf.Google Scholar
- Chang-Seo Park, Koushik Sen, Paul Hargrove, and Costin Iancu. Efficient data race detection for distributed memory parallel programs. In Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, SC '11, pages 51:1--51:12, New York, NY, USA, 2011. ACM. Google ScholarDigital Library
- Joachim Protze, Jonas Hahnfeld, Dong H. Ahn, Martin Schulz, and Matthias S. Müller. OpenMP Tools Interface: Synchronization Information for Data Race Detection. In Scaling OpenMP for Exascale Performance and Portability - 13th International Workshop on OpenMP, IWOMP 2017, Stony Brook, NY, USA, September 20--22, 2017, Proceedings, pages 249--265, 2017.Google Scholar
- Raghavan Raman, Jisheng Zhao, Vivek Sarkar, Martin T. Vechev, and Eran Yahav. Efficient data race detection for async-finish parallelism. In Runtime Verification - First International Conference, RV 2010, St. Julians, Malta, November 1--4, 2010. Proceedings, pages 368--383, 2010. Google ScholarDigital Library
- Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro, and Thomas E. Anderson. Eraser: A Dynamic Data Race Detector for Multithreaded Programs. ACM Trans. Comput. Syst., 15(4):391--411, 1997. Google ScholarDigital Library
- Konstantin Serebryany and Timur Iskhodzhanov. Threadsanitizer: Data race detection in practice. In Proceedings of the Workshop on Binary Instrumentation and Applications, WBIA '09, pages 62--71, New York, NY, USA, 2009. ACM. Google ScholarDigital Library
- Konstantin Serebryany, Alexander Potapenko, Timur Iskhodzhanov, and Dmitriy Vyukov. Dynamic race detection with LLVM compiler. In Runtime Verification, pages 110--114. Springer, 2012. Google ScholarDigital Library
- The Clang Team. Clang 5 documentation: ThreadSanitizer. https://clang.llvm.org/docs/ThreadSanitizer.html.Google Scholar
- Brian Whitney. SPEC OMP 2012 Documentation, https://www.spec.org/omp2012/Docs/.Google Scholar
Recommendations
Semantics-based concurrency control: beyond commutativity
The concurrency of transactions executing on atomic data types can be enhanced through the use of semantic information about operations defined on these types. Hitherto, commutativity of operations has been exploited to provide enchanced concurrency ...
Extracting more concurrency from distributed transactions
OSDI'14: Proceedings of the 11th USENIX conference on Operating Systems Design and ImplementationDistributed storage systems run transactions across machines to ensure serializability. Traditional protocols for distributed transactions are based on two-phase locking (2PL) or optimistic concurrency control (OCC). 2PL serializes transactions as soon ...
Prettier concurrency: purely functional concurrent revisions
Haskell '11This article presents an extension to the work of Launchbury and Peyton-Jones on the ST monad. Using a novel model for concurrency, called concurrent revisions [3,5], we show how we can use concurrency together with imperative mutable variables, while ...
Comments