NZTM: nonblocking zero-indirection transactional memory

ABSTRACT

This paper introduces NZTM, a nonblocking, zero-indirection, object-based, hybrid transactional memory system. NZTM comprises a nonblocking software transactional memory (STM) system that can exploit best-effort hardware transactional memory (HTM) if available to improve performance.

Most previous nonblocking software transactional memory implementations pay a significant performance cost in the common case, as compared to simpler, blocking ones. However, blocking is problematic in some cases and unacceptable in others. NZTM is nonblocking, but shares the advantages of recent blocking STM proposals in the common case: it stores object data "in place", avoiding the costly levels of indirection of previous nonblocking STMs, and improves cache performance by collocating object metadata with the data it controls.

We also explain how our nonblocking NZSTM algorithm can be substantially simplified using very simple hardware transactions, and evaluate its performance on Sun's forthcoming Rock processor. Our results show that nonblocking support introduces little overhead when compared with blocking STMs, and that NZTM is competitive with LogTM-SE, an unbounded HTM.

REFERENCES

• 1: 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]
• 2: C. S. Ananian and M. Rinard. Efficient object-based software transactions. Synchronization and Concurrency in Object-Oriented Languages, 2005.
• 3: 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
• 4: Calin Cascaval , Colin Blundell , Maged Michael , Harold W. Cain , Peng Wu , Stefanie Chiras , Siddhartha Chatterjee, Software Transactional Memory: Why Is It Only a Research Toy?, Queue, v.6 n.5, September 2008 [doi>10.1145/1454456.1454466]
• 5: Shailender Chaudhry , Robert Cypher , Magnus Ekman , Martin Karlsson , Anders Landin , Sherman Yip , Håkan Zeffer , Marc Tremblay, Rock: A High-Performance Sparc CMT Processor, IEEE Micro, v.29 n.2, p.6-16, March 2009 [doi>10.1109/MM.2009.34]
• 6: L. Dalessandro, V. Marathe, M. Spear, and M. L. Scott. Capabilities and limitations of library-based software transactional memory in C++. TRANSACT, 2007.
• 7: 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
• 8: Dave Dice , Yossi Lev , Mark Moir , Daniel Nussbaum, Early experience with a commercial hardware transactional memory implementation, Proceeding of the 14th international conference on Architectural support for programming languages and operating systems, March 07-11, 2009, Washington, DC, USA
• 9: D. Dice, Y. Lev, M. Moir, and D. Nussbaum. Early experience with a commercial hardware transactional memory implementation. Technical Report TR-2009-180, Sun Microsystems Laboratories, 2009.
• 10: D. Dice, O. Shalev, and N. Shavit. Transactional locking II. In Proc. 20th Intl. Symp. on Distributed Computing, September 2006.
• 11: R. Ennals. Software transactional memory should not be obstruction-free, 2005. http://berkeley.intel-research.net/rennals/pubs/052RobEnnals.pdf.
• 12: K. Fraser. Practical Lock-Freedom. PhD thesis, Cambridge University Technical Report UCAM-CL-TR-579, Cambridge, England, Feb. 2004.
• 13: David Geer, Industry Trends: Chip Makers Turn to Multicore Processors, Computer, v.38 n.5, p.11-13, May 2005 [doi>10.1109/MC.2005.160]
• 14: A. Ghuloum. Unwelcome advice, 2008. http://blogs.intel.com/research/2008/06/unwelcome_advice.php.
• 15: 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
• 16: John L. Hennessy , David A. Patterson, Computer Architecture, Fourth Edition: A Quantitative Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2006
• 17: Maurice Herlihy , Victor Luchangco , Mark Moir, Obstruction-Free Synchronization: Double-Ended Queues as an Example, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.522, May 19-22, 2003
• 18: Maurice Herlihy , Victor Luchangco , Mark Moir, A flexible framework for implementing software transactional memory, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 19: 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]
• 20: 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
• 21: G. J. Holzmann. The SPIN Model Checker. Addison-Wesley Professional, 2003.
• 22: G. Koch. Discovering multi-core: Extending the benefits of Moore's law. Technology, 2005.
• 23: Jim Larus , Ravi Rajwar, Transactional Memory (Synthesis Lectures on Computer Architecture), Morgan & Claypool Publishers, 2007
• 24: Y. Lev and M. Moir. Fast read sharing mechanism for software transactional memory, 2004. http://research.sun.com/scalable/pubs/PODC04-Poster.pdf.
• 25: 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]
• 26: Virendra J. Marathe , Mark Moir, Efficient nonblocking software transactional memory, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA [doi>10.1145/1229428.1229454]
• 27: V. Marathe, W. N. Scherer III, and M. L. Scott. Adaptive software transactional memory. In Proc. 19th Intl. Symp. on Distributed Computing, September 2005.
• 28: V. J. Marathe, M. F. Spear, C. Heriot, A. Acharya, D. Eisenstat, W. N. Scherer III, and M. L. Scott. Lowering the overhead of nonblocking software transactional memory. 2006.
• 29: 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]
• 30: C. C. Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford transactional applications for multi-processing. IEEE International Symposium on Workload Characterization, 2008. IISWC 2008., pages 35--46, 2008.
• 31: 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
• 32: M. Moir. Hybrid transactional memory, July 2005. http://research.sun.com/scalable/pubs/Moir-Hybrid-2005.pdf.
• 33: M. Moir, K. E. Moore, and D. Nussbaum. The adaptive transactional memory test platform: A tool for experimenting with transactional code for Rock. The third annual SIGPLAN Workshop on Transactional Memory, 2008.
• 34: K. E. Moore, J. Bobba, M. J. Moravan, M. D. Hill, and D. A. Wood. LogTM: Log-based transactional memory. In Proc. 12th Annual International Symposium on High Performance Computer Architecture, 2006.
• 35: 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
• 36: Hany E. Ramadan , Christopher J. Rossbach , Donald E. Porter , Owen S. Hofmann , Aditya Bhandari , Emmett Witchel, MetaTM/TxLinux: transactional memory for an operating system, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 37: 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]
• 38: 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]
• 39: N. Shavit and D. Touitou. Software transactional memory. Distributed Computing, Special Issue(10):99--116, 1997.
• 40: Michael F. Spear , Arrvindh Shriraman , Luke Dalessandro , Sandhya Dwarkadas , Michael L. Scott, Nonblocking transactions without indirection using alert-on-update, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248414]
• 41: H. Sutter. The free lunch is over: A fundamental turn toward concurrency in software. Dr. Dobb's Journal, 2005.
• 42: F. Tabba, M. Moir, J. R. Goodman, A. W. Hay, and C. Wang. Appendix to NZTM. http://www.cs.auckland.ac.nz/∼fuad/nztm-appendix.pdf.
• 43: F. Tabba, C. Wang, J. R. Goodman, and M. Moir. NZTM: Nonblocking zero-indirection transactional memory. TRANSACT, 2007.
• 44: 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]

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
hardware support, nonblocking synchronization, transactional memory