More Web Proxy on the site http://driver.im/

research-article

Atomicity violation checker for task parallel programs

Authors:

Santosh NagarakatteAuthors Info & Claims

CGO '16: Proceedings of the 2016 International Symposium on Code Generation and Optimization

Pages 239 - 249

https://doi.org/10.1145/2854038.2854063

Published: 29 February 2016 Publication History

Abstract

Task based programming models (e.g., Cilk, Intel TBB, X10, Java Fork-Join tasks) simplify multicore programming in contrast to programming with threads. In a task based model, the programmer specifies parallel tasks and the runtime maps these tasks to hardware threads. The runtime automatically balances the load using work-stealing and provides performance portability. However, interference between parallel tasks can result in concurrency errors. This paper proposes a dynamic analysis technique to detect atomicity violations in task parallel programs, which could occur in different schedules for a given input without performing interleaving exploration. Our technique leverages the series-parallel dynamic execution structure of a task parallel program to identify parallel accesses. It also maintains access history metadata with each shared memory location to identify parallel accesses that can cause atomicity violations in different schedules. To streamline metadata management, the access history metadata is split into global metadata that is shared by all tasks and local metadata that is specific to each task. The global metadata tracks a fixed number of access histories for each shared memory location that capture all possible access patterns necessary for an atomicity violation. Our prototype tool for Intel Threading Building Blocks (TBB) detects atomicity violations that can potentially occur in different interleavings for a given input with performance overheads similar to Velodrome atomicity checker for thread based programs.

References

[1]

P. A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in Database Systems. Addison-Wesley, 1987.

Digital Library

[2]

C. Bienia, S. Kumar, J. P. Singh, and K. Li. The PARSEC Benchmark Suite: Characterization and Architectural Implications. In Proceedings of the 17th International Conference on Parallel Architectures and Compilation Techniques, pages 72–81, 2008.

Digital Library

[3]

S. Biswas, J. Huang, A. Sengupta, and M. D. Bond. DoubleChecker: Efficient Sound and Precise Atomicity Checking. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 28–39, 2014.

Digital Library

[4]

R. L. Bocchino, Jr., V. S. Adve, D. Dig, S. V. Adve, S. Heumann, R. Komuravelli, J. Overbey, P. Simmons, H. Sung, and M. Vakilian. A Type and Effect System for Deterministic Parallel Java. In Proceedings of the 24th ACM SIGPLAN Conference on Object Oriented Programming Systems Languages and Applications, pages 97–116, 2009.

Digital Library

[5]

S. Burckhardt, P. Kothari, M. Musuvathi, and S. Nagarakatte. A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs. In Proceedings of the 15th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 167–178, 2010.

Digital Library

[6]

V. Cavé, J. Zhao, J. Shirako, and V. 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.

Digital Library

[7]

P. Charles, C. Grothoff, V. Saraswat, C. Donawa, A. Kielstra, K. Ebcioglu, C. von Praun, and V. Sarkar. X10: An Objectoriented Approach to Non-uniform Cluster Computing. In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, pages 519–538, 2005.

Digital Library

[8]

Q. Chen, L. Wang, Z. Yang, and S. D. Stoller. HAVE: Detecting Atomicity Violations via Integrated Dynamic and Static Analysis. In Proceedings of the 12th International Conference on Fundamental Approaches to Software Engineering, pages 425–439, 2009.

Digital Library

[9]

G.-I. Cheng, M. Feng, C. E. Leiserson, K. H. Randall, and A. F. Stark. Detecting Data Races in Cilk Programs That Use Locks. In Proceedings of the 10th ACM Symposium on Parallel Algorithms and Architectures, pages 298–309, 1998.

Digital Library

[10]

M. Feng and C. E. Leiserson. Efficient Detection of Determinacy Races in Cilk Programs. In Proceedings of the 9th ACM Symposium on Parallel Algorithms and Architectures, pages 1–11, 1997.

Digital Library

[11]

C. Flanagan and S. N. Freund. Atomizer: A Dynamic Atomicity Checker for Multithreaded Programs. In Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 256–267, 2004.

Digital Library

[12]

C. Flanagan, S. N. Freund, and J. Yi. Velodrome: A Sound and Complete Dynamic Atomicity Checker for Multithreaded Programs. In Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 293–303, 2008.

Digital Library

