Technical reports

Coarse-grained transactions
(extended version)

Eric Koskinen, Matthew Parkinson, Maurice Herlihy

August 2011, 34 pages

DOI: 10.48456/tr-759

Abstract

Traditional transactional memory systems suffer from overly conservative conflict detection, yielding so-called false conflicts, because they are based on fine-grained, low-level read/write conflicts. In response, the recent trend has been toward integrating various abstract data-type libraries using ad-hoc methods of high-level conflict detection. These proposals have led to improved performance but a lack of a unified theory has led to confusion in the literature.

We clarify these recent proposals by defining a generalization of transactional memory in which a transaction consists of course-grained (abstract data-type) operations rather than simply memory read/write operations. We provide semantics for both pessimistic (e.g. transactional boosting) and optimistic (e.g. traditional TMs and recent alternatives) execution. We show that both are included in the standard atomic semantics, yet find that the choice imposes different requirements on the coarse-grained operations: pessimistic requires operations be left-movers, optimistic requires right-movers. Finally, we discuss how the semantics applies to numerous TM implementation details discussed widely in the literature.

Full text

PDF (0.6 MB)

BibTeX record

@TechReport{UCAM-CL-TR-759,
  author =	 {Koskinen, Eric and Parkinson, Matthew and Herlihy, Maurice},
  title = 	 {{Coarse-grained transactions (extended version)}},
  year = 	 2011,
  month = 	 aug,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-759.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-759},
  number = 	 {UCAM-CL-TR-759}
}