More Web Proxy on the site http://driver.im/

research-article

Inherent limitations on disjoint-access parallel implementations of transactional memory

Authors:

Alessia MilaniAuthors Info & Claims

SPAA '09: Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures

Pages 69 - 78

https://doi.org/10.1145/1583991.1584015

Published: 11 August 2009 Publication History

Abstract

Transactional memory (TM) is a promising approach for designing concurrent data structures, and it is essential to develop better understanding of the formal properties that can be achieved by TM implementations. Two fundamental properties of TM implementations are disjoint-access parallelism, which is critical for their scalability, and the invisibility of read operations, which reduces memory contention.

This paper proves an inherent tradeoff for implementations of transactional memories: they cannot be both disjoint-access parallel and have read-only transactions that are invisible and always terminate successfully. In fact, a lower bound of Ω(t) is proved on the number of writes needed in order to implement a read-only transaction of t items, which successfully terminates in a disjoint-access parallel TM implementation. The results assume strict serializability and thus hold under the assumption of opacity. It is shown how to extend the results to hold also for weaker consistency conditions, serializability and snapshot isolation.

References

[1]

Y. Afek, H. Attiya, D. Dolev, E. Gafni, M. Merritt, and N. Shavit. Atomic snapshots of shared memory. J. ACM, 40(4):873--890, 1993.

Digital Library

[2]

H. Attiya, F. Ellen, and P. Fatourou. The complexity of updating multi-writer snapshot objects. In ICDCN '06, pages 319--330.

[3]

H. Attiya, R. Guerraoui, and E. Ruppert. Partial snapshot objects. In SPAA '08, pages 336--343.

Digital Library

[4]

H. Avni and N. Shavit. Maintaining consistent transactional states without a global clock. In SIROCCO '08, pages 131--140.

Digital Library

[5]

U. Aydonat and T. Abdelrahman. Serializability of transactions in software transactional memory. In TRANSACT '08.

[6]

D. Dice, O. Shalev, and N. Shavit. Transactional locking II. In DISC '06, pages 194--208.

[7]

V. Gramoli, D. Harmanci, and P. Felber. Towards a theory of input acceptance for transactional memories. In OPODIS '08, pages 527--533.

Digital Library

[8]

R. Guerraoui, T. A. Henzinger, and V. Singh. Permissiveness in transactional memories. In DISC '08.

Digital Library

[9]

R. Guerraoui and M. Kapalka. On obstruction-free transactions. In SPAA '08, pages 304--313.

Digital Library

[10]

R. Guerraoui and M. Kapalka. On the correctness of transactional memory. In PPoPP '08, pages 175--184.

Digital Library

[11]

R. Guerraoui and M. Kapalka. The semantics of progress in lock-based transactional memory. In POPL '09, pages 404--415.

Digital Library

[12]

T. L. Harris, K. Fraser, and I. A. Pratt. A practical multi-word compare-and-swap operation. In DISC '02, pages 265--279.

Digital Library

[13]

M. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer III. Software transactional memory for dynamic-sized data structures. In PODC '03, pages 92--101.

Digital Library

[14]

M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 2008.

Digital Library

[15]

M. P. Herlihy and J. M. Wing. Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463--492, 1990.

Digital Library

[16]

D. Imbs and M. Raynal. A lock-based protocol for software transactional memory. In OPODIS '08, pages 226--245.

Digital Library

[17]

A. Israeli and L. Rappoport. Disjoint-access-parallel implementations of strong shared memory primitives. PODC '94, pages 151--160.

Digital Library

[18]

A. Israeli and A. Shirazi. The time complexity of updating snapshot memories. Inf. Process. Lett., 65(1):33--40, 1998.

Digital Library

[19]

S. Lu, A. Bernstein, and P. Lewis. Correct execution of transactions at different isolation levels. IEEE Transactions on Knowledge and Data Engineering, 16(9):1070--1081, 2004.

Digital Library

[20]

J. Napper and L. Alvisi. Lock-free serializable transactions. Technical Report TR-05-04, The University of Texas at Austin, 2005.

[21]

C. H. Papadimitriou. The serializability of concurrent database updates. J. ACM, 26(4):631--653, 1979.

Digital Library

[22]

T. Riegel, P. Felber, and C. Fetzer. A lazy snapshot algorithm with eager validation. In DISC '06, pages 284--298.

Digital Library

[23]

T. Riegel, C. Fetzer, and P. Felber. Snapshot isolation for software transactional memory. In TRANSACT '06.

[24]

T. Riegel, C. Fetzer, H. Sturzrehm, and P. Felber. From causal to z-linearizable transactional memory. In PODC '07, pages 340--341.

Digital Library

[25]

G. Weikum and G. Vossen. Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery. Morgan Kaufmann, 2001.

Digital Library

Cited By

