research-article

Transitive joins: a sound and efficient online deadlock-avoidance policy

Authors:

Tiago Cogumbreiro,

Vivek SarkarAuthors Info & Claims

PPoPP '19: Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming

Pages 378 - 390

https://doi.org/10.1145/3293883.3295724

Published: 16 February 2019 Publication History

Abstract

We introduce a new online deadlock-avoidance policy, Transitive Joins (TJ), that targets programs with dynamic task parallelism and arbitrary join operations. In this model, a computation task can asynchronously spawn new tasks and selectively join (block) on any task for which it has a handle. We prove that TJ soundly guarantees the absence of deadlock cycles among the blocking join operations. We present an algorithm for dynamically verifying TJ and show that TJ results in fewer false positives than the state-of-the-art policy, Known Joins (KJ). We evaluate an implementation of our verifier in comparison to prior work. The evaluation results show that instrumenting a program with a TJ verifier incurs geometric mean overheads of only 1.06× in execution time and 1.09× in memory usage, which is better overall than existing KJ verifiers. TJ is a practical online deadlock-avoidance policy that is applicable to a wide range of parallel programming models.

References

[1]

Michael A. Bender and Martín Farach-Colton. 2004. The Level Ancestor Problem Simplified. Theor. Comput. Sci. 321, 1 (2004), 5--12.

Digital Library

[2]

Robert D. Blumofe and Charles E. Leiserson. 1999. Scheduling Multithreaded Computations by Work Stealing. J. ACM 46, 5 (1999), 720--748.

Digital Library

[3]

Gérard Boudol. 2009. A Deadlock-Free Semantics for Shared Memory Concurrency. In Proc. 6th Int'l. Coll. on Theoretical Aspects of Computing (ICTAC '09). Springer-Verlag, Berlin, Germany, 140--154.

Digital Library

[4]

