Vulcan: Hardware support for detecting sequential consistency violations dynamically

Abdullah Muzahid, Shanxiang Qi, Josep Torrellas

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

Abstract

Past work has focused on detecting data races as proxies for Sequential Consistency (SC) violations. However, most data races do not violate SC. In addition, lock-free data structures and synchronization libraries sometimes explicitly employ data races but rely on SC semantics for correctness. Consequently, to uncover SC violations, we need to develop a more precise technique. This paper presents Vulcan, the first hardware scheme to precisely detect SC violations at runtime, in programs running on a relaxed-consistency machine. The scheme leverages cache coherence protocol transactions to dynamically detect cycles in memory access orders across threads. When one such cycle is about to occur, an exception is triggered. For the conditions considered in this paper and with enough hardware, Vulcan suffers neither false positives nor false negatives. In addition, Vulcan induces negligible execution overhead, requires no help from the software, and only takes as input the program executable. Experimental results show that Vulcan detects three new SC violation bugs in the Pthread and Crypt libraries, and in the fmm code from SPLASH-2. Moreover, Vulcan's negligible execution overhead makes it suitable for on-the-fly use.

Original languageEnglish (US)
Title of host publicationProceedings - 2012 IEEE/ACM 45th International Symposium on Microarchitecture, MICRO 2012
Pages363-375
Number of pages13
DOIs
StatePublished - Dec 1 2012
Event2012 IEEE/ACM 45th International Symposium on Microarchitecture, MICRO 2012 - Vancouver, BC, Canada
Duration: Dec 1 2012Dec 5 2012

Publication series

NameProceedings - 2012 IEEE/ACM 45th International Symposium on Microarchitecture, MICRO 2012

Other

Other2012 IEEE/ACM 45th International Symposium on Microarchitecture, MICRO 2012
CountryCanada
CityVancouver, BC
Period12/1/1212/5/12

    Fingerprint

Keywords

  • Bug
  • Memory model
  • Parallel program
  • Sequential consistency violation

ASJC Scopus subject areas

  • Hardware and Architecture

Cite this

Muzahid, A., Qi, S., & Torrellas, J. (2012). Vulcan: Hardware support for detecting sequential consistency violations dynamically. In Proceedings - 2012 IEEE/ACM 45th International Symposium on Microarchitecture, MICRO 2012 (pp. 363-375). [6493634] (Proceedings - 2012 IEEE/ACM 45th International Symposium on Microarchitecture, MICRO 2012). https://doi.org/10.1109/MICRO.2012.41