Software transactional memory offers an appealing alternative to locks by improving programmability, reliability, and scalability. However, existing STMs are impractical because they add high instrumentation costs and often provide weak progress guarantees and/or semantics. This paper introduces a novel STM called LarkTM that provides three significant features. (1) Its instrumentation adds low overhead except when accesses actually conflict, enabling low single-thread overhead and scaling well on low-contention workloads. (2) It uses eager concurrency control mechanisms, yet naturally supports flexible conflict resolution, enabling strong progress guarantees. (3) It naturally provides strong atomicity semantics at low cost. LarkTM's design works well for low-contention workloads, but adds significant overhead under higher contention, so we design an adaptive version of LarkTM that uses alternative concurrency control for high-contention objects. An implementation and evaluation in a Java virtual machine show that the basic and adaptive versions of LarkTM not only provide low single-thread overhead, but their multithreaded performance compares favorably with existing high-performance STMs.
Description
Low-overhead software transactional memory with progress guarantees and strong semantics
%0 Conference Paper
%1 Zhang:2015:LST
%A Zhang, Minjia
%A Huang, Jipeng
%A Cao, Man
%A Bond, Michael D.
%B Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
%D 2015
%I ACM
%K Concurrency JikesRVM LarkTM STM TransactionalMemory Transactions
%P 97--108
%R 10.1145/2688500.2688510
%T Low-overhead Software Transactional Memory with Progress Guarantees and Strong Semantics
%X Software transactional memory offers an appealing alternative to locks by improving programmability, reliability, and scalability. However, existing STMs are impractical because they add high instrumentation costs and often provide weak progress guarantees and/or semantics. This paper introduces a novel STM called LarkTM that provides three significant features. (1) Its instrumentation adds low overhead except when accesses actually conflict, enabling low single-thread overhead and scaling well on low-contention workloads. (2) It uses eager concurrency control mechanisms, yet naturally supports flexible conflict resolution, enabling strong progress guarantees. (3) It naturally provides strong atomicity semantics at low cost. LarkTM's design works well for low-contention workloads, but adds significant overhead under higher contention, so we design an adaptive version of LarkTM that uses alternative concurrency control for high-contention objects. An implementation and evaluation in a Java virtual machine show that the basic and adaptive versions of LarkTM not only provide low single-thread overhead, but their multithreaded performance compares favorably with existing high-performance STMs.
%@ 978-1-4503-3205-7
@inproceedings{Zhang:2015:LST,
abstract = {Software transactional memory offers an appealing alternative to locks by improving programmability, reliability, and scalability. However, existing STMs are impractical because they add high instrumentation costs and often provide weak progress guarantees and/or semantics. This paper introduces a novel STM called LarkTM that provides three significant features. (1) Its instrumentation adds low overhead except when accesses actually conflict, enabling low single-thread overhead and scaling well on low-contention workloads. (2) It uses eager concurrency control mechanisms, yet naturally supports flexible conflict resolution, enabling strong progress guarantees. (3) It naturally provides strong atomicity semantics at low cost. LarkTM's design works well for low-contention workloads, but adds significant overhead under higher contention, so we design an adaptive version of LarkTM that uses alternative concurrency control for high-contention objects. An implementation and evaluation in a Java virtual machine show that the basic and adaptive versions of LarkTM not only provide low single-thread overhead, but their multithreaded performance compares favorably with existing high-performance STMs.},
acmid = {2688510},
added-at = {2015-02-24T16:56:11.000+0100},
author = {Zhang, Minjia and Huang, Jipeng and Cao, Man and Bond, Michael D.},
biburl = {https://www.bibsonomy.org/bibtex/2068259ed149ba3e019fb1aff11b929ca/gron},
booktitle = {Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming},
description = {Low-overhead software transactional memory with progress guarantees and strong semantics},
doi = {10.1145/2688500.2688510},
interhash = {80fc6eee94afde70b6091454f8d3b3b2},
intrahash = {068259ed149ba3e019fb1aff11b929ca},
isbn = {978-1-4503-3205-7},
keywords = {Concurrency JikesRVM LarkTM STM TransactionalMemory Transactions},
location = {San Francisco, CA, USA},
numpages = {12},
pages = {97--108},
publisher = {ACM},
series = {PPoPP 2015},
timestamp = {2015-02-24T16:56:11.000+0100},
title = {Low-overhead Software Transactional Memory with Progress Guarantees and Strong Semantics},
year = 2015
}