article

Supporting nested transactional memory in logTM

Authors:

Michelle J. Moravan,

Kevin E. Moore,

Michael M. Swift,

David A. WoodAuthors Info & Claims

ACM SIGPLAN Notices, Volume 41, Issue 11

Pages 359 - 370

https://doi.org/10.1145/1168918.1168902

Published: 20 October 2006 Publication History

Abstract

Nested transactional memory (TM) facilitates software composition by letting one module invoke another without either knowing whether the other uses transactions. Closed nested transactions extend isolation of an inner transaction until the toplevel transaction commits. Implementations may flatten nested transactions into the top-level one, resulting in a complete abort on conflict, or allow partial abort of inner transactions. Open nested transactions allow a committing inner transaction to immediately release isolation, which increases parallelism and expressiveness at the cost of both software and hardware complexity.This paper extends the recently-proposed flat Log-based Transactional Memory (LogTM) with nested transactions. Flat LogTM saves pre-transaction values in a log, detects conflicts with read (R) and write (W) bits per cache block, and, on abort, invokes a software handler to unroll the log. Nested LogTM supports nesting by segmenting the log into a stack of activation records and modestly replicating R/W bits. To facilitate composition with nontransactional code, such as language runtime and operating system services, we propose escape actions that allow trusted code to run outside the confines of the transactional memory system.

References

[1]

C.S. Ananian, K. Asanovic, B.C. Kuszmaul, C.E. Leiserson, and S. Lie. Unbounded Transactional Memory. In Proceedings of the Eleventh IEEE Symposium on High-Performance Computer Architecture, Feb. 2005.

Digital Library

[2]

C. Blundell, E.C. Lewis, and M.M. Martin. Deconstructing Transactional Semantics: The Subtleties of Atomicity. In Workshop on Duplicating, Deconstructing, and Debunking (WDDD), June 2005.

[3]

C. Blundell, E.C. Lewis, and M.M. Martin. Unrestricted Transactional Memory: Supporting I/O and System Calls within Transactions. Technical Report TR-CIS-06-09, University of Pennsylvania, June 2006.

[4]

B.D. Carlstrom, J. Chung, H. Chafi, A. McDonald, C.C. Minh, L. Hammond, C. Kozyrakis, and K. Olukotun. Transactional Execution of Java Programs. In SCOOL Workshop, Oct. 2005.

[5]

J. Chung, H. Chafi, C.C. Minh, A. McDonald, B.D. Carlstrom, C. Kozyrakis, and K. Olukotun. The Common Case Transactional Behavior of Multithreaded Programs. In Proceedings of the Twelfth IEEE Symposium on High-Performance Computer Architecture, Feb. 2006.

[6]

J. Chung, C.C. Minh, B.D. Carlstrom, and C. Kozyrakis. Parallelizing SPECjbb2000 with Transactional Memory. In PODC Workshop on Concurrency and Synchronization in Java Programs, June 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 Proceedings of the 31st Annual International Symposium on Computer Architecture, June 2004.

Digital Library

[8]

T. Harris. Design Choices for Language-Based Transactions. Technical Report UCAM-CL-TR-572, University of Cambridge, Aug. 2003.

[9]

T. Harris. Exceptions and side-effects in atomic blocks. In PODC Workshop on Concurrency and Synchronization in Java Programs, Jul 2004.

[10]

T. Harris and K. Fraser. Language support for lightweight transactions. In Proceedings of the 18th SIGPLAN Conference on Object-Oriented Programming, Systems, Languages and Application (OOPSLA), Oct. 2003.

Digital Library

[11]

T. Harris, S. Marlow, S.P. Jones, and M. Herlihy. Composable Memory Transactions. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP), June 1991.

[12]

M. Herlihy, V. Luchangco, M. Moir, and W. Scherer III. Software Transactional Memory for Dynamic-Sized Data Structures. In Twenty-Second ACM Symposium on Principles of Distributed Computing, Boston, Massachusetts, July 2003.

Digital Library

[13]

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, pages 289--300, May 1993.

Digital Library

[14]

H.F. Korth, E. Levy, and A. Silberschatz. A formal approach to recovery by compensating transactions. In Proceedings of the sixteenth international conference on Very large databases, pages 95--106, San Francisco, CA, USA, 1990. Morgan Kaufmann Publishers Inc.

Digital Library

[15]

A.R. Lebeck and D.A. Wood. Dynamic Self-Invalidation: Reducing Coherence Overhead in Shared-Memory Multiprocessors. In Proceedings of the 22nd Annual International Symposium on Computer Architecture, pages 48--59, June 1995.

Digital Library

[16]

P.S. Magnusson et al. Simics: A Full System Simulation Platform. IEEE Computer, 35(2):50--58, Feb. 2002.

Digital Library

[17]

M.M. 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. Computer Architecture News, pages 92--99, Sept. 2005.

