TY - GEN
T1 - Coarse-grained transactions
AU - Koskinen, Eric
AU - Parkinson, Matthew
AU - Herlihy, Maurice
PY - 2010
Y1 - 2010
N2 - 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 coarse-grained (abstract data-type) operations rather than simple 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.
AB - 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 coarse-grained (abstract data-type) operations rather than simple 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.
KW - Abstract data-types
KW - Coarse-grained transactions
KW - Commutativity
KW - Movers
KW - Transactional boosting
KW - Transactional memory
UR - http://www.scopus.com/inward/record.url?scp=77950884124&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77950884124&partnerID=8YFLogxK
U2 - 10.1145/1706299.1706304
DO - 10.1145/1706299.1706304
M3 - Conference contribution
AN - SCOPUS:77950884124
SN - 9781605584799
T3 - Conference Record of the Annual ACM Symposium on Principles of Programming Languages
SP - 19
EP - 30
BT - POPL'10 - Proceedings of the 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
T2 - 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL'10
Y2 - 17 January 2010 through 23 January 2010
ER -