research-article

Version management alternatives for hardware transactional memory

Authors:

Grigorios Magklis,

Antonio GonzálezAuthors Info & Claims

MEDEA '08: Proceedings of the 9th workshop on MEmory performance: DEaling with Applications, systems and architecture

Pages 69 - 76

https://doi.org/10.1145/1509084.1509094

Published: 26 October 2008 Publication History

Abstract

Transactional Memory is a promising parallel programming model that addresses the programmability issues of lock-based applications using mechanisms that are transparent to developers. Hardware Transactional Memory (HTM) implements these mechanisms in silicon to obtain better results than fine-grain locking solutions. One of these mechanisms is data version management, that decides how and where the modifications introduced by transactions are stored to guarantee their atomicity and durability.

In this paper, we show that aborts are frequent especially for applications with coarse-grain transactions and many threads, and that this severely restricts the scalability of log-based HTMs. To address this issue, we propose the use of a gated store buffer to accelerate eager version management for log-based HTM. Moreover, we propose a novel design, where the store buffer is used to perform lazy version management (similar to Rock [12]) but overflowed transactions execute with a fallback log-based HTM that uses eager version management.

Assuming an infinite store buffer, we show that lazy version management is better suited to applications with fine-grain transactions while eager version management is better suited to applications with coarse-grain transactions. Limiting the buffer size to 32 entries, we obtain 20.1% average improvement over log-based HTM for applications with fine-grain transactions (using lazy version management) and 54.7% for applications with coarse-grain transactions (using eager version management).

References

[1]

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

Digital Library

[2]

C. Blundell, J. Devietti, E. C. Lewis, and M. M. K. Martin. Making The Fast Case Common And The Uncommon Case Simple In Unbounded Transactional Memory. In Procs. of the 34th Intl Symp on Computer Architecture, June 2007.

Digital Library

[3]

J. Bobba, N. Goyal, M. D. Hill, M. M. Swift, and D. A. Wood. TokenTM: Efficient Execution of Large Transactions with Hardware Transactional Memory. In Procs. of the 35th Intl Symp on Computer Architecture, June 2008.

Digital Library

[4]

J. Bobba, K. E. Moore, L. Yen, H. Volos, M. D. Hill, M. M. Swift, and D. A. Wood. Performance Pathologies in Hardware Transactional Memory. In Procs. of the 34th Intl Symp on Computer Architecture, June 2007.

Digital Library

[5]

C. Cao Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford Transactional Applications for Multi-Processing. In Procs. of The IEEE Intl Symp on Workload Characterization, Sept. 2008.

[6]

J. Chung, H. Chafi, C. Cao Minh, A. McDonald, B. D. Carlstrom, C. Kozyrakis, and K. Olukotun. The Common Case Transactional Behavior of Multithreaded Programs. In Procs. of the 12th Intl Symp on High-Performance Computer Architecture, Feb. 2006.

[7]

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

Digital Library

[8]

M. Herlihy and J. E. B. Moss. Transactional Memory: Architectural Support for Lock-Free Data Structures. In Procs. of the 20th Intl Symp on Computer Architecture, May 1993.

Digital Library

[9]

A. Klaiber. The Technology Behind Crusoe#8482; Processors. Technical Report Technical report, Transmeta Corp., Jan. 2000.

[10]

S. Kumar, M. Chu, C. J. Hughes, P. Kundu, and A. Nguyen. Hybrid Transactional Memory. In Procs. of the ACM SIGPLAN Symp on Principles and Practice of Parallel Programming, Mar. 2006.

Digital Library

[11]

P. S. Magnusson, M. Christensson, J. Eskilson, D. Forsgren, G. Hallberg, J. Hogberg, F. Larsson, A. Moestedt, and B. Werner. Simics: A Full System Simulation Platform. IEEE Computer, 35(2):50--58, 2002.

Digital Library

[12]

K. M. Mark Moir and D. Nussbaum. The Adaptive Transactional Memory Test Platform: A Tool for Experimenting with Transactional Code for Rock. In Procs. of the 3rd ACM SIGPLAN Workshop on Transactional Computing, Feb. 2008.

[13]

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. ACM SIGARCH Computer Architecture News, 33(4):92--99, 2005.

Digital Library

[14]

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

[15]

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

Digital Library

[16]

N. Shavit and D. Touitou. Software transactional memory. In Procs. of the 14th ACM Symp on Principles of Distributed Computing, Aug. 1995.

Digital Library

[17]

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 Procs. of the 1st ACM SIGPLAN Workshop on Transactional Computing, June 2006.

[18]

M. M. Swift, H. Volos, N. Goyal, L. Yen, M. D. Hill, and D. A. Woo. OS Support for Virtualizing Hardware Transactional Memory. In Procs. of the 3rd ACM SIGPLAN Workshop on Transactional Computing, Feb. 2008.

[19]

J. R. Titos, M. E. Acacio, and J. M. Garcia. Characterization of Conflicts in Log-Based Transactional Memory. In Procs. of the 16th Euromicro Conference on Parallel, Distributed and Network-Based Processing, Feb. 2008.

Digital Library

[20]

S. C. Woo, M. Ohara, E. Torrie, J. P. Singh, and A. Gupta. The SPLASH-2 Programs: Characterization and Methodological Considerations. In Procs. of the 22nd Intl Symp on Computer Architecture, June 1995.

Digital Library

[21]

L. Yen, J. Bobba, M. M. Marty, K. E. Moore, H. Volos, M. D. Hill, M. M. Swift, and D. A. Wood. LogTM-SE: Decoupling Hardware Transactional Memory from Caches. In Procs. of the 13th Intl Symp on High-Performance Computer Architecture, Feb. 2007.