Digital Library

[18]

A. McDonald, J. Chung, B. Carlstrom, C.C. Minh, H. Chafi, C. Kozyrakis, and K. Olukotun. Architectural Semantics for Practical Transactional Memory. In Proceedings of the 33nd Annual International Symposium on Computer Architecture, June 2006.

Digital Library

[19]

S. Microsystems. OpenSolaris: Mutex.c. http://cvs.opensolaris.org/-source/xref/on/usr/src/uts/common/os/mutex.c.

[20]

C. Mohan, D. Haderle, B. Lindsay, H. Pirahesh, and P. Schwarz. ARIES: A Transaction Recovery Method Supporting Fine- Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. In Readings in Database Systems, pages 251--285. Morgan Kaufmann Publishers, 1998.

Digital Library

[21]

K.E. Moore, J. Bobba, M.J. Moravan, M.D. Hill, and D.A. Wood. LogTM: Log-Based Transactional Memory. In Proceedings of the Twelfth IEEE Symposium on High-Performance Computer Architecture, Feb. 2006.

[22]

J.E.B. Moss. Nested transactions: an approach to reliable distributed computing. PhD thesis, Massachusetts Institute of Technology, 1981.

[23]

J.E.B. Moss. Nesting Transactions: Why and What Do We Need? TRANSACT Keynote Address, June 2006.

[24]

J.E.B. Moss. Open Nested Transactions: Semantics and Support. In Workshop on Memory Performance Issues, Feb. 2006.

[25]

J.E.B. Moss, N.D. Griffeth, and M.H. Graham. Abstraction in recovery management. In SIGMOD '86: Proceedings of the 1986 ACM SIGMOD international conference on Management of data, pages 72--83, New York, NY, USA, 1986. ACM Press.

Digital Library

[26]

J.E.B. Moss and A.L. Hosking. Nested Transactional Memory: Model and Preliminary Architecture Sketches. In SCOOL Workshop, Oct. 2005.

[27]

D.L. Parnas. On the criteria to be used in Decomposing Systems into Modules. Communications of the ACM, 15(12):1053--1058, Dec 1972.

Digital Library

[28]

R. Rajwar, M. Herlihy, and K. Lai. Virtualizing Transactional Memory. In Proceedings of the 32nd Annual International Symposium on Computer Architecture, June 2005.

Digital Library

[29]

N. Shavit and D. Touitou. Software Transactional Memory. In Fourteenth ACM Symposium on Principles of Distributed Computing, Ottawa, Ontario, Canada, pages 204--213, Aug. 1995.

Digital Library

[30]

I. Sun Microsystems. Solaris 10 Reference Manual Collection: man pages section 2: System Calls. http://docs.sun.com/app/docs/doc/816-5167.

[31]

G. Weikum. A Theoretical Foundation of Multi-Level Concurrency Control. In Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems (PODS), pages 31--43, Mar. 1986.

Digital Library

[32]

G. Weikum and H.-J. Schek. Concepts and Applications of Multilevel Transactions and Open Nested Transactions. Morgan Kaufmann, 1992.

[33]

Wisconsin Multifacet GEMS Simulator. http://www.cs.wisc.edu/gems/.

[34]

S.C. Woo, M. Ohara, E. Torrie, J.P. Singh, and A. Gupta. The SPLASH-2 Programs: Characterization and Methodological Considerations. In Proceedings of the 22nd Annual International Symposium on Computer Architecture, pages 24--37, June 1995.

Digital Library

[35]

D.A. Wood and M.D. Hill. Cost-Effective Parallel Computing. IEEE Computer, pages 69--72, Feb. 1995.

Digital Library

[36]

C. Zilles and L. Baugh. Extending Hardware Transactional Memory to Support Non-busy Waiting and Non-transactional Actions. In First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing, June 2006.

Cited By

Shahid AMurad MQadri MQadri NAhmed J(2016)Hardware Transactional MemoriesInnovative Research and Applications in Next-Generation High Performance Computing10.4018/978-1-5225-0287-6.ch003(47-65)Online publication date: 2016
https://doi.org/10.4018/978-1-5225-0287-6.ch003
Dhoke APalmieri RRavindran BDas SKrishnaswamy DKarkar SKorman AKumar MPortmann MSastry S(2015)On Reducing False Conflicts in Distributed Transactional Data StructuresProceedings of the 2015 International Conference on Distributed Computing and Networking10.1145/2684464.2684467(1-10)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.1145/2684464.2684467
Hayduk YSobe AFelber P(2015)Dynamic Message Processing and Transactional Memory in the Actor ModelProceedings of the 15th IFIP WG 6.1 International Conference on Distributed Applications and Interoperable Systems - Volume 903810.1007/978-3-319-19129-4_8(94-107)Online publication date: 2-Jun-2015
https://dl.acm.org/doi/10.1007/978-3-319-19129-4_8
Show More Cited By

