Article

Enforcing isolation and ordering in STM

Authors:

Tatiana Shpeisman,

Ali-Reza Adl-Tabatabai,

Steven Balensiefer,

Richard L. Hudson,

Katherine F. Moore,

Bratin SahaAuthors Info & Claims

PLDI '07: Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 78 - 88

https://doi.org/10.1145/1250734.1250744

Published: 10 June 2007 Publication History

Abstract

Transactional memory provides a new concurrency control mechanism that avoids many of the pitfalls of lock-based synchronization. High-performance software transactional memory (STM) implementations thus far provide weak atomicity: Accessing shared data both inside and outside a transaction can result in unexpected, implementation-dependent behavior. To guarantee isolation and consistent ordering in such a system, programmers are expected to enclose all shared-memory accesses inside transactions.

A system that provides strong atomicity guarantees isolation even in the presence of threads that access shared data outside transactions. A strongly-atomic system also orders transactions with conflicting non-transactional memory operations in a consistent manner.

In this paper, we discuss some surprising pitfalls of weak atomicity, and we present an STM system that avoids these problems via strong atomicity. We demonstrate how to implement non-transactional data accesses via efficient read and write barriers, and we present compiler optimizations that further reduce the overheads of these barriers. We introduce a dynamic escape analysis that differentiates private and public data at runtime to make barriers cheaper and a static not-accessed-in-transaction analysis that removes many barriers completely. Our results on a set of Java programs show that strong atomicity can be implemented efficiently in a high-performance STM system.

References

[1]

A.-R. Adl-Tabatabai, B. T. Lewis, V. S. Menon, B. R. Murphy, B. Saha, and T. Shpeisman. Compiler and runtime support for efficient software transactional memory. In PLDI 2006.

Digital Library

[2]

S. Adve and K. Gharachorloo. Shared memory consistency models: A tutorial. IEEE Computer, 29(12):66--76, 1996.

Digital Library

[3]

J. Aldrich, E. G. Sirer, C. Chambers, and S. Eggers. Comprehensive synchronization elimination for Java. Sci. Comput. Programming, 47(2--3), May-June 2003.

Digital Library

[4]

E. Allen, D. Chase, J. Hallett, V. Luchangco, J.-W. Maessen, S. Ryu, G. L. Steele, Jr., and STobin-Hochstadt. The Fortress language specification version 1.0&$945; http://research.sun.com/projects/plrg/fortress.pdf, 2006.

[5]

C. S. Ananian, K. Asanovic, B. C. Kuszmaul, C. E. Leiserson, and S. Lie. Unbounded transactional memory. In HPCA 2005.

Digital Library

[6]

C. S. Ananian and M. Rinard. Efficient object-based software transactions. In SCOOL 2005.

[7]

M. Berndl, O. Lhoták, F. Qian, L. Hendren, and N. Umanee. Points-to analysis using BDDs. In PLDI 2003.

Digital Library

[8]

B. Blanchet. Escape analysis for object--oriented languages: Application to Java. In OOPSLA 1999.

Digital Library

[9]

C. Blundell, E. C. Lewis, and M. Martin. Subtleties of transactional memory atomicity semantics. Computer Architecture Letters, 5(2), Nov. 2006.

Digital Library

[10]

H. Boehm. Threads cannot be implemented as a library. In PLDI 2005.

Digital Library

[11]

J. Bogda and U. Hölzle. Removing unnecessary synchronization in Java. In OOPSLA 1999.

Digital Library

[12]

C. Boyapati, R. Lee, and M. Rinard. Ownership types for safe programming: Preventing data races and deadlocks. In OOPSLA 2002.

Digital Library

[13]

B. D. Carlstrom, J. Chung, A. McDonald, H. Chafi, C. Kozyrakis, and K. Olukotun. The Atomos transactional programming language. In PLDI 2006.

Digital Library

[14]

P. Charles, C. Donawa, K. Ebcioglu, C. Grothoff, A. Kielstra, C. von Praun, V. Saraswat, and V. Sarkar. X10: an object--oriented approach to non-uniform cluster computing. In OOPSLA 2005.

Digital Library

[15]

J.-D. Choi, M. Gupta, M. J. Serrano, V. C. Sreedhar, and S. P. Midkiff. Escape analysis for Java. In OOPSLA 1999.

