Checkpoints and continuations instead of nested transactions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Checkpoints and continuations instead of nested transactions

Full text

Pdf (413 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures table of contents

Munich, Germany

SESSION: Special track -- transactional memory table of contents

Pages 160-168

Year of Publication: 2008

ISBN:978-1-59593-973-9

Authors

Eric Koskinen	Brown University, Providence, RI, USA
Maurice Herlihy	Brown University, Providence, RI, USA

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 94, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1378533.1378563 What is a DOI?

ABSTRACT

We present a mechanism for partially aborting transactions through the use of data structure checkpoints and control-flow continuations. In particular, we show that boosted transactions [9] already have built-in restoration points and afford a simple, efficient implementation. Our mechanism is far simpler than previous work, which relied on complex nesting schemes to establish checkpoints. We demonstrate syntactic advantages and we quantify the overhead of checkpoints and explore several examples, illustrating the utility of partially aborting transactions.

We additionally present a novel queue-based spin lock which allows threads to timeout and differ in priority. Unlike the known lock due to Craig [5], our lock is more efficient for priority schemes of few levels.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Andrew W. Appel, Modern Compiler Implementation in ML, Cambridge University Press, New York, NY, 2004
	2	Chi Cao Minh , Martin Trautmann , JaeWoong Chung , Austen McDonald , Nathan Bronson , Jared Casper , Christos Kozyrakis , Kunle Olukotun, An effective hybrid transactional memory system with strong isolation guarantees, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
	3	Brian D. Carlstrom , Austen McDonald , Michael Carbin , Christos Kozyrakis , Kunle Olukotun, Transactional collection classes, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA [doi>10.1145/1229428.1229441]
	4	Craig, T. Building fifo and priority-queueing spin locks from atomic swap. Technical Report 93--02--02, Department of Computer Science & Engineering, University of Washington, 1993.
	5	Craig, T. Queuing spin lock algorithms to support timing predictability. Proceedings of the Real-Time Systems Symposium (1993), 148--157.
	6	Dice, D., Shalev, O., and Shavit, N. Transactional locking II. In Proceedings of the 20th International Symposium on Distributed Computing (DISC'06)(September 2006).
	7	Harris, T., and Stipić, S. Abstract nested transactions. In Proceedings of the 2nd ACM SIGPLAN Workshop on Languages, compilers, and hardware support for transactional computing (TRANSACT'07)(2007).
	8	Herlihy, M., and Koskinen, E. Transactional boosting: A methodology for highly concurrent transactional objects. Technical Report CS--07--08, Department of Computer Science, Brown University, 2007.
	9	Maurice Herlihy , Eric Koskinen, Transactional boosting: a methodology for highly-concurrent transactional objects, 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.1345237]
	10	Yossi Lev , Jan-Willem Maessen, Split hardware transactions: true nesting of transactions using best-effort hardware 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.1345236]
	11	Peter S. Magnusson , Anders Landin , Erik Hagersten, Queue Locks on Cache Coherent Multiprocessors, Proceedings of the 8th International Symposium on Parallel Processing, p.165-171, April 01, 1994
	12	Michelle J. Moravan , Jayaram Bobba , Kevin E. Moore , Luke Yen , Mark D. Hill , Ben Liblit , Michael M. Swift , David A. Wood, Supporting nested transactional memory in logTM, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
	13	Yang Ni , Vijay S. Menon , Ali-Reza Adl-Tabatabai , Antony L. Hosking , Richard L. Hudson , J. Eliot B. Moss , Bratin Saha , Tatiana Shpeisman, Open nesting in software transactional memory, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA [doi>10.1145/1229428.1229442]
	14	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]
	15	Christopher Strachey , Christopher P. Wadsworth, Continuations: A Mathematical Semantics for Handling FullJumps, Higher-Order and Symbolic Computation, v.13 n.1-2, p.135-152, April 2000 [doi>10.1023/A:1010026413531]