research-article

Volition: scalable and precise sequential consistency violation detection

Authors:

Josep Torrellas,

Benjamin Sahelices,

Depei QianAuthors Info & Claims

ASPLOS '13: Proceedings of the eighteenth international conference on Architectural support for programming languages and operating systems

Pages 535 - 548

https://doi.org/10.1145/2451116.2451174

Published: 16 March 2013 Publication History

Abstract

Sequential Consistency (SC) is the most intuitive memory model, and SC Violations (SCVs) produce unintuitive, typically incorrect executions. Most prior SCV detection schemes have used data races as proxies for SCVs, which is highly imprecise. Other schemes that have targeted data-race cycles are either too conservative or are designed only for two-processor cycles and snoopy-based systems.

This paper presents Volition, the first hardware scheme that detects SCVs in a relaxed-consistency machine precisely, in a scalable manner, and for an arbitrary number of processors in the cycle. Volition leverages cache coherence protocol transactions to dynamically detect cycles in memory-access orders across threads. When a cycle is about to occur, an exception is triggered. Volition can be used in both directory- and snoopy-based coherence protocols. Our simulations of Volition in a 64-processor multicore with directory-based coherence running SPLASH-2 and Parsec programs shows that Volition induces negligible traffic and execution overhead. In addition, it can detect SCVs with several processors. Volition is suitable for on-the-fly use.

References

[1]

CheckFence at SourceForge. http://sourceforge.net/projects/checkfence/.

[2]

A. Agarwal, R. Simoni, J. Hennessy, and M. Horowitz. An Evaluation of Directory Schemes for Cache Coherence. In International Symposium on Computer Architecture, May 1988.

Digital Library

[3]

C. Blundell, M. M. Martin, and T. F. Wenisch. InvisiFence: Performance-Transparent Memory Ordering in Conventional Multiprocessors. In Int. Symp. on Computer Architecture, 2009.

Digital Library

[4]

F. Bonomi et al. An Improved Construction for Counting Bloom Filters. In Ann. Euro. Symp. on Algo., Sep 2006.

Digital Library

[5]

S. Burckhardt, R. Alur, and M. M. K. Martin. CheckFence: Checking Consistency of Concurrent Data Types on Relaxed Memory Models. In Programming Language Design and Implementation, Jun 2007.

Digital Library

[6]

S. Burckhardt and M. Musuvathi. Effective Program Verification for Relaxed Memory Models. In Computer Aided Verification, Jul 2008.

Digital Library

[7]

J. Burnim, K. Sen, and C. Stergiou. Sound and Complete Monitoring of Sequential Consistency for Relaxed Memory Models. In Tools and Algo. for the Const. and Ana. of Sys., July 2011.

Digital Library

[8]

L. Ceze, J. M. Tuck, P. Montesinos, and J. Torrellas. BulkSC: Bulk Enforcement of Sequential Consistency. In International Symposium on Computer Architecture, June 2007.

Digital Library

[9]

Y. Chen, L. Yi, W. Hu, T. Chen, H. Shen, P. Wang, and H. Pan. Fast Complete Memory Consistency Verification. In International Symposium on High Performance Computer Architecture, Feb 2009.

[10]

A. Deorio, I.Wagner, and V. Bertacco. DACOTA: Post-silicon Validation of the Memory Subsystem in Multi-core Designs. In International Symposium on High Performance Computer Architecture, Feb 2009.

[11]

Y. Duan, X. Feng, L. Wang, C. Zhang, and P.-C. Yew. Detecting and Eliminating Potential Violations of Sequential Consistency for Concurrent C/C++ Programs. In Code Gen. and Opt., Mar 2009.

Digital Library

[12]

J. Erickson, M. Musuvathi, S. Burckhardt, and K. Olynyk. Effective Data-race Detection for the Kernel. In Operating System Design and Implementation, Feb 2010.

Digital Library

[13]

X. Fang, J. Lee, and S. P. Midkiff. Automatic Fence Insertion for Shared Memory Multiprocessing. In International Conference on SuperComputing, Jun 2003.

Digital Library

[14]

K. Gharachorloo and P. B. Gibbons. Detecting Violations of Sequential Consistency. In Symp. on Par. Alg. and Arch., Jul 1991.

Digital Library

[15]

