On avoiding spare aborts in transactional memory

ABSTRACT

This paper takes a step toward developing a theory for understanding aborts in transactional memory systems (TMs). Existing TMs may abort many transactions that could, in fact, commit without violating correctness. We call such unnecessary aborts spare aborts. We classify what kinds of spare aborts can be eliminated, and which cannot. We further study what kinds of spare aborts can be avoided efficiently. Specifically, we show that some unnecessary aborts cannot be avoided, and that there is an inherent tradeoff between the overhead of a TM and the extent to which it reduces the number of spare aborts. We also present an efficient example TM algorithm that avoids certain kinds of spare aborts, and analyze its properties and performance.

REFERENCES

• 1: Hagit Attiya , Leah Epstein , Hadas Shachnai , Tami Tamir, Transactional contention management as a non-clairvoyant scheduling problem, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146428]
• 2: U. Aydonat and T. Abdelrahman. Serializability of transactions in software transactional memory. In Second ACM SIGPLAN Workshop on Transactional Computing, 2008.
• 3: D. Dice, O. Shalev, and N. Shavit. Transactional locking 2. In DISC, 2006.
• 4: R. Ennals. Cache sensitive software transactional memory. Technical report, Intel.
• 5: K. Fraser. Practical lock-freedom. Technical report, Cambridge, 2004.
• 6: Vincent Gramoli , Derin Harmanci , Pascal Felber, Toward a Theory of Input Acceptance for Transactional Memories, 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_33]
• 7: R. Guerraoui, T. A. Henzinger, and V. Singh. In DISC, 2008.
• 8: 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]
• 9: 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]
• 10: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, ACM SIGARCH Computer Architecture News, v.21 n.2, p.289-300, May 1993
• 11: I. Keidar and D. Perelman. On avoiding spare aborts in Transactional Memory. Technical Report CCIT Report #733, Technion, 2009.
• 12: J. E. B. Moss. Open nested transactions: Semantics and support. In Workshop on Memory Performance Issues (WMPI'06), 2006.
• 13: J. Napper and L. Alvisi. Lock-free serializable transactions. Technical report, The University of Texas at Austin, 2005.
• 14: 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]
• 15: T. Riegel, C. Fetzer, H. Sturzrehm, and P. Felber. From causal to z-linearizable transactional memory. Technical report, Université de Neuchâtel, 2007.
• 16: 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]
• 17: Gerhard Weikum , Gottfried Vossen, Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001

INDEX TERMS

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

General Terms:
Algorithms, Performance, Theory

Keywords:
transactional memory