research-article

Software-improved hardware lock elision

Authors:

Adam MorrisonAuthors Info & Claims

PODC '14: Proceedings of the 2014 ACM symposium on Principles of distributed computing

Pages 212 - 221

https://doi.org/10.1145/2611462.2611482

Published: 15 July 2014 Publication History

Abstract

With hardware transactional memory (HTM) becoming available in mainstream processors, lock-based critical sections may now initiate a hardware transaction instead of taking the lock, enabling their concurrent execution unless a real data conflict occurs. However, just a few transactional aborts can cause the lock to be acquired non-transactionally resulting in the serialization of all the threads, severely degrading the amount of speedup obtained. In this paper we provide two software extension mechanisms that considerably improve the concurrency and speedup levels attained by lock based programs using HTM-based lock elision. The first sacrifices opacity to achieve higher levels of concurrency, and the second retains opacity while reaching slightly lower levels of concurrency.

Evaluation on STAMP and on data structure benchmarks on an Intel Haswell processor shows that these techniques improve the speedup by up to 3.5 times and $10$ times respectively, compared to using Haswell's hardware lock elision as is.

References

[1]

Intel 64 and IA-32 Architectures Optimization Reference Manual.

[2]

Intel Architecture Instruction Set Extensions Programming Reference.

[3]

Y. Afek, A. Levy, and A. Morrison. Programming with hardware lock elision. In PPoPP 2013.

Digital Library

[4]

Y. Afek, A. Levy, and A. Morrison. Software-Improved Hardware Lock Elision. Technical report, Tel Aviv University.

[5]

Y. Afek, A. Matveev, and N. Shavit. Pessimistic software lock-elision. In DISC 2012.

Digital Library

[6]

C. Bienia. Benchmarking Modern Multiprocessors. PhD thesis, Princeton University, January 2011.

Digital Library

[7]

J. Bobba, K. E. Moore, H. Volos, L. Yen, M. D. Hill, M. M. Swift, and D. A. Wood. Performance pathologies in hardware transactional memory. In ISCA 2007.

Digital Library

[8]

H. W. Cain, M. M. Michael, B. Frey, C. May, D. Williams, and H. Le. Robust architectural support for transactional memory in the power architecture. In ISCA 2013.

Digital Library

[9]

I. Calciu, T. Shpeisman, G. Pokam, and M. Herlihy. Improved Single Global Lock Fallback for Best-effort Hardware Transactional Memory. In TRANSACT 2014.

[10]

C. Cao Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford transactional applications for multi-processing. In IISWC 2008.

[11]

T. S. Craig. Building FIFO and priority-queuing spin locks from atomic swap. Technical Report 93-02-02, Department of Computer Science and Engineering, University of Washington, 1993.

[12]

D. Dice, Y. Lev, M. Moir, D. Nussbaum, and M. Olszewski. Early experience with a commercial hardware transactional memory implementation. Technical Report TR-2009-180, Sun Microsystems, 2009.

[13]

N. Diegues and P. Romano. Time-warp: Lightweight Abort Minimization in Transactional Memory. In PPoPP 2014.

Digital Library

[14]

R. Guerraoui and M. Kapalka. On the correctness of transactional memory. In PPoPP 2008.

Digital Library

[15]

M. Herlihy. Wait-free synchronization. ACM TOPLAS, 13:124--149, January 1991.

Digital Library

[16]

M. Herlihy and J. E. B. Moss. Transactional memory: architectural support for lock-free data structures. In ISCA 1993.

Digital Library

[17]

P. S. Magnusson, A. Landin, and E. Hagersten. Queue locks on cache coherent multiprocessors. In ISPP '94.

Digital Library

[18]

J. M. Mellor-Crummey and M. L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM TOCS, 9(1):21--65, Feb. 1991.

Digital Library

[19]

D. Papagiannopoulou, G. Capodanno, R. I. Bahar, T. Moreshet, A. Holla, and M. Herlihy. Energy-Efficient and High-Performance Lock Speculation Hardware for Embedded Multicore Systems. In TRANSACT 2013.

[20]

N. Piggin. x86: FIFO ticket spinlocks. http://lkml.org/lkml/2007/11/1/125, 2007.

[21]

R. Rajwar and J. R. Goodman. Speculative Lock Elision: enabling highly concurrent multithreaded execution. In MICRO 2001.

Digital Library

[22]

R. Rajwar and J. R. Goodman. Transactional lock-free execution of lock-based programs. In ASPLOS 2002.

Digital Library

[23]

A. Roy, S. Hand, and T. Harris. A runtime system for software lock elision. In EuroSys 2009.

Digital Library

[24]

A. Wang, M. Gaudet, P. Wu, J. N. Amaral, M. Ohmacht, C. Barton, R. Silvera, and M. Michael. Evaluation of Blue Gene/Q hardware support for transactional memories. In PACT 2012.

Digital Library

Cited By