[13]

J. S. Foster, T. Terauchi, and A. Aiken. Flow-sensitive Type Qualifiers. In Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation, pages 1–12, 2002.

Digital Library

[14]

M. Frigo, C. E. Leiserson, and K. H. Randall. The Implementation of the Cilk-5 Multithreaded Language. In Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation, pages 212–223, 1998.

Digital Library

[15]

J. Huang, P. O. Meredith, and G. Rosu. Maximal Sound Predictive Race Detection with Control Flow Abstraction. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 337–348, 2014.

Digital Library

[16]

D. Lea. A Java Fork/Join Framework. In Proceedings of the ACM 2000 Conference on Java Grande, pages 36–43, 2000.

Digital Library

[17]

L. Lu, W. Ji, and M. L. Scott. Dynamic Enforcement of Determinism in a Parallel Scripting Language. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 519–529, 2014.

Digital Library

[18]

S. Lu, S. Park, C. Hu, X. Ma, W. Jiang, Z. Li, R. A. Popa, and Y. Zhou. MUVI: Automatically Inferring Multi-variable Access Correlations and Detecting Related Semantic and Concurrency Bugs. In Proceedings of 21st ACM SIGOPS Symposium on Operating Systems Principles, pages 103–116, 2007.

Digital Library

[19]

S. Lu, J. Tucek, F. Qin, and Y. Zhou. AVIO: Detecting Atomicity Violations via Access Interleaving Invariants. In Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 37–48, 2006.

Digital Library

[20]

B. Lucia, J. Devietti, K. Strauss, and L. Ceze. Atom-Aid: Detecting and Surviving Atomicity Violations. In Proceedings of the 35th Annual International Symposium on Computer Architecture, pages 277–288, 2008.

Digital Library

[21]

M. McCool, A. Robison, and J. Reinders. Structured Parallel Programming: Patterns for Efficient Computation. Morgan Kaufmann, 2012.

Digital Library

[22]

J. 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, pages 24–33, 1991.

Digital Library

[23]

M. Musuvathi, S. Qadeer, T. Ball, G. Basler, P. A. Nainar, and I. Neamtiu. Finding and Reproducing Heisenbugs in Concurrent Programs. In Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation, pages 267–280, 2008.

Digital Library

[24]

S. Nagarakatte, S. Burckhardt, M. M. Martin, and M. Musuvathi. Multicore Acceleration of Priority-based Schedulers for Concurrency Bug Detection. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 543–554, 2012.

Digital Library

[25]

S. Park, S. Lu, and Y. Zhou. CTrigger: Exposing Atomicity Violation Bugs from Their Hiding Places. In Proceedings of the 14th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 25–36, 2009.

Digital Library

[26]

R. Raman. Dynamic Data Race Detection for Structured Parallelism. PhD thesis, Rice University, 2012.

[27]

R. Raman, J. Zhao, V. Sarkar, M. Vechev, and E. Yahav. Efficient Data Race Detection for Async-finish Parallelism. In Proceedings of the 1st International Conference on Runtime Verification, pages 368–383, 2010.

Digital Library

[28]

R. Raman, J. Zhao, V. Sarkar, M. Vechev, and E. Yahav. Scalable and Precise Dynamic Datarace Detection for Structured Parallelism. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 531–542, 2012.

Digital Library

[29]

J. Reinders. Intel Threading Building Blocks. O’Reilly & Associates, Inc., 2007.

Digital Library

[30]

A. Sasturkar, R. Agarwal, L. Wang, and S. D. Stoller. Automated Type-based Analysis of Data Races and Atomicity. In Proceedings of the 10th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 83–94, 2005.

Digital Library

[31]

J. Shun, G. E. Blelloch, J. T. Fineman, P. B. Gibbons, A. Kyrola, H. V. Simhadri, and K. Tangwongsan. Brief Announcement: The Problem Based Benchmark Suite. In Proceedings of the 24th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pages 68–70, 2012.

Digital Library

[32]

Y. Smaragdakis, J. Evans, C. Sadowski, J. Yi, and C. Flanagan. Sound Predictive Race Detection in Polynomial Time. In Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 387–400, 2012.

Digital Library

[33]

C. Wang, S. Kundu, M. Ganai, and A. Gupta. Symbolic Predictive Analysis for Concurrent Programs. In Proceedings of Formal Methods, pages 256–272, 2009.

