No Access

ON THE INPUT ACCEPTANCE OF TRANSACTIONAL MEMORY

Vincent Gramoli

EPFL LPD, Station 14, CH-1015 Lausanne, Switzerland

Université de Neuchâtel, rue Emile-Argand 11, CH-2007 Neuchâtel, Switzerland

Contact author. EPFL LPD, Station 14, CH-1015 Lausanne, Switzerland.

Search for more papers by this author

Derin Harmanci

Université de Neuchâtel, rue Emile-Argand 11, CH-2007 Neuchâtel, Switzerland

Search for more papers by this author

, and

Pascal Felber

Université de Neuchâtel, rue Emile-Argand 11, CH-2007 Neuchâtel, Switzerland

Search for more papers by this author

https://doi.org/10.1142/S0129626410000041Cited by:14 (Source: Crossref)

Abstract

We present the Input Acceptance of Transactional Memory (TM). Despite the large interest for performance of TMs, no existing research work has investigated the impact of solving a conflict that does not need to be solved. Traditional solutions for a TM to be correct is to delay or abort a transaction as soon as it presents a risk to violate consistency. Both alternatives are costly and should be avoided if consistency is actually preserved. To address this problem, we introduce the input acceptance of a TM as its ability to commit transactions, we upper-bound the input acceptance of existing TMs and propose a new TM with higher input acceptance.

Part of this work already appeared in the 12th International Conference On Principles Of DIstributed Systems [6]. This work is partially supported by the Velox Project ICT-216852 and the Swiss National Foundation Grant 200021-118043.

Keywords:

References

Utku Aydonat and Tarek S. Abdelrahman , Serializability of transactions in software transactional memory , TRANSACT '08: 3rd ACM SIGPLAN Workshop on Transactional Computing . Google Scholar
Philip A. Bernstein , Vassos Hadzilacos and Nathan Goodman , Concurrency Control and Recovery in Database Systems ( Addison-Wesley , 1987 ) . Google Scholar
Dave Dice, Ori Shalev, and Nir Shavit. Transactional locking II. In DISC '06: Proceedings of the 20th International Symposium on Distributed Computing, volume 4167 of LNCS, pages 194–208. Springer, 2006 . Google Scholar
Pascal Felber, Torvald Riegel and Christof Fetzer, Dynamic performance tuning of word-based software transactional memory, PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (ACM, 2008) pp. 237–246. Google Scholar
H. Garcia-Molina and K. Salem, IEEE Trans. on Knowl. and Data Eng. 4(6), 509 (1992), DOI: 10.1109/69.180602. Crossref, Web of Science, Google Scholar
Vincent Gramoli, Derin Harmanci, and Pascal Felber. Toward a theory of input acceptance for transactional memories. In OPODIS '08: Proceedings of the 12th International Conference on Principles of Distributed Systems, volume 5401 of LNCS, pages 527–533, 2008 . Google Scholar
Rachid Guerraoui, Thomas Henzinger, and Vasu Singh. Permissiveness in transactional memories. In DISC '08: Proceedings of the 22nd International Symposium on Distributed Computing, volume 5218 of LNCS, pages 305–319, 2008 . Google Scholar
Rachid Guerraoui, Maurice Herlihy, and Bastian Pochon. Polymorphic contention management. In DISC '05: Proceedings of the 19th International Symposium on Distributed Computing, volume 3724 of LNCS, pages 303–323. Springer, 2005 . Google Scholar
Rachid Guerraoui and Michał Kapałka, On the correctness of transactional memory, PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (ACM, 2008) pp. 175–184. Google Scholar
Tim Harris and Keir Fraser, SIGPLAN Not. 38(11), 388 (2003), DOI: 10.1145/949343.949340. Crossref, Web of Science, Google Scholar
Maurice Herlihyet al., Software transactional memory for dynamic-sized data structures, PODC '03: Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (2003) pp. 92–101. Google Scholar
Maurice Herlihy and Jeannette M. Wing, ACM Trans. Program. Lang. Syst. 12(3), 463 (1990), DOI: 10.1145/78969.78972. Crossref, Web of Science, Google Scholar
Jeff Napper and Lorenzo Alvisi. Lock-free serializable transactions. Technical Report TR-05-04, Department of Computer Sciences, University of Texas at Austin, 2005 . Google Scholar
Christos H. Papadimitriou, J. ACM 26(4), 631 (1979), DOI: 10.1145/322154.322158. Crossref, Web of Science, Google Scholar
Cristian Perfumo et al. , Dissecting transactional executions in haskell , TRANSACT '07: 2nd ACM SIGPLAN Workshop on Transactional Computing ( 2007 ) . Google Scholar
Torval Riegelet al., From causal to z-linearizable transactional memory, PODC '07: Proceedings of the 26th ACM Symposium on Principles of Distributed Computing (ACM, New York, NY, USA, 2007) pp. 340–341. Google Scholar
Mihalis Yannakakis, J. ACM 31(2), 227 (1984), DOI: 10.1145/62.322425. Crossref, Web of Science, Google Scholar