C. Gniady, B. Falsafi, and T. N. Vijaykumar. Is SC + ILP = RC? In International Symposium on Computer Architecture, May 1999.

Digital Library

[16]

A. Krishnamurthy and K. Yelick. Analyses and Optimizations for Shared Address Space Programs. Jour. Paral. Dist. Comp., Nov 1996.

Digital Library

[17]

L. Lamport. How to Make a Multiprocessor Computer that Correctly Executes Multiprocess Programs. IEEE Tran. on Comp., July 1979.

Digital Library

[18]

J. Lee and D. A. Padua. Hiding Relaxed Memory Consistency with a Compiler. IEEE Trans. Comput., Aug 2001.

Digital Library

[19]

C. Lin, V. Nagarajan, and R. Gupta. Efficient Sequential Consistency using Conditional Fences. In Parallel Architecture and Compilation Techniques, Sep 2010.

Digital Library

[20]

C. Lin, V. Nagarajan, R. Gupta, and B. Rajaram. Efficient Sequential Consistency via Conflict Ordering. In Architectural Support for Programming Languages and Operating Systems, Mar 2012.

Digital Library

[21]

B. Lucia, L. Ceze, K. Strauss, S. Qadeer, and H.-J. Boehm. Conflict Exceptions: Simplifying Concurrent Language Semantics with Precise Hardware Exceptions for Data-races. In International Symposium on Computer Architecture, Jun 2010.

Digital Library

[22]

D. Marino, A. Singh, T. Millstein, M. Musuvathi, and S. Narayanasamy. DRFx: A Simple and Efficient Memory Model for Concurrent Programming Languages. In Programming Language Design and Implementation, June 2010.

Digital Library

[23]

A. Meixner and D. J. Sorin. Dynamic Verification of Sequential Consistency. In Int. Symp. on Comp. Arch., Jun 2005.

Digital Library

[24]

A. Muzahid, S. Qi, and J. Torrellas. Vulcan: Hardware Support for Detecting Sequential Consistency Violations Dynamically. In International Symposium on Microarchitecture, December 2012.

Digital Library

[25]

S. Narayanasamy, Z.Wang, J. Tigani, A. Edwards, and B. Calder. Automatically Classifying Benign and Harmful Data Races using Replay Analysis. In Prog. Lang. Des. and Impl., Jun 2007.

Digital Library

[26]

J. Renau, B. Fraguela, J. Tuck, W. Liu, M. Prvulovic, L. Ceze, S. Sarangi, P. Sack, K. Strauss, and P. Montesinos. SESC Simulator, January 2005. http://sesc.sourceforge.net.

[27]

D. C. Schmidt and T. Harrison. Double-Checked Locking: An Optimization Pattern for Efficiently Initializing and Accessing Thread-safe Objects. In Patt. Lang. of Prog. Des. Conf., 1996.

[28]

D. Shasha and M. Snir. Efficient and Correct Execution of Parallel Programs that Share Memory. ACM Transactions on Programming Languages and Systems, 10(2):282--312, April 1988.

Digital Library

[29]

Z. Sura, X. Fang, C.-L. Wong, S. P. Midkiff, J. Lee, and D. Padua. Compiler Techniques for High Performance Sequentially Consistent Java programs. In Prin. and Pract. of Para. Prog., Jun 2005.

Digital Library

[30]

J. Sevc1k. Safe Optimisations for Shared-memory Concurrent Programs. In Prog. Lang. Des. and Impl., Jun 2011.

Digital Library

[31]

T. F.Wenisch, A. Ailamaki, B. Falsafi, and A. Moshovos. Mechanisms for Store-wait-free Multiprocessors. In International Symposium on Computer Architecture, June 2007.

Digital Library

Cited By

Mansinghka VSchaechtle UHanda SRadul AChen YRinard M(2018)Probabilistic programming with programmable inferenceACM SIGPLAN Notices10.1145/3296979.319240953:4(603-616)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192409
Panchekha PGeller AErnst MTatlock ZKamil S(2018)Verifying that web pages have accessible layoutACM SIGPLAN Notices10.1145/3296979.319240753:4(1-14)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192407
Turakhia YBejerano GDally W(2018)DarwinACM SIGPLAN Notices10.1145/3296957.317319353:2(199-213)Online publication date: 19-Mar-2018
https://dl.acm.org/doi/10.1145/3296957.3173193
Show More Cited By

Index Terms

