Stretching transactional memory

ABSTRACT

Transactional memory (TM) is an appealing abstraction for programming multi-core systems. Potential target applications for TM, such as business software and video games, are likely to involve complex data structures and large transactions, requiring specific software solutions (STM). So far, however, STMs have been mainly evaluated and optimized for smaller scale benchmarks.

We revisit the main STM design choices from the perspective of complex workloads and propose a new STM, which we call SwissTM. In short, SwissTM is lock- and word-based and uses (1) optimistic (commit-time) conflict detection for read/write conflicts and pessimistic (encounter-time) conflict detection for write/write conflicts, as well as (2) a new two-phase contention manager that ensures the progress of long transactions while inducing no overhead on short ones. SwissTM outperforms state-of-the-art STM implementations, namely RSTM, TL2, and TinySTM, in our experiments on STMBench7, STAMP, Lee-TM and red-black tree benchmarks.

Beyond SwissTM, we present the most complete evaluation to date of the individual impact of various STM design choices on the ability to support the mixed workloads of large applications.

REFERENCES

• 1: Martín Abadi , Andrew Birrell , Tim Harris , Michael Isard, Semantics of transactional memory and automatic mutual exclusion, Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 07-12, 2008, San Francisco, California, USA
• 2: Ali-Reza Adl-Tabatabai , Brian T. Lewis , Vijay Menon , Brian R. Murphy , Bratin Saha , Tatiana Shpeisman, Compiler and runtime support for efficient software transactional memory, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 3: 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]
• 4: Mohammad Ansari , Christos Kotselidis , Ian Watson , Chris Kirkham , Mikel Luján , Kim Jarvis, Lee-TM: A Non-trivial Benchmark Suite for Transactional Memory, Proceedings of the 8th international conference on Algorithms and Architectures for Parallel Processing, p.196-207, June 09-11, 2008, Agia Napa, Cyprus [doi>10.1007/978-3-540-69501-1_21]
• 5: The atomic ops project. http://www.hpl.hp.com/research/linux/atomic_ops.
• 6: 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]
• 7: João Cachopo , António Rito-Silva, Versioned boxes as the basis for memory transactions, Science of Computer Programming, v.63 n.2, p.172-185, 1 December 2006 [doi>10.1016/j.scico.2006.05.009]
• 8: C. Cao Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford transactional applications for multi-processing. In IISWC, 2008.
• 9: D. Dice, M. Herlihy, D. Lea, Y. Lev, V. Luchangco, W. Mesard, M. Moir, K. Moore, and D. Nussbaum. Applications of the adaptive transactional memory test platform. In TRANSACT, 2008.
• 10: D. Dice, O. Shalev, and N. Shavit. Transactional locking II. In DISC, 2006.
• 11: A. Dragojevi , R. Guerraoui, and M. Kapalka. Dividing transactional memories by zero. In TRANSACT, 2008.
• 12: R. Ennals. Efficient software transactional memory. Technical report, Intel Research Cambridge, Jan 2005.
• 13: K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
• 14: P. Felber, C. Fetzer, U. Müller, T. Riegel, M. Susskraut, and H. Sturzrehm. Transactifying applications using an open compiler framework. In TRANSACT, 2007.
• 15: R. Guerraoui, M. Herlihy, and B. Pochon. Polymorphic Contention Management. In DISC, 2005.
• 16: Rachid Guerraoui , Maurice Herlihy , Bastian Pochon, Toward a theory of transactional contention managers, 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.1073863]
• 17: Rachid Guerraoui , Michal Kapalka, On the correctness of transactional memory, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345233]
• 18: Rachid Guerraoui , Michal Kapalka , Jan Vitek, STMBench7: a benchmark for software transactional memory, Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, March 21-23, 2007, Lisbon, Portugal
• 19: 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]
• 20: 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]
• 21: V. J. Marathe, M. F. Spear, C. Heriot, A. Acharya, D. Eisenstat, W. N. Scherer III, and M. L. Scott. Lowering the overhead of software transactional memory. In TRANSACT, 2006.
• 22: Virendra J. Marathe , Michael F. Spear , Michael L. Scott, Scalable Techniques for Transparent Privatization in Software Transactional Memory, Proceedings of the 2008 37th International Conference on Parallel Processing, p.67-74, September 09-11, 2008 [doi>10.1109/ICPP.2008.69]
• 23: Yang Ni , Adam Welc , Ali-Reza Adl-Tabatabai , Moshe Bach , Sion Berkowits , James Cownie , Robert Geva , Sergey Kozhukow , Ravi Narayanaswamy , Jeffrey Olivier , Serguei Preis , Bratin Saha , Ady Tal , Xinmin Tian, Design and implementation of transactional constructs for C/C++, Proceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications, October 19-23, 2008, Nashville, TN, USA
• 24: Christos H. Papadimitriou, The serializability of concurrent database updates, Journal of the ACM (JACM), v.26 n.4, p.631-653, Oct. 1979 [doi>10.1145/322154.322158]
• 25: Pascal Felber , Christof Fetzer , Torvald Riegel, Dynamic performance tuning of word-based software transactional memory, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345241]
• 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: T. Riegel, P. Felber, and C. Fetzer. A lazy snapshot algorithm with eager validation. In DISC, 2006. RSTM home page. http://www.cs.rochester.edu/research/synchronization/rstm.
• 28: 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]
• 29: 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]
• 30: 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]
• 31: Michael F. Spear , Virendra J. Marathe , Luke Dalessandro , Michael L. Scott, Privatization techniques for software transactional memory, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281161]
• 32: M. F. Spear, V. J. Marathe, W. N. Scherer III, and M. L. Scott. Conflict detection and validation strategies for software transactional memory. In DISC, 2006.
• 33: Tim Sweeney, The next mainstream programming language: a game developer's perspective, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.269-269, January 11-13, 2006, Charleston, South Carolina, USA
• 34: 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]
• 35: 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]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures

General Terms:
Experimentation, Measurement, Performance

Keywords:
benchmarks, software transactional memories