article

An integrated hardware-software approach to flexible transactional memory

Authors:

Arrvindh Shriraman,

Michael F. Spear,

Hemayet Hossain,

Virendra J. Marathe,

Sandhya Dwarkadas,

Michael L. ScottAuthors Info & Claims

ACM SIGARCH Computer Architecture News, Volume 35, Issue 2

Pages 104 - 115

https://doi.org/10.1145/1273440.1250676

Published: 09 June 2007 Publication History

Abstract

There has been considerable recent interest in both hardware andsoftware transactional memory (TM). We present an intermediateapproach, in which hardware serves to accelerate a TM implementation controlled fundamentally by software. Specifically, we describe an alert on update mechanism (AOU) that allows a thread to receive fast, asynchronous notification when previously-identified lines are written by other threads, and a programmable data isolation mechanism (PDI) that allows a thread to hide its speculative writes from other threads, ignoring conflicts, until software decides to make them visible. These mechanisms reduce bookkeeping, validation, and copying overheads without constraining software policy on a host of design decisions.

We have used AOU and PDI to implement a hardwareacceleratedsoftware transactional memory system we call RTM. We have also used AOU alone to create a simpler "RTM-Lite". Across a range of microbenchmarks, RTM outperforms RSTM, a publicly available software transactional memory system, by as much as 8.7x (geometric mean of 3.5x) in single-thread mode. At 16 threads, it outperforms RSTM by as much as 5x, with an average speedup of 2x. Performance degrades gracefully when transactions overflow hardware structures. RTM-Lite is slightly faster than RTM for transactions that modify only small objects; full RTM is significantly faster when objects are large. In a strongargument for policy flexibility, we find that the choice between eager (first-access) and lazy (commit-time) conflict detection can lead to significant performance differences in both directions, depending on application characteristics.

References

[1]

C. S. Ananian, K. Asanovic, B. C. Kuszmaul, C. E. Leiserson, and S. Lie. Unbounded Transactional Memory. In Proc. of the 11th Intl. Symp. on High Performance Computer Architecture, San Francisco, CA, Feb. 2005.

Digital Library

[2]

C. Blundell, E. C. Lewis, and M. M. K. Martin. Subtleties of Transactional Memory Atomicity Semantics. ACM SIGARCH Computer Architecture News, 5(2), Nov. 2006.

Digital Library

[3]

W. Chuang, S. Narayanasamy, G. Venkatesh, J. Sampson, M. V. Biesbrouck, G. Pokam, B. Calder, and O. Colavin. Unbounded Page-Based Transactional Memory. In Proc. of the 12th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems, San Jose, CA, Oct. 2006.

Digital Library

[4]

P. Damron, A. Fedorova, Y. Lev, V. Luchangco, M. Moir, and D. Nussbaum. Hybrid Transactional Memory. In Proc. of the 12th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems, San Jose, CA, Oct. 2006.

Digital Library

[5]

K. Fraser and T. Harris. Concurrent Programming Without Locks. Submitted for publication, 2004. Available as research.microsoft.com/~tharris/drafts/cpwl-submission.pdf.

Digital Library

[6]

R. Guerraoui, M. Herlihy, and B. Pochon. Polymorphic Contention Management in SXM. In Proc. of the 19th Intl. Symp. on Distributed Computing, Cracow, Poland, Sept. 2005.

Digital Library

[7]

L. Hammond, V. Wong, M. Chen, B. Hertzberg, B. Carlstrom, M. Prabhu, H. Wijaya, C. Kozyrakis, and K. Olukotun. Transactional Memory Coherence and Consistency. In Proc. of the 31st Intl. Symp. on Computer Architecture, Munchen, Germany, June 2004.

Digital Library

[8]

M. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer III. Software Transactional Memory for Dynamic-sized Data Structures. In Proc. of the 22nd ACM Symp. on Principles of Distributed Computing, Boston, MA, July 2003.

Digital Library

[9]

M. Herlihy and J. E. Moss. Transactional Memory: Architectural Support for Lock-Free Data Structures. In Proc. of the 20th Intl. Symp. on Computer Architecture, San Diego, CA, May 1993. Expanded version available as CRL 92/07, DEC Cambridge Research Laboratory, Dec. 1992.

Digital Library

[10]

S. Kumar, M. Chu, C. J. Hughes, P. Kundu, and A. Nguyen. Hybrid Transactional Memory. In Proc. of the 11th ACM Symp. on Principles and Practice of Parallel Programming, New York, NY, Mar. 2006.

Digital Library

[11]

J. R. Larus and R. Rajwar. Transactional Memory, Synthesis Lectures on Computer Architecture. Morgan & Claypool, 2007.

Digital Library

[12]

V. J. Marathe, W. N. Scherer III, and M. L. Scott. Adaptive Software Transactional Memory. In Proc. of the 19th Intl. Symp. on Distributed Computing, Cracow, Poland, Sept. 2005.

Digital Library

[13]

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 ACM SIGPLAN Workshop on Transactional Computing, Ottawa, ON, Canada, June 2006. Expanded version available as TR 893, Dept. of Computer Science, Univ. of Rochester, Mar. 2006.

