Atomicity violation checker for task parallel programs

Adarsh Yoga, Santosh Nagarakatte

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 14th International Symposium on Code Generation and Optimization, CGO 2016
PublisherAssociation for Computing Machinery, Inc
Pages239-249
Number of pages11
ISBN (Electronic)9781450337786
DOIs
StatePublished - Feb 29 2016
Event14th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2016 - Barcelona, Spain
Duration: Mar 12 2016Mar 18 2016

Publication series

NameProceedings of the 14th International Symposium on Code Generation and Optimization, CGO 2016

Other

Other14th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2016
CountrySpain
CityBarcelona
Period3/12/163/18/16

All Science Journal Classification (ASJC) codes

  • Software
  • Applied Mathematics
  • Computational Theory and Mathematics

Keywords

  • Atomicity checking
  • Concurrency
  • Debugging
  • Fork join programs
  • Intel TBB

Fingerprint Dive into the research topics of 'Atomicity violation checker for task parallel programs'. Together they form a unique fingerprint.

  • Cite this

    Yoga, A., & Nagarakatte, S. (2016). Atomicity violation checker for task parallel programs. In Proceedings of the 14th International Symposium on Code Generation and Optimization, CGO 2016 (pp. 239-249). (Proceedings of the 14th International Symposium on Code Generation and Optimization, CGO 2016). Association for Computing Machinery, Inc. https://doi.org/10.1145/2854038.2854063