Digital Library

Cited By

Bae CChoi EJun YHa O(2023)Lightweight Method for On-the-fly Detection of Multivariable Atomicity Violations2023 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW)10.1109/ICSTW58534.2023.00039(165-171)Online publication date: Apr-2023
https://doi.org/10.1109/ICSTW58534.2023.00039
Trimananda RAqajari SChuang JDemsky BXu GLu SDevanbu PCohen MZimmermann T(2020)Understanding and automatically detecting conflicting interactions between smart home IoT applicationsProceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3368089.3409682(1215-1227)Online publication date: 8-Nov-2020
https://dl.acm.org/doi/10.1145/3368089.3409682
Boushehrinejadmoradi NYoga ANagarakatte S(2020)On-the-fly Data Race Detection with the Enhanced OpenMP Series-Parallel GraphOpenMP: Portable Multi-Level Parallelism on Modern Systems10.1007/978-3-030-58144-2_10(149-164)Online publication date: 1-Sep-2020
https://doi.org/10.1007/978-3-030-58144-2_10
Show More Cited By

Index Terms

Atomicity violation checker for task parallel programs

Recommendations

Parallel data race detection for task parallel programs with locks
FSE 2016: Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering

Programming with tasks is a promising approach to write performance portable parallel code. In this model, the programmer explicitly specifies tasks and the task parallel runtime employs work stealing to distribute tasks among threads. Similar to ...
Randomized active atomicity violation detection in concurrent programs
SIGSOFT '08/FSE-16: Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of software engineering

Atomicity is an important specification that enables programmers to understand atomic blocks of code in a multi-threaded program as if they are sequential. This significantly simplifies the programmer's job to reason about correctness. Several modern ...
A fast causal profiler for task parallel programs
ESEC/FSE 2017: Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering

This paper proposes TASKPROF, a profiler that identifies parallelism bottlenecks in task parallel programs. It leverages the structure of a task parallel execution to perform fine-grained attribution of work to various parts of the program. TASKPROF’s ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CGO '16: Proceedings of the 2016 International Symposium on Code Generation and Optimization

February 2016

283 pages

ISBN:9781450337786

DOI:10.1145/2854038

General Chair:
Bjoern Franke
University of Edinburgh, UK
,
Program Chairs:
Youfeng Wu
Intel, USA
,
Fabrice Rastello
Inria, France

Copyright © 2016 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

In-Cooperation

IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 February 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CGO '16

Sponsor:

CGO '16: 14th Annual IEEE/ACM International Symposium on Code Generation and Optimization

March 12 - 18, 2016

Barcelona, Spain

Acceptance Rates

CGO '16 Paper Acceptance Rate 25 of 108 submissions, 23%;

Overall Acceptance Rate 312 of 1,061 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
214
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bae CChoi EJun YHa O(2023)Lightweight Method for On-the-fly Detection of Multivariable Atomicity Violations2023 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW)10.1109/ICSTW58534.2023.00039(165-171)Online publication date: Apr-2023
https://doi.org/10.1109/ICSTW58534.2023.00039
Trimananda RAqajari SChuang JDemsky BXu GLu SDevanbu PCohen MZimmermann T(2020)Understanding and automatically detecting conflicting interactions between smart home IoT applicationsProceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3368089.3409682(1215-1227)Online publication date: 8-Nov-2020
https://dl.acm.org/doi/10.1145/3368089.3409682
Boushehrinejadmoradi NYoga ANagarakatte S(2020)On-the-fly Data Race Detection with the Enhanced OpenMP Series-Parallel GraphOpenMP: Portable Multi-Level Parallelism on Modern Systems10.1007/978-3-030-58144-2_10(149-164)Online publication date: 1-Sep-2020
https://doi.org/10.1007/978-3-030-58144-2_10
Yoga ANagarakatte SMcKinley KFisher K(2019)Parallelism-centric what-if and differential analysesProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314621(485-501)Online publication date: 8-Jun-2019
https://dl.acm.org/doi/10.1145/3314221.3314621
Zheng LLiao XJin HHe BXue JLiu HEvripidou SStenström PO'Boyle M(2018)Towards concurrency race debuggingProceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques10.1145/3243176.3243206(1-13)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1145/3243176.3243206

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