Redundant Synchronization Event Removal for Data Race Detection

Title:  Redundant Synchronization Event Removal for Data Race Detection
Speaker:  Dr.W.K.Chan (City University of Hong Kong)
Time:  3:00pm, December 20th (Thuesday), 2011.
Venue: Lecture Room, Level 3, Building No. 5, State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences

Abstract: Many happens-before based techniques for multithreaded programs implement vector clocks to track incrementally the causal relations among the synchronization operations acting on threads and locks. In such dynamic detectors, every such operation results in a vector-based assignment to a vector clock, even though the assigned value is the same as the value of the vector clock right before the assignment. The cost of such vector-based operations however grows with the number of threads and the amount of such operations. It is unclear to what extent redundant assignments can be removed. We observe that whether two consecutive assignments to the same vector clock of a thread result in the same content critically depends on the operations on the locks occurred in between these assignments.

In this talk, we will discuss our finding on exploring the said insight to quantify a sufficient condition that can remove such operations without affecting the precision of such tracking. We will also discuss the empirical finding using the PARSEC benchmarking suite. The data shows that, on average, our approach removes 58.0% of all such operations commonly incurred by existing detectors such as FastTrack, and runs 16.2% faster than the latter in tracking the causal relations among these operations.

Bibliography:
W.K.Chan is an assistant professor at Department of Computer Science, City University of Hong Kong. He worked in the industry for many years before returning to The University of Hong Kong to complete his PhD degree. His latest research interests are to address the software engineering and green computing issues in large-scale software. Dr. Chan is currently on the editorial board of Journal of Systems and Software. He has published his research results in more than 80 papers in international journals and conferences including TOSEM, TSE, ICSE, and FSE.