Chandrasekhar Boyapati, Robert Lee, and Martin Rinard. 2002. Ownership Types for Safe Programming: Preventing Data Races and Deadlocks. In Proc. 17th ACM SIGPLAN Conf. on Object-oriented Programming, Systems, Languages, and Applications (OOPSLA '02). ACM, New York, NY, 211--230.

Digital Library

[5]

Jeremy D. Buhler, Kunal Agrawal, Peng Li, and Roger D. Chamberlain. 2012. Efficient Deadlock Avoidance for Streaming Computation with Filtering. In Proc. 17th ACM SIGPLAN Symp. Principles and Practice of Parallel Programming (PPoPP '12). ACM, New York, NY, 235--246.

Digital Library

[6]

Vincent Cavé, Jisheng Zhao, Jun Shirako, and Vivek Sarkar. 2011. Habanero-Java: The New Adventures of Old X10. In Proc. 9th Int'l. Conf. on Principles and Practice of Programming in Java (PPPJ '11). ACM, New York, NY, 51--61.

Digital Library

[7]

Philippe Charles, Christian Grothoff, Vijay Saraswat, Christopher Donawa, Allan Kielstra, Kemal Ebcioglu, Christoph von Praun, and Vivek Sarkar. 2005. X10: An Object-oriented Approach to Non-uniform Cluster Computing. In Proc. 20th ACM SIGPLAN Conf. on Object-oriented Programming, Systems, Languages, and Applications (OOPSLA '05). ACM, New York, NY, 519--538.

Digital Library

[8]

E. G. Coffman, M. Elphick, and A. Shoshani. 1971. System Deadlocks. ACM Comput. Surv. 3, 2 (1971), 67--78.

Digital Library

[9]

Tiago Cogumbreiro, Raymond Hu, Francisco Martins, and Nobuko Yoshida. 2015. Dynamic Deadlock Verification for General Barrier Synchronisation. In Proc. 20th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPoPP '15). ACM, New York, NY, 150--160.

Digital Library

[10]

Tiago Cogumbreiro, Rishi Surendran, Francisco Martins, Vivek Sarkar, Vasco T. Vasconcelos, and Max Grossman. 2017. Deadlock Avoidance in Parallel Programs with Futures: Why Parallel Tasks Should Not Wait for Strangers. Proc. ACM Program. Lang. OOPSLA, Article 103 (2017), 26 pages.

Digital Library

[11]

Alejandro Duran, Xavier Teruel, Roger Ferrer, Xavier Martorell, and Eduard Ayguade. 2009. Barcelona OpenMP Tasks Suite: A Set of Benchmarks Targeting the Exploitation of Task Parallelism in OpenMP. In Proc. 2009 Int'l. Conf. on Parallel Processing (ICPP '09). IEEE Computer Society, Washington, DC, 124--131.

Digital Library

[12]

Matteo Frigo, Charles E. Leiserson, and Keith H. Randall. 1998. The Implementation of the Cilk-5 Multithreaded Language. In Proc. ACM SIGPLAN 1998 Conf. on Programming Language Design and Implementation (PLDI '98). ACM, New York, NY, 212--223.

Digital Library

[13]

Andy Georges, Dries Buytaert, and Lieven Eeckhout. 2007. Statistically Rigorous Java Performance Evaluation. In Proc. 22nd ACM SIGPLAN Conf. on Object-oriented Programming, Systems, Languages, and Applications (OOPSLA '07). ACM, New York, NY, 57--76.

Digital Library

[14]

Prodromos Gerakios, Nikolaos Papaspyrou, Konstantinos Sagonas, and Panagiotis Vekris. 2011. Dynamic Deadlock Avoidance in Systems Code Using Statically Inferred Effects. In Proc. 6th Workshop on Programming Languages and Operating Systems (PLOS '11). ACM, New York, NY, Article 5, 5 pages.

Digital Library

[15]

B. Goetz, T. Peierls, J. Bloch, J. Bowbeer, D. Lea, and D. Holmes. 2006. Java Concurrency in Practice. Pearson Education, London, England.

Digital Library

[16]

Yi Guo, Rajkishore Barik, Raghavan Raman, and Vivek Sarkar. 2009. Work-first and Help-first Scheduling Policies for Async-finish Task Parallelism. In Proc. 2009 IEEE Int'l. Symp. on Parallel & Distributed Processing (IPDPS '09). IEEE Computer Society, Washington, DC, 1--12.

Digital Library

[17]

Robert H. Halstead, Jr. 1985. MULTILISP: A Language for Concurrent Symbolic Computation. ACM Trans. Program. Lang. Syst. 7, 4 (1985), 501--538.

Digital Library

[18]

Dov Harel and Robert Endre Tarjan. 1984. Fast Algorithms for Finding Nearest Common Ancestors. SIAM J. Comput. 13, 2 (1984), 338--355.

Digital Library

[19]

Tobias Hilbrich, Bronis R. de Supinski, Martin Schulz, and Matthias S. Müller. 2009. A Graph Based Approach for MPI Deadlock Detection. In Proc. 23rd Int'l. Conf. on Supercomputing (ICS '09). ACM, New York, NY, 296--305.

Digital Library

[20]

Tobias Hilbrich, Joachim Protze, Martin Schulz, Bronis R. de Supinski, and Matthias S. Müller. 2012. MPI Runtime Error Detection with MUST: Advances in Deadlock Detection. In Proc. Int'l. Conf. on High Performance Computing, Networking, Storage and Analysis (SC '12). IEEE Computer Society, Los Alamitos, CA, Article 30, 11 pages.

Digital Library

[21]

Shams Imam and Vivek Sarkar. 2014. Habanero-Java Library: A Java 8 Framework for Multicore Programming. In Proc. 2014 Int'l. Conf. on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools (PPPJ '14). ACM, New York, NY, 75--86.

[22]

S. Sreekaanth Isloor and T. Anthony Marsland. 1980. The Deadlock Problem: An Overview. Computer 13, 9 (1980), 58--78.

Digital Library

[23]

ISO. 2011. ISO/IEC 14882:2011: Programming languages --- C++. International Organization for Standardization, Geneva, Switzerland.