Digital Library

Cited By

Kim SChoi DRo WGaudiot J(2014)Complexity-Effective Contention Management with Dynamic Backoff for Transactional Memory SystemsIEEE Transactions on Computers10.1109/TC.2013.4963:7(1696-1708)Online publication date: Jul-2014
https://doi.org/10.1109/TC.2013.49
Li GAn HLi QDeng BDai W(2014)Efficient execution of speculative threads and transactions with hardware transactional memoryFuture Generation Computer Systems10.1016/j.future.2013.06.01730:C(242-253)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1016/j.future.2013.06.017
Yan ZJiang HTan YFeng D(2013)An integrated pseudo-associativity and relaxed-order approach to hardware transactional memoryACM Transactions on Architecture and Code Optimization (TACO)10.1145/2400682.24007019:4(1-26)Online publication date: 20-Jan-2013
https://dl.acm.org/doi/10.1145/2400682.2400701
Show More Cited By

Index Terms

Version management alternatives for hardware transactional memory

Recommendations

A Dynamically Adaptable Hardware Transactional Memory
MICRO '43: Proceedings of the 2010 43rd Annual IEEE/ACM International Symposium on Microarchitecture

Most Hardware Transactional Memory (HTM) implementations choose fixed version and conflict management policies at design time. While eager HTM systems store transactional state in-place in memory and resolve conflicts when they are produced, lazy HTM ...
Using a Reconfigurable L1 Data Cache for Efficient Version Management in Hardware Transactional Memory
PACT '11: Proceedings of the 2011 International Conference on Parallel Architectures and Compilation Techniques

Transactional Memory (TM) potentially simplifies parallel programming by providing atomicity and isolation for executed transactions. One of the key mechanisms to provide such properties is version management, which defines where and how transactional ...
A Case Study of the Interplay between Conflict Management and Version Management in Hardware Transactional Memory Systems
PAAP '11: Proceedings of the 2011 Fourth International Symposium on Parallel Architectures, Algorithms and Programming

As one of the most potential solution to parallel programming on the future many-core platforms, Transactional Memory (TM) systems have attracted a great deal of attention from both the industry and academic since the first TM was proposed in 1993. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

MEDEA '08: Proceedings of the 9th workshop on MEmory performance: DEaling with Applications, systems and architecture

October 2008

88 pages

ISBN:9781605582436

DOI:10.1145/1509084

Conference Chairs:
Pierfrancesco Foglia
Università di Pisa
,
Cosimo Antonio Prete
Università di Pisa
,
Sandro Bartolini
Università di Siena
,
Roberto Giorgi
Università di Siena

Copyright © 2008 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: 26 October 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

MEDEA '08

MEDEA '08: The 2008 workshop on MEmory performance: DEaling with Applications, systems and architectures

October 26, 2008

Toronto, Canada

Acceptance Rates

Overall Acceptance Rate 6 of 9 submissions, 67%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
279
Total Downloads

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

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kim SChoi DRo WGaudiot J(2014)Complexity-Effective Contention Management with Dynamic Backoff for Transactional Memory SystemsIEEE Transactions on Computers10.1109/TC.2013.4963:7(1696-1708)Online publication date: Jul-2014
https://doi.org/10.1109/TC.2013.49
Li GAn HLi QDeng BDai W(2014)Efficient execution of speculative threads and transactions with hardware transactional memoryFuture Generation Computer Systems10.1016/j.future.2013.06.01730:C(242-253)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1016/j.future.2013.06.017
Yan ZJiang HTan YFeng D(2013)An integrated pseudo-associativity and relaxed-order approach to hardware transactional memoryACM Transactions on Architecture and Code Optimization (TACO)10.1145/2400682.24007019:4(1-26)Online publication date: 20-Jan-2013
https://dl.acm.org/doi/10.1145/2400682.2400701
Huang SJou JHsieh CLin D(2013)Design of a Dynamic Parallel Execution Architecture for Multi-core SystemsAdvances in Intelligent Systems and Applications - Volume 210.1007/978-3-642-35473-1_72(731-740)Online publication date: 2013
https://doi.org/10.1007/978-3-642-35473-1_72
Yan ZJiang HFeng DTian LTan Y(2012)SUVProceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium10.1109/IPDPS.2012.22(131-143)Online publication date: 21-May-2012
https://dl.acm.org/doi/10.1109/IPDPS.2012.22
Zhao LChoi WDraper J(2012)SEL-TMProceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium10.1109/IPDPS.2012.19(95-106)Online publication date: 21-May-2012
https://dl.acm.org/doi/10.1109/IPDPS.2012.19
Li GAn HLi QDeng BDai W(2012)SeTMProceedings of the 2012 IEEE 18th International Conference on Parallel and Distributed Systems10.1109/ICPADS.2012.77(522-531)Online publication date: 17-Dec-2012
https://dl.acm.org/doi/10.1109/ICPADS.2012.77
Harris TLarus JRajwar R(2010)Transactional Memory, 2nd editionSynthesis Lectures on Computer Architecture10.2200/S00272ED1V01Y201006CAC0115:1(1-263)Online publication date: 22-Dec-2010
https://doi.org/10.2200/S00272ED1V01Y201006CAC011
Lupon MMagklis GGonzalez A(2009)FASTMProceedings of the 2009 18th International Conference on Parallel Architectures and Compilation Techniques10.1109/PACT.2009.19(293-302)Online publication date: 12-Sep-2009
https://dl.acm.org/doi/10.1109/PACT.2009.19

View Options

Get Access

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