Performance pathologies in hardware transactional memory

ABSTRACT

Hardware Transactional Memory (HTM) systems reflect choices from three key design dimensions: conflict detection, version management, and conflict resolution. Previously proposed HTMs represent three points in this design space: lazy conflict detection, lazy version management, committer wins (LL); eager conflict detection, lazy version management, requester wins (EL); and eager conflict detection, eager version management, and requester stalls with conservative deadlock avoidance (EE). To isolate the effects of these high-level design decisions, we develop a common framework that abstracts away differences in cache write policies, interconnects, and ISA to compare these three design points. Not surprisingly, the relative performance of these systems depends on the workload. Under light transactional loads they perform similarly, but under heavy loads they differ by up to 80%. None of the systems performs best on all of our benchmarks. We identify seven performance pathologies-interactions between workload and system that degrade performance-as the root cause of many performance differences: FriendlyFire, StarvingWriter, SerializedCommit, FutileStall, StarvingElder, RestartConvoy, and DuelingUpgrades. We discuss when and on which systems these pathologies can occur and show that they actually manifest within TM workloads. The insight provided by these pathologies motivated four enhanced systems that often significantly reduce transactional memory overhead. Importantly, by avoiding transaction pathologies, each enhanced system performs well across our suite of benchmarks.

REFERENCES

• 1: Alaa R. Alameldeen , David A. Wood, Variability in Architectural Simulations of Multi-Threaded Workloads, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.7, February 08-12, 2003
• 2: C. Scott Ananian , Krste Asanovic , Bradley C. Kuszmaul , Charles E. Leiserson , Sean Lie, Unbounded Transactional Memory, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.316-327, February 12-16, 2005 [doi>10.1109/HPCA.2005.41]
• 3: Mike Blasgen , Jim Gray , Mike Mitoma , Tom Price, The convoy phenomenon, ACM SIGOPS Operating Systems Review, v.13 n.2, p.20-25, April 1979 [doi>10.1145/850657.850659]
• 4: Luis Ceze , James Tuck , Josep Torrellas , Calin Cascaval, Bulk Disambiguation of Speculative Threads in Multiprocessors, Proceedings of the 33rd annual international symposium on Computer Architecture, p.227-238, June 17-21, 2006
• 5: Hassan Chafi, Chi Cao Minh, Austen McDonald, Brian D. Carlstrom, JaeWoong Chung, Lance Hammond, Christos Kozyrakis, and Kunle Olukotun. A Scalable, Non-blocking Approach to Transactional Memory. In Proceedings of the Thirteenth IEEE Symposium on High-Performance Computer Architecture, pages 97--108, February 2007.
• 6: Weihaw Chuang , Satish Narayanasamy , Ganesh Venkatesh , Jack Sampson , Michael Van Biesbrouck , Gilles Pokam , Brad Calder , Osvaldo Colavin, Unbounded page-based transactional memory, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 7: JaeWoong Chung , Chi Cao Minh , Austen McDonald , Travis Skare , Hassan Chafi , Brian D. Carlstrom , Christos Kozyrakis , Kunle Olukotun, Tradeoffs in transactional memory virtualization, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 8: P. J. Courtois , F. Heymans , D. L. Parnas, Concurrent control with “readers” and “writers”, Communications of the ACM, v.14 n.10, p.667-668, Oct. 1971 [doi>10.1145/362759.362813]
• 9: Peter Damron , Alexandra Fedorova , Yossi Lev , Victor Luchangco , Mark Moir , Daniel Nussbaum, Hybrid transactional memory, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 10: Lance Hammond , Vicky Wong , Mike Chen , Brian D. Carlstrom , John D. Davis , Ben Hertzberg , Manohar K. Prabhu , Honggo Wijaya , Christos Kozyrakis , Kunle Olukotun, Transactional Memory Coherence and Consistency, Proceedings of the 31st annual international symposium on Computer architecture, p.102, June 19-23, 2004, München, Germany
• 11: Tim Harris , Mark Plesko , Avraham Shinnar , David Tarditi, Optimizing memory transactions, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 12: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 13: Stefanos Kaxiras , James R. Goodman, Improving CC-NUMA Performance Using Instruction-Based Prediction, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.161, January 09-12, 1999
• 14: James R. Larus and Ravi Rajwar. Transactional Memory. Morgan & Claypool Publishers, 2006.
• 15: Peter S. Magnusson , Magnus Christensson , Jesper Eskilson , Daniel Forsgren , Gustav Hållberg , Johan Högberg , Fredrik Larsson , Andreas Moestedt , Bengt Werner, Simics: A Full System Simulation Platform, Computer, v.35 n.2, p.50-58, February 2002 [doi>10.1109/2.982916]
• 16: Milo M. K. Martin , Daniel J. Sorin , Bradford M. Beckmann , Michael R. Marty , Min Xu , Alaa R. Alameldeen , Kevin E. Moore , Mark D. Hill , David A. Wood, Multifacet's general execution-driven multiprocessor simulator (GEMS) toolset, ACM SIGARCH Computer Architecture News, v.33 n.4, November 2005 [doi>10.1145/1105734.1105747]
• 17: Austen McDonald , JaeWoong Chung , Brian D. Carlstrom , Chi Cao Minh , Hassan Chafi , Christos Kozyrakis , Kunle Olukotun, Architectural Semantics for Practical Transactional Memory, Proceedings of the 33rd annual international symposium on Computer Architecture, p.53-65, June 17-21, 2006
• 18: John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991 [doi>10.1145/103727.103729]
• 19: Kevin E. Moore, Jayaram Bobba, Michelle J. Moravan, Mark D. Hill, and David A. Wood. LogTM: Log-Based Transactional Memory. In Proceedings of the Twelfth IEEE Symposium on High-Performance Computer Architecture, pages 258--269, February 2006.
• 20: Michelle J. Moravan , Jayaram Bobba , Kevin E. Moore , Luke Yen , Mark D. Hill , Ben Liblit , Michael M. Swift , David A. Wood, Supporting nested transactional memory in logTM, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 21: Ravi Rajwar , James R. Goodman, Transactional lock-free execution of lock-based programs, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 22: Ravi Rajwar , Maurice Herlihy , Konrad Lai, Virtualizing Transactional Memory, Proceedings of the 32nd annual international symposium on Computer Architecture, p.494-505, June 04-08, 2005
• 23: Bratin Saha , Ali-Reza Adl-Tabatabai , Richard L. Hudson , Chi Cao Minh , Benjamin Hertzberg, McRT-STM: a high performance software transactional memory system for a multi-core runtime, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1123001]
• 24: William N. Scherer, III , Michael L. Scott, Advanced contention management for dynamic software transactional memory, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073861]
• 25: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy
• 26: Luke Yen, Jayaram Bobba, Michael R. Marty, Kevin E. Moore, Haris Volos, Mark D. Hill, Michael M. Swift, and David A. Wood. LogTM-SE: Decoupling Hardware Transactional Memory from Caches. In Proceedings of the Thirteenth IEEE Symposium on High-Performance Computer Architecture, pages 261--272, February 2007.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Design, Experimentation, Performance

Keywords:
contention management, hardware, pathology, performance, transactional memory