Preventing versus curing: avoiding conflicts in transactional memories

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.

REFERENCES

• 1: Virgílio Almeida , Azer Bestavros , Mark Crovella , Adriana de Oliveira, Characterizing reference locality in the WWW, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.92-107, December 18-20, 1996, Miami Beach, Florida, United States
• 2: Mohammad Ansari , Mikel Luján , Christos Kotselidis , Kim Jarvis , Chris Kirkham , Ian Watson, Steal-on-Abort: Improving Transactional Memory Performance through Dynamic Transaction Reordering, Proceedings of the 4th International Conference on High Performance Embedded Architectures and Compilers, January 25-28, 2009, Paphos, Cyprus [doi>10.1007/978-3-540-92990-1_3]
• 3: Hagit Attiya , Leah Epstein , Hadas Shachnai , Tami Tamir, Transactional contention management as a non-clairvoyant scheduling problem, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146428]
• 4: D. Dice, O. Shalev, and N. Shavit. Transactional Locking II. In DISC, pages 194--208. Springer, 2006.
• 5: Shlomi Dolev , Danny Hendler , Adi Suissa, CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400769]
• 6: Aleksandar Dragojević , Rachid Guerraoui , Michal Kapalka, Stretching transactional memory, Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation, June 15-21, 2009, Dublin, Ireland
• 7: R. Guerraoui, M. Herlihy, and B. Pochon. Polymorphic contention management. In DISC, pages 303--323. Springer, 2005.
• 8: Rachid Guerraoui , Maurice Herlihy , Bastian Pochon, Towards a theory of transactional contention managers, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146429]
• 9: Rachid Guerraoui , Michal Kapalka , Jan Vitek, STMBench7: a benchmark for software transactional memory, Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, March 21-23, 2007, Lisbon, Portugal
• 10: Maurice Herlihy , Victor Luchangco , Mark Moir , William N. Scherer, III, Software transactional memory for dynamic-sized data structures, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.92-101, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872048]
• 11: V. J. Marathe, M. F. Spear, C. Heriot, A. Acharya, D. Eisenstat, W. N. Scherer III, and M. L. Scott. Lowering the overhead of software transactional memory. In TRANSACT. Jun 2006.
• 12: C. Cao Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford Transactional Applications for Multi-Processing. In IISWC. IEEE, 2008.
• 13: K. E. Moore, J. Bobba, M. J. Moravan, M.D. Hill, and D. A. Wood. LogTM: Log-based transactional memory. In HPCA, pages 254--265. IEEE Computer Society, Feb 2006.
• 14: Rajeev Motwani , Steven Phillips , Eric Torng, Nonclairvoyant scheduling, Theoretical Computer Science, v.130 n.1, p.17-47, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90151-1]
• 15: Torvald Riegel , Christof Fetzer , Pascal Felber, Time-based transactional memory with scalable time bases, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248415]
• 16: Christopher J. Rossbach , Owen S. Hofmann , Donald E. Porter , Hany E. Ramadan , Bhandari Aditya , Emmett Witchel, TxLinux: using and managing hardware transactional memory in an operating system, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 17: William N. Scherer, III , Michael L. Scott, Advanced contention management for dynamic software transactional memory, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073861]
• 18: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 19: A. Tomar. Dynamic prediction based scheduling for tm. In Master Thesis, pages 169--178. EPFL, February 2009.
• 20: M. M. Waliullah and P. Stenstrom. Intermediate checkpointing with conflicting access prediction in transactional memory systems. In IPDPS, pages 1--11. IEEE Computer Society, 2008.
• 21: Richard M. Yoo , Hsien-Hsin S. Lee, Adaptive transaction scheduling for transactional memory systems, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378564]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Performance, Theory

Keywords:
contention management, scheduling, software transactional memory