Digital Library

[16]

Cray Inc. Chapel Specification 0.4. http://linebreak{0}chapel.cs.linebreak{0}washington.edu/specification.pdf, 2005.

[17]

P. Damron, A. Fedorova, Y. Lev, V. Luchangco, M. Moir, and D. Nussbaum. Hybrid transactional memory. In ASPLOS 2006.

Digital Library

[18]

D. Dice, O. Shalev, and N. Shavit. Transactional Locking II. In DISC 2006.

Digital Library

[19]

T. Domani, G. Goldshtein, E. K. Kolodner, E. Lewis, E. Petrank, and D. Sheinwald. Thread-local heaps for Java. In ISMM 2002.

Digital Library

[20]

C. Flanagan and S. N. Freund. Type inference against races. In SAS 2004.

Digital Library

[21]

K. Fraser. Practical lock freedom. PhD thesis, Cambridge University Computer Laboratory, 2003. Technical Report UCAM-CL-TR-579.

[22]

J. Gray and A. Reuter. Transaction Processing: Concepts and Techniques. Morgan Kaufmann, 1993.

Digital Library

[23]

D. Grossman, J. Manson, and W. Pugh. What do high-level memory models mean for transactions? In ACM SIGPLAN Workshop on Memory Systems Performance & Correctness 2006.

Digital Library

[24]

L. Hammond, B. D. Carlstrom, V. Wong, B. Hertzberg, M. Chen, C. Kozyrakis, and K. Olukotun. Programming with transactional coherence and consistency (tcc). In ASPLOS 2004.

Digital Library

[25]

T. Harris and K. Fraser. Language support for lightweight transactions. In OOPSLA 2003.

Digital Library

[26]

T. Harris, S. Marlow, S. P. Jones, and M. Herlihy. Composable memory transactions. In PPoPP 2005.

Digital Library

[27]

T. Harris, M. Plesko, A. Shinnar, and D. Tarditi. Optimizing memory transactions. In PLDI 2006.

Digital Library

[28]

M. Herlihy, V. Luch-angco, M. Moir, and I. William N. Scherer. Software transactional memory for dynamic-sized data structures. In PODC 2003.

Digital Library

[29]

M. Herlihy, V. Luchangco, and M. Moir. A flexible framework for implementing software transactional memory. In OOPSLA 2006.

Digital Library

[30]

M. Herlihy and J. E. B. Moss. Transactional memory: architectural support for lock-free data structures. In ISCA 1993.

Digital Library

[31]

B. Hindman and D. Grossman. Atomicity via source-to-source translation. In ACM SIGPLAN Workshop on Memory Systems Performance & Correctness 2006.

Digital Library

[32]

R. L. Hudson, B. Saha, A.-R. Adl-Tabatabai, and B. C. Hertzberg. Mcrt-malloc: A scalable transactional memory allocator. In ISMM 2006.

Digital Library

[33]

S. Kumar, M. Chu, C. J. Hughes, P. Kundu, and A. Nguyen. Hybrid transactional memory. In PPoPP 2006.

Digital Library

[34]

H. T. Kung and J. T. Robinson. On optimistic methods for concurrency control. ACM Trans. Database Syst., 6(2), 1981.

Digital Library

[35]

J. Larus and R. Rajwar. Transactional Memory. Morgan & Claypool Publishers, 2006.

[36]

Y. Lev and J.-W. Maessen. Towards a safer interaction with transactional memory by tracking object visibility. In SCOOL 2005.

[37]

J. Manson, J. Baker, A. Cunei, S. Jagannathan, M. Prochazka, B. Xin, and J. Vitek. Preemptible atomic regions for real-time Java. In IEEE Real-Time Systems Symposium 2005.

Digital Library

[38]

J. Manson, W. Pugh, and S. V. Adve. The Java memory model. In POPL 2005.

Digital Library

[39]

V. J. Marathe, W. N. Scherer, and M. L. Scott. Adaptive software transactional memory. In International Symposium on Distributed Computing 2005.

Digital Library

[40]

B. McCloskey, F. Zhou, D. Gay, and E. Brewer. Autolocker: synchronization inference for atomic sections. In POPL 2006.

Digital Library

[41]

A. McDonald, J. Chung, B. D. Carlstrom, C. Cao Minh, H. Chafi, C. Kozyrakis, and K. Olukotun. Architectural semantics for practical transactional memory. In ISCA 2006.

Digital Library

[42]

K. E. Moore, J. Bobba, M. J. Moravan, M. D. Hill, and D. A. Wood. LogTM: Log-based transactional memory. In HPCA 2006.

[43]

M. J. Moravan, J. Bobba, K. E. Moore, L. Yen, M. D. Hill, BLiblit, M. M. Swift, and D. A. Wood. Supporting nested transactional memory in LogTM. In ASPLOS 2006.

Digital Library

[44]

M. Naik, A. Aiken, and J. Whaley. Effective static race detection for Java. In PLDI 2006.

Digital Library

[45]

Y. Ni, V. Menon, A.-R. Adl-Tabatabai, A. L. Hosking, R. L. Hudson, J. E. B. Moss, B. Saha, and T. Shpeisman. Open Nesting in Software Transactional Memory. In PPoPP 2007.

Digital Library

[46]

R. Rajwar, M. Herlihy, and K. Lai. Virtualizing transactional memory. In ISCA 2005.

Digital Library

[47]

M. F. Ringenburg and D. Grossman. AtomCaml: first-class atomicity via rollback. In ICFP 2005.

Digital Library

[48]

E. Ruf. Effective synchronization removal for Java. In PLDI 2000.

Digital Library

[49]

B. Saha, A.-R. Adl-Tabatabai, R. Hudson, C. C. Minh, and B. Hertzberg. McRT-STM: A high performance software transactional memory system for a multi-core runtime. In PPoPP 2006.

Digital Library

[50]

B. Saha, A.-R. Adl-Tabatabai, and Q. Jacobson. Architectural support for software transactional memory. In MICRO 2006.

Digital Library

[51]

N. Shavit and D. Touitou. Software transactional memory. In PODC 1995.

Digital Library

[52]

M. F. Spear, V. J. Marathe, L. Dalessandro, and M. L. Scott. Privatization techniques for software transactional memory. Technical Report 915, University of Rochester, Computer Science Dept., 2007.

Digital Library

[53]

M. F. Spear, V. J. Marathe, W. N. Scherer, and M. L. Scott. Conflict detection and validation strategies for software transactional memory. In DISC 2006.

Digital Library

[54]

Standard Performance Evaluation Corporation. SPEC JVM98 Benchmarks. http://www.spec.org/osg/jvm98.

[55]

Standard Performance Evaluation Corporation. SPEC JBB2000, 2000. See http://www.spec.org/jbb2000.

[56]

RVallée-Rai, L. Hendren, V. Sundaresan, P. Lam, E. Gagnon, and P. Co. Soot - a Java optimization framework. In CASCON 1999.

[57]

C. von Praun and T. R. Gross. Static conflict analysis for multi-threaded object-oriented programs. In PLDI 2003.

Digital Library

[58]

C. Wang, W.-Y. Chen, Y. Wu, B. Saha, and A.-R. Adl-Tabatabai. Code Generation and Optimization for Transactional Memory Constructs in an Unmanaged Language. In CGO 2007.

Digital Library

[59]

A. Welc, S. Jagannathan, and A. L. Hosking. Revocation techniques for Java concurrency. In Concurrency and Computation:Practice and Experience. John Wiley and Sons, 2005.

Digital Library

Cited By

Jain AKadiyala DDaglis A(2023)Safety Hints for HTM Capacity Abort Mitigation2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA56546.2023.10071113(206-219)Online publication date: Feb-2023
https://doi.org/10.1109/HPCA56546.2023.10071113
Li ZLiu LDeng YWang JLiu ZYin SWei S(2019)FPGA-Accelerated Optimistic Concurrency Control for Transactional MemoryProceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3352460.3358270(911-923)Online publication date: 12-Oct-2019
https://dl.acm.org/doi/10.1145/3352460.3358270
Dongol BJagadeesan RRiely JHollingsworth JKeidar I(2019)Modular transactionsProceedings of the 24th Symposium on Principles and Practice of Parallel Programming10.1145/3293883.3295708(82-93)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1145/3293883.3295708
Show More Cited By

Index Terms