[24]

Bettina Krammer, Tobias Hilbrich, Valentin Himmler, Blasius Czink, Kiril Dichev, and Matthias S. Müller. 2008. MPI Correctness Checking with Marmot. In Tools for High Performance Computing. Springer, Berlin, Germany, 61--78.

[25]

Bettina Krammer, Matthias S. Müller, and Michael M. Resch. 2004. MPI Application Development Using the Analysis Tool MARMOT. In Proc. Int'l. Conf. on Computational Science (ICCS '04). Springer-Verlag, Berlin, Germany, 464--471.

[26]

Glenn Luecke, Hua Chen, James Coyle, Jim Hoekstra, Marina Kraeva, and Yan Zou. 2003. MPI-CHECK: a tool for checking Fortran 90 MPI programs. Concurrency and Computation: Practice and Experience 15, 2 (2003), 93--100.

[27]

Mayur Naik, Chang-Seo Park, Koushik Sen, and David Gay. 2009. Effective Static Deadlock Detection. In Proc. 31st Int'l. Conf. on Software Engineering (ICSE '09). IEEE Computer Society, Washington, DC, 386--396.

Digital Library

[28]

Armand Navabi, Xiangyu Zhang, and Suresh Jagannathan. 2008. Quasistatic Scheduling for Safe Futures. In Proc. 13th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPoPP '08). ACM, New York, NY, 23--32.

Digital Library

[29]

Spiridon A. Reveliotis, Mark A. Lawley, and Placid M. Ferreira. 1997. Polynomial-complexity deadlock avoidance policies for sequential resource allocation systems. IEEE Trans. Automat. Control 42, 10 (1997), 1344--1357.

[30]

Jun Shirako, Vincent Cavé, Jisheng Zhao, and Vivek Sarkar. 2013. Finish Accumulators: An Efficient Reduction Construct for Dynamic Task Parallelism. In Languages and Compilers for Parallel Computing. Springer-Verlag, Berlin, Germany, 264--265.

[31]

L. A. Smith, J. M. Bull, and J. Obdrzálek. 2001. A Parallel Java Grande Benchmark Suite. In Proc. 2001 ACM/IEEE Conf. on Supercomputing (SC '01). ACM, New York, NY, Article 8, 10 pages.

Digital Library

[32]

Anh Vo, Ganesh Gopalakrishnan, Robert M. Kirby, Bronis R. de Supinski, Martin Schulz, and Greg Bronevetsky. 2011. Large Scale Verification of MPI Programs Using Lamport Clocks with Lazy Update. In Proc. 2011 Int't. Conf. on Parallel Architectures and Compilation Techniques (PACT '11). IEEE Computer Society, Washington, DC, 330--339.

Digital Library

[33]