Zhang GShang ZVerlan SMartínez-del-Amor MYuan CValencia-Cabrera LPérez-Jiménez M(2020)An Overview of Hardware Implementation of Membrane Computing ModelsACM Computing Surveys10.1145/340245653:4(1-38)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3402456
Szekeres AWhittaker MLi JSharma NKrishnamurthy APorts DZhang IBilas AMagoutis KMarkatos EKostic DSeltzer M(2020)MeerkatProceedings of the Fifteenth European Conference on Computer Systems10.1145/3342195.3387529(1-14)Online publication date: 15-Apr-2020
https://dl.acm.org/doi/10.1145/3342195.3387529
Bushkov VDziuma DFatourou PGuerraoui R(2018)The PCL TheoremJournal of the ACM10.1145/326614166:1(1-66)Online publication date: 12-Dec-2018
https://dl.acm.org/doi/10.1145/3266141
Show More Cited By

Index Terms

Inherent limitations on disjoint-access parallel implementations of transactional memory

Recommendations

Inherent Limitations on Disjoint-Access Parallel Implementations of Transactional Memory
Special Issue: Parallelism in Algorithms and Architectures

Transactional memory (TM) is a popular approach for alleviating the difficulty of programming concurrent applications; TM guarantees that a transaction, consisting of a sequence of operations, appear to be executed atomically. Two fundamental properties ...
Disjoint-Access Parallelism: Impossibility, Possibility, and Cost of Transactional Memory Implementations
PODC '15: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing

Disjoint-Access Parallelism (DAP) is considered one of the most desirable properties to maximize the scalability of Transactional Memory (TM). This paper investigates the possibility and inherent cost of implementing a DAP TM that ensures two properties ...
Grasping the gap between blocking and non-blocking transactional memories

Transactional memory (TM) is an inherently optimistic abstraction: it allows concurrent processes to execute sequences of shared-data accesses (transactions) speculatively, with an option of aborting them in the future. Early TM designs avoided using ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '09: Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures

August 2009

370 pages

ISBN:9781605586069

DOI:10.1145/1583991

General Chair:
Friedhelm Meyer auf der Heide
University of Paderborn, Germany)
,
Program Chair:
Michael A. Bender
Stony Brook University and Tokutek, Inc., USA

Copyright © 2009 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 August 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPAA 09

Sponsor:

SPAA 09: 21st ACM Symposium on Parallelism in Algorithms and Architectures

August 11 - 13, 2009

AB, Calgary, Canada

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

42
Total Citations
View Citations
301
Total Downloads

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

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang GShang ZVerlan SMartínez-del-Amor MYuan CValencia-Cabrera LPérez-Jiménez M(2020)An Overview of Hardware Implementation of Membrane Computing ModelsACM Computing Surveys10.1145/340245653:4(1-38)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3402456
Szekeres AWhittaker MLi JSharma NKrishnamurthy APorts DZhang IBilas AMagoutis KMarkatos EKostic DSeltzer M(2020)MeerkatProceedings of the Fifteenth European Conference on Computer Systems10.1145/3342195.3387529(1-14)Online publication date: 15-Apr-2020
https://dl.acm.org/doi/10.1145/3342195.3387529
Bushkov VDziuma DFatourou PGuerraoui R(2018)The PCL TheoremJournal of the ACM10.1145/326614166:1(1-66)Online publication date: 12-Dec-2018
https://dl.acm.org/doi/10.1145/3266141
Sutra PMarlier PSchiavoni VTrahay F(2018)Boosting Transactional Memory with Stricter SerializabilityCoordination Models and Languages10.1007/978-3-319-92408-3_11(231-251)Online publication date: 27-May-2018
https://doi.org/10.1007/978-3-319-92408-3_11
Bhat SEqbal RClements AKaashoek MZeldovich N(2017)Scaling a file system to many cores using an operation logProceedings of the 26th Symposium on Operating Systems Principles10.1145/3132747.3132779(69-86)Online publication date: 14-Oct-2017
https://dl.acm.org/doi/10.1145/3132747.3132779
Clements AKaashoek MKohler EMorris RZeldovich N(2017)The scalable commutativity ruleCommunications of the ACM10.1145/306891460:8(83-90)Online publication date: 24-Jul-2017
https://dl.acm.org/doi/10.1145/3068914
Fatourou P(2017)Concurrency for the Masses: The Paradigm of Software Transactional Memory2017 19th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)10.1109/SYNASC.2017.00012(17-22)Online publication date: Sep-2017
https://doi.org/10.1109/SYNASC.2017.00012
Lu HHodsdon CNgo KMu SLloyd WKeeton KRoscoe T(2016)The SNOW theorem and latency-optimal read-only transactionsProceedings of the 12th USENIX conference on Operating Systems Design and Implementation10.5555/3026877.3026889(135-150)Online publication date: 2-Nov-2016
https://dl.acm.org/doi/10.5555/3026877.3026889
Fatourou PKanellou EKosmas ERabbi M(2016)WFR-TMJournal of Parallel and Distributed Computing10.1016/j.jpdc.2016.05.00296:C(134-151)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1016/j.jpdc.2016.05.002
Clements AKaashoek MZeldovich NMorris RKohler E(2015)The Scalable Commutativity RuleACM Transactions on Computer Systems10.1145/269968132:4(1-47)Online publication date: 20-Jan-2015
https://dl.acm.org/doi/10.1145/2699681
Show More Cited By

View Options

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