Split hardware transactions: true nesting of transactions using best-effort hardware transactional memory

ABSTRACT

Transactional Memory (TM) is on its way to becoming the programming API of choice for writing correct, concurrent, and scalable programs. Hardware TM (HTM) implementations are expected to be significantly faster than pure software TM (STM); however, full hardware support for true closed and open nested transactions is unlikely to be practical.

This paper presents a novel mechanism, the split hardware transaction (SpHT), that uses minimal software support to combine multiple segments of an atomic block, each executed using a separate hardware transaction, into one atomic operation. The idea of segmenting transactions can be used for many purposes, including nesting, local retry, orElse, and user-level thread scheduling; in this paper we focus on how it allows linear closed and open nesting of transactions. SpHT overcomes the limited expressive power of best-effort HTM while imposing overheads dramatically lower than STM and preserving useful guarantees such as strong atomicity provided by the underlying HTM.

REFERENCES

• 1: Eric Allen, David Chase, Joe Hallett, Victor Luchangco, Jan-Willem Maessen, Sukyoung Ryu, and Sam Tobin-Hochstadt. The fortress language specification, version 1.0ß. Available from http://research.sun.com/projects/plrg/Publications/, March 2007.
• 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: C. Scott Ananian and Martin Rinard. Efficient object-based software transactions. In Workshop on Synchronization and Concurrency in Object-Oriented Languages (SCOOL), October 2005.
• 4: Brian D. Carlstrom , Austen McDonald , Hassan Chafi , JaeWoong Chung , Chi Cao Minh , Christos Kozyrakis , Kunle Olukotun, The Atomos transactional programming language, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 5: JaeWoong Chung, Hassan Chafi, Chi Cao Minh, Austen McDonald, Brian D. Carlstrom, Christos Kozyrakis, and Kunle Olukotun. The common case transactional behavior of multithreaded programs. In 12th International Symposium on High Performance Computer Architecture (HPCA). Feb 2006.
• 6: 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
• 7: D. Dice, O. Shalev, and N. Shavit. Transactional locking II. In Proc. International Symposium on Distributed Computing, 2006.
• 8: Robert Ennals. Software transactional memory should not be obstruction-free, 2005. http://www.cambridge.intel-research.net/~rennals/notlockfree.pdf.
• 9: Keir Fraser. Practical lock freedom. PhD thesis, Cambridge University Computer Laboratory, 2003. Also available as Technical Report UCAM-CL-TR-579.
• 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 , 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]
• 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: 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]
• 14: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 15: Sanjeev Kumar , Michael Chu , Christopher J. Hughes , Partha Kundu , Anthony Nguyen, Hybrid transactional memory, 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.1123003]
• 16: Yossi Lev and Mark Moir. Debugging with transactional memory. Transact 2006 workshop, June 2006. http://research.sun.com/scalable/pubs/Lev-Moir-Debugging-2006.pdf.
• 17: Yossi Lev, Mark Moir, and Dan Nussbaum. Phtm: Phased transactional memory. Transact 2007 workshop, August 2007. http://www.cs.rochester.edu/meetings/TRANSACT07/papers/lev.pdf.
• 18: Peter S. Magnusson , Fredrik Dahlgren , Håkan Grahn , Magnus Karlsson , Fredrik Larsson , Fredrik Lundholm , Andreas Moestedt , Jim Nilsson , Per Stenström , Bengt Werner, SimICS/sun4m: a virtual workstation, Proceedings of the annual conference on USENIX Annual Technical Conference, p.10-10, June 15-19, 1998, New Orleans, Louisiana
• 19: Virendra J. Marathe, William N. Scherer III, and Michael L. Scott. Adaptive software transactional memory. Technical report, Cracow, Poland, Sep 2005. Earlier but expanded version available as TR-868, University of Rochester Computer Science Dept., May 2005.
• 20: 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]
• 21: Mark Moir. Hybrid transactional memory, Jul 2005. http://www.cs.wisc.edu/trans-memory/misc-papers/moir:hybrid-tm:tr:2005.pdf.
• 22: Kevin E. Moore, Jayaram Bobba, Michelle J. Moravan, Mark D. Hill, and David A. Wood. Log?: Log-based transactional memory. In Proc. 12th Annual International Symposium on High Performance Computer Architecture, 2006.
• 23: 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
• 24: J. Eliot B. Moss , Antony L. Hosking, Nested transactional memory: model and architecture sketches, Science of Computer Programming, v.63 n.2, p.186-201, 1 December 2006 [doi>10.1016/j.scico.2006.05.010]
• 25: Manohar K. Prabhu , Kunle Olukotun, Using thread-level speculation to simplify manual parallelization, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 26: 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
• 27: 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]
• 28: N. Shavit and D. Touitou. Software transactional memory. Distributed Computing, 10(2):99--116, February 1997.

INDEX TERMS

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

General Terms:
Algorithms, Languages, Performance

Keywords:
atomicity, nesting, transactional memory