Refined transactional lock elision

Abstract

Transactional lock elision (TLE) is a well-known technique that exploits hardware transactional memory (HTM) to introduce concurrency into lock-based software. It achieves that by attempting to execute a critical section protected by a lock in an atomic hardware transaction, reverting to the lock if these attempts fail. One significant drawback of TLE is that it disables hardware speculation once there is a thread running under lock. In this paper we present two algorithms that rely on existing compiler support for transactional programs and allow threads to speculate concurrently on HTM along with a thread holding the lock. We demonstrate the benefit of our algorithms over TLE and other related approaches with an in-depth analysis of a number of benchmarks and a wide range of workloads, including an AVL tree-based micro-benchmark and ccTSA, a real sequence assembler application.

References

1. Y. Afek, A. Levy, and A. Morrison. Software-improved hardware lock elision. In Proceedings of ACM PODC, pages 212--221, 2014.
2. Y. Afek, A. Matveev, O. R. Moll, and N. Shavit. Amalgamated lock-elision. In Proceedings of DISC, pages 309--324, 2015.
3. J. H. Ahn. ccTSA: A Coverage-Centric Threaded Sequence Assembler. PLoS ONE, 7(6), June 2012. doi: 10.1371/journal.pone.0039232. URL http://dx.doi.org/10.1371/journal.pone.0039232.
4. I. Calciu, T. Shpeisman, G. Pokam, and M. Herlihy. Improved single global lock fallback for best-effort hardware transactional memory. In ACM Workshop on Transactional Computing (TRANSACT), 2014.
5. A. T. Clements, M. F. Kaashoek, and N. Zeldovich. Scalable address spaces using RCU balanced trees. In Proceedings of ASPLOS, pages 199--210, 2012.
6. L. Dalessandro, M. F. Spear, and M. L. Scott. Norec: Streamlining stm by abolishing ownership records. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 67--78, 2010.
7. L. Dalessandro, F. Carouge, S. White, Y. Lev, M. Moir, M. L. Scott, and M. F. Spear. Hybrid NOrec: a case study in the effectiveness of best effort hardware transactional memory. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 39--52, 2011.
8. P. Damron, A. Fedorova, Y. Lev, V. Luchangco, M. Moir, and D. Nussbaum. Hybrid transactional memory. In Proceedings of ASPLOS, pages 336--346, 2006.
9. D. Dice, Y. Lev, M. Moir, and D. Nussbaum. Early experience with a commercial hardware transactional memory implementation. In Proceedings of ASPLOS, pages 157--168, 2009.
10. D. Dice, Y. Lev, M. Moir, D. Nussbaum, and M. Olszewski. Early experience with a commercial hardware transactional memory implementation. Technical report, Sun Labs, 2009.
11. D. Dice, T. L. Harris, A. Kogan, Y. Lev, and M. Moir. Pitfalls of lazy subscription. In Workshop on the Theory of Transactional Memory (WTTM), 2014.
12. D. Dice, A. Kogan, Y. Lev, T. Merrifield, and M. Moir. Adaptive integration of hardware and software lock elision techniques. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 188--197, 2014.
13. N. Diegues and P. Romano. Self-tuning intel transactional synchronization extensions. In Proceedings of the International Conference on Autonomic Computing (ICAC), pages 209--219, 2014.
14. N. Diegues, P. Romano, and L. Rodrigues. Virtues and limitations of commodity hardware transactional memory. In Proceedings of the International Conference on Parallel Architectures and Compilation (PACT), pages 3--14, 2014.
15. T. Harris and K. Fraser. Language support for lightweight transactions. In Proceedings of ACM OOPSLA, pages 388--402, 2003.
16. A. Kleen. TSX anti patterns in lock elision code, Mar. 2014. https://software.intel.com/en-us/articles/tsx-anti-patterns-in-lock-elision-code.
17. A. Matveev and N. Shavit. Reduced hardware lock elision. In Workshop on the Theory of Transactional Memory (WTTM), 2014.
18. A. Matveev and N. Shavit. Reduced hardware NOREC: An opaque obstruction-free and privatizing HyTM. In ACM Workshop on Transactional Computing (TRANSACT), 2014.
19. A. Matveev and N. Shavit. Reduced Hardware NOrec: A Safe and Scalable Hybrid Transactional Memory. In Proceedings of ASPLOS, pages 59--71, 2015.
20. F. McSherry, M. Isard, and D. G. Murray. Scalability! but at what cost? In Workshop on Hot Topics in Operating Systems (HotOS), 2015.
21. T. Nakaike, R. Odaira, M. Gaudet, M. Michael, and H. Tomari. Quantitative Comparison of Hardware Transactional Memory for Blue Gene/Q, zEnterprise EC12, Intel Core, and POWER8. In International Symposium on Computer Architecture (ISCA), 2015.
22. R. Rajwar and J. R. Goodman. Speculative lock elision: Enabling highly concurrent multithreaded execution. In ACM/IEEE International Symposium on Microarchitecture, pages 294--305, 2001.
23. T. Riegel, P. Marlier, M. Nowack, P. Felber, and C. Fetzer. Optimizing hybrid transactional memory: The importance of nonspeculative operations. In ACM SPAA, pages 53--64, 2011.
24. W. Ruan and M. Spear. Hybrid transactional memory revisited. In Proceedings of the International Conference on Distributed Computing (DISC), pages 215--231, 2015.
25. T. Wang. Integer hash function. http://web.archive.org/web/20071223173210/http://www.concentric.net/~Ttwang/tech/inthash.htm, 2007. Accessed: 2015-02-13.
26. R. M. Yoo, C. J. Hughes, K. Lai, and R. Rajwar. Performance evaluation of Intel® transactional synchronization extensions for high-performance computing. In International Conference for High Performance Computing, Networking, Storage and Analysis (SC), 2013.

Index Terms

• Computing methodologies

  • Concurrent computing methodologies

    • Concurrent programming languages

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language types

        • Concurrent programming languages