Preventing versus curing: Avoiding conflicts in transactional memories
Dragojevic A, Guerraoui R, Singh A, Singh V. 2009. Preventing versus curing: Avoiding conflicts in transactional memories. Proceedings of the 28th ACM symposium on Principles of distributed computing. POPL: Principles of Programming Languages, 7–16.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Scopus indexed
Author
Dragojevic, Aleksandar;
Guerraoui, Rachid;
Singh, Anmol;
Singh, VasuISTA
Abstract
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 offline TM scheduler, but (2) even a slight inaccuracy in prediction makes the competitive ratio of the TM scheduler in 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 (1) bases its prediction of transactional accesses on the access patterns of the past transactions from the same thread, and (2) 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 read and write access predictions on STMBench7 and STAMP. In our experimental evaluation, Shrink significantly improves STM performance in cases the number of executing threads is higher than the number of available CPU cores. For SwissTM, Shrink improves the performance by up to 55% on STMBench7, and up to 120% on STAMP. For TinySTM, Shrink drastically improves the performance on STMBench7 and STAMP benchmarks.
Publishing Year
Date Published
2009-08-10
Proceedings Title
Proceedings of the 28th ACM symposium on Principles of distributed computing
Publisher
ACM
Page
7 - 16
Conference
POPL: Principles of Programming Languages
Conference Location
Calgary, Canada
Conference Date
2009-08-10 – 2009-08-12
IST-REx-ID
Cite this
Dragojevic A, Guerraoui R, Singh A, Singh V. Preventing versus curing: Avoiding conflicts in transactional memories. In: Proceedings of the 28th ACM Symposium on Principles of Distributed Computing. ACM; 2009:7-16. doi:10.1145/1582716.1582725
Dragojevic, A., Guerraoui, R., Singh, A., & Singh, V. (2009). Preventing versus curing: Avoiding conflicts in transactional memories. In Proceedings of the 28th ACM symposium on Principles of distributed computing (pp. 7–16). Calgary, Canada: ACM. https://doi.org/10.1145/1582716.1582725
Dragojevic, Aleksandar, Rachid Guerraoui, Anmol Singh, and Vasu Singh. “Preventing versus Curing: Avoiding Conflicts in Transactional Memories.” In Proceedings of the 28th ACM Symposium on Principles of Distributed Computing, 7–16. ACM, 2009. https://doi.org/10.1145/1582716.1582725.
A. Dragojevic, R. Guerraoui, A. Singh, and V. Singh, “Preventing versus curing: Avoiding conflicts in transactional memories,” in Proceedings of the 28th ACM symposium on Principles of distributed computing, Calgary, Canada, 2009, pp. 7–16.
Dragojevic A, Guerraoui R, Singh A, Singh V. 2009. Preventing versus curing: Avoiding conflicts in transactional memories. Proceedings of the 28th ACM symposium on Principles of distributed computing. POPL: Principles of Programming Languages, 7–16.
Dragojevic, Aleksandar, et al. “Preventing versus Curing: Avoiding Conflicts in Transactional Memories.” Proceedings of the 28th ACM Symposium on Principles of Distributed Computing, ACM, 2009, pp. 7–16, doi:10.1145/1582716.1582725.