Enforcing isolation and ordering in STM
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Runtime environments
      2. Source code generation
    2. General programming languages
      1. Language features
        Concurrent programming structures
      2. Language types
        Parallel programming languages

Recommendations

Compiler and runtime support for efficient software transactional memory
PLDI '06: Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation

Programmers have traditionally used locks to synchronize concurrent access to shared data. Lock-based synchronization, however, has well-known pitfalls: using locks for fine-grain synchronization and composing code that already uses locks are both ...
Enforcing isolation and ordering in STM
Proceedings of the 2007 PLDI conference

Transactional memory provides a new concurrency control mechanism that avoids many of the pitfalls of lock-based synchronization. High-performance software transactional memory (STM) implementations thus far provide weak atomicity: Accessing shared data ...
High-level small-step operational semantics for transactions
POPL '08: Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Software transactions have received significant attention as a way to simplify shared-memory concurrent programming, but insufficient focus has been given to the precise meaning of software transactions or their interaction with other language features. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '07: Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2007

508 pages

ISBN:9781595936332

DOI:10.1145/1250734

General Chair:
Jeanne Ferrante
University of California, San Diego, USA
,
Program Chair:
Kathryn S. McKinley
University of Texas at Austin, USA

ACM SIGPLAN Notices Volume 42, Issue 6
Proceedings of the 2007 PLDI conference
June 2007
491 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1273442
Issue’s Table of Contents

Copyright © 2007 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: 10 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PLDI '07

Sponsor:

PLDI '07: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 10 - 13, 2007

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

153
Total Citations
View Citations
1,204
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jain AKadiyala DDaglis A(2023)Safety Hints for HTM Capacity Abort Mitigation2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA56546.2023.10071113(206-219)Online publication date: Feb-2023
https://doi.org/10.1109/HPCA56546.2023.10071113
Li ZLiu LDeng YWang JLiu ZYin SWei S(2019)FPGA-Accelerated Optimistic Concurrency Control for Transactional MemoryProceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3352460.3358270(911-923)Online publication date: 12-Oct-2019
https://dl.acm.org/doi/10.1145/3352460.3358270
Dongol BJagadeesan RRiely JHollingsworth JKeidar I(2019)Modular transactionsProceedings of the 24th Symposium on Principles and Practice of Parallel Programming10.1145/3293883.3295708(82-93)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1145/3293883.3295708
Sotiropolos PVassilakis C(2019)Detection of intermittent faults in software programs through identification of suspicious shared variable access patternsJournal of Systems and Software10.1016/j.jss.2019.110455(110455)Online publication date: Oct-2019
https://doi.org/10.1016/j.jss.2019.110455
Chong NSorensen TWickerson J(2018)The semantics of transactions and weak memory in x86, Power, ARM, and C++ACM SIGPLAN Notices10.1145/3296979.319237353:4(211-225)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192373
Chong NSorensen TWickerson JFoster JGrossman D(2018)The semantics of transactions and weak memory in x86, Power, ARM, and C++Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3192366.3192373(211-225)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3192366.3192373
Kanrar S(2018)SME: A New Software Transactional Memory Based Mutual Exclusion Algorithm for Distributed SystemsComputer Information Systems and Industrial Management10.1007/978-3-319-99954-8_30(354-369)Online publication date: 5-Sep-2018
https://doi.org/10.1007/978-3-319-99954-8_30
Sengupta ACao MBond MKulkarni MReddi VSmith ATang L(2017)Legato: end-to-end bounded region serializability using commodity hardware transactional memoryProceedings of the 2017 International Symposium on Code Generation and Optimization10.5555/3049832.3049834(1-13)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3049832.3049834
Wood BCao MBond MGrossman D(2017)Instrumentation bias for dynamic data race detectionProceedings of the ACM on Programming Languages10.1145/31338931:OOPSLA(1-31)Online publication date: 12-Oct-2017
https://dl.acm.org/doi/10.1145/3133893
Zhou TLuchangco VSpear MScheideler CHajiaghayi M(2017)Hand-Over-Hand Transactions with Precise Memory ReclamationProceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3087556.3087587(255-264)Online publication date: 24-Jul-2017
https://dl.acm.org/doi/10.1145/3087556.3087587
Show More Cited By

View Options

Get Access

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.

Media

Figures

Other

Tables

View Table of Contents