research-article

Coarse-grained transactions

Authors:

Matthew Parkinson,

Maurice HerlihyAuthors Info & Claims

ACM SIGPLAN Notices, Volume 45, Issue 1

Pages 19 - 30

https://doi.org/10.1145/1707801.1706304

Published: 17 January 2010 Publication History

Abstract

Traditional transactional memory systems suffer from overly conservative conflict detection, yielding so-called false conflicts, because they are based on fine-grained, low-level read/write conflicts. In response, the recent trend has been toward integrating various abstract data-type libraries using ad-hoc methods of high-level conflict detection. These proposals have led to improved performance but a lack of a unified theory has led to confusion in the literature.

We clarify these recent proposals by defining a generalization of transactional memory in which a transaction consists of coarse-grained (abstract data-type) operations rather than simple memory read/write operations. We provide semantics for both pessimistic (e.g. transactional boosting) and optimistic (e.g. traditional TMs and recent alternatives) execution. We show that both are included in the standard atomic semantics, yet find that the choice imposes different requirements on the coarse-grained operations: pessimistic requires operations be left-movers, optimistic requires right-movers. Finally, we discuss how the semantics applies to numerous TM implementation details discussed widely in the literature.

References

[1]

Abadi, M., Birrell, A., Harris, T., and Isard, M. Semantics of transactional memory and automatic mutual exclusion. In The 35th ACM SIGPLAN SIGACT Symposium on Principles of Programming Languages (POPL'08) (2008), G. C. Necula and P. Wadler, Eds., ACM, pp. 63--74.

Digital Library

[2]

Aleen, F., and Clark, N. Commutativity analysis for software parallelization: letting program transformations see the big picture. In Proceedings of the 14th international conference on Architectural support for programming languages and operating systems (ASPLOS-XII) (2009), M. L. Soffa and M. J. Irwin, Eds., ACM, pp. 241--252.

Digital Library

[3]

Baldassin, A., and Burckhardt, S. Lightweight software transactions for games. In Proceedings of the First USENIX Workshop on Hot Topics in Parallelism (HotPar'09) (2009).

Digital Library

[4]

Beeri, C., Bernstein, P., Goodman, N., Lai, M.-Y., and Shasha, D. A concurrency control theory for nested transactions (preliminary report). In Proceedings of the 2nd annual ACM symposium on Principles of distributed computing (PODC'83) (New York, NY, USA, 1983), ACM Press, pp. 45--62.

Digital Library

[5]

Bernstein, A. Analysis of programs for parallel processing. IEEE Transactions on Electronic Computers 15, 5 (1966), 757--763.

[6]

Damron, P., Fedorova, A., Lev, Y., Luchangco, V., Moir, M., and Nussbaum, D. Hybrid transactional memory. In Proceedings of the 12th international conference on Architectural support for programming languages and operating systems (ASPLOS-XII) (New York, NY, USA, 2006), ACM Press, pp. 336--346.

Digital Library

[7]

Dice, D., Shalev, O., and Shavit, N. Transactional locking II. In Proceedings of the 20th International Symposium on Distributed Computing (DISC'06) (September 2006).

Digital Library

[8]

Flanagan, C., Freund, S. N., and Yi, J. Velodrome: a sound and complete dynamic atomicity checker for multithreaded programs. In PLDI'08: Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation (New York, NY, USA, 2008), ACM, pp. 293--303.

Digital Library

[9]

Guerraoui, R., and Kapalka, M. On the correctness of transactional memory. In Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming (PPoPP'08) (New York, NY, USA, 2008), ACM, pp. 175--184.

Digital Library

[10]

Harris, T., Marlow, S., Jones, S. L. P., and Herlihy, M. Composable memory transactions. Commun. ACM 51, 8 (2008), 91--100.

Digital Library

[11]

Herlihy, M., and Koskinen, E. Transactional boosting: A methodology for highly concurrent transactional objects. In Proceedings of the 13th ACM SIGPLAN symposium on Principles and practice of parallel programming (PPoPP'08) (2008).

Digital Library

[12]

Herlihy, M., Luchangco, V., Moir, M., and Scherer, III, W. N. Software transactional memory for dynamic-sized data structures. In Proceedings of the 22nd annual symposium on Principles of distributed computing (PODC'03) (2003), ACM Press, pp. 92--101.

Digital Library

[13]

Herlihy, M., and Moss, J. E. B. Transactional memory: architectural support for lock-free data structures. In Proceedings of the 20th Annual International Symposium on Computer Architecture (ISCA'93) (1993), ACM Press, pp. 289--300.

Digital Library

[14]

Herlihy, M. P., and Wing, J. M. Linearizability: a correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS) 12, 3 (1990), 463--492.

Digital Library

[15]

Jagannathan, S. Vitek, J., Welc, A., Hosking, A. A Transactional object calculus. Science of Computer Programming. 57, 2 (August 2005), 164--186.

Digital Library

[16]

Korth, H. F. Locking primitives in a database system. J. ACM 30, 1 (1983), 55--79.

Digital Library

[17]

Koskinen, E., and Herlihy, M. Checkpoints and continuations instead of nested transactions. In Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures (SPAA'08) (New York, NY, USA, 2008), ACM, pp. 160--168.

Digital Library

[18]

Koskinen, E., and Herlihy, M. Dreadlocks: efficient deadlock detection. In Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures (SPAA'08) (New York, NY, USA, 2008), ACM, pp. 297--303.

Digital Library

[19]

Koskinen, E., Parkinson, M., and Herlihy, M. Coarse-grained transactions. Tech. Rep. 759, Computer Laboratory, University of Cambridge, 2009.

[20]

Kulkarni, M., Pingali, K., Walter, B., Ramanarayanan, G., Bala, K., and Chew, L. P. Optimistic parallelism requires abstractions. In Proceedings of the ACM SIGPLAN 2007 Conference on Programming Language Design and Implementation (PLDI'07) (2007), J. Ferrante and K. S. McKinley, Eds., ACM, pp. 211--222.

Digital Library

[21]

Lam, M., and Rinard, M. Coarse-grain parallel programming in Jade. In Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming (PPoPP'91) (1991), ACM New York, NY, USA, pp. 94--105.

Digital Library

[22]

Lipton, R. J. Reduction: a method of proving properties of parallel programs. Commun. ACM 18, 12 (1975), 717--721.

Digital Library

[23]

Moore, K. F., and Grossman, D. High-level small-step operational semantics for transactions. In Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL'08) (New York, NY, USA, 2008), ACM, pp. 51--62.

Digital Library

[24]

Moravan, M. J., Bobba, J., Moore, K. E., Yen, L., Hill, M. D., Liblit, B., Swift, M. M., and Wood, D. A. Supporting nested transactional memory in logtm. In Proceedings of the 12th international conference on Architectural support for programming languages and operating systems (ASPLOS-XII) (New York, NY, USA, 2006), ACM Press, pp. 359--370.

Digital Library

[25]

Moravan, M. J., Bobba, J., Moore, K. E., Yen, L., Hill, M. D., Liblit, B., Swift, M. M., and Wood, D. A. Supporting nested transactional memory in logtm. SIGOPS Oper. Syst. Rev. 40, 5 (2006), 359--370.

Digital Library

[26]

Rinard, M., and Lam, M. The design, implementation, and evaluation of Jade. ACM Transactions on Programming Languages and Systems (TOPLAS) 20, 3 (1998), 483--545.

Digital Library

[27]

Rinard, M. C., and Diniz, P. C. Commutativity analysis: A new analysis technique for parallelizing compilers. ACM Transactions on Programming Languages and Systems (TOPLAS) 19, 6 (November 1997), 942--991.

Digital Library

[28]

Saha, B., Adl-Tabatabai, A.-R., Hudson, R. L., Minh, C. C., and Hertzberg, B. McRT-STM: a high performance software transactional memory system for a multi-core runtime. In Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming (PPoPP'06) (New York, NY, USA, 2006), ACM, pp. 187--197.

Digital Library

[29]

Schwarz, P. M., and Spector, A. Z. Synchronizing shared abstract types. ACM Trans. on Comp. Sys. 2, 3 (1984), 223--250.

Digital Library

[30]

Spear, M. F., Marathe, V. J., Dalessandro, L., and Scott, M. L. Privatization techniques for software transactional memory. In Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing (PODC'07) (New York, NY, USA, 2007), ACM, pp. 338--339.

Digital Library

[31]

Steele, Jr, G. L. Making asynchronous parallelism safe for the world. In Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL'90) (New York, NY, USA, 1990), ACM Press, pp. 218--231.

Digital Library

[32]

Weihl, W. E. Data-dependent concurrency control and recovery (extended abstract). In Proceedings of the second annual ACM symposium on Principles of distributed computing (PODC'83) (New York, NY, USA, 1983), ACM Press, pp. 63--75.

Digital Library

[33]

William N. Scherer, I., and Scott, M. L. Advanced contention management for dynamic software transactional memory. In Proceedings of the 24th annual ACM symposium on Principles of distributed computing (PODC'05) (New York, NY, USA, 2005), ACM, pp. 240--248.

Digital Library

Cited By

Koskinen EBansal K(2021)Decomposing Data Structure Commutativity Proofs with $$m\!n$$-DifferencingVerification, Model Checking, and Abstract Interpretation10.1007/978-3-030-67067-2_5(81-103)Online publication date: 12-Jan-2021
https://doi.org/10.1007/978-3-030-67067-2_5
Bansal KKoskinen ETripp O(2020)Synthesizing Precise and Useful Commutativity ConditionsJournal of Automated Reasoning10.1007/s10817-020-09573-wOnline publication date: 29-Aug-2020
https://doi.org/10.1007/s10817-020-09573-w
LaBorde PLebanoff LPeterson CZhang DDechev D(2020)Dynamic Transactional TransformationConcurrency and Computation: Practice and Experience10.1002/cpe.573234:2Online publication date: 3-Apr-2020
https://doi.org/10.1002/cpe.5732
Show More Cited By

Index Terms

Coarse-grained transactions

Recommendations

Coarse-grained transactions
POPL '10: Proceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Traditional transactional memory systems suffer from overly conservative conflict detection, yielding so-called false conflicts, because they are based on fine-grained, low-level read/write conflicts. In response, the recent trend has been toward ...
The Push/Pull model of transactions
PLDI '15

We present a general theory of serializability, unifying a wide range of transactional algorithms, including some that are yet to come. To this end, we provide a compact semantics in which concurrent transactions PUSH their effects into the shared view ...
The Push/Pull model of transactions
PLDI '15: Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation

We present a general theory of serializability, unifying a wide range of transactional algorithms, including some that are yet to come. To this end, we provide a compact semantics in which concurrent transactions PUSH their effects into the shared view ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 45, Issue 1

POPL '10

January 2010

500 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1707801

Issue’s Table of Contents

POPL '10: Proceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages
January 2010
520 pages
ISBN:9781605584799
DOI:10.1145/1706299
General Chair:
Manuel Hermenegildo
IMDEA-Software and T.U. of Madrid, Spain
,
Program Chair:
Jens Palsberg
UCLA, University of California, Los Angeles

Copyright © 2010 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: 17 January 2010

Published in SIGPLAN Volume 45, Issue 1

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

85
Total Citations
View Citations
625
Total Downloads

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

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Koskinen EBansal K(2021)Decomposing Data Structure Commutativity Proofs with $$m\!n$$-DifferencingVerification, Model Checking, and Abstract Interpretation10.1007/978-3-030-67067-2_5(81-103)Online publication date: 12-Jan-2021
https://doi.org/10.1007/978-3-030-67067-2_5
Bansal KKoskinen ETripp O(2020)Synthesizing Precise and Useful Commutativity ConditionsJournal of Automated Reasoning10.1007/s10817-020-09573-wOnline publication date: 29-Aug-2020
https://doi.org/10.1007/s10817-020-09573-w
LaBorde PLebanoff LPeterson CZhang DDechev D(2020)Dynamic Transactional TransformationConcurrency and Computation: Practice and Experience10.1002/cpe.573234:2Online publication date: 3-Apr-2020
https://doi.org/10.1002/cpe.5732
Sharit JMoxley JBoot WCharness NRogers WCzaja S(2019)Effects of Extended Use of an Age-friendly Computer System on Assessments of Computer Proficiency, Attitudes, and Usability by Older Non--Computer UsersACM Transactions on Accessible Computing10.1145/332529012:2(1-28)Online publication date: 11-Jun-2019
https://dl.acm.org/doi/10.1145/3325290
Vacher MAman FRossato SPortet FLecouteux B(2019)Making Emergency Calls More Accessible to Older Adults Through a Hands-free Speech Interface in the HouseACM Transactions on Accessible Computing10.1145/331013212:2(1-25)Online publication date: 11-Jun-2019
https://dl.acm.org/doi/10.1145/3310132
LaBorde PLebanoff LPeterson CZhang DDechev D(2019)Wait-free Dynamic Transactions for Linked Data StructuresProceedings of the 10th International Workshop on Programming Models and Applications for Multicores and Manycores10.1145/3303084.3309491(41-50)Online publication date: 17-Feb-2019
https://dl.acm.org/doi/10.1145/3303084.3309491
Lebanoff LPeterson CDechev D(2019)Check-Wait-Pounce: Increasing Transactional Data Structure Throughput by Delaying TransactionsDistributed Applications and Interoperable Systems10.1007/978-3-030-22496-7_2(19-35)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-22496-7_2
Zhang DLaborde PLebanoff LDechev D(2018)Lock-Free Transactional Transformation for Linked Data StructuresACM Transactions on Parallel Computing10.1145/32096905:1(1-37)Online publication date: 13-Jun-2018
https://dl.acm.org/doi/10.1145/3209690
Golan-Gueta GRamalingam GSagiv MYahav E(2017)Automatic Scalable Atomicity via Semantic LockingACM Transactions on Parallel Computing10.1145/30402233:4(1-29)Online publication date: 23-Mar-2017
https://dl.acm.org/doi/10.1145/3040223
Cole RRamachandran V(2017)Resource Oblivious Sorting on MulticoresACM Transactions on Parallel Computing10.1145/30402213:4(1-31)Online publication date: 23-Mar-2017
https://dl.acm.org/doi/10.1145/3040221
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