Adam Welc, Suresh Jagannathan, and Antony Hosking. 2005. Safe Futures for Java. In Proc. 20th Annual ACM SIGPLAN Conf. on Object-oriented Programming, Systems, Languages, and Applications (OOPSLA '05). ACM, New York, NY, 439--453.

Digital Library

[34]

Amy Williams, William Thies, and Michael D. Ernst. 2005. Static Deadlock Detection for Java Libraries. In Proc. 19th European Conf. on Object-Oriented Programming (ECOOP '05). Springer-Verlag, Berlin, Germany, 602--629.

Digital Library

Cited By

Muller SLee IChabbi MSteuwer M(2024)Language-Agnostic Static Deadlock Detection for FuturesProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3627535.3638487(68-79)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3627535.3638487
Jin FTao AYu LSarkar V(2024)Visualizing Correctness Issues in OpenMP ProgramsAdvancing OpenMP for Future Accelerators10.1007/978-3-031-72567-8_11(161-175)Online publication date: 16-Sep-2024
https://doi.org/10.1007/978-3-031-72567-8_11
Muller S(2022)Static prediction of parallel computation graphsProceedings of the ACM on Programming Languages10.1145/34987086:POPL(1-31)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498708
Show More Cited By

Index Terms

Transitive joins: a sound and efficient online deadlock-avoidance policy
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Parallel programming languages
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Deadlocks

Recommendations

Deadlock avoidance in parallel programs with futures: why parallel tasks should not wait for strangers

Futures are an elegant approach to expressing parallelism in functional programs. However, combining futures with imperative programming (as in C++ or in Java) can lead to pernicious bugs in the form of data races and deadlocks, as a consequence of ...
Automatic repair for multi-threaded programs with Deadlock/Livelock using maximum satisfiability
ISSTA 2014: Proceedings of the 2014 International Symposium on Software Testing and Analysis

Deadlock-freedom is a major challenge in developing multi-threaded programs, as a deadlock cannot be resolved until one restarts the program (mostly by using manual intervention). To avoid the risk of blocking, a program may use the trylock operations ...
Groups that are transitive on all partitions of a given shape

Let $$[n] = K_1\dot{\cup }K_2 \dot{\cup }\cdots \dot{\cup }K_r$$[n]=K1 K2 Kr be a partition of $$[n] = \{1,2,\ldots ,n\}$$[n]={1,2, ,n} and set $$\ell _i = |K_i|$$ℓi=|Ki| for $$1\le i\le r$$1≤i≤r. Then the tuple $$P = \{K_1,K_2,\ldots ,K_r\}$$P={K1,K2, ,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PPoPP '19: Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming

February 2019

472 pages

ISBN:9781450362252

DOI:10.1145/3293883

General Chair:
Jeff Hollingsworth
University of Maryland
,
Program Chair:
Idit Keidar
Technion, Israel

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication Notes

Badge change: Article originally badged under Version 1.0 guidelines https://www.acm.org/publications/policies/artifact-review-badging

Publication History

Published: 16 February 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Conference

PPoPP '19

Sponsor:

PPoPP '19: 24th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

February 16 - 20, 2019

District of Columbia, Washington

Acceptance Rates

PPoPP '19 Paper Acceptance Rate 29 of 152 submissions, 19%;

Overall Acceptance Rate 230 of 1,014 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
266
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)2

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Muller SLee IChabbi MSteuwer M(2024)Language-Agnostic Static Deadlock Detection for FuturesProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3627535.3638487(68-79)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3627535.3638487
Jin FTao AYu LSarkar V(2024)Visualizing Correctness Issues in OpenMP ProgramsAdvancing OpenMP for Future Accelerators10.1007/978-3-031-72567-8_11(161-175)Online publication date: 16-Sep-2024
https://doi.org/10.1007/978-3-031-72567-8_11
Muller S(2022)Static prediction of parallel computation graphsProceedings of the ACM on Programming Languages10.1145/34987086:POPL(1-31)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498708
Voss CSarkar VLee JPetrank E(2021)An ownership policy and deadlock detector for promisesProceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3437801.3441616(348-361)Online publication date: 17-Feb-2021
https://dl.acm.org/doi/10.1145/3437801.3441616
Wang YLi MDai HKent KYe KXu C(2021)Deadlock Avoidance Algorithms for Recursion-Tree Modeled Requests in Parallel ExecutionsIEEE Transactions on Computers10.1109/TC.2021.3122843(1-1)Online publication date: 2021
https://doi.org/10.1109/TC.2021.3122843
Yu LProtze JHernandez OSarkar V(2021)ARBALEST: Dynamic Detection of Data Mapping Issues in Heterogeneous OpenMP Applications2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS49936.2021.00055(464-474)Online publication date: May-2021
https://doi.org/10.1109/IPDPS49936.2021.00055
Muller SSinger KGoldstein NAcar UAgrawal KLee IDonaldson ATorlak E(2020)Responsive parallelism with futures and stateProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3385412.3386013(577-591)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3385412.3386013
Xu YSinger KLee IGupta RShen X(2020)Parallel determinacy race detection for futuresProceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3332466.3374536(217-231)Online publication date: 19-Feb-2020
https://dl.acm.org/doi/10.1145/3332466.3374536

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents