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

research-article

Optimizing hybrid transactional memory: the importance of nonspeculative operations

Authors:

Torvald Riegel,

Patrick Marlier,

Christof FetzerAuthors Info & Claims

SPAA '11: Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures

Pages 53 - 64

https://doi.org/10.1145/1989493.1989501

Published: 04 June 2011 Publication History

Abstract

Transactional memory (TM) is a speculative shared-memory synchronization mechanism used to speed up concurrent programs. Most current TM implementations are software-based (STM) and incur noticeable overheads for each transactional memory access. Hardware TM proposals (HTM) address this issue but typically suffer from other restrictions such as limits on the number of data locations that can be accessed in a transaction.

In this paper, we present several new hybrid TM algorithms that can execute HTM and STM transactions concurrently and can thus provide good performance over a large spectrum of workloads. The algorithms exploit the ability of some HTMs to have both speculative and nonspeculative (nontransactional) memory accesses within a transaction to decrease the transactions' runtime overhead, abort rates, and hardware capacity requirements. We evaluate implementations of these algorithms based on AMD's Advanced Synchronization Facility, an x86 instruction set extension proposal that has been shown to provide a sound basis for HTM.

References

[1]

Advanced Micro Devices, Inc. Advanced Synchronization Facility - Proposed Architectural Specification, 2.1 edition, Mar. 2009.

[2]

E. D. Berger, K. S. McKinley, R. D. Blumofe, and P. R. Wilson. Hoard: a scalable memory allocator for multithreaded applications. In Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, ASPLOS-IX, pages 117--128, New York, NY, USA, 2000. ACM.

Digital Library

[3]

Bratin Saha, Ali-Reza Adl Tabatabai, and Quinn Jacobson. Architectural Support for Software Transactional Memory. In International Symposium on Microarchitecture (MICRO'06), 2006.

Digital Library

[4]

C. Cao Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford Transactional Applications for Multi-Processing. In IISWC '08: Proceedings of The IEEE International Symposium on Workload Characterization, September 2008.

[5]

D. Christie, J.-W. Chung, S. Diestelhorst, M. Hohmuth, M. Pohlack, C. Fetzer, M. Nowack, T. Riegel, P. Felber, P. Marlier, and E. Riviere. Evaluation of AMD's Advanced Synchronization Facility Within a Complete Transactional Memory Stack. In EuroSys '10: Proceedings of the 5th European conference on Computer systems, pages 27--40, New York, NY, USA, 2010. ACM.

Digital Library

[6]

J. Chung, D. Christie, M. Pohlack, S. Diestelhorst, M. Hohmuth, and L. Yen. Compilation of Thoughts about AMD Advanced Synchronization Facility and First-Generation Hardware Transactional Memory Support. In TRANSACT, 2010.

[7]

L. Dalessandro, F. Carouge, S. White, Y. Lev, M. Moir, M. L. Scott, and M. F. Spear. Hybrid NOrec: A Case Study in the Effectiveness of Best Effort Hardware Transactional Memory. In Architectural Support for Programming Languages and Operating Systems (ASPLOS), Mar. 2011.

Digital Library

[8]

L. Dalessandro, M. F. Spear, and M. L. Scott. NOrec: streamlining S™ by abolishing ownership records. In PPoPP '10: Proceedings of the 15th ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 67--78, New York, NY, USA, 2010. ACM.

Digital Library

[9]

David Dice, Ori Shalev, and Nir Shavit. Transactional Locking II. In S. Dolev, editor, DISC, volume 4167 of Lecture Notes in Computer Science, pages 194--208. Springer, 2006.

Digital Library

[10]

D. Dice, Y. Lev, M. Moir, and D. Nussbaum. Early experience with a commercial hardware transactional memory implementation. In ASPLOS '09: Proceeding of the 14th international conference on Architectural support for programming languages and operating systems, pages 157--168, New York, NY, USA, 2009. ACM.

Digital Library

[11]

S. Diestelhorst, M. Pohlack, M. Hohmuth, D. Christie, J.-W. Chung, and L. Yen. Implementing AMD's Advanced Synchronization Facility in an out-of-order x86 core. In TRANSACT, 2010.

[12]

P. Felber, C. Fetzer, P. Marlier, M. Nowack, and T. Riegel. Brief Announcement: Hybrid Time-Based Transactional Memory. In N. Lynch and A. Shvartsman, editors, Distributed Computing, volume 6343 of Lecture Notes in Computer Science, pages 124--126. Springer Berlin / Heidelberg, 2010. The full version is available as technical report TUD-FI10-06-Nov.2010.

Digital Library

[13]

P. Felber, C. Fetzer, P. Marlier, and T. Riegel. Time-based Software Transactional Memory. IEEE Trans. Parallel Distrib. Syst., 21:1793--1807, December 2010.

Digital Library

[14]

O. S. Hofmann, C. J. Rossbach, and E. Witchel. Maximum benefit from a minimal H™. In ASPLOS '09: Proceeding of the 14th international conference on Architectural support for programming languages and operating systems, pages 145--156, New York, NY, USA, 2009. ACM.

Digital Library

[15]

Intel. Draft Specification of Transactional Language Constructs for C++. Intel, IBM, Sun, 1.0 edition, Aug. 2009.

[16]

ISO. Programming Languages -- C++, ISO/IEC JTC1 SC22 WG21 N 3092 edition, Mar. 2010.

[17]

Y. Lev, M. Moir, and D. Nussbaum. Ph™: Phased Transactional Memory. In TRANSACT '07: 2nd Workshop on Transactional Computing, aug 2007.

[18]

V. Menon, S. Balensiefer, T. Shpeisman, A.-R. Adl-Tabatabai, R. L. Hudson, B. Saha, and A. Welc. Practical Weak-Atomicity Semantics for Java S™. In SPAA '08: Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, pages 314--325, New York, NY, USA, 2008. ACM.

Digital Library

[19]

Michael F. Spear, Arrvindh Shriraman, Luke Dalessandro, Sandhya Dwarkadas, and Michael L. Scott. Nonblocking Transactions Without Indirection Using Alert-on-Update. In 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2007.

Digital Library

[20]

Pascal Felber, Christof Fetzer, and Torvald Riegel. Dynamic Performance Tuning of Word-Based Software Transactional Memory. In Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2008.

Digital Library

[21]

Peter Damron, Alexandra Fedorova, Yossi Lev, Victor Luchangco, Mark Moir, and Daniel Nussbaum. Hybrid transactional memory. In ASPLOS-XII: Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, pages 336--346, New York, NY, USA, 2006. ACM Press.

Digital Library

[22]

R. Rajwar and J. R. Goodman. Speculative lock elision: enabling highly concurrent multithreaded execution. In MICRO 34: Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, pages 294--305, Washington, DC, USA, 2001. IEEE Computer Society.

Digital Library

[23]

T. Riegel, P. Marlier, M. Nowack, P. Felber, and C. Fetzer. Optimizing Hybrid Transactional Memory: The Importance of Nonspeculative Operations. Technical Report TUD-FI10-06-Nov.2010, Technische Universitat Dresden, November 2010. Full version of the DISC 2010 brief announcement.

[24]

Sanjeev Kumar, Michael Chu, Christopher J. Hughes, Partha Kundu, and Anthony Nguyen. Hybrid transactional memory. In PPoPP '06: Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 209--220, New York, NY, USA, 2006. ACM Press.

Digital Library

[25]

Torvald Riegel, Pascal Felber, and Christof Fetzer. A Lazy Snapshot Algorithm with Eager Validation. In 20th International Symposium on Distributed Computing (DISC), September 2006.

Digital Library

Cited By

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
Bhat KKouwe EBos HGiuffrida C(2021)FIRestarter: Practical Software Crash Recovery with Targeted Library-level Fault Injection2021 51st Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)10.1109/DSN48987.2021.00048(363-375)Online publication date: Jun-2021
https://doi.org/10.1109/DSN48987.2021.00048
Yates RScott MHollingsworth JKeidar I(2019)Leveraging hardware TM in HaskellProceedings of the 24th Symposium on Principles and Practice of Parallel Programming10.1145/3293883.3295711(94-106)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1145/3293883.3295711
Show More Cited By

Index Terms

Optimizing hybrid transactional memory: the importance of nonspeculative operations
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Concurrent programming languages

Recommendations

Hybrid transactional memory
PPoPP '06: Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming

High performance parallel programs are currently difficult to write and debug. One major source of difficulty is protecting concurrent accesses to shared data with an appropriate synchronization mechanism. Locks are the most common mechanism but they ...
Hybrid transactional memory
Proceedings of the 2006 ASPLOS Conference

Transactional memory (TM) promises to substantially reduce the difficulty of writing correct, efficient, and scalable concurrent programs. But "bounded" and "best-effort" hardware TM proposals impose unreasonable constraints on programmers, while more ...
Hybrid transactional memory
Proceedings of the 2006 ASPLOS Conference

Transactional memory (TM) promises to substantially reduce the difficulty of writing correct, efficient, and scalable concurrent programs. But "bounded" and "best-effort" hardware TM proposals impose unreasonable constraints on programmers, while more ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '11: Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures

June 2011

404 pages

ISBN:9781450307437

DOI:10.1145/1989493

Co-chairs:
Friedhelm Meyer auf der Heide
University of Paderborn, Germany
,
Rajmohan Rajaraman
Northeastern University, USA

Copyright © 2011 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

In-Cooperation

EATCS: European Association for Theoretical Computer Science

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

transactional memory

Qualifiers

Research-article

Conference

SPAA '11

Sponsor:

SPAA '11: 23rd ACM Symposium on Parallelism in Algorithms and Architectures

June 4 - 6, 2011

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Upcoming Conference

SPAA '25

Sponsor:
sigact
sigact

37th ACM Symposium on Parallelism in Algorithms and Architectures

July 28 - August 1, 2025

Portland , OR , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
233
Total Downloads

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

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

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
Bhat KKouwe EBos HGiuffrida C(2021)FIRestarter: Practical Software Crash Recovery with Targeted Library-level Fault Injection2021 51st Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)10.1109/DSN48987.2021.00048(363-375)Online publication date: Jun-2021
https://doi.org/10.1109/DSN48987.2021.00048
Yates RScott MHollingsworth JKeidar I(2019)Leveraging hardware TM in HaskellProceedings of the 24th Symposium on Principles and Practice of Parallel Programming10.1145/3293883.3295711(94-106)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1145/3293883.3295711
de Carvalho JAraujo GBaldassin A(2019)The Case for Phase-Based Transactional MemoryIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.286171230:2(459-472)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1109/TPDS.2018.2861712
Raminhas PIssa SRomano PEl-Araby EEl-Ghazawi TPanda D(2018)Enhancing efficiency of hybrid transactional memory via dynamic data partitioning schemesProceedings of the 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing10.1109/CCGRID.2018.00020(51-61)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1109/CCGRID.2018.00020
Alistarh DKopinsky JKuznetsov PRavi SShavit N(2018)Inherent limitations of hybrid transactional memoryDistributed Computing10.1007/s00446-017-0305-331:3(167-185)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s00446-017-0305-3
Qayum MBadawy ACook JJacob B(2017)DyAdHyTMProceedings of the International Symposium on Memory Systems10.1145/3132402.3132442(327-336)Online publication date: 2-Oct-2017
https://dl.acm.org/doi/10.1145/3132402.3132442
Brown TSchiller ESchwarzmann A(2017)A Template for Implementing Fast Lock-free Trees Using HTMProceedings of the ACM Symposium on Principles of Distributed Computing10.1145/3087801.3087834(293-302)Online publication date: 25-Jul-2017
https://dl.acm.org/doi/10.1145/3087801.3087834
de Carvalho JAraujo GBaldassin AGropp WBeckman PLi ZCazorla F(2017)Revisiting phased transactional memoryProceedings of the International Conference on Supercomputing10.1145/3079079.3079094(1-10)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3079079.3079094
Mohamedin MPalmieri RHassan ARavindran B(2017)Managing Resource Limitation of Best-Effort HTMIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2017.266841528:8(2299-2313)Online publication date: 1-Aug-2017
https://doi.org/10.1109/TPDS.2017.2668415
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