research-article

Committing conflicting transactions in an STM

Authors:

Hany E. Ramadan,

Maurice Herlihy,

Emmett WitchelAuthors Info & Claims

ACM SIGPLAN Notices, Volume 44, Issue 4

Pages 163 - 172

https://doi.org/10.1145/1594835.1504201

Published: 14 February 2009 Publication History

Abstract

Dependence-aware transactional memory (DATM) is a recently proposed model for increasing concurrency of memory transactions without complicating their interface. DATM manages dependences between conflicting, uncommitted transactions so that they commit safely.

The contributions of this paper are twofold. First, we provide a safety proof for the dependence-aware model. This proof also shows that the DATM model accepts all concurrent interleavings that are conflict-serializable.

Second, we describe the first application of dependence tracking to software transactional memory (STM) design and implementation. We compare our implementation with a state of the art STM, TL2 [4]. We use benchmarks from the STAMP [21] suite, quantifying how dependence tracking converts certain types of transactional conflicts into successful commits. On high contention workloads, DATM is able to take advantage of dependences to speed up execution by up to 4.8x.

References

[1]

Ali-Reza Adl-Tabatabai, Brian Lewis, Vijay Menon, Brian Murphy, Bratin Saha, and Tatiana Shpeisman. Compiler and runtime support for efficient software transactional memory. In PLDI, Jun 2006.

Digital Library

[2]

Utku Aydonat and Tarek Abdelrahman. Serializability of transactions in software transactional memory. In TRANS-ACT, Feb 2008.

[3]

Philip Bernstein, Vassos Hadzilacos, and Nathan Goodman. Concurrency Control and Recovery in Database Systems. Addison Wesley, 1987.

Digital Library

[4]

Charles T. Davies. Data processing spheres of control. IBM Systems Journal, 17(2), 1978.

Digital Library

[5]

Dave Dice, Ori Shalev, and Nir Shavit. Transactional locking II. In DISC, Sep 2006.

Digital Library

[6]

Dave Dice and Nir Shavit. What really makes transactions faster? In TRANSACT, Jun 2006.

[7]

Aleksandar Dragojevic, Rachid Guerraoui, and Michal Kapalka. Dividing Transactional Memories by Zero. In TRANSACT, Feb 2008.

[8]

Jim Gray and Andreas Reuter. Transaction Processing: Concepts and Techniques. Morgan Kaufmann, 1993.

Digital Library

[9]

Rachid Guerraoui, Michal Kapalka, and Jan Vitek. Stmbench7: A benchmark for software transactional memory. In EuroSys, Mar 2007.

Digital Library

[10]

Tim Harris and Keir Fraser. Language support for lightweight transactions. In OOPSLA, Oct 2003.

Digital Library

[11]

Tim Harris, Mark Plesko, Avraham Shinnar, and David Tarditi. Optimizing memory transactions. In PLDI, Jun 2006.

Digital Library

[12]

Tim Harris and Srdan Stipic. Abstract nested transactions. In TRANSACT, Aug 2007.

[13]

Maurice Herlihy and Eric Koskinen. Dreadlocks: Efficient deadlock detection for stm. In TRANSACT, Feb 2008.

[14]

Maurice Herlihy and Eric Koskinen. Transactional boosting: amethodology for highly-concurrent transactional objects. In PPoPP, Feb 2008.

Digital Library

[15]

Maurice Herlihy, Victor Luchangco, and Mark Moir. A flexible framework for implementing software transactional memory. In OOPSLA, Oct 2006.

Digital Library

[16]

Maurice Herlihy and J. Eliot Moss. Transactional memory: Architectural support for lock-free data structures. In ISCA, May 1993.

Digital Library

[17]

Maurice Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM TOPLAS, 12(3):463--492, Jul 1990.

Digital Library

[18]

Milind Kulkarni, Keshav Pingali, Bruce Walter, Ganesh Ramanarayanan, Kavita Bala, and L. Paul Chew. Optimistic parallelism requires abstractions. In PLDI, Jun 2007.

Digital Library

[19]

