Name
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1582716.1582725 | PODC |
Keywords | Field | DocType |
transactional memory,complementary approach,accurate prediction,good average case performance,tm scheduler,access prediction,access pattern,stamp benchmarks,access set,optimal offline tm scheduler,stm performance,competitive ratio,software transactional memory,scheduling,content management | Software transactional memory,Heuristic,Serialization,Scheduling (computing),Computer science,Parallel computing,Thread (computing),Transactional leadership,Multi-core processor,Distributed computing,Competitive analysis | Conference |
Citations | PageRank | References |
59 | 1.42 | 18 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aleksandar Dragojevic | 1 | 470 | 16.41 |
| Rachid Guerraoui | 2 | 6364 | 430.90 |
| Anmol V. Singh | 3 | 108 | 4.88 |
| Vasu Singh | 4 | 186 | 9.36 |