More Web Proxy on the site http://driver.im/

research-article

Stretching transactional memory

Authors:

Aleksandar Dragojević,

Rachid Guerraoui,

Michal KapalkaAuthors Info & Claims

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

Pages 155 - 165

https://doi.org/10.1145/1542476.1542494

Published: 15 June 2009 Publication History

Abstract

Transactional memory (TM) is an appealing abstraction for programming multi-core systems. Potential target applications for TM, such as business software and video games, are likely to involve complex data structures and large transactions, requiring specific software solutions (STM). So far, however, STMs have been mainly evaluated and optimized for smaller scale benchmarks.

We revisit the main STM design choices from the perspective of complex workloads and propose a new STM, which we call SwissTM. In short, SwissTM is lock- and word-based and uses (1) optimistic (commit-time) conflict detection for read/write conflicts and pessimistic (encounter-time) conflict detection for write/write conflicts, as well as (2) a new two-phase contention manager that ensures the progress of long transactions while inducing no overhead on short ones. SwissTM outperforms state-of-the-art STM implementations, namely RSTM, TL2, and TinySTM, in our experiments on STMBench7, STAMP, Lee-TM and red-black tree benchmarks.

Beyond SwissTM, we present the most complete evaluation to date of the individual impact of various STM design choices on the ability to support the mixed workloads of large applications.

References

[1]

M. Abadi, A. Birrell, T. Harris, and M. Isard. Semantics of transactional memory and automatic mutual exclusion. In POPL, 2008.

Digital Library

[2]

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

Digital Library

[3]

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

Digital Library

[4]

M. Ansari, C. Kotselidis, K. Jarvis, M. Lujan, C. Kirkham, and I. Watson. Lee-TM: A non-trivial benchmark for transactional memory. In ICA3PP, 2008.

Digital Library

[5]

The atomic ops project. http://www.hpl.hp.com/research/linux/atomic_ops.

[6]

C. Blundell, H. Cain, M. M. Michael, P. Wu, S. Chiras, and S. Chatterjee. Software transactional memory: Why is it only a research toy? ACM Queue, Sept. 2008.

Digital Library

[7]

J. Cachopo and A. Rito-Silva. Versioned boxes as the basis for memory transactions. Sci. Comput. Program., 63(2):172--185, 2006.

Digital Library

[8]

C. Cao Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford transactional applications for multi-processing. In IISWC, 2008.

[9]

D. Dice, M. Herlihy, D. Lea, Y. Lev, V. Luchangco, W. Mesard, M. Moir, K. Moore, and D. Nussbaum. Applications of the adaptive transactional memory test platform. In TRANSACT, 2008.

[10]

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

Digital Library

[11]

A. Dragojevi, R. Guerraoui, and M. Kapalka. Dividing transactional memories by zero. In TRANSACT, 2008.

[12]

R. Ennals. Efficient software transactional memory. Technical report, Intel Research Cambridge, Jan 2005.

[13]

K. P. Eswaran, J. N. Gray, R. A. Lorie, and I. L. Traiger. The notions of consistency and predicate locks in a database system. Commun. ACM, 19(11): 624--633, 1976.

Digital Library

[14]

P. Felber, C. Fetzer, U. Müller, T. Riegel, M. Susskraut, and H. Sturzrehm. Transactifying applications using an open compiler framework. In TRANSACT, 2007.

[15]

R. Guerraoui, M. Herlihy, and B. Pochon. Polymorphic Contention Management. In DISC, 2005.

Digital Library

[16]

R. Guerraoui, M. Herlihy, and B. Pochon. Toward a theory of transactional contention managers. In PODC, 2005.

Digital Library

[17]

R. Guerraoui and M. Kapalka. On the correctness of transactional memory. In PPoPP, 2008.

Digital Library

[18]

R. Guerraoui, M. Kapalka, and J. Vitek. STMBench7: A benchmark for software transactional memory. In EuroSys, 2007.

Digital Library

[19]

T. Harris and K. Fraser. Revocable locks for non-blocking programming. In PPoPP, 2005.

Digital Library

[20]

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

Digital Library

[21]

V. J. Marathe, M. F. Spear, C. Heriot, A. Acharya, D. Eisenstat, W. N. Scherer III, and M. L. Scott. Lowering the overhead of software transactional memory. In TRANSACT, 2006.

[22]

V. J. Marathe, M. F. Spear, and M. L. Scott. Scalable techniques for transparent privatization in software transactional memory. In ICPP, 2008.

Digital Library

[23]

Y. Ni, A. Welc, A.-R. Adl-Tabatabai, M. Bach, S. Berkowits, J. Cownie, R. Geva, S. Kozhukow, R. Narayanaswamy, J. Olivier, S. Preis, B. Saha, A. Tal, and X. Tian. Design and implementation of transactional constructs for c/c++. In OOPSLA, 2008.

Digital Library

[24]

C. H. Papadimitriou. The serializability of concurrent database updates. J. ACM, 26(4), 1979.

Digital Library

[25]

T. R. Pascal Felber and C. Fetzer. Dynamic performance tuning of word-based software transactional memory. In PPoPP, 2008.

Digital Library

[26]

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

Digital Library

[27]

T. Riegel, P. Felber, and C. Fetzer. A lazy snapshot algorithm with eager validation. In DISC, 2006. RSTM home page. http://www.cs.rochester.edu/research/synchronization/rstm.

Digital Library

[28]

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

Digital Library

[29]

W. N. Scherer III and M. L. Scott. Contention management in dynamic software transactional memory. In CSJP, 2004.

Digital Library

[30]

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

Digital Library

[31]

M. F. Spear, V. J. Marathe, L. Dalessandro, and M. L. Scott. Privatization techniques for software transactional memory. In PODC), 2007.

Digital Library

[32]

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

Digital Library

[33]

T. Sweeney. The next mainstream programming language: a game developer's perspective. Invited talk at POPL, 2006.

Digital Library

[34]

I. William N. Scherer and M. L. Scott. Advanced contention management for dynamic software transactional memory. In PODC, 2005.

Digital Library

[35]

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, 2008.

Digital Library

Cited By

Nunes DCastro DRomano P(2023)CSMV: A highly scalable multi-versioned software transactional memory for GPUsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2023.04.002180(104701)Online publication date: Oct-2023
https://doi.org/10.1016/j.jpdc.2023.04.002
Nunes DCastro DRomano P(2022)CSMV: A Highly Scalable Multi-Versioned Software Transactional Memory for GPUs2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS53621.2022.00057(526-536)Online publication date: May-2022
https://doi.org/10.1109/IPDPS53621.2022.00057
Poudel PSharma G(2021)Adaptive Versioning in Transactional Memory SystemsAlgorithms10.3390/a1406017114:6(171)Online publication date: 31-May-2021
https://doi.org/10.3390/a14060171
Show More Cited By

Index Terms

Stretching transactional memory

Recommendations

Stretching transactional memory
PLDI '09

Transactional memory (TM) is an appealing abstraction for programming multi-core systems. Potential target applications for TM, such as business software and video games, are likely to involve complex data structures and large transactions, requiring ...
On speculative replication of transactional systems

In this paper we investigate, from a theoretical perspective, the problem of how to build speculative replication protocols for transactional systems layered on top of an Optimistic Atomic Broadcast (OAB) service. The OAB service provides an early, ...
Safe privatization in transactional memory
PPoPP '18

Transactional memory (TM) facilitates the development of concurrent applications by letting the programmer designate certain code blocks as atomic. Programmers using a TM often would like to access the same data both inside and outside transactions, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

June 2009

492 pages

ISBN:9781605583921

DOI:10.1145/1542476

General Chair:
Michael Hind
IBM Research, USA
,
Program Chair:
Amer Diwan
University of Colorado at Boulder, USA

ACM SIGPLAN Notices Volume 44, Issue 6
PLDI '09
June 2009
478 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1543135
Issue’s Table of Contents

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PLDI '09

Sponsor:

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

June 15 - 21, 2009

Dublin, Ireland

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

168
Total Citations
View Citations
901
Total Downloads

Downloads (Last 12 months)22
Downloads (Last 6 weeks)5

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nunes DCastro DRomano P(2023)CSMV: A highly scalable multi-versioned software transactional memory for GPUsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2023.04.002180(104701)Online publication date: Oct-2023
https://doi.org/10.1016/j.jpdc.2023.04.002
Nunes DCastro DRomano P(2022)CSMV: A Highly Scalable Multi-Versioned Software Transactional Memory for GPUs2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS53621.2022.00057(526-536)Online publication date: May-2022
https://doi.org/10.1109/IPDPS53621.2022.00057
Poudel PSharma G(2021)Adaptive Versioning in Transactional Memory SystemsAlgorithms10.3390/a1406017114:6(171)Online publication date: 31-May-2021
https://doi.org/10.3390/a14060171
D. Jardim AOliveira KJ. Cardoso DDi Domenico DR. Du Bois AH. Cavalheiro G(2021)An extension for Transactional Memory in OpenMPProceedings of the 25th Brazilian Symposium on Programming Languages10.1145/3475061.3475089(58-65)Online publication date: 27-Sep-2021
https://dl.acm.org/doi/10.1145/3475061.3475089
Huang YQian WKohler ELiskov BShrira L(2020)Opportunities for optimism in contended main-memory multicore transactionsProceedings of the VLDB Endowment10.14778/3377369.337737313:5(629-642)Online publication date: 19-Feb-2020
https://dl.acm.org/doi/10.14778/3377369.3377373
de Carvalho JHonorio BBaldassin AAraujo G(2020)Improving Transactional Code Generation via Variable Annotation and Barrier Elision2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS47924.2020.00107(1008-1017)Online publication date: May-2020
https://doi.org/10.1109/IPDPS47924.2020.00107
Kaffes KYadwadkar NKozyrakis C(2019)Centralized Core-granular Scheduling for Serverless FunctionsProceedings of the ACM Symposium on Cloud Computing10.1145/3357223.3362709(158-164)Online publication date: 20-Nov-2019
https://dl.acm.org/doi/10.1145/3357223.3362709
Kim JMathew AKashyap SRamanathan MMin CBahar IHerlihy MWitchel ELebeck A(2019)MV-RLUProceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3297858.3304040(779-792)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1145/3297858.3304040
Yu XXia YPavlo ASanchez DRudolph LDevadas S(2018)SundialProceedings of the VLDB Endowment10.14778/3231751.323176311:10(1289-1302)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.14778/3231751.3231763
Mohamedin MPeluso SKishi MHassan APalmieri R(2018)NemoProceedings of the 47th International Conference on Parallel Processing10.1145/3225058.3225123(1-10)Online publication date: 13-Aug-2018
https://dl.acm.org/doi/10.1145/3225058.3225123
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.

Media

Figures

Other

Tables

View Table of Contents