Jim Larus and Ravi Rajwar. Transactional Memory. Morgan & Claypool, 2006.

[20]

Nancy A. Lynch, Michael Merritt, William E. Weihl, and Alan Fekete. Atomic Transactions. Morgan Kaufmann, 1993.

[21]

Virendra J. Marathe, Michael F. Spear, Christopher Heriot, Athul Acharya, David Eisenstat, William N. Scherer III, and Michael L. Scott. Lowering the overhead of nonblocking software transactional memory. In TRANSACT, Jun 2006.

[22]

Chi Cao Minh, JaeWoong Chung, Christos Kozyrakis, and Kunle Olukotun. Stamp: Stanford transactional applications for multi-processing. In IEEE International Symposium on Workload Characterization (IISWC), Sep 2008.

[23]

Chi Cao Minh, Martin Trautmann, JaeWoong Chung, Austen McDonald, Nathan Bronson, Jared Casper, Christos Kozyrakis, and Kunle Olukotun. An effective hybrid transactional memory system with strong isolation guarantees. In ISCA, Jun 2007.

Digital Library

[24]

Michelle J. Moravan, Jayaram Bobba, Kevin E. Moore, Luke Yen,Mark D. Hill, Ben Liblit,MichaelM. Swift, and David A. Wood. Supporting nested transactional memory in Log™. In ASPLOS, Oct 2006.

Digital Library

[25]

J. Eliot Moss and Antony L. Hosking. Nested transactional memory: Model and preliminary architecture sketches. In SCOOL, Oct 2005.

[26]

Hany E. Ramadan, Christopher J. Rossbach, Owen Hofmann, and Emmett Witchel. Dependence-aware transactional memory. Technical Report TR-07-58, University of Texas at Austin, Computer Sciences Department, 2007.

[27]

Hany E. Ramadan, Christopher J. Rossbach, and Emmett Witchel. Dependence-aware transactions for increased concurrency. In MICRO, Nov 2008.

Digital Library

[28]

David P. Reed. Implementing atomic actions on decentralized data. ACM TOCS, 1(1), 1981.

Digital Library

[29]

Torvald Riegel, Christof Fetzer, and Pascal Felber. Snapshot isolation for software transactional memory. In TRANSACT, Jun 2006.

[30]

Torvald Riegel, Heiko Sturzrehm, Pascal Felber, and Christof Fetzer. From causal to z-linearizable transactional memory. Technical Report RR-I-07-02.1, Universite de Neuchatel, Institut d'Informatique, February 2007.

Digital Library

[31]

Nir Shavit and Dan Touitou. Software transactional memory. In PODC, Aug 1995.

Digital Library

[32]

Travis Skare and Christos Kozyrakis. Early release: Friend or foe? In Workshop on Transactional Memory Workloads, Jun 2006.

[33]

Michael Spear, Virendra Marathe, Luke Dalessandro, and Michael Scott. Privatization techniques for software transactional memory. In PODC, Aug 2007.

Digital Library

Cited By

Jin HWei SSha YYe CLiu HLiao X(2023)PMLiteDB: Streamlining Access Paths for High-Performance Persistent Memory Document Database SystemsIEEE Transactions on Computers10.1109/TC.2022.322437272:6(1778-1791)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1109/TC.2022.3224372
Pellegrini ADi Sanzo PPiccione AQuaglia F(2022)Design and implementation of a fully transparent partial abort support for software transactional memorySoftware: Practice and Experience10.1002/spe.313452:11(2456-2475)Online publication date: 8-Aug-2022
https://doi.org/10.1002/spe.3134
Mu SAngel SShasha D(2019)Deferred Runtime Pipelining for contentious multicore software transactionsProceedings of the Fourteenth EuroSys Conference 201910.1145/3302424.3303966(1-16)Online publication date: 25-Mar-2019
https://dl.acm.org/doi/10.1145/3302424.3303966
Show More Cited By

Index Terms

Committing conflicting transactions in an STM

Recommendations

Committing conflicting transactions in an STM
PPoPP '09: Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming

Dependence-aware transactional memory (DATM) is a recently proposed model for increasing concurrency of memory transactions without complicating their interface. DATM manages dependences between conflicting, uncommitted transactions so that they commit ...
Alternative Correctness Criteria for Concurrent Execution of Transactions in Multilevel Secure Databases

This paper investigates issues related to transaction concurrency control in multilevel secure databases. It demonstrates how the conflicts between the correctness requirements and the secrecy requirements can be reconciled by proposing two different ...
Allocating isolation levels to transactions
PODS '05: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

Serializability is a key property for executions of OLTP systems; without this, integrity constraints on the data can be violated due to concurrent activity. Serializability can be guaranteed regardless of application logic, by using a serializable ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 44, Issue 4

PPoPP '09

April 2009

294 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1594835

Issue’s Table of Contents

PPoPP '09: Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming
February 2009
322 pages
ISBN:9781605583976
DOI:10.1145/1504176
General Chair:
Daniel Reed
Microsoft Research, USA
,
Program Chair:
Vivek Sarkar
Rice University, USA

Copyright © 2009 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 February 2009

Published in SIGPLAN Volume 44, Issue 4

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
650
Total Downloads

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

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jin HWei SSha YYe CLiu HLiao X(2023)PMLiteDB: Streamlining Access Paths for High-Performance Persistent Memory Document Database SystemsIEEE Transactions on Computers10.1109/TC.2022.322437272:6(1778-1791)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1109/TC.2022.3224372
Pellegrini ADi Sanzo PPiccione AQuaglia F(2022)Design and implementation of a fully transparent partial abort support for software transactional memorySoftware: Practice and Experience10.1002/spe.313452:11(2456-2475)Online publication date: 8-Aug-2022
https://doi.org/10.1002/spe.3134
Mu SAngel SShasha D(2019)Deferred Runtime Pipelining for contentious multicore software transactionsProceedings of the Fourteenth EuroSys Conference 201910.1145/3302424.3303966(1-16)Online publication date: 25-Mar-2019
https://dl.acm.org/doi/10.1145/3302424.3303966
Saad MKishi MJing SHans SPalmieri RHollingsworth JKeidar I(2019)Processing transactions in a predefined orderProceedings of the 24th Symposium on Principles and Practice of Parallel Programming10.1145/3293883.3295730(120-132)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1145/3293883.3295730
Singh APeri SMonika GKumari A(2017)Performance comparison of various STM concurrency control protocols using synchrobench2017 National Conference on Parallel Computing Technologies (PARCOMPTECH)10.1109/PARCOMPTECH.2017.8068330(1-7)Online publication date: Feb-2017
https://doi.org/10.1109/PARCOMPTECH.2017.8068330
Pedrero MGutierrez ERomero SPlata O(2017)ReduxSTM: Optimizing STM designs for Irregular ApplicationsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2017.04.009107(114-133)Online publication date: Sep-2017
https://doi.org/10.1016/j.jpdc.2017.04.009
Koskinen EYang J(2016)Reducing crash recoverability to reachabilityACM SIGPLAN Notices10.1145/2914770.283764851:1(97-108)Online publication date: 11-Jan-2016
https://dl.acm.org/doi/10.1145/2914770.2837648
Wang ZMu SCui YYi HChen HLi JÖzcan FKoutrika GMadden S(2016)Scaling Multicore Databases via Constrained Parallel ExecutionProceedings of the 2016 International Conference on Management of Data10.1145/2882903.2882934(1643-1658)Online publication date: 26-Jun-2016
https://dl.acm.org/doi/10.1145/2882903.2882934
Koskinen EYang JBodik RMajumdar R(2016)Reducing crash recoverability to reachabilityProceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages10.1145/2837614.2837648(97-108)Online publication date: 11-Jan-2016
https://dl.acm.org/doi/10.1145/2837614.2837648
Zhao WYang WZhang HYang JLuo XZhu YYang MLuo C(2016)High-throughput state-machine replication using software transactional memoryThe Journal of Supercomputing10.1007/s11227-016-1747-272:11(4379-4398)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1007/s11227-016-1747-2
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 Issue’s Table of Contents