Preventing versus Curing: Avoiding Conflicts in Transactional Memories

Transactional memories are typically speculative and rely on contention managers to cure conflicts. This paper explores a complementary approach that prevents conflicts by scheduling transactions according to predictions on their access sets. We first explore the theoretical boundaries of this approach and prove that (1) a TM scheduler with an accurate prediction can be 2- competitive with an optimal TM scheduler, but (2) even a slight inaccuracy in prediction makes the competitive ratio of the TM scheduler of the order of the number of transactions. We then show that, in practice, there is room for a pragmatic approach with good average case performance. We present Shrink, a scheduler that (a) bases its prediction on the access patterns of the past transactions from the same threads, and (b) uses a novel heuristic, which we call serialization affinity, to schedule transactions with a probability proportional to the current amount of contention. Shrink obtains roughly 70% accurate predictions on STMBench7 and STAMP. For SwissTM, Shrink improves the performance by up to 55% on STMBench7, and up to 120% on STAMP. For TinySTM, Shrink improves the performance by up to 30 times on STMBench7 and 100 times on STAMP.


Published in:
Twenty-Eighth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
Presented at:
Twenty-Eighth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Calgary, Alberta, Canada, August 10-12, 2009
Year:
2009
Keywords:
Laboratories:




 Record created 2009-04-27, last modified 2018-01-28

External links:
Download fulltextURL
Download fulltextn/a
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)