Scalable Data Race Detection for Lock-Intensive Programs with Pending Period Representation

作者：Liao, Xiaofei; Lin, Minhao; Zheng, Long^*; Jin, Hai; Shao, Zhiyuan

来源：IEEE Transactions on Parallel and Distributed Systems, 2018, 29(11): 2599-2612.

DOI：10.1109/TPDS.2018.2836899

• Data race
• scalability
• efficiency
• happens-before relation
• global clock
• sampling

Most of dynamic data race detection essentially relies on the underlying happens-before orders to yield the precise reports. They are notoriously prone to a prohibitively basic overhead. Although there exist a wealth of research advances that succeed in significantly reducing the analysis overhead on memory accesses, there remains an open problem in handling a great deal of fundamentally unscalable synchronization overhead, which can be particularly serious for the large, lock-intensive programs with a long running time and a large number of threads. In this paper, we revisit the synchronization problem of off-the-shelf race detection with a comprehensive study. The key insight of this work is that a full collection of partial orders for synchronization operations in prior work is not necessarily tracked and analyzed from a new perspective of "global clock" representation. We therefore develop this insight into a novel pending-period based approach, aiming at reducing the overhead of monitoring and analysis on unnecessary synchronization operations. Further, we also enable a significant improvement for enhancing the efficiency of existing sampling techniques, in which synchronization operations are often conservatively identified. Our experimental results on a wide variety of programs show that our approach outperforms state-of-the-art by 5.85x (versus FastTrack), 3.51x (versus ThreadSanitizer) and 1.34x (versus IFRit) program execution slowdown improvement on average, which can be more significant as the number of threads is increasing. Particularly for the lock-intensive programs (e.g., barnes), our approach can be 26.04x faster than FastTrack. Further, our pending period extended sampling is more efficient than Pacer (with up to 31.28 percent improvement in the case of 10 percent sampling rate).

• 出版日期2018-11
• 单位华中科技大学