000136703 001__ 136703
000136703 005__ 20190316234536.0
000136703 02470 $$2ISI$$a000271790300001
000136703 037__ $$aCONF
000136703 245__ $$aPreventing versus Curing: Avoiding Conflicts in Transactional Memories
000136703 260__ $$c2009
000136703 269__ $$a2009
000136703 336__ $$aConference Papers
000136703 520__ $$aTransactional 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.
000136703 6531_ $$aSoftware Transactional Memory
000136703 6531_ $$aContention Management
000136703 6531_ $$aScheduling
000136703 700__ $$0242986$$g173244$$aDragojevic, Aleksandar
000136703 700__ $$aSingh, Anmol
000136703 700__ $$g105326$$aGuerraoui, Rachid$$0240335
000136703 700__ $$aSingh, Vasu
000136703 7112_ $$dAugust 10-12, 2009$$cCalgary, Alberta, Canada$$aTwenty-Eighth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
000136703 773__ $$tTwenty-Eighth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
000136703 8564_ $$uhttp://www.podc.org/podc2009/$$zURL
000136703 8564_ $$uhttps://infoscience.epfl.ch/record/136703/files/main.pdf$$zn/a$$s385038
000136703 909C0 $$xU10407$$0252114$$pDCL
000136703 909CO $$ooai:infoscience.tind.io:136703$$qGLOBAL_SET$$pconf$$pIC
000136703 937__ $$aLPD-CONF-2009-003
000136703 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000136703 980__ $$aCONF