A comprehensive strategy for contention management in software transactional memory

ABSTRACT

In Software Transactional Memory (STM), contention management refers to the mechanisms used to ensure forward progress--to avoid livelock and starvation, and to promote throughput and fairness. Unfortunately, most past approaches to contention management were designed for obstruction-free STM frameworks, and impose significant constant-time overheads. Priority-based approaches in particular typically require that reads be visible to all transactions, an expensive property that is not easy to support in most STM systems.

In this paper we present a comprehensive strategy for contention management via fair resolution of conflicts in an STM with invisible reads. Our strategy depends on (1) lazy acquisition of ownership, (2) extendable timestamps, and (3) an efficient way to capture both priority and conflicts. We introduce two mechanisms--one using Bloom filters, the other using visible read bits--that implement point (3). These mechanisms unify the notions of conflict resolution, inevitability, and transaction retry. They are orthogonal to the rest of the contention management strategy, and could be used in a wide variety of hardware and software TM systems. Experimental evaluation demonstrates that the overhead of the mechanisms is low, particularly when conflicts are rare, and that our strategy as a whole provides good throughput and fairness, including livelock and starvation freedom, even for challenging workloads.

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: 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: 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
• 4: D. Dice, O. Shalev, and N. Shavit. Transactional Locking II. In Proc. of the 20th Intl. Symp. on Distributed Computing, Stockholm, Sweden, Sept. 2006.
• 5: A. Dragojević, R. Guerraoui, and M. Kapałka. Dividing Transactional Memories by Zero. In Proc. of the 3rd ACM SIGPLAN Workshop on Transactional Computing, Salt Lake City, UT, Feb. 2008.
• 6: 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]
• 7: J. Gottschlich and D. A. Connors. Extending Contention Managers for User-Defined Priority-Based Transactions. In Workshop on Exploiting Parallelism with Transactional Memoryand other Hardware Assisted Methods (EPHAM), Boston, MA, Apr. 2008. In conjunction with phCGO.
• 8: 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]
• 9: 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]
• 10: 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]
• 11: 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 Proc. of the 1st ACM SIGPLAN Workshop on Transactional Computing, Ottawa, ON, Canada, June 2006. Expanded version available as TR 893, Dept. of Computer Science, Univ. of Rochester, Mar. 2006.
• 12: Vijay Menon , Steven Balensiefer , Tatiana Shpeisman , Ali-Reza Adl-Tabatabai , Richard L. Hudson , Bratin Saha , Adam Welc, Practical weak-atomicity semantics for java stm, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378588]
• 13: Katherine F. Moore , Dan Grossman, High-level small-step operational semantics for transactions, Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 07-12, 2008, San Francisco, California, USA
• 14: 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]
• 15: 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]
• 16: 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]
• 17: Yannis Smaragdakis , Anthony Kay , Reimer Behrends , Michal Young, Transactions with isolation and cooperation, Proceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
• 18: M. F. Spear, V. J. Marathe, W. N. Scherer III, and M. L. Scott. Conflict Detection and Validation Strategies for Software Transactional Memory. In Proc. of the 20th Intl. Symp. on Distributed Computing, Stockholm, Sweden, Sept. 2006.
• 19: Michael F. Spear , Michael Silverman , Luke Dalessandro , Maged M. Michael , Michael L. Scott, Implementing and Exploiting Inevitability in Software Transactional Memory, Proceedings of the 2008 37th International Conference on Parallel Processing, p.59-66, September 09-11, 2008 [doi>10.1109/ICPP.2008.55]
• 20: M. F. Spear, M. M. Michael, and M. L. Scott. Inevitability Mechanisms for Software Transactional Memory. In Proc. of the 3rd ACM SIGPLAN Workshop on Transactional Computing, Salt Lake City, UT, Feb. 2008.
• 21: Michael F. Spear , Luke Dalessandro , Virendra J. Marathe , Michael L. Scott, Ordering-Based Semantics for Software Transactional Memory, Proceedings of the 12th International Conference on Principles of Distributed Systems, December 15-18, 2008, Luxor, Egypt [doi>10.1007/978-3-540-92221-6_19]
• 22: Michael F. Spear , Maged M. Michael , Christoph von Praun, RingSTM: scalable transactions with a single atomic instruction, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378583]
• 23: Michael F. Spear , Andrew Sveikauskas , Michael L. Scott, Transactional memory retry mechanisms, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400850]
• 24: Adam Welc , Bratin Saha , Ali-Reza Adl-Tabatabai, Irrevocable transactions and their applications, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378584]
• 25: 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:
condition synchronization, contention management, inevitability, priority, software transactional memory