Detecting and eliminating potential violation of sequential consistency for concurrent C/C++ programs

Yuelu Duan, Xiaobing Feng, Lei Wang, Chao Zhang, Pen Chung Yew

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

15 Scopus citations

Abstract

When a concurrent shared-memory program written with a sequential consistency (SC) model is run on a machine implemented with a relaxed consistency (RC) model, it could cause SC violations that are very hard to debug. To avoid such violations, programmers need to provide explicit synchronizations or insert fence instructions. In this paper, we propose a scheme to detect and eliminate potential SC violations by combining Shasha/Snir's conflict graph and delay set theory with existing data race detection techniques. For each execution, we generate a race graph, which contains the improperly synchronized conflict accesses, called race accesses, and race cycles formed with those accesses. As a race cycle would probably lead to a non-sequentialconsistent execution, we call it a potential violation of sequential consistency (PVSC) bug. We then compute the race delays of race cycles, and suggest programmers to insert fences into source code to eliminate PVSC bugs. We further convert a race graph into a PC race graph, and improves cycle detection and race delay computation to O(n2), where n is the number of race access instructions. We evaluate our approach with the SPLASH-2 benchmarks, two large real-world applications (MySQL and Apache), and several multi-threaded Cilk programs. The results show that (1) the proposed approach could effectively detect PVSC bugs in real-world applications with good scalability; (2) it retains most of the performance of the concurrent program after inserting required fence instructions, with 6.3% performance loss on average; and (3) the additional cost of our approach over traditional race detection techniques is quite low, with 3.3% on average.

Original languageEnglish (US)
Title of host publicationProceedings of the 2009 CGO - 7th International Symposium on Code Generation and Optimization
Pages25-34
Number of pages10
DOIs
StatePublished - Jul 21 2009
Event7th International Symposium on Code Generation and Optimization, CGO 2009 - Seattle, WA, United States
Duration: Apr 22 2009Apr 25 2009

Publication series

NameProceedings of the 2009 CGO - 7th International Symposium on Code Generation and Optimization

Other

Other7th International Symposium on Code Generation and Optimization, CGO 2009
CountryUnited States
CitySeattle, WA
Period4/22/094/25/09

Keywords

  • Data race detection
  • Delay set
  • Fence
  • Relaxed memory model
  • Sequential consistency

Fingerprint Dive into the research topics of 'Detecting and eliminating potential violation of sequential consistency for concurrent C/C++ programs'. Together they form a unique fingerprint.

Cite this