Document Open Access Logo

Dynamic Determinacy Race Detection for Task-Parallel Programs with Promises

Authors Feiyang Jin, Lechen Yu, Tiago Cogumbreiro, Jun Shirako, Vivek Sarkar

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2023.13.pdf
  • Filesize: 1.12 MB
  • 30 pages

Document Identifiers

Author Details

Feiyang Jin
  • College of Computing, Georgia Institute of Technology, Atlanta, GA, USA
Lechen Yu
  • College of Computing, Georgia Institute of Technology, Atlanta, GA, USA
Tiago Cogumbreiro
  • College of Science and Mathematics, University of Massachusetts Boston, MA, USA
Jun Shirako
  • College of Computing, Georgia Institute of Technology, Atlanta, GA, USA
Vivek Sarkar
  • College of Computing, Georgia Institute of Technology, Atlanta, GA, USA

Funding

This material is based upon work supported by the National Science Foundation under Grant No. 2204986.

Cite As Get BibTex

Feiyang Jin, Lechen Yu, Tiago Cogumbreiro, Jun Shirako, and Vivek Sarkar. Dynamic Determinacy Race Detection for Task-Parallel Programs with Promises. In 37th European Conference on Object-Oriented Programming (ECOOP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 263, pp. 13:1-13:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ECOOP.2023.13

Abstract

Much of the past work on dynamic data-race and determinacy-race detection algorithms for task parallelism has focused on structured parallelism with fork-join constructs and, more recently, with future constructs. This paper addresses the problem of dynamic detection of data-races and determinacy-races in task-parallel programs with promises, which are more general than fork-join constructs and futures. The motivation for our work is twofold. First, promises have now become a mainstream synchronization construct, with their inclusion in multiple languages, including C++, JavaScript, and Java. Second, past work on dynamic data-race and determinacy-race detection for task-parallel programs does not apply to programs with promises, thereby identifying a vital need for this work.
This paper makes multiple contributions. First, we introduce a featherweight programming language that captures the semantics of task-parallel programs with promises and provides a basis for formally defining determinacy using our semantics. This definition subsumes functional determinacy (same output for same input) and structural determinacy (same computation graph for same input). The main theoretical result shows that the absence of data races is sufficient to guarantee determinacy with both properties. We are unaware of any prior work that established this result for task-parallel programs with promises. Next, we introduce a new Dynamic Race Detector for Promises that we call DRDP. DRDP is the first known race detection algorithm that executes a task-parallel program sequentially without requiring the serial-projection property; this is a critical requirement since programs with promises do not satisfy the serial-projection property in general. Finally, the paper includes experimental results obtained from an implementation of DRDP. The results show that, with some important optimizations introduced in our work, the space and time overheads of DRDP are comparable to those of more restrictive race detection algorithms from past work. To the best of our knowledge, DRDP is the first determinacy race detector for task-parallel programs with promises.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Software creation and management
  • Software and its engineering → Software verification and validation
  • Software and its engineering → Software defect analysis
  • Software and its engineering → Software testing and debugging
  • Software and its engineering → Software notations and tools
  • Software and its engineering → General programming languages
  • Software and its engineering → Concurrent programming languages
Keywords
  • Race detection
  • Promise
  • Determinism
  • Determinacy-race
  • Serial projection

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. 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), pages 53-62. IEEE, 2016. Google Scholar
  2. Cedric Bastoul. Code generation in the polyhedral model is easier than you think. In Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, PACT '04, pages 7-16, USA, 2004. IEEE Computer Society. Google Scholar
  3. Mohamed-Walid Benabderrahmane, Louis-Noël Pouchet, Albert Cohen, and Cédric Bastoul. The polyhedral model is more widely applicable than you think. In Rajiv Gupta, editor, CC, volume 6011 of Lecture Notes in Computer Science, pages 283-303. Springer, 2010. URL: http://dblp.uni-trier.de/db/conf/cc/cc2010.html#BenabderrahmanePCB10.
  4. Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Charles E. Leiserson. On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs. In Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, New York, NY, USA, 2004. Association for Computing Machinery. URL: https://doi.org/10.1145/1007912.1007933.
  5. Utpal Bora, Santanu Das, Pankaj Kukreja, Saurabh Joshi, Ramakrishna Upadrasta, and Sanjay Rajopadhye. Llov: A fast static data-race checker for openmp programs. ACM Transactions on Architecture and Code Optimization (TACO), 17(4):1-26, 2020. Google Scholar
  6. Zoran Budimlić, Michael Burke, Vincent Cavé, Kathleen Knobe, Geoff Lowney, Ryan Newton, Jens Palsberg, David Peixotto, Vivek Sarkar, Frank Schlimbach, and Sağnak Taşırlar. Concurrent collections. Scientific Programming, 18:203-217, 2010. 3-4. URL: https://doi.org/10.3233/SPR-2011-0305.
  7. Vincent Cavé, Jisheng Zhao, Jun Shirako, and Vivek Sarkar. Habanero-java: the new adventures of old x10. In Proceedings of the 9th International Conference on Principles and Practice of Programming in Java, pages 51-61, 2011. Google Scholar
  8. Sanjay Chatterjee, Sagnak Tasırlar, Zoran Budimlic, Vincent Cavé, Milind Chabbi, Max Grossman, Vivek Sarkar, and Yonghong Yan. Integrating asynchronous task parallelism with mpi. In 2013 IEEE 27th International Symposium on Parallel and Distributed Processing, pages 712-725, 2013. URL: https://doi.org/10.1109/IPDPS.2013.78.
  9. Shuai Che, Michael Boyer, Jiayuan Meng, David Tarjan, Jeremy W. Sheaffer, Sang-Ha Lee, and Kevin Skadron. Rodinia: A benchmark suite for heterogeneous computing. In 2009 IEEE International Symposium on Workload Characterization (IISWC), pages 44-54, 2009. URL: https://doi.org/10.1109/IISWC.2009.5306797.
  10. Nathan Chong, Alastair F. Donaldson, and Jeroen Ketema. A sound and complete abstraction for reasoning about parallel prefix sums. In Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '14, pages 397-409, New York, NY, USA, 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2535838.2535882.
  11. LLVM Community. Tsan predefined constants for vector clocks, May 2022. URL: https://github.com/lechenyu/llvm-project/blob/main/compiler-rt/lib/tsan/rtl/tsan_defs.h.
  12. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009. Google Scholar
  13. Jack B Dennis, Guang R Gao, and Vivek Sarkar. Determinacy and repeatability of parallel program schemata. In 2012 Data-Flow Execution Models for Extreme Scale Computing, pages 1-9. IEEE, 2012. Google Scholar
  14. Alejandro Duran, Xavier Teruel, Roger Ferrer, Xavier Martorell, and Eduard Ayguade. Barcelona openmp tasks suite: A set of benchmarks targeting the exploitation of task parallelism in openmp. In Proceedings of the 2009 International Conference on Parallel Processing, ICPP '09, pages 124-131, USA, 2009. IEEE Computer Society. URL: https://doi.org/10.1109/ICPP.2009.64.
  15. Mingdong Feng and Charles E. Leiserson. Efficient detection of determinacy races in cilk programs. In Proceedings of the Ninth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '97, pages 1-11, New York, NY, USA, 1997. Association for Computing Machinery. URL: https://doi.org/10.1145/258492.258493.
  16. Cormac Flanagan and Stephen N Freund. Fasttrack: efficient and precise dynamic race detection. ACM Sigplan Notices, 44(6):121-133, 2009. Google Scholar
  17. Standard C++ Foundation. C++11 Standard Library Extensions — Concurrency, May 2021. URL: https://isocpp.org/wiki/faq/cpp11-library-concurrency.
  18. Tobias Grosser, J. Ramanujam, Louis-Noel Pouchet, P. Sadayappan, and Sebastian Pop. Optimistic delinearization of parametrically sized arrays. In Proceedings of the 29th ACM on International Conference on Supercomputing, ICS '15, pages 351-360, New York, NY, USA, 2015. Association for Computing Machinery. URL: https://doi.org/10.1145/2751205.2751248.
  19. Yizi Gu and John Mellor-Crummey. Dynamic data race detection for openmp programs. In SC18: International Conference for High Performance Computing, Networking, Storage and Analysis, pages 767-778. IEEE, 2018. Google Scholar
  20. Robert H. Halstead. Multilisp: A language for concurrent symbolic computation. ACM Trans. Program. Lang. Syst., 7(4):501-538, October 1985. URL: https://doi.org/10.1145/4472.4478.
  21. Intel. Intel inspector, May 2021. URL: https://software.intel.com/content/www/us/en/develop/tools/oneapi/components/inspector.html#gs.1wvmbu.
  22. Feiyang Jin, John Jacobson, Samuel D. Pollard, and Vivek Sarkar. Minikokkos: A calculus of portable parallelism. In 2022 IEEE/ACM Sixth International Workshop on Software Correctness for HPC Applications (Correctness), pages 37-44, 2022. URL: https://doi.org/10.1109/Correctness56720.2022.00010.
  23. Richard M. Karp and Raymond E. Miller. Parallel program schemata. Journal of Computer and System Sciences, 3(2):147-195, 1969. URL: https://doi.org/10.1016/S0022-0000(69)80011-5.
  24. Chunhua Liao, Pei-Hung Lin, Joshua Asplund, Markus Schordan, and Ian Karlin. 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, SC '17, New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3126908.3126958.
  25. LLNL. C cpp details oct 2021, October 2021. URL: https://github.com/LLNL/dataracebench/wiki/Tool-Evaluation-Dashboard.
  26. 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. Association for Computing Machinery. URL: https://doi.org/10.1145/125826.125861.
  27. Mozilla Developer Network. Javascript reference - Promise, July 2021. URL: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Promise.
  28. Oracle. Java® Platform, Standard Edition and Java Development Kit Version 17 API Specification - CompletableFuture, October 2021. URL: https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/concurrent/CompletableFuture.html.
  29. Joachim Protze, Martin Schulz, Dong H Ahn, and Matthias S Müller. Thread-local concurrency: a technique to handle data race detection at programming model abstraction. In Proceedings of the 27th International Symposium on High-Performance Parallel and Distributed Computing, pages 144-155, 2018. Google Scholar
  30. Raghavan Raman, Jisheng Zhao, Vivek Sarkar, Martin Vechev, and Eran Yahav. Efficient data race detection for async-finish parallelism. Formal Methods in System Design, 41(3):321-347, December 2012. URL: https://doi.org/10.1007/s10703-012-0143-7.
  31. Raghavan Raman, Jisheng Zhao, Vivek Sarkar, Martin Vechev, and Eran Yahav. Scalable and precise dynamic datarace detection for structured parallelism. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '12, pages 531-542, New York, NY, USA, 2012. Association for Computing Machinery. URL: https://doi.org/10.1145/2254064.2254127.
  32. Tao B. Schardl, William S. Moses, and Charles E. Leiserson. Tapir: Embedding recursive fork-join parallelism into llvm’s intermediate representation. ACM Trans. Parallel Comput., 6(4), December 2019. URL: https://doi.org/10.1145/3365655.
  33. Konstantin Serebryany and Timur Iskhodzhanov. Threadsanitizer: Data race detection in practice. In Proceedings of the workshop on binary instrumentation and applications, pages 62-71, 2009. Google Scholar
  34. Jun Shirako and Vivek Sarkar. Integrating Data Layout Transformations with the Polyhedral Model. In Proc. of IMPACT 2019, 2019. Google Scholar
  35. Rishi Surendran and Vivek Sarkar. Dynamic determinacy race detection for task parallelism with futures. In Yliès Falcone and César Sánchez, editors, Runtime Verification, pages 368-385, Cham, 2016. Springer International Publishing. Google Scholar
  36. Bradley Swain, Yanze Li, Peiming Liu, Ignacio Laguna, Giorgis Georgakoudis, and Jeff Huang. Ompracer: A scalable and precise static race detector for openmp programs. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1-14. IEEE, 2020. Google Scholar
  37. Robert Utterback, Kunal Agrawal, Jeremy Fineman, and I-Ting Angelina Lee. Efficient race detection with futures. In Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming, PPoPP '19, pages 340-354, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3293883.3295732.
  38. Robert Utterback, Kunal Agrawal, Jeremy T. Fineman, and I-Ting Angelina Lee. 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 '16, pages 83-94, New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2935764.2935801.
  39. Sven Verdoolaege. isl: An integer set library for the polyhedral model. In Mathematical Software – ICMS 2010, Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2010. Google Scholar
  40. Sven Verdoolaege and Tobias Grosser. Polyhedral extraction tool. In Second Int. Workshop on Polyhedral Compilation Techniques (IMPACT'12), Paris, France, January 2012. Google Scholar
  41. Philippe Virouleau, Pierrick Brunet, François Broquedis, Nathalie Furmento, Samuel Thibault, Olivier Aumage, and Thierry Gautier. Evaluation of openmp dependent tasks with the kastors benchmark suite. In Luiz DeRose, Bronis R. de Supinski, Stephen L. Olivier, Barbara M. Chapman, and Matthias S. Müller, editors, Using and Improving OpenMP for Devices, Tasks, and More, pages 16-29, Cham, 2014. Springer International Publishing. Google Scholar
  42. Caleb Voss and Vivek Sarkar. An ownership policy and deadlock detector for promises. In Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '21, pages 348-361, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3437801.3441616.
  43. Yifan Xu, Kyle Singer, and I-Ting Angelina Lee. Parallel determinacy race detection for futures. In Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '20, pages 217-231, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3332466.3374536.
  44. Adarsh Yoga, Santosh Nagarakatte, and Aarti Gupta. 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, pages 833-845, 2016. Google Scholar
  45. Lechen Yu, Feiyang Jin, Joachim Protze, and Vivek Sarkar. Leveraging the dynamic program structure tree to detect data races in openmp programs. In 2022 IEEE/ACM Sixth International Workshop on Software Correctness for HPC Applications (Correctness), pages 54-62, 2022. URL: https://doi.org/10.1109/Correctness56720.2022.00012.
  46. Qin Zhao, Derek Bruening, and Saman Amarasinghe. Efficient memory shadowing for 64-bit architectures. In Proceedings of the 2010 international symposium on Memory management, pages 93-102, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact