The week's pick
Reseach Article
Clustered Checkpointing and Partial Rollbacks for Reducing Conflict Costs in STMs
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 1 - Number 22 |
| Year of Publication: 2010 |
| Authors: Monika Gupta, Rudrapatna K Shyamasundar, Shivali Agarwal |
10.5120/438-668
|
Monika Gupta, Rudrapatna K Shyamasundar, Shivali Agarwal . Clustered Checkpointing and Partial Rollbacks for Reducing Conflict Costs in STMs. International Journal of Computer Applications. 1, 22 ( February 2010), 80-85. DOI=10.5120/438-668
Abstract
A Software Transactional Memory is a concurrency control mechanism that executes multiple concurrent, optimistic, lock-free, atomic transactions, thus alleviating many problems associated with conventional mutual exclusion primitives such as monitors and locks. With the advent of massive multi-cores, more transactions can be initiated concurrently, however resulting in an increase in the percentage of conflicting transactions. Each time a transaction conflicts, it imposes a significant cost on the system, originating from the need to abort and redo all the operations, including the costly shared memory read operations, thus making the overall system significantly heavy and impractical. We present an algorithm, Clustered Checkpointing and Partial Rollback (CCPR), for reducing the conflict costs of transactions in the face of increasing conflicts. The algorithm is based on intelligent checkpointing of transactions as they proceed, and, in case of conflict, rolling them back to a safe, consistent, intermediate checkpoint, thus reducing conflict costs.
References
- Nir Shavit and Dan Touitou. 1995. Software transactional memory. In PODC'95
- Larus, J.R. and Rajwar, R. 2006. Transactional Memory. Morgan and Claypool.
- Calin Cascaval, Colin Blundell, Maged Michael, Harold W. Cain, Peng Wu, Stefanie Chiras, Siddhartha Chatterjee. 2008. Software Transactional Memory: why is it only a research toy? DOI=http://www.cse.ust.hk/~charlesz/comp610/paper/p46-cascaval.pdf
- Dave Dice, Ori Shalev, and Nir Shavit. Transactional locking II. DISC, 06.
- Eric Koskinen and Maurice Herlihy. Checkpoints and continuations instead of nested transactions. In SPAA, 08
- Maurice Herlihy and Eric Koskinen. Transactional boosting: a methodology for highly-concurrent transactional objects. In PPoPP, 08
- M. M. Waliullah and P. Stenstrom. Intermediate checkpointing with conflicting access prediction in transactional memory systems. In IPDPS 08.
- Michelle J. Moravan, Jayaram Bobba, Kevin E. Moore, Luke Yen, Mark D. Hill, Ben Liblit, Michael M. Swift, and David A. Wood. Supporting nested transactional memory in logTM. SIGPLAN Not., 06.
- Yang Ni, Vijay S. Menon, Ali-Reza Adl-Tabatabai, Antony L. Hosking, Richard L. Hudson, J. Eliot B. Moss, Bratin Saha, and Tatiana Shpeisman. Open nesting in software transactional memory. In PPoPP, 07.
- Tim Harris and Srdan Stipic. Abstract nested transactions. In TRANSACT, 07
- Tabba, Fuad and Moir, Mark and Goodman, James R. and Hay, Andrew W. and Wang, Cong. NZTM: nonblocking zero-indirection transactional memory. In SPAA' 09
- Sonmez, Nehir and Harris, Tim and Cristal, Adrian and Unsal, Osman S. and Valero, Mateo. Taking the heat off transactions: Dynamic selection of pessimistic concurrency control. In IPDPS '09
- Michael L. Scott. Sequential Specification of Transactional Memory Semantics. In TRANSACT, 06.
- Ariel Cohen, JohnW. O'Leary, Amir Pnueli, Mark R. Tuttle, and Lenore D. Zuck. Verifying Correctness of Transactional Memories. In FMCAD, 09
- Keidar, Idit and Perelman, Dmitri. On avoiding spare aborts in transactional memory. In SPAA 09
- Attiya, Hagit and Hillel, Eshcar and Milani, Alessia. Inherent limitations on disjoint-access parallel implementations of transactional memory. In SPAA 09.
Index Terms
Keywords