[14]

J. F. Martinez and J. Torrellas. Speculative Synchronization: Applying Thread-Level Speculation to Explicitly Parallel Applications. In Proc. of the 10th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems, San Jose, CA, Oct. 2002.

Digital Library

[15]

M. M. K. Martin, D. J. Sorin, B. M. Beckmann, M. R. Marty, M. Xu, A. R. Alameldeen, K. E. Moore, M. D. Hill, and D. A. Wood. Multifacetâs General Execution-driven Multiprocessor Simulator (GEMS) Toolset. In ACM SIGARCH Computer Architecture News, Sept. 2005.

Digital Library

[16]

K. E. Moore, J. Bobba, M. J. Moravan, M. D. Hill, and D. A. Wood. LogTM: Log-based Transactional Memory. In Proc. of the 12th Intl. Symp. on High Performance Computer Architecture, Austin, TX, Feb. 2006.

[17]

J. E. B. Moss. Open Nested Transactions: Semantics and Support. In Proc. of the 4th IEEE Workshop on Memory Performance Issues, Austin, TX, Feb. 2006.

[18]

R. Rajwar and J. R. Goodman. Speculative Lock Elision: Enabling Highly Concurrent Multithreaded Execution. In Proc. of the 34th Intl. Symp. on Microarchitecture, Austin, TX, Dec. 2001.

Digital Library

[19]

R. Rajwar and J. R. Goodman. Transactional Lock-Free Execution of Lock-Based Programs. In Proc. of the 10th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems, San Jose, CA, Oct. 2002.

Digital Library

[20]

R. Rajwar, M. Herlihy, and K. Lai. Virtualizing Transactional Memory. In Proc. of the 32nd Intl. Symp. on Computer Architecture, Madison, WI, June 2005.

Digital Library

[21]

B. Saha, A.-R. Adl-Tabatabai, and Q. Jacobson. Architectural Support for Software Transactional Memory. In Proc. of the 39th Intl. Symp. on Microarchitecture, Dec. 2006. Orlando, FL.

Digital Library

[22]

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 Proc. of the 11th ACM Symp. on Principles and Practice of Parallel Programming, New York, NY, Mar. 2006.

Digital Library

[23]

W. N. Scherer III and M. L. Scott. Advanced Contention Management for Dynamic Software Transactional Memory. In Proc. of the 24th ACM Symp. on Principles of Distributed Computing, Las Vegas, NV, July 2005.

Digital Library

[24]

N. Shavit and D. Touitou. Software Transactional Memory. Distributed Computing, 10(2):99--116, Feb. 1997. Originally presented at the 14th ACM Symp. on Principles of Distributed Computing, Aug. 1995.

Digital Library

[25]

A. Shriraman, M. F. Spear, H. Hossain, S. Dwarkadas, and M. L. Scott. An Integrated Hardware-Software Approach to Flexible Transactional Memory. TR 910, Dept. of Computer Science, Univ. of Rochester, Dec. 2006.

[26]

A. Shriraman, V. J. Marathe, S. Dwarkadas, M. L. Scott, D. Eisenstat, C. Heriot, W. N. Scherer III, and M. F. Spear. Hardware Acceleration of Software Transactional Memory. In ACM SIGPLAN Workshop on Transactional Computing, Ottawa, ON, Canada, June 2006. Expanded version available as TR 887, Dept. of Computer Science, Univ. of Rochester, Dec. 2005, revised Mar. 2006.

[27]

M. F. Spear, V. J. Marathe, W. N. Scherer III, and M. L. Scott. Conflict Detection and Validation Strategies for Software Transactional Memory. In Proc. of the 20th Intl. Symp. on Distributed Computing, Stockholm, Sweden, Sept. 2006.

Digital Library

[28]

M. F. Spear, A. Shriraman, H. Hossain, S. Dwarkadas, and M. L. Scott. Alert-on-Update: A Communication Aid for Shared Memory Multiprocessors (poster paper). In Proc. of the 12th ACM Symp. on Principles and Practice of Parallel Programming, San Jose, CA, Mar. 2007.

Digital Library

[29]

M. F. Spear, A. Shriraman, L. Dalessandro, S. Dwarkadas, and M. L. Scott. Nonblocking Transactions Without Indirection Using Alert-on-Update. In Proc. of the 19th Annual ACM Symp. on Parallelism in Algorithms and Architectures, San Diego, CA, June 2007.

Digital Library

[30]

M. F. Spear, V. J. Marathe, L. Dalessandro, and M. L. Scott. Privatization Techniques for Software Transactional Memory. TR 915, Dept. of Computer Science, Univ. of Rochester, Feb. 2007.

Cited By

Scott M(2013)Shared-Memory SynchronizationSynthesis Lectures on Computer Architecture10.2200/S00499ED1V01Y201304CAC0238:2(1-221)Online publication date: 12-Jun-2013
https://doi.org/10.2200/S00499ED1V01Y201304CAC023
Casper JOguntebi THong SBronson NKozyrakis COlukotun K(2011)Hardware acceleration of transactional memory on commodity systemsACM SIGPLAN Notices10.1145/1961296.195037246:3(27-38)Online publication date: 5-Mar-2011
https://dl.acm.org/doi/10.1145/1961296.1950372
Casper JOguntebi THong SBronson NKozyrakis COlukotun K(2011)Hardware acceleration of transactional memory on commodity systemsACM SIGARCH Computer Architecture News10.1145/1961295.195037239:1(27-38)Online publication date: 5-Mar-2011
https://dl.acm.org/doi/10.1145/1961295.1950372
Show More Cited By

Index Terms

An integrated hardware-software approach to flexible transactional memory

Recommendations

An integrated hardware-software approach to flexible transactional memory
ISCA '07: Proceedings of the 34th annual international symposium on Computer architecture

There has been considerable recent interest in both hardware andsoftware transactional memory (TM). We present an intermediateapproach, in which hardware serves to accelerate a TM implementation controlled fundamentally by software. Specifically, we ...
Flexible Decoupled Transactional Memory Support

A high-concurrency transactional memory (TM) implementation needs to track concurrent accesses, buffer speculative updates, and manage conflicts. We present a system, FlexTM (FLEXible Transactional Memory), that coordinates four decoupled hardware ...
Flexible Decoupled Transactional Memory Support
ISCA '08: Proceedings of the 35th Annual International Symposium on Computer Architecture

A high-concurrency transactional memory (TM) implementation needs to track concurrent accesses, buffer speculative updates, and manage conflicts. We present a system, FlexTM (FLEXible Transactional Memory), that coordinates four decoupled hardware ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGARCH Computer Architecture News

ACM SIGARCH Computer Architecture News Volume 35, Issue 2

May 2007

527 pages

ISSN:0163-5964

DOI:10.1145/1273440

Issue’s Table of Contents

ISCA '07: Proceedings of the 34th annual international symposium on Computer architecture
June 2007
542 pages
ISBN:9781595937063
DOI:10.1145/1250662
General Chair:
Dean Tullsen
University of California, San Diego
,
Program Chair:
Brad Calder
Microsoft & University of California, San Diego

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2007

Published in SIGARCH Volume 35, Issue 2

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

71
Total Citations
View Citations
1,053
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Scott M(2013)Shared-Memory SynchronizationSynthesis Lectures on Computer Architecture10.2200/S00499ED1V01Y201304CAC0238:2(1-221)Online publication date: 12-Jun-2013
https://doi.org/10.2200/S00499ED1V01Y201304CAC023
Casper JOguntebi THong SBronson NKozyrakis COlukotun K(2011)Hardware acceleration of transactional memory on commodity systemsACM SIGPLAN Notices10.1145/1961296.195037246:3(27-38)Online publication date: 5-Mar-2011
https://dl.acm.org/doi/10.1145/1961296.1950372
Casper JOguntebi THong SBronson NKozyrakis COlukotun K(2011)Hardware acceleration of transactional memory on commodity systemsACM SIGARCH Computer Architecture News10.1145/1961295.195037239:1(27-38)Online publication date: 5-Mar-2011
https://dl.acm.org/doi/10.1145/1961295.1950372
Casper JOguntebi THong SBronson NKozyrakis COlukotun KGupta RMowry T(2011)Hardware acceleration of transactional memory on commodity systemsProceedings of the sixteenth international conference on Architectural support for programming languages and operating systems10.1145/1950365.1950372(27-38)Online publication date: 5-Mar-2011
https://dl.acm.org/doi/10.1145/1950365.1950372
Chen YWang SLu SSankaralingam K(2019)Applying Transactional Memory for Concurrency-Bug Failure Recovery in Production RunsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.287765630:5(990-1006)Online publication date: 1-May-2019
https://doi.org/10.1109/TPDS.2018.2877656
Ren XLis M(2018)High-Performance GPU Transactional Memory via Eager Conflict Detection2018 IEEE International Symposium on High Performance Computer Architecture (HPCA)10.1109/HPCA.2018.00029(235-246)Online publication date: Feb-2018
https://doi.org/10.1109/HPCA.2018.00029
Nguyen DPingali K(2017)What Scalable Programs Need from Transactional MemoryACM SIGARCH Computer Architecture News10.1145/3093337.303775045:1(105-118)Online publication date: 4-Apr-2017
https://dl.acm.org/doi/10.1145/3093337.3037750
Nguyen DPingali K(2017)What Scalable Programs Need from Transactional MemoryACM SIGPLAN Notices10.1145/3093336.303775052:4(105-118)Online publication date: 4-Apr-2017
https://dl.acm.org/doi/10.1145/3093336.3037750
Nguyen DPingali K(2017)What Scalable Programs Need from Transactional MemoryACM SIGOPS Operating Systems Review10.1145/3093315.303775051:2(105-118)Online publication date: 4-Apr-2017
https://doi.org/10.1145/3093315.3037750
Nguyen DPingali KChen YTemam OCarter J(2017)What Scalable Programs Need from Transactional MemoryProceedings of the Twenty-Second International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3037697.3037750(105-118)Online publication date: 4-Apr-2017
https://dl.acm.org/doi/10.1145/3037697.3037750
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