Volition: scalable and precise sequential consistency violation detection
1. Computer systems organization
  1. Architectures
    1. Parallel architectures

Recommendations

Volition: scalable and precise sequential consistency violation detection
ASPLOS '13

Sequential Consistency (SC) is the most intuitive memory model, and SC Violations (SCVs) produce unintuitive, typically incorrect executions. Most prior SCV detection schemes have used data races as proxies for SCVs, which is highly imprecise. Other ...
Volition: scalable and precise sequential consistency violation detection
ASPLOS '13

Sequential Consistency (SC) is the most intuitive memory model, and SC Violations (SCVs) produce unintuitive, typically incorrect executions. Most prior SCV detection schemes have used data races as proxies for SCVs, which is highly imprecise. Other ...
WeeFence: toward making fences free in TSO
ICSA '13

Although fences are designed for low-overhead concurrency coordination, they can be expensive in current machines. If fences were largely free, faster fine-grained concurrent algorithms could be devised, and compilers could guarantee Sequential ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASPLOS '13: Proceedings of the eighteenth international conference on Architectural support for programming languages and operating systems

March 2013

574 pages

ISBN:9781450318709

DOI:10.1145/2451116

General Chair:
Vivek Sarkar
Rice University, USA
,
Program Chair:
Rastislav Bodik
University of California, Berkeley, USA

ACM SIGPLAN Notices Volume 48, Issue 4
ASPLOS '13
April 2013
540 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2499368
Issue’s Table of Contents
ACM SIGARCH Computer Architecture News Volume 41, Issue 1
ASPLOS '13
March 2013
540 pages
ISSN:0163-5964
DOI:10.1145/2490301
Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 March 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ASPLOS '13

Sponsor:

ASPLOS '13: Architectural Support for Programming Languages and Operating Systems

March 16 - 20, 2013

Texas, Houston, USA

Acceptance Rates

Overall Acceptance Rate 535 of 2,713 submissions, 20%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
379
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mansinghka VSchaechtle UHanda SRadul AChen YRinard M(2018)Probabilistic programming with programmable inferenceACM SIGPLAN Notices10.1145/3296979.319240953:4(603-616)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192409
Panchekha PGeller AErnst MTatlock ZKamil S(2018)Verifying that web pages have accessible layoutACM SIGPLAN Notices10.1145/3296979.319240753:4(1-14)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192407
Turakhia YBejerano GDally W(2018)DarwinACM SIGPLAN Notices10.1145/3296957.317319353:2(199-213)Online publication date: 19-Mar-2018
https://dl.acm.org/doi/10.1145/3296957.3173193
DeLozier CEizenberg ALucia BDevietti J(2018)SOFRITASACM SIGPLAN Notices10.1145/3296957.317319253:2(286-300)Online publication date: 19-Mar-2018
https://dl.acm.org/doi/10.1145/3296957.3173192
Anisetti MArdagna CDamiani EPolegri G(2018)Test-Based Security Certification of Composite ServicesACM Transactions on the Web10.1145/326746813:1(1-43)Online publication date: 4-Dec-2018
https://dl.acm.org/doi/10.1145/3267468
Pradhan SBaig GMao WQiu LChen GYang B(2018)Smartphone-based Acoustic Indoor Space MappingProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/32142782:2(1-26)Online publication date: 5-Jul-2018
https://dl.acm.org/doi/10.1145/3214278
Peng LChen LYe ZZhang Y(2018)AROMAProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/32142772:2(1-16)Online publication date: 5-Jul-2018
https://dl.acm.org/doi/10.1145/3214277
DeLozier CEizenberg ALucia BDevietti JShen XTuck JBianchini RSarkar V(2018)SOFRITASProceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3173162.3173192(286-300)Online publication date: 19-Mar-2018
https://dl.acm.org/doi/10.1145/3173162.3173192
Bowling MBurch NJohanson MTammelin O(2017)Heads-up limit hold'em poker is solvedCommunications of the ACM10.1145/313128460:11(81-88)Online publication date: 24-Oct-2017
https://dl.acm.org/doi/10.1145/3131284
Crane KWeischedel CWardetzky M(2017)The heat method for distance computationCommunications of the ACM10.1145/313128060:11(90-99)Online publication date: 24-Oct-2017
https://dl.acm.org/doi/10.1145/3131280
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten