Feedback-directed barrier optimization in a strongly isolated STM

ABSTRACT

Speed improvements in today's processors have largely been delivered in the form of multiple cores, increasing the importance of abstractions that ease parallel programming. Software transactional memory (STM) addresses many of the complications of concurrency by providing a simple and composable model for safe access to shared data structures. Software transactions extend a language with an atomic primitive that declares that the effects of a block of code should not be interleaved with actions executing concurrently on other threads. Adding barriers to shared memory accesses provides atomicity, consistency and isolation.

Strongly isolated STMs preserve the safety properties of transactions for all memory operations in a program, not just those inside an atomic block. Isolation barriers are added to non-transactional loads and stores in such a system to prevent those accesses from observing or corrupting a partially completed transaction. Strong isolation is especially important when integrating transactions into an existing language and memory model. Isolation barriers have a prohibitive performance overhead, however, so most STM proposals have chosen not to provide strong isolation.

In this paper we reduce the costs of strong isolation by customizing isolation barriers for their observed usage. The customized barriers provide accelerated execution by blocking threads whose accesses do not follow the expected pattern. We use hot swap to tighten or loosen the hypothesized pattern, while preserving strong isolation. We introduce a family of optimization hypotheses that balance verification cost against generality.

We demonstrate the feasibility of dynamic barrier optimization by implementing it in a bytecode-rewriting Java STM. Feedback-directed customization reduces the overhead of strong isolation from 505% to 38% across 11 non-transactional benchmarks; persistent feedback data further reduces the overhead to 16%. Dynamic optimization accelerates a multi-threaded transactional benchmark by 31% for weakly-isolated execution and 34% for strongly-isolated execution.

REFERENCES

• 1: Intel C++ STM Compiler, Prototype Edition. http://software.intel.com.
• 2: Ali-Reza Adl-Tabatabai , Brian T. Lewis , Vijay Menon , Brian R. Murphy , Bratin Saha , Tatiana Shpeisman, Compiler and runtime support for efficient software transactional memory, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 3: Stephen M. Blackburn , Robin Garner , Chris Hoffmann , Asjad M. Khang , Kathryn S. McKinley , Rotem Bentzur , Amer Diwan , Daniel Feinberg , Daniel Frampton , Samuel Z. Guyer , Martin Hirzel , Antony Hosking , Maria Jump , Han Lee , J. Eliot B. Moss , B. Moss , Aashish Phansalkar , Darko Stefanović , Thomas VanDrunen , Daniel von Dincklage , Ben Wiedermann, The DaCapo benchmarks: java benchmarking development and analysis, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 4: E. Bruneton, R. Lenglet, and T. Coupaye. ASM: a code manipulation tool to implement adaptable systems. Adaptable and Extensible Component Systems, 2002.
• 5: J. Chung, H. Chafi, C. Cao Minh, A. McDonald, B. D. Carlstrom, C. Kozyrakis, and K. Olukotun. The Common Case Transactional Behavior of Multithreaded Programs. In Proceedings of the 12th International Conference on High-Performance Computer Architecture, February 2006.
• 6: D. Dice, O. Shalev, and N. Shavit. Transactional locking II. In DISC'06: Proceedings of the 20th International Symposium on Distributed Computing, March 2006.
• 7: Dan Grossman, The transactional memory / garbage collection analogy, ACM SIGPLAN Notices, v.42 n.10, October 2007
• 8: Dan Grossman , Jeremy Manson , William Pugh, What do high-level memory models mean for transactions?, Proceedings of the 2006 workshop on Memory system performance and correctness, October 22-22, 2006, San Jose, California [doi>10.1145/1178597.1178609]
• 9: 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
• 10: Maurice Herlihy , Victor Luchangco , Mark Moir , William N. Scherer, III, Software transactional memory for dynamic-sized data structures, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.92-101, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872048]
• 11: Benjamin Hindman , Dan Grossman, Atomicity via source-to-source translation, Proceedings of the 2006 workshop on Memory system performance and correctness, October 22-22, 2006, San Jose, California [doi>10.1145/1178597.1178611]
• 12: Specification Request (JSR) 133: Java Memory Model and Thread Specification, September 2004.
• 13: Victor Luchangco, Against lock-based semantics for transactional memory, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378549]
• 14: Vijay Menon , Steven Balensiefer , Tatiana Shpeisman , Ali-Reza Adl-Tabatabai , Richard L. Hudson , Bratin Saha , Adam Welc, Practical weak-atomicity semantics for java stm, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378588]
• 15: Michael Paleczny , Christopher Vick , Cliff Click, The java hotspot^TM server compiler, Proceedings of the 2001 Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.1-1, April 23-24, 2001, Monterey, California
• 16: Torvald Riegel , Christof Fetzer , Pascal Felber, Automatic data partitioning in software transactional memories, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378562]
• 17: Kenneth Russell , David Detlefs, Eliminating synchronization-related atomic operations with biased locking and bulk rebiasing, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 18: 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]
• 19: Florian T. Schneider , Vijay Menon , Tatiana Shpeisman , Ali-Reza Adl-Tabatabai, Dynamic optimization for efficient strong atomicity, Proceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications, October 19-23, 2008, Nashville, TN, USA
• 20: Michael L. Scott , Michael F. Spear , Luke Dalessandro , Virendra J. Marathe, Transactions and privatization in Delaunay triangulation, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281160]
• 21: Tatiana Shpeisman , Vijay Menon , Ali-Reza Adl-Tabatabai , Steven Balensiefer , Dan Grossman , Richard L. Hudson , Katherine F. Moore , Bratin Saha, Enforcing isolation and ordering in STM, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 22: Christopher Unkel , Monica S. Lam, Automatic inference of stationary fields: a generalization of java's final fields, Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 07-12, 2008, San Francisco, California, USA
• 23: Cheng Wang , Wei-Yu Chen , Youfeng Wu , Bratin Saha , Ali-Reza Adl-Tabatabai, Code Generation and Optimization for Transactional Memory Constructs in an Unmanaged Language, Proceedings of the International Symposium on Code Generation and Optimization, p.34-48, March 11-14, 2007 [doi>10.1109/CGO.2007.4]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures
      D.3.4 Processors
          Subjects: Run-time environments; Compilers; Optimization

General Terms:
Algorithms, Design, Experimentation, Languages, Measurement, Performance

Keywords:
bytecode rewriting, deoptimization, hot swap, strong isolation, transactional memory, weak isolation