research-article

On the power of hardware transactional memory to simplify memory management

Authors:

Aleksandar Dragojević,

Maurice Herlihy,

Mark MoirAuthors Info & Claims

PODC '11: Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing

Pages 99 - 108

https://doi.org/10.1145/1993806.1993821

Published: 06 June 2011 Publication History

Abstract

Dynamic memory management is a significant source of complexity in the design and implementation of practical concurrent data structures. We study how hardware transactional memory (HTM) can be used to simplify and streamline memory reclamation for such data structures. We propose and evaluate several new HTM-based algorithms for the "Dynamic Collect" problem that lies at the heart of many modern memory management algorithms. We demonstrate that HTM enables simpler and faster solutions, with better memory reclamation properties, than prior approaches. Despite recent theoretical arguments that HTM provides no worst-case advantages, our results support the claim that HTM can provide significantly better common-case performance, as well as reduced conceptual complexity.

References

[1]

Advanced Micro Devices. Advanced synchronization facility proposed architectural specification, March 2009. Publication # 45432, Revision: 2.1.

[2]

Y. Afek, H. Attiya, D. Dolev, E. Gafni, M. Merritt, and N. Shavit. Atomic snapshots of shared memory. Journal of the ACM, September 1993.

Digital Library

[3]

H. Attiya, A. Fouren, and E. Gafni. An adaptive collect algorithm with applications. Distributed Computing, April 2002.

Digital Library

[4]

H. Attiya and D. Hendler. Time and space lower bounds for implementations using k-cas. IEEE Transactions on Parallel and Distributed Systems, February 2010.

Digital Library

[5]

C. Blundell, E. C. Lewis, and M. Martin. Deconstructing Transactions: The Subtleties of Atomicity. In the 4th Annual Workshop on Duplicating, Deconstructing, and Debunking, 2005.

[6]

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. Transact 2008 workshop. http://research.sun.com/scalable/pubs/TRANSACT2008-ATMTP-Apps.pdf.

[7]

D. Dice, Y. Lev, V. J. Marathe, M. Moir, D. Nussbaum, and M. Oleszewski. Simplifying concurrent algorithms by exploiting hardware transactional memory. In Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures, SPAA '10, 2010.

Digital Library

[8]

D. Dice, Y. Lev, M. Moir, and D. Nussbaum. Early experience with a commercial hardware transactional memory implementation. In Proceeding of the 14th international conference on Architectural support for programming languages and operating systems, ASPLOS '09, 2009.

Digital Library

[9]

D. Dice, Y. Lev, M. Moir, D. Nussbaum, and M. Olszewski. Early experience with a commercial hardware transactional memory implementation. Technical Report TR-2009-180, Sun Microsystems Laboratories, 2009.

Digital Library

[10]

M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Nonblocking memory management support for dynamic-sized data structures. ACM Transactions on Computer Systems, May 2005.

Digital Library

[11]

M. Herlihy, V. Luchangco, and M. Moir. Space and time adaptive non-blocking algorithms. Electronic Notes in Theoretical Computer Science, April 2003.

[12]

M. Herlihy and J. E. B. Moss. Transactional memory: architectural support for lock-free data structures. In Proceedings of the 20th annual international symposium on Computer architecture, ISCA '93, 1993.

Digital Library

[13]

JSR166: Concurrency Utilities. http://gee.cs.oswego.edu/dl/concurrency-interest/.

[14]

M. Michael. Hazard pointers: Safe memory reclamation for lock-free objects. IEEE Transactions on Parallel and Distributed Systems, June 2004.

Digital Library

[15]

M. M. Michael and M. L. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In Proceedings of the 15th annual ACM symposium on Principles of distributed computing, PODC '96, 1996.

Digital Library

[16]

M. Saks, N. Shavit, and H. Woll. Optimal time randomized consensus making resilient algorithms fast in practice. In Proceedings of the 2nd annual ACM-SIAM symposium on Discrete algorithms, SODA '91, 1991.

Digital Library

[17]

Sparc International, Inc. The SPARC architecture manual, version 8, 1991.

Digital Library

Cited By

Singh ABrown TMashtizadeh A(2024)Simple, Fast and Widely Applicable Concurrent Memory Reclamation via NeutralizationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.333567135:2(203-220)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TPDS.2023.3335671
Wei YBlelloch GFatourou PRuppert EDehnavi MKulkarni MKrishnamoorthy S(2023)Practically and Theoretically Efficient Garbage Collection for MultiversioningProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3572848.3577508(66-78)Online publication date: 25-Feb-2023
https://dl.acm.org/doi/10.1145/3572848.3577508
Singh ABrown TSpear M(2023)Efficient Hardware Primitives for Immediate Memory Reclamation in Optimistic Data Structures2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS54959.2023.00021(112-122)Online publication date: May-2023
https://doi.org/10.1109/IPDPS54959.2023.00021
Show More Cited By

Index Terms

On the power of hardware transactional memory to simplify memory management
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

Transactional memory: from semantics to silicon
IWMSE '08: Proceedings of the 1st international workshop on Multicore software engineering

Multi-core architectures bring parallel programming into the mainstream. Parallel programming poses many new challenges to the developer, one of which is synchronizing concurrent access to shared memory by multiple threads. Programmers have ...
Unbounded page-based transactional memory
Proceedings of the 2006 ASPLOS Conference

Exploiting thread level parallelism is paramount in the multicore era. Transactions enable programmers to expose such parallelism by greatly simplifying the multi-threaded programming model. Virtualized transactions (unbounded in space and time) are ...
Hardware transactional memory: A high performance parallel programming model

The transactional memory in multicore processors has been a major research area over past several years. Many transactional memory systems have been proposed to be used to solve the synchronization problem of multicore processors. Hardware transactional ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '11: Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing

June 2011

406 pages

ISBN:9781450307192

DOI:10.1145/1993806

General Chair:
Cyril Gavoille
LaBRI, University of Bordeaux, France
,
Program Chair:
Pierre Fraigniaud
CNRS and University of Paris Diderot, France

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '11

Sponsor:

PODC '11: ACM Symposium on Principles of Distributed Computing

June 6 - 8, 2011

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

49
Total Citations
View Citations
376
Total Downloads

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

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Singh ABrown TMashtizadeh A(2024)Simple, Fast and Widely Applicable Concurrent Memory Reclamation via NeutralizationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.333567135:2(203-220)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TPDS.2023.3335671
Wei YBlelloch GFatourou PRuppert EDehnavi MKulkarni MKrishnamoorthy S(2023)Practically and Theoretically Efficient Garbage Collection for MultiversioningProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3572848.3577508(66-78)Online publication date: 25-Feb-2023
https://dl.acm.org/doi/10.1145/3572848.3577508
Singh ABrown TSpear M(2023)Efficient Hardware Primitives for Immediate Memory Reclamation in Optimistic Data Structures2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS54959.2023.00021(112-122)Online publication date: May-2023
https://doi.org/10.1109/IPDPS54959.2023.00021
Nikolaev RRavindran BFreund SYahav E(2021)Snapshot-free, transparent, and robust memory reclamation for lock-free data structuresProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454090(987-1002)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454090
Anderson DBlelloch GWei YFreund SYahav E(2021)Concurrent deferred reference counting with constant-time overheadProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454060(526-541)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454060
Singh ABrown TMashtizadeh ALee JPetrank E(2021)NBRProceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3437801.3441625(175-190)Online publication date: 17-Feb-2021
https://dl.acm.org/doi/10.1145/3437801.3441625
Nikolaev RRavindran BGupta RShen X(2020)Universal wait-free memory reclamationProceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3332466.3374540(130-143)Online publication date: 19-Feb-2020
https://dl.acm.org/doi/10.1145/3332466.3374540
Jabal ADavari MBertino EMakaya CCalo SVerma DRusso AWilliams C(2019)Methods and Tools for Policy AnalysisACM Computing Surveys10.1145/329574951:6(1-35)Online publication date: 4-Feb-2019
https://dl.acm.org/doi/10.1145/3295749
Meyer RWolff S(2019)Decoupling lock-free data structures from memory reclamation for static analysisProceedings of the ACM on Programming Languages10.1145/32903713:POPL(1-31)Online publication date: 2-Jan-2019
https://dl.acm.org/doi/10.1145/3290371
Alistarh DLeiserson WMatveev AShavit N(2018)ThreadScanACM Transactions on Parallel Computing10.1145/32018974:4(1-18)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1145/3201897
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