Transactional boosting

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Transactional boosting: a methodology for highly-concurrent transactional objects

Full text

Pdf (240 KB)

Source

Principles and Practice of Parallel Programming archive
Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming table of contents

Salt Lake City, UT, USA

SESSION: Transactional memory I table of contents

Pages 207-216

Year of Publication: 2008

ISBN:978-1-59593-795-7

Authors

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

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 151, Citation Count: 13

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/1345206.1345237 What is a DOI?

ABSTRACT

We describe a methodology for transforming a large class of highly-concurrent linearizable objects into highly-concurrent transactional objects. As long as the linearizable implementation satisfies certain regularity properties (informally, that every method has an inverse), we define a simple wrapper for the linearizable implementation that guarantees that concurrent transactions without inherent conflicts can synchronize at the same granularity as the original linearizable implementation.

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	SXM 1.1: Software Transactional Memory package for C#. http://research.microsoft.com/research/downloads/Details/6cfc842d-1c16-4739-afaf-edb35f544384/Details.aspx.
	2	Bayer, R., and Schkolnick, M. Concurrency of operations on B-Trees. Acta Informatica 9 (1977), 1--21.
	3	C. Beeri , P. A. Bernstein , N. Goodman , M. Y. Lai , D. E. Shasha, A concurrency control theory for nested transactions (Preliminary Report), Proceedings of the second annual ACM symposium on Principles of distributed computing, p.45-62, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806709]
	4	Bernstein, A. Analysis of programs for parallel processing. IEEE Transactions on Electronic Computers 15, 5 (1966), 757--763.
	5	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
	6	Peter Damron , Alexandra Fedorova , Yossi Lev , Victor Luchangco , Mark Moir , Daniel Nussbaum, Hybrid transactional memory, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
	7	Dice, D., Shalev, O., and Shavit, N. Transactional locking II. In Proceedings of the 20th International Symposium on Distributed Computing (DISC '06) (2006), pp. 194--208.
	8	Tim Harris , Keir Fraser, Language support for lightweight transactions, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
	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	Harris, T., and Stipiç, S. Abstract nested transactions. http://research.microsoft.com/~tharris/papers/2007-ant.pdf, 2007.
	11	Herlihy, M., and Koskinen, E. Transactional boosting: A methodology for highly-concurrent transactional objects. Tech. Rep. CS-07-08, Brown University, Department of Computer Science, 2007.
	12	Maurice Herlihy , Victor Luchangco , Mark Moir, A flexible framework for implementing software transactional memory, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
	13	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]
	14	Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
	15	Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
	16	Galen C. Hunt , Maged M. Michael , Srinivasan Parthasarathy , Michael L. Scott, An efficient algorithm for concurrent priority queue heaps, Information Processing Letters, v.60 n.3, p.151-157, Nov. 11, 1996 [doi>10.1016/S0020-0190(96)00148-2]
	17	Henry F. Korth, Locking Primitives in a Database System, Journal of the ACM (JACM), v.30 n.1, p.55-79, Jan. 1983 [doi>10.1145/322358.322363]
	18	Milind Kulkarni , Keshav Pingali , Bruce Walter , Ganesh Ramanarayanan , Kavita Bala , L. Paul Chew, Optimistic parallelism requires abstractions, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
	19	David B. Lomet, MLR: a recovery method for multi-level systems, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.185-194, June 02-05, 1992, San Diego, California, United States
	20	Maged M. Michael, High performance dynamic lock-free hash tables and list-based sets, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564881]
	21	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
	22	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]
	23	William Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees, Proceedings of the Workshop on Algorithms and Data Structures, p.437-449, August 17-19, 1989
	24	Martin C. Rinard , Pedro C. Diniz, Commutativity analysis: a new analysis technique for parallelizing compilers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.6, p.942-991, Nov. 1997 [doi>10.1145/267959.269969]
	25	Saha, B., Adl-Tabatabai, A.-R., Hudson, R., Minh, C. C., and Hertzberg, B. Mcrt-S?. In Proceedings of the 11th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming (PPoPP '06) (2006).
	26	Peter M. Schwarz , Alfred Z. Spector, Synchronizing shared abstract types, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.223-250, Aug. 1984 [doi>10.1145/989.1188]
	27	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]
	28	Michael F. Spear , Virendra J. Marathe , Luke Dalessandro , Michael L. Scott, Privatization techniques for software transactional memory, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281161]
	29	Guy L. Steele, Jr., Making asynchronous parallelism safe for the world, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.218-231, December 1989, San Francisco, California, United States [doi>10.1145/96709.96731]
	30	William E. Weihl, Data-dependent concurrency control and recovery (Extended Abstract), Proceedings of the second annual ACM symposium on Principles of distributed computing, p.63-75, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806710]
	31	Zilles, C., and Baugh, L. Extending hardware transactional memory to support nonbusy waiting and nontransactional actions. In Proceedings of the 1st ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (TRANSACT '06). June 2006.

CITED BY 13

	Justin E. Gottschlich , Jeremy G. Siek , Manish Vachharajani , Dwight Y. Winkler , Daniel A. Connors, An efficient lock-aware transactional memory implementation, Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems, p.10-17, July 06-06, 2009, Genova, Italy
	Eric Koskinen , Maurice Herlihy, Checkpoints and continuations instead of nested transactions, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Kunal Agrawal , I-Ting Angelina Lee , Jim Sukha, Safe open-nested transactions through ownership, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
	Chinmay Eishan Kulkarni , Osman Unsal , Adrián Cristal , Eduard Ayguadé , Mateo Valero, Turbocharging boosted transactions or: how i learnt to stop worrying and love longer transactions, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
	Eric Koskinen , Maurice Herlihy, Dreadlocks: efficient deadlock detection, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Maurice Herlihy , Victor Luchangco, Distributed computing and the multicore revolution, ACM SIGACT News, v.39 n.1, March 2008
	Andrey Brito, Optimistic parallelization support for event stream processing systems, Proceedings of the 5th Middleware doctoral symposium, p.7-12, December 01-01, 2008, Leuven, Belgium
	Yang Ni , Adam Welc , Ali-Reza Adl-Tabatabai , Moshe Bach , Sion Berkowits , James Cownie , Robert Geva , Sergey Kozhukow , Ravi Narayanaswamy , Jeffrey Olivier , Serguei Preis , Bratin Saha , Ady Tal , Xinmin Tian, Design and implementation of transactional constructs for C/C++, ACM SIGPLAN Notices, v.43 n.10, September 2008
	Hany E. Ramadan , Indrajit Roy , Maurice Herlihy , Emmett Witchel, Committing conflicting transactions in an STM, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
	Ferad Zyulkyarov , Vladimir Gajinov , Osman S. Unsal , Adrián Cristal , Eduard Ayguadé , Tim Harris , Mateo Valero, Atomic quake: using transactional memory in an interactive multiplayer game server, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
	Martin Sulzmann , Edmund S.L. Lam , Simon Marlow, Comparing the performance of concurrent linked-list implementations in Haskell, Proceedings of the 4th workshop on Declarative aspects of multicore programming, January 20-20, 2009, Savannah, GA, USA
	Vladimir Gajinov , Ferad Zyulkyarov , Osman S. Unsal , Adrian Cristal , Eduard Ayguade , Tim Harris , Mateo Valero, QuakeTM: parallelizing a complex sequential application using transactional memory, Proceedings of the 23rd international conference on Supercomputing, June 08-12, 2009, Yorktown Heights, NY, USA
	Eric Koskinen , Maurice Herlihy, Brief announcement: concurrent non-commutative boosted transactions, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada