RingSTM: scalable transactions with a single atomic instruction

ABSTRACT

Existing Software Transactional Memory (STM) designs attach metadata to ranges of shared memory; subsequent runtime instructions read and update this metadata in order to ensure that an in-flight transaction's reads and writes remain correct. The overhead of metadata manipulation and inspection is linear in the number of reads and writes performed by a transaction, and involves expensive read-modify-write instructions, resulting in substantial overheads.

We consider a novel approach to STM, in which transactions represent their read and write sets as Bloom filters, and transactions commit by enqueuing a Bloom filter onto a global list. Using this approach, our RingSTM system requires at most one read-modify-write operation for any transaction, and incurs validation overhead linear not in transaction size, but in the number of concurrent writers who commit. Furthermore, RingSTM is the first STM that is inherently livelock-free and privatization-safe while at the same time permitting parallel writeback by concurrent disjoint transactions.We evaluate three variants of the RingSTM algorithm, and find that it offers superior performance and/or stronger semantics than the state-of-the-art TL2 algorithm under a number of workloads.

REFERENCES

• 1: L. Baugh and C. Zilles. An Analysis of I/O and Syscalls in Critical Sections and Their Implications for Transactional Memory. In Proceedings of the 2nd ACM SIGPLAN Workshop on Transactional Computing, Portland, OR, Aug. 2007.
• 2: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 3: 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
• 4: Jayaram Bobba , Kevin E. Moore , Haris Volos , Luke Yen , Mark D. Hill , Michael M. Swift , David A. Wood, Performance pathologies in hardware transactional memory, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 5: 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
• 6: D. Dice, O. Shalev, and N. Shavit. Transactional Locking II. In Proceedings of the 20th International Symposium on Distributed Computing, Stockholm, Sweden, Sept. 2006.
• 7: R. Ennals. Software Transactional Memory Should Not Be Lock Free. Technical Report IRC-TR-06-052, Intel Research Cambridge, 2006.
• 8: K. Fraser. Practical Lock-Freedom. Technical Report UCAM-CL-TR-579, Cambridge University Computer Laboratory, Feb. 2004.
• 9: R. Guerraoui, M. Herlihy, and B. Pochon. Polymorphic Contention Management in SXM. In Proceedings of the 19th International Symposium on Distributed Computing, Cracow, Poland, Sept. 2005.
• 10: 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
• 11: 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]
• 12: O. S. Hofmann, D. E. Porter, C. J. Rossbach, H. E. Ramadan, and E. Witchel. Solving Difficult HTM Problems Without Difficult Hardware. In Proceedings of the 2nd ACM SIGPLAN Workshop on Transactional Computing, Portland, OR, Aug. 2007.
• 13: Richard L. Hudson , Bratin Saha , Ali-Reza Adl-Tabatabai , Benjamin C. Hertzberg, McRT-Malloc: a scalable transactional memory allocator, Proceedings of the 5th international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada [doi>10.1145/1133956.1133967]
• 14: Jim Larus , Ravi Rajwar, Transactional Memory (Synthesis Lectures on Computer Architecture), Morgan & Claypool Publishers, 2007
• 15: V. J. Marathe, W. N. Scherer III, and M. L. Scott. Adaptive Software Transactional Memory. In Proceedings of the 19th International Symposium on Distributed Computing, Cracow, Poland, Sept. 2005.
• 16: 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. In Proceedings of the 1st ACM Workshop on Languages, Compilers, and Hardware Support for Transactional Computing, June 2006.
• 17: 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
• 18: U. of Rochester. Rochester Software Transactional Memory. http://www.cs.rochester.edu/research/synchronization/rstm/.
• 19: 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]
• 20: 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
• 21: T. Riegel, P. Felber, and C. Fetzer. A Lazy Snapshot Algorithm with Eager Validation. In Proceedings of the 20th International Symposium on Distributed Computing, Stockholm, Sweden, Sept. 2006.
• 22: 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]
• 23: 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]
• 24: 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]
• 25: 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]
• 26: 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]
• 27: 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
• 28: M. F. Spear, V. J. Marathe, L. Dalessandro, and M. L. Scott. Privatization Techniques for Software Transactional Memory. Technical Report TR 915, Department of Computer Science, University of Rochester, Feb. 2007.
• 29: M. F. Spear, V. J. Marathe, W. N. Scherer III, and M. L. Scott. Conflict Detection and Validation Strategies for Software Transactional Memory. In Proceedings of the 20th International Symposium on Distributed Computing, Stockholm, Sweden, Sept. 2006.
• 30: M. F. Spear, M. M. Michael, and M. L. Scott. Inevitability Mechanisms for Software Transactional Memory. In Proceedings of the 3rd ACM SIGPLAN Workshop on Transactional Computing, Salt Lake City, UT, Feb. 2008.
• 31: 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]
• 32: Christoph von Praun , Luis Ceze , Calin Caşcaval, Implicit parallelism with ordered transactions, 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.1229443]
• 33: 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]
• 34: 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]
• 35: Craig Zilles , Ravi Rajwar, Transactional memory and the birthday paradox, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248428]

INDEX TERMS

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

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

General Terms:
Algorithms, Design, Performance

Keywords:
atomicity, software transactional memory, synchronization