Parallel data race detection for task parallel programs with locks

Adarsh Yoga, Santosh Nagarakatte, Aarti Gupta

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

17 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationFSE 2016 - Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering
EditorsZhendong Su, Thomas Zimmermann, Jane Cleland-Huang
PublisherAssociation for Computing Machinery
Pages833-845
Number of pages13
ISBN (Electronic)9781450342186
DOIs
StatePublished - Nov 1 2016
Externally publishedYes
Event24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE 2016 - Seattle, United States
Duration: Nov 13 2016Nov 18 2016

Publication series

NameProceedings of the ACM SIGSOFT Symposium on the Foundations of Software Engineering
Volume13-18-November-2016

Other

Other24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE 2016
Country/TerritoryUnited States
CitySeattle
Period11/13/1611/18/16

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Data Races
  • Fork Join Programs
  • Intel TBB

Fingerprint

Dive into the research topics of 'Parallel data race detection for task parallel programs with locks'. Together they form a unique fingerprint.

Cite this