McRT-STM: a high performance software transactional memory system for a multi-core runtime

ABSTRACT

Applications need to become more concurrent to take advantage of the increased computational power provided by chip level multiprocessing. Programmers have traditionally managed this concurrency using locks (mutex based synchronization). Unfortunately, lock based synchronization often leads to deadlocks, makes fine-grained synchronization difficult, hinders composition of atomic primitives, and provides no support for error recovery. Transactions avoid many of these problems, and therefore, promise to ease concurrent programming.We describe a software transactional memory (STM) system that is part of McRT, an experimental Multi-Core RunTime. The McRT-STM implementation uses a number of novel algorithms, and supports advanced features such as nested transactions with partial aborts, conditional signaling within a transaction, and object based conflict detection for C/C++ applications. The McRT-STM exports interfaces that can be used from C/C++ programs directly or as a target for compilers translating higher level linguistic constructs.We present a detailed performance analysis of various STM design tradeoffs such as pessimistic versus optimistic concurrency, undo logging versus write buffering, and cache line based versus object based conflict detection. We also show a MCAS implementation that works on arbitrary values, coexists with the STM, and can be used as a more efficient form of transactional memory. To provide a baseline we compare the performance of the STM with that of fine-grained and coarse-grained locking using a number of concurrent data structures on a 16-processor SMP system. We also show our STM performance on a non-synthetic workload -- the Linux sendmail application.

REFERENCES

• 1: Adl-Tabatabai, A., Lewis, B.T., Menon, V.S., Murphy, B.R., Saha, B., and Shpeisman, T. Compiler and runtime optimizations for efficient software transactional memory. To appear PLDI 2006.
• 2: Allan, E., Chase, D., Luchango, V., Maessen, J., Ryu, S., Steele Jr., G., and Tobin-Hochstadt, S. The Fortress language specification, version 0.618. Sun Microsystems Technical Report, April 2005.
• 3: A. W. Appel, Simple generational garbage collection and fast allocation, Software—Practice & Experience, v.19 n.2, p.171-183, February 1989 [doi>10.1002/spe.4380190206]
• 4: Philippe Charles , Christian Grothoff , Vijay Saraswat , Christopher Donawa , Allan Kielstra , Kemal Ebcioglu , Christoph von Praun , Vivek Sarkar, X10: an object-oriented approach to non-uniform cluster computing, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 5: Michal Cierniak , Marsha Eng , Neal Glew , Brian Lewis , James Stichnoth, The Open Runtime Platform: a flexible high-performance managed runtime environment: Research Articles, Concurrency and Computation: Practice & Experience, v.17 n.5-6, p.617-637, April 2005 [doi>10.1002/cpe.v17:5/6]
• 6: Cray Inc. The Chapel language specification, version 0.4. Technical Report, Cray Inc. Feb 2005.
• 7: Ennals, R. Cache sensitive software transactional memory. Technical Report.
• 8: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 9: Lance Hammond , Brian D. Carlstrom , Vicky Wong , Ben Hertzberg , Mike Chen , Christos Kozyrakis , Kunle Olukotun, Programming with transactional coherence and consistency (TCC), Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 10: Harris, T.L. Design choices for language based transactions. University of Cambridge Computer Laboratory, Tech Report, Aug 2003.
• 11: 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
• 12: Tim Harris , Keir Fraser, Revocable locks for non-blocking programming, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065954]
• 13: Timothy L. Harris , Keir Fraser , Ian A. Pratt, A Practical Multi-word Compare-and-Swap Operation, Proceedings of the 16th International Conference on Distributed Computing, p.265-279, October 28-30, 2002
• 14: Tim Harris , Simon Marlow , Simon Peyton-Jones , Maurice Herlihy, Composable memory transactions, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065952]
• 15: 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]
• 16: 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
• 17: Hosking, A, and Moss, J.E.B. Nested transactional memory: Model and preliminary Sketches, SCOOL 2005.
• 18: Antony L. Hosking , J. Eliot B. Moss , Darko Stefanovic, A comparative performance evaluation of write barrier implementation, conference proceedings on Object-oriented programming systems, languages, and applications, p.92-109, October 18-22, 1992, Vancouver, British Columbia, Canada
• 19: 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
• 20: Justin Rattner, Multi-Core to the Masses, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques (PACT'05), p.3, September 17-21, 2005 [doi>10.1109/PACT.2005.31]
• 21: Virendra J. Marathe , William N. Scherer , Michael L. Scott, Design tradeoffs in modern software transactional memory systems, Proceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems, p.1-7, October 22-23, 2004, Houston, Texas [doi>10.1145/1066650.1066660]
• 22: Maged M. Michael, Safe memory reclamation for dynamic lock-free objects using atomic reads and writes, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571829]
• 23: Scherer III, W. N. and Scott, M. Contention management in dynamic software transactional memory. PODC Workshop on Concurrency and Synchronization in Java programs, 2004.
• 24: 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]
• 25: Janice M. Stone , Harold S. Stone , Philip Heidelberger , John Turek, Multiple Reservations and the Oklahoma Update, IEEE Parallel & Distributed Technology: Systems & Technology, v.1 n.4, p.58-71, November 1993 [doi>10.1109/88.260295]
• 26: Welc, A, Jagannathan, S and Hosking, A Transactional Monitors for Concurrent Objects, ECOOP, 2004.
• 27: Emery D. Berger , Kathryn S. McKinley , Robert D. Blumofe , Paul R. Wilson, Hoard: a scalable memory allocator for multithreaded applications, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.117-128, November 2000, Cambridge, Massachusetts, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Frameworks

General Terms:
Algorithms, Languages, Performance

Keywords:
atomic constructs, runtime environment, software transactional memory, two-phase locking and read-versioning