TY - GEN
T1 - Atomicity violation checker for task parallel programs
AU - Yoga, Adarsh
AU - Nagarakatte, Santosh
PY - 2016/2/29
Y1 - 2016/2/29
N2 - 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.
AB - 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.
KW - Atomicity checking
KW - Concurrency
KW - Debugging
KW - Fork join programs
KW - Intel TBB
UR - http://www.scopus.com/inward/record.url?scp=84968847486&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84968847486&partnerID=8YFLogxK
U2 - 10.1145/2854038.2854063
DO - 10.1145/2854038.2854063
M3 - Conference contribution
AN - SCOPUS:84968847486
T3 - Proceedings of the 14th International Symposium on Code Generation and Optimization, CGO 2016
SP - 239
EP - 249
BT - Proceedings of the 14th International Symposium on Code Generation and Optimization, CGO 2016
PB - Association for Computing Machinery, Inc
T2 - 14th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2016
Y2 - 12 March 2016 through 18 March 2016
ER -