TY - GEN
T1 - Parallel data race detection for task parallel programs with locks
AU - Yoga, Adarsh
AU - Nagarakatte, Santosh
AU - Gupta, Aarti
PY - 2016/11/1
Y1 - 2016/11/1
N2 - 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 multithreaded programs, task parallel programs can also exhibit data races. Unfortunately, prior data race detectors for task parallel programs either run the program serially or do not handle locks, and/or detect races only in the schedule observed by the analysis. This paper proposes PTRacer, a parallel on-The-fly data race detector for task parallel programs that use locks. PTRacer detects data races not only in the observed schedule but also those that can happen in other schedules (which are permutations of the memory operations in the observed schedule) for a given input. It accomplishes the above goal by leveraging the dynamic execution graph of a task parallel execution to determine whether two accesses can happen in parallel and by maintaining constant amount of access history metadata with each distinct set of locks held for each shared memory location. To detect data races (beyond the observed schedule) in programs with branches sensitive to scheduling decisions, we propose static compiler instrumentation that records memory accesses that will be executed in the other path with simple branches. PTRacer has performance overheads similar to the state-of-Theart race detector for task parallel programs, SPD3, while detecting more races in programs with locks.
AB - 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 multithreaded programs, task parallel programs can also exhibit data races. Unfortunately, prior data race detectors for task parallel programs either run the program serially or do not handle locks, and/or detect races only in the schedule observed by the analysis. This paper proposes PTRacer, a parallel on-The-fly data race detector for task parallel programs that use locks. PTRacer detects data races not only in the observed schedule but also those that can happen in other schedules (which are permutations of the memory operations in the observed schedule) for a given input. It accomplishes the above goal by leveraging the dynamic execution graph of a task parallel execution to determine whether two accesses can happen in parallel and by maintaining constant amount of access history metadata with each distinct set of locks held for each shared memory location. To detect data races (beyond the observed schedule) in programs with branches sensitive to scheduling decisions, we propose static compiler instrumentation that records memory accesses that will be executed in the other path with simple branches. PTRacer has performance overheads similar to the state-of-Theart race detector for task parallel programs, SPD3, while detecting more races in programs with locks.
KW - Data Races
KW - Fork Join Programs
KW - Intel TBB
UR - http://www.scopus.com/inward/record.url?scp=84997206961&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84997206961&partnerID=8YFLogxK
U2 - 10.1145/2950290.2950329
DO - 10.1145/2950290.2950329
M3 - Conference contribution
AN - SCOPUS:84997206961
T3 - Proceedings of the ACM SIGSOFT Symposium on the Foundations of Software Engineering
SP - 833
EP - 845
BT - FSE 2016 - Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering
A2 - Su, Zhendong
A2 - Zimmermann, Thomas
A2 - Cleland-Huang, Jane
PB - Association for Computing Machinery
T2 - 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE 2016
Y2 - 13 November 2016 through 18 November 2016
ER -