Index Terms

Supporting nested transactional memory in logTM
1. Computer systems organization
  1. Architectures
    1. Parallel architectures

Recommendations

Supporting nested transactional memory in logTM
Proceedings of the 2006 ASPLOS Conference

Nested transactional memory (TM) facilitates software composition by letting one module invoke another without either knowing whether the other uses transactions. Closed nested transactions extend isolation of an inner transaction until the toplevel ...
Supporting nested transactional memory in logTM
Proceedings of the 2006 ASPLOS Conference

Nested transactional memory (TM) facilitates software composition by letting one module invoke another without either knowing whether the other uses transactions. Closed nested transactions extend isolation of an inner transaction until the toplevel ...
Supporting nested transactional memory in logTM
ASPLOS XII: Proceedings of the 12th international conference on Architectural support for programming languages and operating systems

Nested transactional memory (TM) facilitates software composition by letting one module invoke another without either knowing whether the other uses transactions. Closed nested transactions extend isolation of an inner transaction until the toplevel ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 41, Issue 11

Proceedings of the 2006 ASPLOS Conference

November 2006

425 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1168918

Issue’s Table of Contents

ASPLOS XII: Proceedings of the 12th international conference on Architectural support for programming languages and operating systems
October 2006
440 pages
ISBN:1595934510
DOI:10.1145/1168857
General Chair:
John Paul Shen
Intel Corp.
,
Program Chair:
Margaret R. Martonosi
Princeton University

Copyright © 2006 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: 20 October 2006

Published in SIGPLAN Volume 41, Issue 11

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

128
Total Citations
View Citations
952
Total Downloads

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

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shahid AMurad MQadri MQadri NAhmed J(2016)Hardware Transactional MemoriesInnovative Research and Applications in Next-Generation High Performance Computing10.4018/978-1-5225-0287-6.ch003(47-65)Online publication date: 2016
https://doi.org/10.4018/978-1-5225-0287-6.ch003
Dhoke APalmieri RRavindran BDas SKrishnaswamy DKarkar SKorman AKumar MPortmann MSastry S(2015)On Reducing False Conflicts in Distributed Transactional Data StructuresProceedings of the 2015 International Conference on Distributed Computing and Networking10.1145/2684464.2684467(1-10)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.1145/2684464.2684467
Hayduk YSobe AFelber P(2015)Dynamic Message Processing and Transactional Memory in the Actor ModelProceedings of the 15th IFIP WG 6.1 International Conference on Distributed Applications and Interoperable Systems - Volume 903810.1007/978-3-319-19129-4_8(94-107)Online publication date: 2-Jun-2015
https://dl.acm.org/doi/10.1007/978-3-319-19129-4_8
Titos-Gil JAcacio M(2015)Hardware Approaches to Transactional Memory in Chip MultiprocessorsHandbook on Data Centers10.1007/978-1-4939-2092-1_27(805-835)Online publication date: 17-Mar-2015
https://doi.org/10.1007/978-1-4939-2092-1_27
Kim JPalmieri RRavindran B(2013)Scheduling Open-Nested Transactions in Distributed Transactional MemoryCoordination Models and Languages10.1007/978-3-642-38493-6_8(105-120)Online publication date: 2013
https://doi.org/10.1007/978-3-642-38493-6_8
Midkiff S(2012)Automatic Parallelization: An Overview of Fundamental Compiler TechniquesSynthesis Lectures on Computer Architecture10.2200/S00340ED1V01Y201201CAC0197:1(1-169)Online publication date: 28-Jan-2012
https://doi.org/10.2200/S00340ED1V01Y201201CAC019
Barreto JDragojević AFerreira PGuerraoui RKapalka M(2010)Leveraging parallel nesting in transactional memoryACM SIGPLAN Notices10.1145/1837853.169346645:5(91-100)Online publication date: 9-Jan-2010
https://dl.acm.org/doi/10.1145/1837853.1693466
Koskinen EParkinson MHerlihy M(2010)Coarse-grained transactionsACM SIGPLAN Notices10.1145/1707801.170630445:1(19-30)Online publication date: 17-Jan-2010
https://dl.acm.org/doi/10.1145/1707801.1706304
Koskinen EParkinson MHerlihy MHermenegildo MPalsberg J(2010)Coarse-grained transactionsProceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/1706299.1706304(19-30)Online publication date: 17-Jan-2010
https://dl.acm.org/doi/10.1145/1706299.1706304
Barreto JDragojević AFerreira PGuerraoui RKapalka MGovindarajan RPadua DHall M(2010)Leveraging parallel nesting in transactional memoryProceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/1693453.1693466(91-100)Online publication date: 9-Jan-2010
https://dl.acm.org/doi/10.1145/1693453.1693466
Show More Cited By

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 Issue’s Table of Contents