skip to main content
10.1145/2688500.2688510acmconferencesArticle/Chapter ViewAbstractPublication PagesppoppConference Proceedingsconference-collections
research-article

Low-overhead software transactional memory with progress guarantees and strong semantics

Published: 24 January 2015 Publication History

Abstract

Software transactional memory offers an appealing alternative to locks by improving programmability, reliability, and scalability. However, existing STMs are impractical because they add high instrumentation costs and often provide weak progress guarantees and/or semantics. This paper introduces a novel STM called LarkTM that provides three significant features. (1) Its instrumentation adds low overhead except when accesses actually conflict, enabling low single-thread overhead and scaling well on low-contention workloads. (2) It uses eager concurrency control mechanisms, yet naturally supports flexible conflict resolution, enabling strong progress guarantees. (3) It naturally provides strong atomicity semantics at low cost. LarkTM's design works well for low-contention workloads, but adds significant overhead under higher contention, so we design an adaptive version of LarkTM that uses alternative concurrency control for high-contention objects. An implementation and evaluation in a Java virtual machine show that the basic and adaptive versions of LarkTM not only provide low single-thread overhead, but their multithreaded performance compares favorably with existing high-performance STMs.

References

[1]
M. Abadi, A. Birrell, T. Harris, and M. Isard. Semantics of Transactional Memory and Automatic Mutual Exclusion. In POPL, pages 63–74, 2008.
[2]
M. Abadi, T. Harris, and M. Mehrara. Transactional Memory with Strong Atomicity Using Off-the-Shelf Memory Protection Hardware. In PPoPP, pages 185–196, 2009.
[3]
S. V. Adve and H.-J. Boehm. Memory Models: A Case for Rethinking Parallel Languages and Hardware. CACM, 53:90–101, 2010.
[4]
B. Alpern, S. Augart, S. M. Blackburn, M. Butrico, A. Cocchi, P. Cheng, J. Dolby, S. Fink, D. Grove, M. Hind, K. S. McKinley, M. Mergen, J. E. B. Moss, T. Ngo, and V. Sarkar. The Jikes Research Virtual Machine Project: Building an Open-Source Research Community. IBM Systems Journal, 44:399–417, 2005.
[5]
L. Baugh, N. Neelakantam, and C. Zilles. Using Hardware Memory Protection to Build a High-Performance, Strongly-Atomic Hybrid Transactional Memory. In ISCA, pages 115–126, 2008.
[6]
M. D. Bond, M. Kulkarni, M. Cao, M. Zhang, M. Fathi Salmi, S. Biswas, A. Sengupta, and J. Huang. Octet: Capturing and Controlling Cross-Thread Dependences Efficiently. In OOPSLA, pages 693–712, 2013.
[7]
N. G. Bronson, C. Kozyrakis, and K. Olukotun. Feedback-Directed Barrier Optimization in a Strongly Isolated STM. In POPL, pages 213–225, 2009.
[8]
I. Calciu, J. Gottschlich, T. Shpeisman, G. Pokam, and M. Herlihy. Invyswell: A Hybrid Transactional Memory for Haswell’s Restricted Transactional Memory. In PACT, pages 187–200, 2014.
[9]
M. Cao, M. Zhang, and M. D. Bond. Drinking from Both Glasses: Adaptively Combining Pessimistic and Optimistic Synchronization for Efficient Parallel Runtime Support. In WoDet, 2014.
[10]
C. Cao Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford Transactional Applications for Multi-Processing. In IISWC, 2008.
[11]
C. Cascaval, C. Blundell, M. Michael, H. W. Cain, P. Wu, S. Chiras, and S. Chatterjee. Software Transactional Memory: Why Is It Only a Research Toy? CACM, 51(11):40–46, 2008.
[12]
L. Dalessandro and M. L. Scott. Strong Isolation is a Weak Idea. In TRANSACT, 2009.
[13]
L. Dalessandro and M. L. Scott. Sandboxing Transactional Memory. In PACT, pages 171–180, 2012.
[14]
L. Dalessandro, M. L. Scott, and M. F. Spear. Transactions as the Foundation of a Memory Consistency Model. In DISC, pages 20–34, 2010.
[15]
L. Dalessandro, M. F. Spear, and M. L. Scott. NOrec: Streamlining STM by Abolishing Ownership Records. In PPoPP, pages 67–78, 2010.
[16]
M. de Kruijf and K. Sankaralingam. Idempotent Code Generation: Implementation, Analysis, and Evaluation. In CGO, pages 1–12, 2013.
[17]
B. Demsky and A. Dash. Evaluating Contention Management Using Discrete Event Simulation. In TRANSACT, 2010.
[18]
D. Dice, O. Shalev, and N. Shavit. Transactional Locking II. In DISC, pages 194–208, 2006.
[19]
D. Dice and N. Shavit. TLRW: Return of the Read-Write Lock. In SPAA, pages 284–293, 2010.
[20]
A. Dragojevi´c, P. Felber, V. Gramoli, and R. Guerraoui. Why STM Can Be More than a Research Toy. CACM, 54:70–77, 2011.
[21]
A. Dragojevi´c, R. Guerraoui, and M. Kapalka. Stretching Transactional Memory. In PLDI, pages 155–165, 2009.
[22]
J. E. Gottschlich, M. Vachharajani, and J. G. Siek. An Efficient Software Transactional Memory Using Commit-Time Invalidation. In CGO, pages 101–110, 2010.
[23]
R. Guerraoui, M. Herlihy, and B. Pochon. Toward a Theory of Transactional Contention Managers. In PODC, pages 258–264, 2005.
[24]
L. Hammond, V. Wong, M. Chen, B. D. Carlstrom, J. D. Davis, B. Hertzberg, M. K. Prabhu, H. Wijaya, C. Kozyrakis, and K. Olukotun. Transactional Memory Coherence and Consistency. In ISCA, pages 102–113, 2004.
[25]
T. Harris and K. Fraser. Language Support for Lightweight Transactions. In OOPSLA, pages 388–402, 2003.
[26]
T. Harris and K. Fraser. Revocable Locks for Non-Blocking Programming. In PPoPP, pages 72–82, 2005.
[27]
T. Harris, J. Larus, and R. Rajwar. Transactional Memory. Morgan and Claypool Publishers, 2nd edition, 2010.
[28]
T. Harris, M. Plesko, A. Shinnar, and D. Tarditi. Optimizing Memory Transactions. In PLDI, pages 14–25, 2006.
[29]
A. Hassan, R. Palmieri, and B. Ravindran. Remote Invalidation: Optimizing the Critical Path of Memory Transactions. In IPDPS, pages 187–197, 2014.
[30]
M. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer, III. Software Transactional Memory for Dynamic-Sized Data Structures. In PODC, pages 92–101, 2003.
[31]
M. Herlihy and J. E. B. Moss. Transactional Memory: Architectural Support for Lock-Free Data Structures. In ISCA, pages 289–300, 1993.
[32]
B. Hindman and D. Grossman. Atomicity via Source-to-Source Translation. In MSPC, pages 82–91, 2006.
[33]
K. Kawachiya, A. Koseki, and T. Onodera. Lock Reservation: Java Locks Can Mostly Do Without Atomic Operations. In OOPSLA, pages 130–141, 2002.
[34]
G. Korland, N. Shavit, and P. Felber. Deuce: Noninvasive Software Transactional Memory in Java. Transactions on HiPEAC, 5(2), 2010.
[35]
V. J. Marathe, M. F. Spear, C. Heriot, A. Acharya, D. Eisenstat, W. N. Scherer III, and M. L. Scott. Lowering the Overhead of Nonblocking Software Transactional Memory. In TRANSACT, 2006.
[36]
V. Menon, S. Balensiefer, T. Shpeisman, A.-R. Adl-Tabatabai, R. L. Hudson, B. Saha, and A. Welc. Practical Weak-Atomicity Semantics for Java STM. In SPAA, pages 314–325, 2008.
[37]
V. Menon, S. Balensiefer, T. Shpeisman, A.-R. Adl-Tabatabai, R. L. Hudson, B. Saha, and A. Welc. Single Global Lock Semantics in a Weakly Atomic STM. In TRANSACT, 2008.
[38]
K. E. Moore, J. Bobba, M. J. Moravan, M. D. Hill, and D. A. Wood. LogTM: Log-based Transactional Memory. In HPCA, pages 254–265, 2006.
[39]
K. F. Moore and D. Grossman. High-Level Small-Step Operational Semantics for Transactions. In POPL, pages 51–62, 2008.
[40]
N. Neelakantam, R. Rajwar, S. Srinivas, U. Srinivasan, and C. Zilles. Hardware Atomicity for Reliable Software Speculation. In ISCA, pages 174–185, 2007.
[41]
M. Olszewski, J. Cutler, and J. G. Steffan. JudoSTM: A Dynamic Binary-Rewriting Approach to Software Transactional Memory. In PACT, pages 365–375, 2007.
[42]
V. Pankratius and A.-R. Adl-Tabatabai. A Study of Transactional Memory vs. Locks in Practice. In SPAA, pages 43–52, 2011.
[43]
C. G. Ritson and F. R. Barnes. An Evaluation of Intel’s Restricted Transactional Memory for CPAs. In CPA, pages 271–292, 2013.
[44]
K. Russell and D. Detlefs. Eliminating Synchronization-Related Atomic Operations with Biased Locking and Bulk Rebiasing. In OOPSLA, pages 263–272, 2006.
[45]
B. Saha, A.-R. Adl-Tabatabai, R. L. Hudson, C. C. Minh, and B. Hertzberg. McRT-STM: A High Performance Software Transactional Memory System for a Multi-Core Runtime. In PPoPP, pages 187–197, 2006.
[46]
D. J. Scales, K. Gharachorloo, and C. A. Thekkath. Shasta: A Low Overhead, Software-Only Approach for Supporting Fine-Grain Shared Memory. In ASPLOS, pages 174–185, 1996.
[47]
F. T. Schneider, V. Menon, T. Shpeisman, and A.-R. Adl-Tabatabai. Dynamic Optimization for Efficient Strong Atomicity. In OOPSLA, pages 181–194, 2008.
[48]
A. Sengupta, S. Biswas, M. Zhang, M. D. Bond, and M. Kulkarni. Hybrid Static–Dynamic Analysis for Statically Bounded Region Serializability. In ASPLOS, 2015. To appear.
[49]
T. Shpeisman, V. Menon, A.-R. Adl-Tabatabai, S. Balensiefer, D. Grossman, R. L. Hudson, K. F. Moore, and B. Saha. Enforcing Isolation and Ordering in STM. In PLDI, pages 78–88, 2007.
[50]
M. F. Spear, L. Dalessandro, V. J. Marathe, and M. L. Scott. A Comprehensive Strategy for Contention Management in Software Transactional Memory. In PPoPP, pages 141–150, 2009.
[51]
M. F. Spear, V. J. Marathe, L. Dalessandro, and M. L. Scott. Privatization Techniques for Software Transactional Memory. In PODC, 2007.
[52]
M. F. Spear, M. M. Michael, and C. von Praun. RingSTM: Scalable Transactions with a Single Atomic Instruction. In SPAA, pages 275– 284, 2008.
[53]
T. Usui, R. Behrends, J. Evans, and Y. Smaragdakis. Adaptive Locks: Combining Transactions and Locks for Efficient Concurrency. In PACT, pages 3–14, 2009.
[54]
C. von Praun and T. R. Gross. Object Race Detection. In OOPSLA, pages 70–82, 2001.
[55]
J.-T. Wamhoff, C. Fetzer, P. Felber, E. Rivière, and G. Muller. Fast-Lane: Improving Performance of Software Transactional Memory for Low Thread Counts. In PPoPP, pages 113–122, 2013.
[56]
A. Wang, M. Gaudet, P. Wu, J. N. Amaral, M. Ohmacht, C. Barton, R. Silvera, and M. Michael. Evaluation of Blue Gene/Q Hardware Support for Transactional Memories. In PACT, pages 127–136, 2012.
[57]
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, pages 34–48, 2007.
[58]
R. M. Yoo, C. J. Hughes, K. Lai, and R. Rajwar. Performance Evaluation of Intel Transactional Synchronization Extensions for High-Performance Computing. In SC, pages 19:1–19:11, 2013.
[59]
R. M. Yoo, Y. Ni, A. Welc, B. Saha, A.-R. Adl-Tabatabai, and H.-H. S. Lee. Kicking the Tires of Software Transactional Memory: Why the Going Gets Tough. In SPAA, pages 265–274, 2008.
[60]
F. Zyulkyarov, S. Stipic, T. Harris, O. S. Unsal, A. Cristal, I. Hur, and M. Valero. Discovering and Understanding Performance Bottlenecks in Transactional Applications. In PACT, pages 285–294, 2010.

Cited By

View all
  • (2023)Separating Mechanism from Policy in STMProceedings of the 32nd International Conference on Parallel Architectures and Compilation Techniques10.1109/PACT58117.2023.00031(279-296)Online publication date: 21-Oct-2023
  • (2019)Dynamic one-to-one mapping of ownership records for STM using versioned weak referencesProceedings of the 16th ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3357390.3361020(37-49)Online publication date: 21-Oct-2019
  • (2019)Encapsulated open nesting for STMProceedings of the 24th Symposium on Principles and Practice of Parallel Programming10.1145/3293883.3295723(315-326)Online publication date: 16-Feb-2019
  • Show More Cited By

Index Terms

  1. Low-overhead software transactional memory with progress guarantees and strong semantics

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    PPoPP 2015: Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
    January 2015
    290 pages
    ISBN:9781450332057
    DOI:10.1145/2688500
    • cover image ACM SIGPLAN Notices
      ACM SIGPLAN Notices  Volume 50, Issue 8
      PPoPP '15
      August 2015
      290 pages
      ISSN:0362-1340
      EISSN:1558-1160
      DOI:10.1145/2858788
      • Editor:
      • Andy Gill
      Issue’s Table of Contents
    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 the author(s) 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: 24 January 2015

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. Software transactional memory
    2. biased reader-writer locks
    3. concurrency control
    4. managed languages
    5. strong atomicity

    Qualifiers

    • Research-article

    Funding Sources

    Conference

    PPoPP '15
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 230 of 1,014 submissions, 23%

    Upcoming Conference

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)9
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 15 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)Separating Mechanism from Policy in STMProceedings of the 32nd International Conference on Parallel Architectures and Compilation Techniques10.1109/PACT58117.2023.00031(279-296)Online publication date: 21-Oct-2023
    • (2019)Dynamic one-to-one mapping of ownership records for STM using versioned weak referencesProceedings of the 16th ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3357390.3361020(37-49)Online publication date: 21-Oct-2019
    • (2019)Encapsulated open nesting for STMProceedings of the 24th Symposium on Principles and Practice of Parallel Programming10.1145/3293883.3295723(315-326)Online publication date: 16-Feb-2019
    • (2018)Lock-Free Transactional Transformation for Linked Data StructuresACM Transactions on Parallel Computing10.1145/32096905:1(1-37)Online publication date: 13-Jun-2018
    • (2017)Synchronized-by-Default Concurrency for Shared-Memory SystemsACM SIGPLAN Notices10.1145/3155284.301874752:8(299-312)Online publication date: 26-Jan-2017
    • (2017)Hybridizing and Relaxing Dependence Tracking for Efficient Parallel Runtime SupportACM Transactions on Parallel Computing10.1145/31081384:2(1-42)Online publication date: 30-Aug-2017
    • (2017)Synchronized-by-Default Concurrency for Shared-Memory SystemsProceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3018743.3018747(299-312)Online publication date: 26-Jan-2017
    • (2016)Mostly-optimistic concurrency control for highly contended dynamic workloads on a thousand coresProceedings of the VLDB Endowment10.14778/3015274.301527610:2(49-60)Online publication date: 1-Oct-2016
    • (2016)Efficient and thread-safe objects for dynamically-typed languagesACM SIGPLAN Notices10.1145/3022671.298400151:10(642-659)Online publication date: 19-Oct-2016
    • (2016)Efficient and thread-safe objects for dynamically-typed languagesProceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2983990.2984001(642-659)Online publication date: 19-Oct-2016
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media