research-article

Optimizing transactions for captured memory

Authors:

Aleksandar Dragojevic,

Ali-Reza Adl-TabatabaiAuthors Info & Claims

SPAA '09: Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures

Pages 214 - 222

https://doi.org/10.1145/1583991.1584049

Published: 11 August 2009 Publication History

Abstract

In this paper, we identify transaction-local memory as a major source of overhead from compiler instrumentation in software transactional memory (STM). Transaction-local memory is memory allocated inside a transaction, which cannot escape (i.e., is captured by) the allocating transaction. Accesses to such memory do not require calls to STM memory access functions (also called STM barriers). A compiler unaware of that, however, may translate simple memory load/store operations accessing such memory into more expensive STM barriers. This presents us opportunities to improve STM performance. Our measurements with the STAMP benchmark suite (version 0.9.9) revealed that as many as 60% of the STM barriers generated by our baseline compiler can be accesses to captured memory, which include 90% of the write barriers and 45% of the read barriers. We propose runtime and compiler optimizations to elide STM barriers to captured memory. Similar techniques can also be used to elide barriers for accesses to thread-local and read-only data. We implemented those optimizations in the Intel C++ STM compiler. Our experiments with the STAMP benchmark suite on a Intel Dunnington system (with 24 cores in a 4-node SMP system) showed that upto 18% performance improvement could be achieved at 16 threads.

References

[1]

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

Digital Library

[2]

Emery D. Berger, Kathryn S. McKinley, Robert D. Blumofe, and Paul R. Wilson. Hoard: a scalable memory allocator for multithreaded applications. SIGPLAN Not., 35(11):117--128, 2000.

Digital Library

[3]

Chi Cao Minh, JaeWoong Chung, Christos Kozyrakis, and Kunle Olukotun. STAMP: Stanford transactional applications for multi-processing. In IISWC, 2008.

[4]

Jong-Deok Choi, Manish Gupta, Mauricio J. Serrano, Vugranam C. Sreedhar, and Samuel P. Midkiff. Escape analysis for Java. In OOPSLA 1999.

Digital Library

[5]

Luke Dalessandro, Virendra J. Marathe, Michael F. Spear, and Michael L. Scott. Capabilities and limitations of library-based software transactional memory in C++. In TRANSACT 2007.

[6]

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

Digital Library

[7]

Guy Eddon and Maurice Herlihy. Language support and compiler optimizations for STM and transactional boosting. In ICDCIT, pages 209--224, 2007.

Digital Library

[8]

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

Digital Library

[9]

Maurice Herlihy, Victor Luchangco, Mark Moir, and III William N. Scherer. Software transactional memory for dynamic-sized data structures. In PODC 2003.

Digital Library

[10]

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

Digital Library

[11]

Richard L. Hudson, Bratin Saha, Ali-Reza Adl-Tabatabai, and Benjamin C. Hertzberg. McRT-Malloc: A scalable transactional memory allocator. In ISMM 2006.

Digital Library

[12]

Donald E. Knuth. Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd Edition). Addison-Wesley Professional, July 1997.

Digital Library

[13]

Yosef Lev, Mark Moir, and Dan Nussbaum. PhTM: Phased transactional memory. In TRANSACT 2007.

[14]

Yang Ni, Adam Welc, Ali-Reza Adl-Tabatabai, Moshe Bach, Sion Berkowits, James Cownie, Robert Geva, Sergey Kozhukow, Ravi Narayanaswamy, Jeffrey Olivier, Serguei Preis, Bratin Saha, Ady Tal, and Xinmin Tian. Design and implementation of transactional constructs for C/C++. In OOPSLA '08: Proceedings of the 23rd ACM SIGPLAN conference on Object oriented programming systems languages and applications, pages 195--212, New York, NY, USA, 2008. ACM.

Digital Library

[15]

Torvald Riegel, Christof Fetzer, and Pascal Felber. Automatic data partitioning in software transactional memories. In 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), June 2008.

Digital Library

[16]

Bratin Saha, Ali-Reza Adl-Tabatabai, Rick Hudson, Chi Cao Minh, and Benjamin Hertzberg. McRT-STM: A high performance software transactional memory system for a multi-core runtime. In PPoPP 2006.

Digital Library

[17]

Bratin Saha, Ali-Reza Adl-Tabatabai, and Quinn Jacobson. Architectural support for software transactional memory. In MICRO 2006.

Digital Library

[18]

Tatiana Shpeisman, Vijay Menon, Ali-Reza Adl-Tabatabai, Steven Balensiefer, Dan Grossman, Richard L. Hudson, Katherine F. Moore, and Saha Bratin. Enforcing isolation and ordering in STM. In PLDI 2007.

Digital Library

[19]

Richard M. Yoo, Yang Ni, Adam Welc, Bratin Saha, Ali-Reza Adl-Tabatabai, and Hsien-Hsin S. Lee. Kicking the tires of software transactional memory: Why the going gets tough. In SPAA 2008.

Digital Library

Cited By

Honorio BDe Carvalho JMorales CBaldassin AAraujo G(2022)Using Barrier Elision to Improve Transactional Code GenerationACM Transactions on Architecture and Code Optimization10.1145/353331819:3(1-23)Online publication date: 6-Jul-2022
https://dl.acm.org/doi/10.1145/3533318
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
Zardoshti PZhou TLiu YSpear M(2019)Optimizing Persistent Memory Transactions2019 28th International Conference on Parallel Architectures and Compilation Techniques (PACT)10.1109/PACT.2019.00025(219-231)Online publication date: Sep-2019
https://doi.org/10.1109/PACT.2019.00025
Show More Cited By

Index Terms

Optimizing transactions for captured memory
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Concurrent programming structures
      2. Language types
        Parallel programming languages

Recommendations

Optimizing memory transactions for large-scale programs

Even though Software Transactional Memory (STM) is one of the most promising approaches to simplify concurrent programming, current STM implementations incur significant overheads that render them impractical for many real-sized programs. The key ...
Lightweight Identification of Captured Memory for Software Transactional Memory
ICA3PP 2013: Proceedings of the 13th International Conference on Algorithms and Architectures for Parallel Processing - Volume 8285

Software Transactional Memory (STM) implementations typically instrument each memory access within transactions with a call to an STM barrier to ensure the correctness of the transactions. Compared to simple memory accesses, STM barriers are complex ...
Versioned boxes as the basis for memory transactions
Special issue: Synchronization and concurrency in object-oriented languages

In this paper, we propose the use of Versioned Boxes, which keep a history of values, as the basis for language-level memory transactions. Unlike previous work on software transactional memory, in our proposal read-only transactions never conflict with ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '09: Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures

August 2009

370 pages

ISBN:9781605586069

DOI:10.1145/1583991

General Chair:
Friedhelm Meyer auf der Heide
University of Paderborn, Germany)
,
Program Chair:
Michael A. Bender
Stony Brook University and Tokutek, Inc., 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 August 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPAA 09

Sponsor:

SPAA 09: 21st ACM Symposium on Parallelism in Algorithms and Architectures

August 11 - 13, 2009

AB, Calgary, Canada

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
257
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Honorio BDe Carvalho JMorales CBaldassin AAraujo G(2022)Using Barrier Elision to Improve Transactional Code GenerationACM Transactions on Architecture and Code Optimization10.1145/353331819:3(1-23)Online publication date: 6-Jul-2022
https://dl.acm.org/doi/10.1145/3533318
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
Zardoshti PZhou TLiu YSpear M(2019)Optimizing Persistent Memory Transactions2019 28th International Conference on Parallel Architectures and Compilation Techniques (PACT)10.1109/PACT.2019.00025(219-231)Online publication date: Sep-2019
https://doi.org/10.1109/PACT.2019.00025
Honorio BLabegalini de Carvalho JBaldassin A(2018)On the Efficiency of Transactional Code Generation: A GCC Case Study2018 Symposium on High Performance Computing Systems (WSCAD)10.1109/WSCAD.2018.00037(184-190)Online publication date: Oct-2018
https://doi.org/10.1109/WSCAD.2018.00037
Wang CSpear MCadar CPietzuch PKeeton KRodrigues R(2016)Practical condition synchronization for transactional memoryProceedings of the Eleventh European Conference on Computer Systems10.1145/2901318.2901342(1-16)Online publication date: 18-Apr-2016
https://dl.acm.org/doi/10.1145/2901318.2901342
Carvalho FCachopo J(2016)Optimizing memory transactions for large-scale programsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2015.12.00189:C(13-24)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1016/j.jpdc.2015.12.001
Spear MRuan WLiu YVyas T(2015)Case Study: Using Transactions in MemcachedTransactional Memory. Foundations, Algorithms, Tools, and Applications10.1007/978-3-319-14720-8_20(449-467)Online publication date: 2015
https://doi.org/10.1007/978-3-319-14720-8_20
Ruan WVyas TLiu YSpear M(2014)Transactionalizing legacy codeACM SIGARCH Computer Architecture News10.1145/2654822.254196042:1(399-412)Online publication date: 24-Feb-2014
https://dl.acm.org/doi/10.1145/2654822.2541960
Ruan WVyas TLiu YSpear M(2014)Transactionalizing legacy codeACM SIGPLAN Notices10.1145/2644865.254196049:4(399-412)Online publication date: 24-Feb-2014
https://dl.acm.org/doi/10.1145/2644865.2541960
Stipić SKarakostas VSmiljković VGajinov VUnsal OCristal AValero MTrancoso PFranklin DMcKee S(2014)Dynamic transaction coalescingProceedings of the 11th ACM Conference on Computing Frontiers10.1145/2597917.2597930(1-10)Online publication date: 20-May-2014
https://dl.acm.org/doi/10.1145/2597917.2597930
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