Publications

Archer

Thread-local Concurrency: A Technique to Handle Data Race Detection at Programming Model Abstraction. Joachim Protze, Martin Schulz, Dong H. Ahn, and Matthias S. Müller, 27th International Symposium on High-Performance Parallel and Distributed Computing (HPDC), 2018, Tempe, Arizona, USA.
[Abstract] [BibTex] [PDF]
BibTex
@inproceedings{3208056, author = {Joachim Protze and Martin Schulz and Dong H. Ahn and Matthias S. M\"{u}ller}, title = {{Thread-local Concurrency: A Technique to Handle Data Race Detection at Programming Model Abstraction}}, booktitle = {Proceedings of the 27th International Symposium on High-Performance Parallel and Distributed Computing}, series = {HPDC 18}, year = {2018}, isbn = {978-1-4503-5785-2}, location = {Tempe, Arizona}, pages = {144--155}, numpages = {12}, url = {http://doi.acm.org/10.1145/3208040.3208056}, doi = {10.1145/3208040.3208056}, acmid = {3208056}, publisher = {ACM}, address = {New York, NY, USA}, }
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.
SWORD: A Bounded Memory-Overhead Detector of OpenMP Data Races in Production Runs. Simone Atzeni, Ganesh Gopalakrishnan, Zvonimir Rakamarić, Ignacio Laguna, and Gregory L. Lee, 32nd IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2018, Vancouver, British Columbia, CANADA.
[Abstract] [BibTex] [PDF]
BibTex
@INPROCEEDINGS{8425238, author = {Simone Atzeni and Ganesh Gopalakrishnan and Zvonimir Rakamari{\'c} and Ignacio Laguna and Gregory L. Lee and Dong H. Ahn}, booktitle = {2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS)}, title = {{SWORD: A Bounded Memory-Overhead Detector of OpenMP Data Races in Production Runs}}, year = {2018}, pages = {845-854}, doi = {10.1109/IPDPS.2018.00094}, issn = {1530-2075}, month = {May}, }
Abstract

The detection and elimination of data races in large-scale OpenMP programs is of critical importance. Unfortunately, today's state-of-the-art OpenMP race checkers suffer from high memory overheads and/or miss races. In this paper, we present SWORD, a data race detector that significantly improves upon these limitations. SWORD limits the application slowdown and memory usage by utilizing only a bounded, user-adjustable memory buffer to collect targeted memory accesses. When the buffer fills up, the accesses are compressed and flushed to a file system for later offline analysis. SWORD builds on an operational semantics that formally captures the notion of concurrent accesses within OpenMP regions. An offline race checker that is driven by these semantic rules allows SWORD to improve upon happens-before techniques that are known to mask races. To make its offline analysis highly efficient and scalable, SWORD employs effective self-balancing interval-tree-based algorithms. Our experimental results demonstrate that SWORD is capable of detecting races even within programs that use over 90% of the memory on each compute node. Further, our evaluation shows that it matches or exceeds the best available dynamic OpenMP race checker in detection capability while remaining efficient in execution time.
OpenMP Tools Interface: Synchronization Information for Data Race Detection. Joachim Protze, Jonas Hahnfeld, Dong H. Ahn, Martin Schulz, and Matthias S. Müller, 13th International Workshop on OpenMP, IWOMP 2017, 2017, Stony Brook, NY, USA.
[Abstract] [BibTex] [PDF]
BibTex
@inproceedings{IWOMP_2017_paper_21, title = {{OpenMP Tools Interface: Synchronization Information for Data Race Detection}}, author = {Joachim Protze and Jonas Hahnfeld and Dong H. Ahn and Martin Schulz and Matthias S. M{\"u}ller}, booktitle = {{13th International Workshop on OpenMP, IWOMP 2017}}, doi = {10.1007/978-3-319-65578-9_17}, isbn = {978-3-319-65577-2}, month = {September}, pages = {249-265}, year = {2017}, }
Abstract

When it comes to data race detection, complete information about synchronization, concurrency and memory accesses is needed. This information might be gathered at various levels of abstraction. For best results regarding accuracy this information should be collected at the abstraction level of the parallel programming paradigm. With the latest preview of the OpenMP specification, a tools interface (OMPT) was added to OpenMP. In this paper we discuss whether the synchronization information provided by OMPT is sufficient to apply accurate data race analysis for OpenMP applications. We also present some implementation details for our data race detection tool called Archer which derives the synchronization information from OMPT.
ARCHER: Effectively Spotting Data Races in Large OpenMP Applications. Simone Atzeni, Ganesh Gopalakrishnan, Zvonimir Rakamarić, Dong H. Ahn, Ignacio Laguna, Martin Schulz, Gregory L. Lee, Joachim Protze, and Matthias S. Müller, 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2016, Chicago, IL, USA.
[Abstract] [BibTex] [PDF]
BibTex
@inproceedings{7516001, title = {{ARCHER: Effectively Spotting Data Races in Large OpenMP Applications}}, author = {Simone Atzeni and Ganesh Gopalakrishnan and Zvonimir Rakamari{\'c} and Dong H. Ahn and Ignacio Laguna and Martin Schulz and Gregory L. Lee and Joachim Protze and Matthias S. M{\"u}ller}, booktitle = {{2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS)}}, pages = {53-62}, month = {May}, year = {2016}, doi = {10.1109/IPDPS.2016.68}, issn = {1530-2075}, }
Abstract

OpenMP plays a growing role as a portable programming model to harness on-node parallelism, yet, existing data race checkers for OpenMP have high overheads and generate many false positives. In this paper, we propose the first OpenMP data race checker, ARCHER, that achieves high accuracy, low overheads on large applications, and portability. ARCHER incorporates scalable happens-before tracking, exploits structured parallelism via combined static and dynamic analysis, and modularly interfaces with OpenMP runtimes. ARCHER significantly outperforms TSan and Intel Inspector XE, while providing the same or better precision. It has helped detect critical data races in the Hypre library that is central to many projects at Lawrence Livermore National Laboratory and elsewhere.
Towards Providing Low-Overhead Data Race Detection for Large OpenMP Applications. Joachim Protze, Simone Atzeni, Dong H. Ahn, Martin Schulz, Ganesh Gopalakrishnan, Matthias S. Müller, Ignacio Laguna, Zvonimir Rakamarić, and Gregory L. Lee, 2014 LLVM Compiler Infrastructure in HPC, 2014, New Orleans, LA, USA.
[Abstract] [BibTex] [PDF]
BibTex
@inproceedings{7069300, title = {{Towards Providing Low-Overhead Data Race Detection for Large OpenMP Applications}}, author = {Joachim Protze and Simone Atzeni and Dong H. Ahn and Martin Schulz and Ganesh Gopalakrishnan and Matthias S. M{\"u}ller and Ignacio Laguna and Zvonimir Rakamari{\'c} and Gregory L. Lee}, booktitle = {{2014 LLVM Compiler Infrastructure in HPC}}, doi = {10.1109/LLVM-HPC.2014.7}, month = {Nov}, pages = {40-47}, year = {2014}, }
Abstract

Neither static nor dynamic data race detection methods, by themselves, have proven to be sufficient for large HPC applications, as they often result in high runtime overheads and/or low race-checking accuracy. While combined static and dynamic approaches can fare better, creating such combinations, in practice, requires attention to many details. Specifically, existing state-of-the-art dynamic race detectors are aimed at low-level threading models, and cannot handle high-level models such as OpenMP. Further, they do not provide mechanisms by which static analysis methods can target selected regions of code with sufficient precision. In this paper, we present our solutions to both challenges. Specifically, we identify patterns within OpenMP runtimes that tend to mislead existing dynamic race checkers and provide mechanisms that help establish an explicit happens-before relation to prevent such misleading checks. We also implement a fine-grained blacklist mechanism to allow a runtime analyzer to exclude regions of code at line number granularity. We support race checking by adapting ThreadSanitizer, a mature data-race checker developed at Google that is now an integral part of Clang and GCC; and we have implemented our techniques within the state-of-the-art Intel OpenMP Runtime. Our results demonstrate that these techniques can significantly improve runtime analysis accuracy and overhead in the context of data race checking of OpenMP applications.

FLiT

Multi-level analysis of compiler-induced variability and performance tradeoffs. Michael Bentley, Ian Briggs, Ganesh Gopalakrishnan, Dong H. Ahn, Ignacio Laguna, Gregory L. Lee, and Holger E. Jones, Proceedings of the 28th international symposium on high-performance parallel and distributed computing, 2019, Phoenix, Arizona, USA.
[Abstract] [BibTex] [PDF]
BibTex
@inproceedings{bentley_flit_2019, title = {{Multi-Level Analysis of Compiler-Induced Variability and Performance Tradeoffs}}, author = {Michael Bentley and Ian Briggs and Ganesh Gopalakrishnan and Dong H. Ahn and Ignacio Laguna and Gregory L. Lee and Holger E. Jones}, booktitle = {Proceedings of the 28th International Symposium on High-Performance Parallel and Distributed Computing}, series = {HPDC 19}, pages = {61--72}, month = {June}, year = {2019}, publisher = {ACM}, isbn = {978-1-4503-6670-0}, url = {http://doi.acm.org/10.1145/3307681.3325960}, doi = {10.1145/3307681.3325960}, acmid = {3325960}, }
Abstract

Successful HPC software applications are long-lived. When ported across machines and their compilers, these applications often produce different numerical results, many of which are unacceptable. Such variability is also a concern while optimizing the code more aggressively to gain performance. Efficient tools that help locate the program units (files and functions) within which most of the variability occurs are badly needed, both to plan for code ports and to root-cause errors due to variability when they happen in the field. In this work, we offer an enhanced version of the open-source testing framework FLiT to serve these roles. Key new features of FLiT include a suite of bisection algorithms that help locate the root causes of variability. Another added feature allows an analysis of the tradeoffs between performance and the degree of variability. Our new contributions also include a collection of case studies. Results on the MFEM finite-element library include variability/performance tradeoffs, and the identification of a (hitherto unknown) abnormal level of result-variability even under mild compiler optimizations. Results from studying the Laghos proxy application include identifying a significantly divergent floating-point result-variability and successful root-causing down to the problematic function over as little as 14 program executions. Finally, in an evaluation of 4,376 controlled injections of floating-point perturbations on the LULESH proxy application, we showed that the FLiT framework has 100% precision and recall in discovering the file and function locations of the injections all within an average of only 15 program executions.
FLiT: Cross-platform floating-point result-consistency tester and workload. Geof Sawaya, Michael Bentley, Ian Briggs, Ganesh Gopalakrishnan, and Dong H. Ahn, 2017 IEEE International Symposium on Workload Characterization (IISWC), 2017, .
[Abstract] [BibTex] [PDF]
BibTex
@inproceedings{sawaya_flit_2017, title = {{FLiT: Cross-Platform Floating-Point Result-Consistency Tester and Workload}}, author = {Geof Sawaya and Michael Bentley and Ian Briggs and Ganesh Gopalakrishnan and Dong H. Ahn}, booktitle = {2017 IEEE International Symposium on Workload Characterization (IISWC)}, pages = {229--238}, month = {Oct}, year = {2017}, publisher = {IEEE}, url = {https://doi.org/10.1109/IISWC.2017.8167780}, doi = {10.1109/IISWC.2017.8167780}, isbn = {978-1-5386-1233-0}, }
Abstract

Understanding the extent to which computational results can change across platforms, compilers, and compiler flags can go a long way toward supporting reproducible experiments. In this work, we offer the first automated testing aid called FLiT (Floating-point Litmus Tester) that can show how much these results can vary for any user-given collection of computational kernels. Our approach is to take a collection of these kernels, disperse them across a collection of compute nodes (each with a different architecture), have them compiled and run, and bring the results to a central SQL database for deeper analysis. Properly conducting these activities requires a careful selection (or design) of these kernels, input generation methods for them, and the ability to interpret the results in meaningful ways. The results in this paper are meant to inform two different communities: (a) those interested in seeking higher performance by considering “IEEE unsafe” optimizations, but then want to understand how much result variability to expect, and (b) those interested in standardizing compiler flags and their meanings, so that one may safely port code across generations of compilers and architectures. By releasing FLiT, we have also opened up the possibility of all HPC developers using it as a common resource as well as contributing back interesting test kernels as well as best practices, thus extending the floating-point result-consistency workload we contribute. This is the first such workload and result-consistency tester underlying floating-point reproducibility of which we are aware.

Ninja

Noise injection techniques to expose subtle and unintended message races. Kento Sato, Dong H. Ahn, Ignacio Laguna, Gregory L. Lee, Martin Schulz, and Christopher M. Chambreau, Proceedings of the 22Nd acm sigplan symposium on principles and practice of parallel programming, 2017, Austin, TX, USA.
[Abstract] [BibTex] [PDF]
BibTex
@inproceedings{30187433018767, Acmid = {3018767}, Address = {New York, NY, USA}, Author = {Sato, Kento and Ahn, Dong H. and Laguna, Ignacio and Lee, Gregory L. and Schulz, Martin and Chambreau, Christopher M.}, Booktitle = {Proceedings of the 22Nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming}, Doi = {10.1145/3018743.3018767}, Isbn = {978-1-4503-4493-7}, Keywords = {debugging, mpi, non-determinism}, Location = {Austin, Texas, USA}, Numpages = {13}, Pages = {89--101}, Publisher = {ACM}, Series = {PPoPP '17}, Title = {Noise Injection Techniques to Expose Subtle and Unintended Message Races}, Url = {http://doi.acm.org/10.1145/3018743.3018767}, Year = {2017},}
Abstract

Debugging intermittently occurring bugs within MPI applications is challenging, and message races, a condition in which two or more sends race to match with a receive, are one of the common root causes. Many debugging tools have been proposed to help programmers resolve them, but their runtime interference perturbs the timing such that subtle races often cannot be reproduced with debugging tools. We present novel noise injection techniques to expose message races even under a tool’s control. We first formalize this race problem in the context of non-deterministic parallel applications and use this analysis to determine an effective noise-injection strategy to uncover them. We codified these techniques in NINJA (Noise INJection Agent) that exposes these races without modification to the application. Our evaluations on synthetic cases as well as a real-world bug in Hypre-2.10.1 show that NINJA significantly helps expose races.

ReMPI

Clock Delta Compression for Scalable Order-replay of Non-deterministic Parallel Applications. Kento Sato, Dong H. Ahn, Ignacio Laguna, Gregory L. Lee, and Martin Schulz, Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2015, Austin, TX, USA.
[Abstract] [BibTex] [PDF]
BibTex
@inproceedings{Sato:2015:CDC:2807591.2807642, Acmid = {2807642}, Address = {New York, NY, USA}, Articleno = {62}, Author = {Sato, Kento and Ahn, Dong H. and Laguna, Ignacio and Lee, Gregory L. and Schulz, Martin}, Booktitle = {{P}roceedings of the {I}nternational {C}onference for {H}igh {P}erformance {C}omputing, {N}etworking, {S}torage and {A}nalysis}, Doi = {10.1145/2807591.2807642}, Isbn = {978-1-4503-3723-6}, Location = {Austin, Texas}, Numpages = {12}, Pages = {62:1--62:12}, Publisher = {ACM}, Title = {{C}lock {D}elta {C}ompression for {S}calable {O}rder-replay of {N}on-deterministic {P}arallel {A}pplications}, Url = {http://doi.acm.org/10.1145/2807591.2807642}, Year = {2015},}
Abstract

The ability to record and replay program execution helps significantly in debugging non-deterministic MPI applications by reproducing message-receive orders. However, the large amount of data that traditional record-and-reply techniques record precludes its practical applicability to massively parallel applications. In this paper, we propose a new compression algorithm, Clock Delta Compression (CDC), for scalable record and replay of non-deterministic MPI applications. CDC defines a reference order of message receives based on a totally ordered relation using Lamport clocks, and only records the differences between this reference logical-clock order and an observed order. Our evaluation shows that CDC significantly reduces the record data size. For example, when we apply CDC to Monte Carlo particle transport Benchmark (MCB), which represents common non-deterministic communication patterns, CDC reduces the record size by approximately two orders of magnitude compared to traditional techniques and incurs between 13.1% and 25.5% of runtime overhead.

Copyright notice: This material is presented to ensure timely dissemination of research and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright.

Providing Reproducibility for Uncovering Non-deterministic Errors in Runs on Supercomputers

Publications

Archer

FLiT

Ninja

ReMPI