[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/1565824.1565826acmotherconferencesArticle/Chapter ViewAbstractPublication PagesisstaConference Proceedingsconference-collections
research-article

An efficient lock-aware transactional memory implementation

Published: 06 July 2009 Publication History

Abstract

Transactional memory (TM) is an emerging concurrency control mechanism that provides a simple and composable programming model. Unfortunately, transactions violate the semantics of mutual exclusion locks when they execute concurrently. Due to the prevalence of locks, transactions must be made lock-aware enabling them to correctly interoperate with locks.
We present a lock-aware transactional memory (LATM) system that employs a unique communication method using local knowledge of locks coupled with granularity-based policies. Our system allows higher concurrent throughput than prior systems because it only prevents truly conflicting critical sections from executing concurrently. Furthermore, our system relaxes the prior requirement of transaction isolation when executing conflicting transactional critical sections and instead runs these transactions as irrevocable, improving transaction concurrency. We demonstrate our performance improvements mathematically and empirically.
Our system also advances LATM research in terms of program consistency. This is achieved by detecting potential deadlocks at run-time and aborting the programs that contain them. Prior systems break deadlocks, which reveal partially executed critical sections to other threads, thereby violating mutual exclusion. Because our system disallows deadlocks, it does not suffer from mutual exclusion violations, improving program consistency.

References

[1]
A.-R. Adl-Tabatabai, D. Dice, M. Herlihy, N. Shavit, C. Kozyrakis, C. von Praun, and M. Scott. Potential show-stoppers for transactional synchronization. In PPOPP, page 55, 2007.
[2]
E. W. Dijkstra. Solution of a problem in concurrent programming control. Commun. ACM, 8(9):569, 1965.
[3]
J. E. Gottschlich and D. A. Connors. DracoSTM: A practical C++ approach to software transactional memory. In ACM SIGPLAN Library-Centric Software Design (LCSD), Oct. 2007.
[4]
J. E. Gottschlich and D. A. Connors. Optimizing consistency checking for memory-intensive transactions. In ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Aug. 2008.
[5]
J. E. Gottschlich, J. G. Siek, P. J. Rogers, and M. Vachharajani. Toward simplified parallel support in C++. In Proceedings of the Fourth International Conference on Boost Libraries (BoostCon). May 2009.
[6]
T. Harris, S. Marlow, S. L. P. Jones, and M. Herlihy. Composable memory transactions. In K. Pingali, K. A. Yelick, and A. S. Grimshaw, editors, PPoPP, pages 48--60. ACM, 2005.
[7]
M. Herlihy and E. Koskinen. Transactional boosting: a methodology for highly-concurrent transactional objects. In PPoPP. ACM, 2008.
[8]
M. Herlihy and J. E. B. Moss. Transactional memory: Architectural support for lock-free data structures. In Proceedings of the International Symposium on Computer Architecture. May 1993.
[9]
M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Elsevier, Inc., 2008.
[10]
J. R. Larus and R. Rajwar. Transactional Memory. Morgan and Claypool, 2006.
[11]
V. J. Marathe and M. Moir. Toward high performance nonblocking software transactional memory. In PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, pages 227--236, New York, NY, USA, 2008. ACM.
[12]
K. E. Moore, J. Bobba, M. J. Moravan, M. D. Hill, and D. A. Wood. Logtm: Log-based transactional memory. In Proceedings of the 12th International Symposium on High-Performance Computer Architecture, pages 254--265. IEEE Computer Society, Feb. 2006.
[13]
J. E. B. Moss and A. L. Hosking. Nested transactional memory: model and architecture sketches. Sci. Comput. Program., 63(2), 2006.
[14]
R. Rajwar and P. A. Bernstein. Atomic transactional execution in hardware: A new high performance abstraction for databases. In Workshop on High Performance Transaction Systems, 2003.
[15]
C. J. Rossbach, O. S. Hofmann, D. E. Porter, H. E. Ramadan, B. Aditya, and E. Witchel. Txlinux: using and managing hardware transactional memory in an operating system. In T. C. Bressoud and M. F. Kaashoek, editors, SOSP, pages 87--102. ACM, 2007.
[16]
N. Shavit and D. Touitou. Software transactional memory. In Proceedings of the Principles of Distributed Computing. Aug 1995.
[17]
M. F. Spear, L. Dalessandro, V. Marathe, and M. L. Scott. A comprehensive strategy for contention management in software transactional memory. In PPoPP, Feb. 2009.
[18]
M. F. Spear, M. M. Michael, and M. L. Scott. Inevitability mechanisms for software transactional memory. In Proceedings of the 3rd ACM SIGPLAN Workshop on Transactional Computing. Feb 2008.
[19]
H. Volos, N. Goyal, and M. M. Swift. Pathological interaction of locks with transactional memory. In ACM SIGPLAN Workshop on Transactional Computing, February 2008.
[20]
A. Welc, B. Saha, and A.-R. Adl-Tabatabai. Irrevocable transactions and their applications. In SPAA, 2008.
[21]
L. Ziarek, A. Welc, A.-R. Adl-Tabatabai, V. Menon, T. Shpeisman, and S. Jagannathan. A uniform transactional execution environment for Java. In ECOOP, pages 129--154, 2008.
[22]
C. Zilles and D. Flint. Challenges to providing performance isolation in transactional memories. In Proceedings of the Fourth Workshop on Duplicating, Deconstructing, and Debunking, pages 48--55, Jun 2005.

Cited By

View all
  • (2013)Optimizing the Concurrent Execution of Locks and TransactionsLanguages and Compilers for Parallel Computing10.1007/978-3-642-36036-7_9(124-140)Online publication date: 2013
  • (2010)Transactional Memory, 2nd editionSynthesis Lectures on Computer Architecture10.2200/S00272ED1V01Y201006CAC0115:1(1-263)Online publication date: 22-Dec-2010

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences
ICOOOLPS '09: Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems
July 2009
73 pages
ISBN:9781605585413
DOI:10.1145/1565824
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]

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2009

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. irrevocable/inevitable transactions
  2. lock-aware transactional memory
  3. mutual exclusion
  4. software transactional memory

Qualifiers

  • Research-article

Conference

ECOOP '09

Acceptance Rates

Overall Acceptance Rate 11 of 14 submissions, 79%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2013)Optimizing the Concurrent Execution of Locks and TransactionsLanguages and Compilers for Parallel Computing10.1007/978-3-642-36036-7_9(124-140)Online publication date: 2013
  • (2010)Transactional Memory, 2nd editionSynthesis Lectures on Computer Architecture10.2200/S00272ED1V01Y201006CAC0115:1(1-263)Online publication date: 22-Dec-2010

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media