Article

Advanced contention management for dynamic software transactional memory

Authors:

William N. Scherer, III,

Michael L. ScottAuthors Info & Claims

PODC '05: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing

Pages 240 - 248

https://doi.org/10.1145/1073814.1073861

Published: 17 July 2005 Publication History

Abstract

The obstruction-free Dynamic Software Transactional Memory (DSTM) system of Herlihy et al@. allows only one transaction at a time to acquire an object for writing. Should a second require an object currently in use, a contention manager must determine which may proceed and which must wait or abort.We analyze both new and existing policies for this contention management problem, using experimental results from a 16-processor SunFire machine. We consider both visible and invisible versions of read access, and benchmarks that vary in complexity, level of contention, tendency toward circular dependence, and mix of reads and writes. We present fair proportional-share prioritized versions of several policies, and identify a candidate default policy: one that provides, for the first time, good performance in every case we test. The tradeoff between visible and invisible reads remains application-specific: visible reads reduce the overhead for incremental validation when opening new objects, but the requisite bookkeeping exacerbates contention for the memory interconnect.

References

[1]

T. E. Anderson. The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors. IEEE Trans. on Parallel and Distributed Systems, 1(1):6--16, Jan. 1990.]]

Digital Library

[2]

K. M. Chandy and J. Misra. The Drinking Philosophers Problem. ACM Trans. on Programming Languages and Systems, 6(4):632--646, Oct. 1984.]]

Digital Library

[3]

K. Fraser. Practical Lock-Freedom. Ph.17emD. dissertation, UCAM-CL-TR-579, Computer Laboratory, University of Cambridge, Feb. 2004.]]

[4]

T. Harris and K. Fraser. Language Support for Lightweight Transactions. In OOPSLA 2003 Conf. Proc., Anaheim, CA, Oct. 2003.]]

Digital Library

[5]

B. He, W. N. Scherer III, and M. L. Scott. Preemption Adaptivity in Time-Published Queue-Based Spin Locks. TR 867, Computer Science Dept., Univ. of Rochester, May 2005.]]

[6]

M. Herlihy, V. Luchangco, and M. Moir. Obstruction-Free Synchronization: Double-Ended Queues as an Example. In Proc. of the 23rd Intl. Conf. on Distributed Computing Systems, Providence, RI, May, 2003.]]

Digital Library

[7]

M. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer III. Software Transactional Memory for Dynamic-sized Data Structures. In Proc. of the 22nd ACM Symp. on Principles of Distributed Computing, pages 92--101, Boston, MA, July 2003.]]

Digital Library

[8]

M. Herlihy and J. E. Moss. Transactional Memory: Architectural Support for Lock-Free Data Structures. In Proc. of the 20th Intl. Symp. on Computer Architecture, pages 289--300, San Diego, CA, May 1993. Expanded version available as CRL 92/07, Dec. Cambridge Research Laboratory, Dec. 1992.]]

Digital Library

[9]

D. Lea. Concurrency JSR-166 Interest Site. http://gee.cs.oswego.edu/dl/concurrency-interest/.]]

[10]

V. J. Marathe, M. L. Scott, and W. N. Scherer III. Adaptive Software Transactional Memory. TR 868, Computer Science Dept., Univ. of Rochester, May 2005.]]

[11]

J. T. Robinson and M. V. Devarakonda. Data Cache Management Using Frequency-Based Replacement. In Proc. of ACM SIGMETRICS, pages 134--142, 1990.]]

Digital Library

[12]

W. N. Scherer III and M. L. Scott. Contention Management in Dynamic Software Transactional Memory. In Proc. of the ACM PODC Workshop on Concurrency and Synchronization in Java Programs, St. John's, NL, Canada, July, 2004.]]

Digital Library

[13]

N. Shavit and D. Touitou. Software Transactional Memory. In Proc. of the 14th ACM Symp. on Principles of Distributed Computing, pages 204--213, Ottawa, Canada, Aug. 1995.]]

Digital Library

[14]

E. Tune, D. Liang, D. M. Tullsen, and B. Calder. Dynamic Prediction of Critical Path Instructions. In Proc. of the 7th Intl. Symp. on High Performance Computer Architecture, pages 185--196, Jan. 2001.]]

Digital Library

[15]

C. A. Waldspurger and W. E. Weihl. Lottery Scheduling: Flexible Proportional-Share Resource Management. In Proc. of the 1st Symp. on Operating Systems Design and Implementation, Monterey, CA, Nov. 1994.]]

Digital Library

Cited By

Ramos JDu Bois ACavalheiro G(2023)Obstruction-Free Distributed Transactional MemoryProceedings of the XXVII Brazilian Symposium on Programming Languages10.1145/3624309.3624316(33-40)Online publication date: 25-Sep-2023
https://dl.acm.org/doi/10.1145/3624309.3624316
Zhang ZGlova ASherwood TBalkind JAamodt TJerger NSwift M(2023)A Prediction System ServiceProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3575693.3575714(48-60)Online publication date: 27-Jan-2023
https://dl.acm.org/doi/10.1145/3575693.3575714
Sheng YHassan ASpear M(2023)Separating Mechanism from Policy in STM2023 32nd International Conference on Parallel Architectures and Compilation Techniques (PACT)10.1109/PACT58117.2023.00031(279-296)Online publication date: 21-Oct-2023
https://doi.org/10.1109/PACT58117.2023.00031
Show More Cited By

Index Terms

Advanced contention management for dynamic software transactional memory
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Parallel programming languages

Recommendations

Scheduling support for transactional memory contention management
PPoPP '10

Transactional Memory (TM) is considered as one of the most promising paradigms for developing concurrent applications. TM has been shown to scale well on >multiple cores when the data access pattern behaves "well," i.e., when few conflicts are induced. ...
Scheduling support for transactional memory contention management
PPoPP '10: Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Transactional Memory (TM) is considered as one of the most promising paradigms for developing concurrent applications. TM has been shown to scale well on >multiple cores when the data access pattern behaves "well," i.e., when few conflicts are induced. ...
Mileage-based contention management in transactional memory
PACT '12: Proceedings of the 21st international conference on Parallel architectures and compilation techniques

In Transactional Memory (TM), a conflict occurs when a memory block is accessed concurrently by two or more transactions and at least one of them is a write access. The management of conflicts significantly impacts TM performance. There are two ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '05: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing

July 2005

364 pages

ISBN:1581139942

DOI:10.1145/1073814

General Chair:
Marcos Aguilera
HP Labs
,
Program Chair:
James Aspnes
Yale University

Copyright © 2005 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: 17 July 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PODC05

Sponsor:

PODC05: ACM Symposium on Principles of Distributed Computing

July 17 - 20, 2005

NV, Las Vegas, USA

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

306
Total Citations
View Citations
1,122
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ramos JDu Bois ACavalheiro G(2023)Obstruction-Free Distributed Transactional MemoryProceedings of the XXVII Brazilian Symposium on Programming Languages10.1145/3624309.3624316(33-40)Online publication date: 25-Sep-2023
https://dl.acm.org/doi/10.1145/3624309.3624316
Zhang ZGlova ASherwood TBalkind JAamodt TJerger NSwift M(2023)A Prediction System ServiceProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3575693.3575714(48-60)Online publication date: 27-Jan-2023
https://dl.acm.org/doi/10.1145/3575693.3575714
Sheng YHassan ASpear M(2023)Separating Mechanism from Policy in STM2023 32nd International Conference on Parallel Architectures and Compilation Techniques (PACT)10.1109/PACT58117.2023.00031(279-296)Online publication date: 21-Oct-2023
https://doi.org/10.1109/PACT58117.2023.00031
Zhang JYi QPeterson CDechev D(2023)Compiler‐driven approach for automating nonblocking synchronization in concurrent data abstractionsConcurrency and Computation: Practice and Experience10.1002/cpe.793536:5Online publication date: 24-Oct-2023
https://doi.org/10.1002/cpe.7935
Gao LWang JZhang W(2022)Adaptive Contention Management for Fine-Grained Synchronization on Commodity GPUsACM Transactions on Architecture and Code Optimization10.1145/354730119:4(1-21)Online publication date: 16-Sep-2022
https://dl.acm.org/doi/10.1145/3547301
Larus JRajwar RLarus JRajwar R(2022)Software Transactional MemoryTransactional Memory10.1007/978-3-031-01719-3_3(53-130)Online publication date: 17-Oct-2022
https://doi.org/10.1007/978-3-031-01719-3_3
Larus JRajwar RLarus JRajwar R(2022)Programming Transactional MemoryTransactional Memory10.1007/978-3-031-01719-3_2(15-52)Online publication date: 17-Oct-2022
https://doi.org/10.1007/978-3-031-01719-3_2
Anderton WChakraborty TYoung M(2021)Windowed backoff algorithms for WiFi: theory and performance under batched arrivalsDistributed Computing10.1007/s00446-021-00403-9Online publication date: 13-Sep-2021
https://doi.org/10.1007/s00446-021-00403-9
Skrzypczak JSchintke FSchutt T(2020)RMWPaxos: Fault-Tolerant In-Place Consensus SequencesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2020.298189131:10(2392-2405)Online publication date: 1-Oct-2020
https://doi.org/10.1109/TPDS.2020.2981891
Busch CHerlihy MPopovic MSharma G(2020)Fast Scheduling in Distributed Transactional MemoryTheory of Computing Systems10.1007/s00224-020-10008-7Online publication date: 23-Oct-2020
https://doi.org/10.1007/s00224-020-10008-7
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.

Figures

Tables

Media

View Table of Conten