Thesis
-
Techniques for Static Detection of Data-Races in OpenMP ProgramsPhD dissertation (2022)
In the era of exascale computing, writing efficient parallel programs is indispensable, and yet writing sound parallel programs is very difficult. Specifying parallelism with frameworks such as OpenMP is relatively easy. However, incorrect usage of OpenMP may introduce bugs into a parallel program. A concurrency bug, referred to as data-race, occurs when two threads incorrectly access the same memory location simultaneously. Data-races can result in loss of manpower, time, as well as data loss due to system failures.
Considerable amount of research has gone into detecting data-races in parallel programs. Recently, race detection in OpenMP programs has drawn the attention of researchers. The techniques used for detecting data-races in parallel programs are also applicable to OpenMP programs. However, these techniques are ill-equipped to handle many high level OpenMP features, either in the form of constructs, or in the form of semantics. And not considering these semantics results in false positives.
Most static race detection tools employ a single technique to detect data-races, which is not adequate in supporting the multitude of features provided by OpenMP. Hence, the existing static race detection tools support limited features of OpenMP. The dynamic race detection tools take a considerable amount of time to report races and come with a significant memory overhead. In this dissertation, we present two approaches to statically detect data-races in OpenMP programs and improve turnaround time and/or developer productivity.
Firstly, we use the precise dependence analysis of the polyhedral framework to detect data-races by analyzing violations of data dependences. We also use the framework to certify race freedom of program segments.
Firstly, we use the precise dependence analysis of the polyhedral framework to detect data-races by analyzing violations of data dependences. Secondly, we formalize and provide a data-flow analysis framework to perform Phase Interval Analysis (PIA) of OpenMP programs. PIA computes the execution phase intervals for each basic block in a static task graph. Phase intervals are then used to compute the May-Happen-in-Parallel (MHP) and its complement Never-Happen-in-Parallel (NHP) sets for the program. The MHP information is used to detect data-races statically.
We have implemented the proposed techniques in the LLVM compiler framework and developed LLOV --- a fast, lightweight, language agnostic, and static data-race checker for OpenMP programs. The checker can detect data-races in the frequently used OpenMP constructs, target offloading constructs, presence or absence of explicit barriers, and implicit or explicit synchronization. To improve developer productivity, we provide the option to visualize the analyzed information as an annotated task graph in the DOT language using a common graph viewer such as Graphviz.
We evaluate our work using multiple OpenMP race detection benchmarks and real world applications. Our experiments show that the checker is comparable to the state-of-the-art in various performance metrics with around 90% accuracy, almost perfect recall, and significantly lower runtime and memory footprint.@phdthesis{Bora-thesis-2022, author = {Bora, Utpal}, title = {{Techniques for Static Detection of Data-Races in OpenMP Programs}}, school = {Indian Institute of Technology Hyderabad}, address = {Hyderabad, India}, year = {2022}, month = {October}, note = {\url{https://utpalbora.com/documents/Utpal_thesis_CSE_final_singed.pdf}}, keywords = {OpenMP, program verification, polyhedral compilation, static analysis, data race detection, shared memory programming}, pdf = {https://utpalbora.com/documents/Utpal_thesis_CSE_final_singed.pdf}, slides = {https://utpalbora.com/documents/Utpal_Bora_Thesis_Defense_slides.pdf}, project = {https://github.com/utpalbora/llov}, }
Journal Articles
-
LLOV: A Fast Static Data-Race Checker for OpenMP Programs
ACM Trans. Archit. Code Optim. (2020)In the era of Exascale computing, writing efficient parallel programs is indispensable, and, at the same time, writing sound parallel programs is very difficult. Specifying parallelism with frameworks such as OpenMP is relatively easy, but data races in these programs are an important source of bugs. In this article, we propose LLOV, a fast, lightweight, language agnostic, and static data race checker for OpenMP programs based on the LLVM compiler framework. We compare LLOV with other state-of-the-art data race checkers on a variety of well-established benchmarks. We show that the precision, accuracy, and the F1 score of LLOV is comparable to other checkers while being orders of magnitude faster. To the best of our knowledge, LLOV is the only tool among the state-of-the-art data race checkers that can verify a C/C++ or FORTRAN program to be data race free.
@article{Bora-taco-2020, author = {Bora, Utpal and Das, Santanu and Kukreja, Pankaj and Joshi, Saurabh and Upadrasta, Ramakrishna and Rajopadhye, Sanjay}, title = {{LLOV: A Fast Static Data-Race Checker for OpenMP Programs}}, year = {2020}, issue_date = {November 2020}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, volume = {17}, number = {4}, issn = {1544-3566}, url = {https://doi.org/10.1145/3418597}, doi = {10.1145/3418597}, journal = {ACM Trans. Archit. Code Optim.}, month = dec, articleno = {35}, numpages = {26}, keywords = {OpenMP, program verification, polyhedral compilation, static analysis, data race detection, shared memory programming}, pdf = {https://arxiv.org/pdf/1912.12189}, video = {https://www.youtube.com/watch?v=kyD4ysn8ljE&t=3781s}, slides = {https://github.com/utpalbora/talks/blob/main/2021/HiPEAC/LLOV_Slides_HiPEAC_2021.pdf}, project = {https://github.com/utpalbora/llov}, blog = {https://compilers.cse.iith.ac.in/projects/llov/} } -
An analysis of executable size reduction by LLVM passes
CSI Transactions on ICT (2019)The formidable increase in the number of smaller and smarter embedded devices has compelled programmers to develop more and more specialized application programs for these systems. These resource intensive programs that have to be executed on limited memory systems make a strong case for compiler optimizations that reduce the executable size of programs. Standard compilers (like LLVM) offer an out-of-the-box -Oz optimization option—just a series of compiler optimization passes—that is specifically targeted for the reduction of the generated executable size. In this paper, we aim to analyze the effects of optimizations of LLVM compiler on the reduction of executable size. Specifically, we take the size of the executable as a metric and attempt to divide the -Oz series into logical groups and study their individual effects; while also study the effect of their combinations. Our preliminary study over SPEC CPU 2017 benchmarks gives us an insight into the comparative effect of the groups of passes on the executable size. Our work has potential to enable the user to tailor a custom series of passes so as to obtain the desired executable size.
@article{Jain-csitict-2019, author = {Jain, Shalini and Bora, Utpal and Kumar, Prateek and Sinha, Vaibhav B. and Purini, Suresh and Upadrasta, Ramakrishna}, title = {An analysis of executable size reduction by LLVM passes}, journal = {CSI Transactions on ICT}, year = {2019}, month = jun, day = {01}, volume = {7}, number = {2}, pages = {105--110}, issn = {2277-9086}, doi = {10.1007/s40012-019-00248-5}, url = {https://doi.org/10.1007/s40012-019-00248-5}, pdf = {https://utpalbora.com/documents/CodeSize.pdf} }
Conference Papers
-
OpenMP aware MHP Analysis for Improved Static Data-Race Detection
In 2021 IEEE/ACM 7th Workshop on the LLVM Compiler Infrastructure in HPC (LLVM-HPC) (2021)Data races, a major source of bugs in concurrent programs, can result in loss of manpower and time as well as data loss due to system failures. OpenMP, the de facto shared memory parallelism framework used in the HPC community, also suffers from data races. To detect race conditions in OpenMP programs and improve turnaround time and/or developer productivity, we present a data flow analysis based, fast, static data race checker in the LLVM compiler framework. Our tool can detect races in the presence or absence of explicit barriers, with implicit or explicit synchronization. In addition, our tool effectively works for the OpenMP target offloading constructs and also supports the frequently used OpenMP constructs.We formalize and provide a data flow analysis framework to perform Phase Interval Analysis (PIA) of OpenMP programs. Phase intervals are then used to compute the MHP (and its complement NHP) sets for the programs, which, in turn, are used to detect data races statically.We evaluate our work using multiple OpenMP race detection benchmarks and real world applications. Our experiments show that the checker is comparable to the state-of-the-art in various performance metrics with around 90% accuracy, almost perfect recall, and significantly lower runtime and memory footprint.
@inproceedings{Bora-llvm-hpc-2021, author = {Bora, Utpal and Vaishay, Shraiysh and Joshi, Saurabh and Upadrasta, Ramakrishna}, booktitle = {{2021 IEEE/ACM 7th Workshop on the LLVM Compiler Infrastructure in HPC (LLVM-HPC)}}, title = {{OpenMP aware MHP Analysis for Improved Static Data-Race Detection}}, year = {2021}, volume = {}, number = {}, pages = {1-11}, keywords = {}, doi = {10.1109/LLVMHPC54804.2021.00006}, series = {{LLVM-HPC '21}}, issn = {}, month = nov, pdf = {https://arxiv.org/pdf/2111.04259.pdf}, project = {https://github.com/utpalbora/llov} }
Technical Talks and Posters
-
LLOV: A Fast Static Data-Race Checker for OpenMP Programs
(2021)@misc{bora2021llov-hipeac, title = {{LLOV: A Fast Static Data-Race Checker for OpenMP Programs}}, author = {Bora, Utpal and Das, Santanu and Kukreja, Pankaj and Joshi, Saurabh and Upadrasta, Ramakrishna and Rajopadhye, Sanjay}, year = {2021}, howpublished = {\url{https://www.hipeac.net/2021/budapest/\#/program/paper-track/}}, note = {\href{https://www.hipeac.net/2021/budapest/#/program/paper-track/}{Invited Talk, HiPEAC}}, video = {https://www.youtube.com/watch?v=kyD4ysn8ljE&t=3781s}, slides = {https://github.com/utpalbora/talks/blob/main/2021/HiPEAC/LLOV_Slides_HiPEAC_2021.pdf} } -
@misc{bora2021datarace-llvmsocial, title = {{Talk @LLVM Social Bangalore}}, author = {Bora, Utpal}, year = {2021}, video = {https://www.youtube.com/watch?v=TVhVX8cR088}, slides = {https://github.com/utpalbora/talks/blob/main/2021/LLVM-Social-Bangalore/LLVM_Social_Bangalore_April_2021.pdf} } -
LLOV: A Fast Static Data-Race Checker for OpenMP Programs
(2020)@misc{bora2020llov-cgo, title = {{LLOV: A Fast Static Data-Race Checker for OpenMP Programs}}, author = {Bora, Utpal and Das, Santanu and Kukreja, Pankaj and Joshi, Saurabh and Upadrasta, Ramakrishna and Rajopadhye, Sanjay}, year = {2020}, howpublished = {\url{https://llvm.org/devmtg/2020-02-23/}}, note = {\href{https://llvm.org/devmtg/2020-02-23/\#ub}{Technical Talk, LLVM Performance Workshop at CGO}}, slides = {https://github.com/utpalbora/talks/blob/main/2020/LLVM-Performance/LLOV_LLVM_Performance_CGO_2020.pdf} } -
LLOV: A Fast Static Data-Race Checker for OpenMP Programs
(2020)@misc{bora2020llov-fsttcs, title = {{LLOV: A Fast Static Data-Race Checker for OpenMP Programs}}, author = {Bora, Utpal and Das, Santanu and Kukreja, Pankaj and Joshi, Saurabh and Upadrasta, Ramakrishna and Rajopadhye, Sanjay}, year = {2020}, howpublished = {\url{https://www.microsoft.com/en-us/research/event/research-highlights-in-programming-languages-fsttcs-2020/\#!schedule-17th-dec-2020}}, note = {\href{https://www.microsoft.com/en-us/research/event/research-highlights-in-programming-languages-fsttcs-2020/\#!schedule-17th-dec-2020}{Technical Talk, RHPL Workshop at FSTTCS}}, slides = {https://github.com/utpalbora/talks/blob/main/2020/RHPL/LLOV_Slides_RHPL_FSTTCS_2020.pdf} } -
DataRaceBench FORTRAN
(2019)@misc{drbForturl, author = {Kukreja, Pankaj and Shukla, Himanshu and Bora, Utpal}, title = {{DataRaceBench FORTRAN}}, howpublished = {\url{https://github.com/IITH-Compilers/drb_fortran}}, year = {2019}, note = {\href{https://github.com/IITH-Compilers/drb_fortran}{Github}}, project = {https://github.com/utpalbora/drb_fortran} } -
Improved loop distribution in LLVM using polyhedral dependences
(2017)@misc{dangeti2017improved, title = {Improved loop distribution in LLVM using polyhedral dependences}, author = {Dangeti, Tharun Kumar and Bora, Utpal and Das, Santanu and Grosser, Tobias and Upadrasta, Ramakrishna}, booktitle = {The Fourth Workshop on the LLVM Compiler Infrastructure in HPC}, howpublished = {\url{https://llvm-hpc4-workshop.github.io/talks.html}}, year = {2017}, note = {\href{https://llvm-hpc4-workshop.github.io/talks.html}{Lightning Talk, LLVM-HPC Workshop at SC}} } -
GSoC 2016: PolyhedralInfo - Polly as an analysis pass in LLVM
(2016)@misc{utpal2016gsoc, author = {Bora, Utpal and Doerfert, Johannes and Grosser, Tobias and Upadrasta, Ramakrishna}, title = {{GSoC 2016: PolyhedralInfo - Polly as an analysis pass in LLVM}}, howpublished = {\url{https://llvmdevelopersmeetingbay2016.sched.com/event/8Z2Z/lightning-talks}}, year = {2016}, note = {\href{https://llvmdevelopersmeetingbay2016.sched.com/event/8Z2Z/lightning-talks}{Lightning Talk, US LLVM Dev Meet}}, pdf = {https://llvm.org/SummerOfCode/2016.html#paap}, project = {https://drive.google.com/drive/folders/0B6y_K1BShACaZHVuTHF5ZWdmeUE?resourcekey=0-krdDhACZEUQSG-3-12BjXA}, blog = {https://utpalbora.com/gsoc/2016.html} } -
A Comparative Study of Vectorization in Compilers
(2016)@misc{das2016vec, title = {A Comparative Study of Vectorization in Compilers}, author = {Das, Santanu and Kumar, Dangeti Tharun and Bora, Utpal and Upadrasta, Ramakrishna}, year = {2016}, howpublished = {\url{https://www.hipc.org/hipc2016/studentsymposium.php}}, note = {\href{https://www.hipc.org/hipc2016/studentsymposium.php}{Poster, HiPC}} } -
Introduction to LLVM Compiler Infrastructure
(2016)@misc{bora2016gdg, title = {Introduction to LLVM Compiler Infrastructure}, author = {Bora, Utpal and Pratik, Bhatu}, year = {2016}, howpublished = {\url{}}, note = {\href{}{Invited Talk, GDG DevFest Hyderabad}} }