Khalaji MBrown TDaudjee KAksenov VLee IChabbi MSteuwer M(2024)Practical Hardware Transactional vEB TreesProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3627535.3638504(215-228)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3627535.3638504
Sustran ZProtic J(2021)Migration in Hardware Transactional Memory on Asymmetric MultiprocessorIEEE Access10.1109/ACCESS.2021.30775399(69346-69364)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3077539
Dice DHerlihy MKogan A(2018)Improving Parallelism in Hardware Transactional MemoryACM Transactions on Architecture and Code Optimization10.1145/317796215:1(1-24)Online publication date: 22-Mar-2018
https://dl.acm.org/doi/10.1145/3177962
Show More Cited By

Index Terms

Software-improved hardware lock elision
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Concurrent programming languages

Recommendations

Hardware read-write lock elision
EuroSys '16: Proceedings of the Eleventh European Conference on Computer Systems

Hardware Lock Elision (HLE) represents a promising technique to enhance parallelism of concurrent applications relying on conventional, lock-based synchronization. The idea at the basis of current HLE approaches is to wrap critical sections into ...
Programming with hardware lock elision
PPoPP '13: Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming

We present a simple yet effective technique for improving performance of lock-based code using the hardware lock elision (HLE) feature in Intel's upcoming Haswell processor.

We also describe how to extend Haswell's HLE mechanism to achieve a similar ...
Transactional Lock Elision Meets Combining
PODC '17: Proceedings of the ACM Symposium on Principles of Distributed Computing

Flat combining (FC) and transactional lock elision (TLE) are two techniques that facilitate efficient multi-thread access to a sequentially implemented data structure protected by a lock. FC allows threads to delegate their operations to another (...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '14: Proceedings of the 2014 ACM symposium on Principles of distributed computing

July 2014

444 pages

ISBN:9781450329446

DOI:10.1145/2611462

General Chair:
Magnús Halldórsson
Reykjavik Universite, Iceland
,
Program Chair:
Shlomi Dolev
Ben-Gurion University, Israel

Copyright © 2014 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: 15 July 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '14

Sponsor:

PODC '14: ACM Symposium on Principles of Distributed Computing

July 15 - 18, 2014

Paris, France

Acceptance Rates

PODC '14 Paper Acceptance Rate 39 of 141 submissions, 28%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
291
Total Downloads

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

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Khalaji MBrown TDaudjee KAksenov VLee IChabbi MSteuwer M(2024)Practical Hardware Transactional vEB TreesProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3627535.3638504(215-228)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3627535.3638504
Sustran ZProtic J(2021)Migration in Hardware Transactional Memory on Asymmetric MultiprocessorIEEE Access10.1109/ACCESS.2021.30775399(69346-69364)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3077539
Dice DHerlihy MKogan A(2018)Improving Parallelism in Hardware Transactional MemoryACM Transactions on Architecture and Code Optimization10.1145/317796215:1(1-24)Online publication date: 22-Mar-2018
https://dl.acm.org/doi/10.1145/3177962
Wu ZLuo YLu KWang X(2018)Parallelizing Stochastic Gradient Descent with Hardware Transactional Memory for Matrix Factorization2018 3rd International Conference on Information Systems Engineering (ICISE)10.1109/ICISE.2018.00029(118-121)Online publication date: May-2018
https://doi.org/10.1109/ICISE.2018.00029
Raminhas PIssa SRomano PEl-Araby EEl-Ghazawi TPanda D(2018)Enhancing efficiency of hybrid transactional memory via dynamic data partitioning schemesProceedings of the 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing10.1109/CCGRID.2018.00020(51-61)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1109/CCGRID.2018.00020
Chen ZHe XSun JChen HHe L(2018)Concurrent hash tables on multicore machines: Comparison, evaluation and implicationsFuture Generation Computer Systems10.1016/j.future.2017.12.05482(127-141)Online publication date: May-2018
https://doi.org/10.1016/j.future.2017.12.054
Chen ZHe XSun JChen H(2018)Have Your Cake and Eat it (Too)International Journal of Parallel Programming10.1007/s10766-017-0529-746:4(699-709)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1007/s10766-017-0529-7
Alistarh DKopinsky JKuznetsov PRavi SShavit N(2018)Inherent limitations of hybrid transactional memoryDistributed Computing10.1007/s00446-017-0305-331:3(167-185)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s00446-017-0305-3
Diegues NRomano PGarbatov S(2017)SeerACM Transactions on Computer Systems10.1145/313203635:3(1-41)Online publication date: 14-Nov-2017
https://dl.acm.org/doi/10.1145/3132036
Kogan ALev YSchiller ESchwarzmann A(2017)Transactional Lock Elision Meets CombiningProceedings of the ACM Symposium on Principles of Distributed Computing10.1145/3087801.3087838(231-240)Online publication date: 25-Jul-2017
https://dl.acm.org/doi/10.1145/3087801.3087838
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 Table of Contents