TY - GEN
T1 - Detecting and eliminating potential violation of sequential consistency for concurrent C/C++ programs
AU - Duan, Yuelu
AU - Feng, Xiaobing
AU - Wang, Lei
AU - Zhang, Chao
AU - Yew, Pen Chung
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
KW - Data race detection
KW - Delay set
KW - Fence
KW - Relaxed memory model
KW - Sequential consistency
UR - http://www.scopus.com/inward/record.url?scp=67650518203&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=67650518203&partnerID=8YFLogxK
U2 - 10.1109/CGO.2009.29
DO - 10.1109/CGO.2009.29
M3 - Conference contribution
AN - SCOPUS:67650518203
SN - 9780769535760
T3 - Proceedings of the 2009 CGO - 7th International Symposium on Code Generation and Optimization
SP - 25
EP - 34
BT - Proceedings of the 2009 CGO - 7th International Symposium on Code Generation and Optimization
T2 - 7th International Symposium on Code Generation and Optimization, CGO 2009
Y2 - 22 April 2009 through 25 April 2009
ER -