Software Transactional Memory: Why Is It Only a Research Toy?

ABSTRACT

STM is sometimes touted as the way forward for developing concurrent software, but is it ready for use in real-world applications? The authors built an STM runtime system and compiler framework, the IBM STM, and compared its performance to other similar products by Intel and Sun. They conclude that from both performance and productivity standpoints, STM still has a long way to go before it can be viable in the real world.

REFERENCES

• 1: 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
• 2: Larus, J.R., Rajwar, R. 2006. Transactional Memory. Morgan Claypool.
• 3: Dice, D., Shalev, O., Shavit, N. 2006. Transactional Locking II. DISC (September): 194-208.
• 4: Tim Harris , Keir Fraser, Language support for lightweight transactions, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 5: 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]
• 6: Intel C++ STM compiler, prototype edition 2.0.; http://softwarecommunity.intel.com/articles/eng/1460.htm/ (2008).
• 7: Marathe, V.J., Spear, M.F., Heriot, C., Acharya, A., Eisenstat, D., Scherer III, W.N., Scott, M.L. 2006. Lowering the overhead of software transactional memory. Technical Report TR 893, Computer Science Department, University of Rochester (March). Condensed version submitted for publication.
• 8: 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]
• 9: Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224987]
• 10: Colin Blundell , Joe Devietti , E. Christopher Lewis , Milo M. K. Martin, Making the fast case common and the uncommon case simple in unbounded transactional memory, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 11: Jayaram Bobba , Neelam Goyal , Mark D. Hill , Michael M. Swift , David A. Wood, TokenTM: Efficient Execution of Large Transactions with Hardware Transactional Memory, Proceedings of the 35th International Symposium on Computer Architecture, p.127-138, June 21-25, 2008
• 12: 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
• 13: See reference 1.
• 14: Chi Cao Minh , Martin Trautmann , JaeWoong Chung , Austen McDonald , Nathan Bronson , Jared Casper , Christos Kozyrakis , Kunle Olukotun, An effective hybrid transactional memory system with strong isolation guarantees, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 15: Moore, K.E., Bobba, J., Moravan, M.J., Hill, M.D., Wood, D.A. 2006. LogTM: Log-based transactional memory. In Proceedings of the 12th Annual International Symposium on High Performance Computer Architecture (February).
• 16: Luke Yen , Jayaram Bobba , Michael R. Marty , Kevin E. Moore , Haris Volos , Mark D. Hill , Michael M. Swift , David A. Wood, LogTM-SE: Decoupling Hardware Transactional Memory from Caches, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.261-272, February 10-14, 2007 [doi>10.1109/HPCA.2007.346204]
• 17: 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
• 18: Tremblay, M. Chaudhry, S. 2008. A third-generation 65nm 16-core 32-thread plus 32-scout-thread CMT. In Proceedings of the IEEE International Solid-State Circuits Conference (February).
• 19: Lee Baugh , Naveen Neelakantam , Craig Zilles, Using Hardware Memory Protection to Build a High-Performance, Strongly-Atomic Hybrid Transactional Memory, Proceedings of the 35th International Symposium on Computer Architecture, p.115-126, June 21-25, 2008
• 20: 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
• 21: Bratin Saha , Ali-Reza Adl-Tabatabai , Quinn Jacobson, Architectural Support for Software Transactional Memory, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.185-196, December 09-13, 2006 [doi>10.1109/MICRO.2006.9]
• 22: Arrvindh Shriraman , Michael F. Spear , Hemayet Hossain , Virendra J. Marathe , Sandhya Dwarkadas , Michael L. Scott, An integrated hardware-software approach to flexible transactional memory, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 23: STAMP benchmark suite. 2007. http://stamp.stanford.edu/.
• 24: The Lonestar benchmark suite. 2008. http://iss.ices.utexas.edu/lonestar/.
• 25: (IBM) XL C/C++ for Transactional Memory for AIX. 2008. www.alphaworks.ibm.com/tech/xlcstm/.
• 26: See reference 6.
• 27: See reference 3.
• 28: Milo Martin , Colin Blundell , E. Lewis, Subtleties of Transactional Memory Atomicity Semantics, IEEE Computer Architecture Letters, v.5 n.2, p.17, July 2006 [doi>10.1109/L-CA.2006.18]
• 29: Milind Kulkarni , Keshav Pingali , Bruce Walter , Ganesh Ramanarayanan , Kavita Bala , L. Paul Chew, Optimistic parallelism requires abstractions, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 30: See reference 14.
• 31: See reference 23.
• 32: See reference 25.
• 33: Peng Wu , Maged M. Michael , Christoph von Praun , Takuya Nakaike , Rajesh Bordawekar , Harold W. Cain , Calin Cascaval , Siddhartha Chatterjee , Stefanie Chiras , Rui Hou , Mark Mergen , Xiaowei Shen , Michael F. Spear , Hua Yong Wang , Kun Wang, Compiler and runtime techniques for software transactional memory optimization, Concurrency and Computation: Practice & Experience, v.21 n.1, p.7-23, January 2009 [doi>10.1002/cpe.v21:1]
• 34: See reference 6.
• 35: See reference 3.
• 36: Richard M. Yoo , Yang Ni , Adam Welc , Bratin Saha , Ali-Reza Adl-Tabatabai , Hsien-Hsin S. Lee, Kicking the tires of software transactional memory: why the going gets tough, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378582]
• 37: See reference 36.
• 38: See reference 25.
• 39: 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
• 40: Harris, T., Plesko, M., Shinnar, A., Tarditi, D. 2003. Optimizing memory transactions. In Proceedings of the Programming Language Design and Implementation Conference: 388-402.
• 41: See reference 39.
• 42: See reference 40.
• 43: Rui Zhang , Zoran Budimlić , William N. Scherer, III, Commit phase in timestamp-based stm, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378589]
• 44: Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224987]
• 45: See reference 3.
• 46: See reference 5.
• 47: See reference 4.
• 48: See reference 7.
• 49: Torvald Riegel , Christof Fetzer , Pascal Felber, Time-based transactional memory with scalable time bases, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248415]
• 50: Marek Olszewski , Jeremy Cutler , J. Gregory Steffan, JudoSTM: A Dynamic Binary-Rewriting Approach to Software Transactional Memory, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.365-375, September 15-19, 2007 [doi>10.1109/PACT.2007.42]
• 51: Michael F. Spear , Maged M. Michael , Christoph von Praun, RingSTM: scalable transactions with a single atomic instruction, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378583]
• 52: Felber, P., Fetzer, C., Mueller, U., Riegel, T., Suesskraut, M., Sturzrehm, H. 2007. Transactifying applications using an open compiler framework. In Proceedings of the ACM SIGPLAN Workshop on Transactional Computing (August).
• 53: See reference 50.
• 54: 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]
• 55: See reference 36.
• 56: See reference 6.
• 57: See reference 8.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
      D.4.8 Performance
      D.4.m Miscellaneous

General Terms:
Algorithms, Design, Management, Performance, Theory