Shlomi Dolev
ABSTRACT
Transactional memory (TM) is a key concurrent programming abstraction. Several software-based transactional memory (STM) implementations have been developed in recent years. All STM implementations must guarantee transaction atomicity but different STM implementations may provide different progress guarantees. In order to ensure progress, an STM implementation must resolve transaction conflicts. This is done either by the implementation itself or by delegating conflict resolution to a separate contention manager module that tries to resolve transaction collisions once they are detected.
We present CAR-STM, a scheduling-based mechanism for STM Collision Avoidance and Resolution, that can be incorporated into existing STM implementations. CAR-STM maintains per-core transaction queues and schedules a thread while it is performing a transaction. CAR-STM employs the following two novel collision reduction techniques: (1) seriailizing contention managers resolve conflicts by aborting one transaction and moving it to the transactions queue of the other, effectively serializing the execution of these transactions and ensuring they will not collide again. (2) Proactive collision reduction allows applications to provide information about transactions' collision-probability. CAR-STM uses this information to pre-assign transactions that are more likely to collide to the same core.
We have incorporated CAR-STM into the University of Rochester's STM (RSTM) and compared the performance of the new implementation with that of the original RSTM by using STMBench7. Our results show that the new implementation provides orders-of-magnitude reduction of execution times and improved throughput for almost all concurrency levels. Additionally, since CAR-STM greatly reduces the unpredictable influence of operating-system scheduling on STM performance, the new implementation provides a much more stable performance. In contrast, the performance of the original RSTM implementation on STMBench7 workloads exhibits extremely high variance. Though our paper focuses on software transactional memory, we believe the ideas introduced by CAR-STM may prove useful also for hybrid implementations of transactional memory.
- C. S. Ananian, K. Asanovic, B. C. Kuszmaul, C. E. Leiserson, and S. Lie. Unbounded transactional memory. In Proceedings of the Eleventh International Symposium on High-Performance Computer Architecture, pages 316--327, 2005. Google Scholar
Digital Library
- H. Attiya, L. Epstein, H. Shachnai, and T. Tamir. Transactional contention management as a non-clairvoyant scheduling problem. In PODC, pages 308--315, 2006. Google ScholarDigital Library
- T. Bai, X. Shen, C. Zhang, W. N. Scherer III, C. Ding, and M. L. Scott. A key-based adaptive transactional memory executor. In IPDPS, pages 1--8, 2007.Google ScholarCross Ref
- P. Damron, A. Fedorova, Y. Lev, V. Luchangco, M. Moir, and D. Nussbaum. Hybrid transactional memory. In ASPLOS, pages 336--346, 2006. Google ScholarDigital Library
- K. Fraser. Practical lock-freedom. Ph. D. dissertation, UCAM-CL-TR-579, Computer Laboratory, University of Cambridge, 2004.Google Scholar
- R. Guerraoui, M. Herlihy, and B. Pochon. Polymorphic contention management. In DISC, pages 303--323, 2005. Google ScholarDigital Library
- R. Guerraoui, M. Herlihy, and B. Pochon. Towards a theory of transactional contention managers. In PODC, pages 316--317, 2006. Google ScholarDigital Library
- R. Guerraoui, M. Kapalka, and J. Vitek. Stmbench7: a benchmark for software transactional memory. SIGOPS Oper. Syst. Rev., 41(3):315--324, 2007. Google ScholarDigital Library
- L. Hammond, M. C. V.Wong, B. D. Carlstrom, J. D. Davis, B. Hertzberg, M. K. Prabju, H. Wijaya, C. Kozyrakis, , and K. Olukotun. Transactional memory coherence and consistency. In Proc. of the 31st Annual Intl. Symp. on Computer Architecture, pages 102--113, 2004. Google ScholarDigital Library
- T. Harris and K. Fraser. Language support for lightweight transactions. In OOPSLA, pages 388--402, 2003. Google ScholarDigital Library
- M. Herlihy. SXM software transactional memory package for C\#. http://www.cs.brown.edu/ mph.Google Scholar
- M. Herlihy, V. Luchangco, M. Moir, and W. N. S. III. Software transactional memory for dynamic-sized data structures. In PODC, pages 92--101, 2003. Google ScholarDigital Library
- M. Herlihy and J. E. B. Moss. Transactional memory: Architectural support for lock-free data structures. In ISCA, pages 289--300, 1993. Google ScholarDigital Library
- S. Kumar, M. Chu, C. J. Hughes, P. Kundu, and A. Nguyen. Hybrid transactional memory. In PPOPP, pages 209--220, 2006. Google ScholarDigital Library
- V. J. Marathe, W. N. S. III, and M. L. Scott. Adaptive software transactional memory. In DISC, pages 354--368, 2005. Google ScholarDigital Library
- V. J. Marathe, M. F. Spear, C. Heriot, A. Acharya, D. Eisenstat, I. W. N. Scherer, and M. L. Scott. Lowering the overhead of nonblocking software transactional memory. In Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (TRANSACT06),, 2006.Google Scholar
- K. E. Moore, J. Bobba, M. J. Moravan, M. D. Hill, and D. A. Wood. Logtm: Log-based transactional memory. In Proceedings of the 12th International Conference on High Performance Computer Architecture, pages 254--265, 2006.Google ScholarCross Ref
- R. Rajwar and J. R. Goodman. Transactional lock-free execution of lock-based programs. In Proceedings of the 10th International Conference on Architectural Support for Programming Languages and Operating Systems, 2002. Google ScholarDigital Library
- R. Rajwar, M. Herlihy, and K. Lai. Virtualizing transactional memory. In Proceedings of the 32nd Annual International Symposium on Computer Architecture, pages 494--505, 2005. Google ScholarDigital Library
- C. J. Rossbach, O. S. Hofmann, D. E. Porter, H. E. Ramadan, B. Aditya, and E. Witchel. Txlinux: using and managing hardware transactional memory in an operating system. In SOSP '07, pages 87--102, New York, NY, USA, 2007. ACM. Google ScholarDigital Library
- B. Saha, A.-R. Adl-Tabatabai, R. L. Hudson, C. C. Minh, and B. Hertzberg. Mcrt-stm: a high performance software transactional memory system for a multi-core runtime. In PPOPP, pages 187--197, 2006. Google ScholarDigital Library
- M. L. Scott and W. N. Scherer III. Advanced contention management for dynamic software transactional memory. In PODC, pages 240--248, 2005. Google ScholarDigital Library
- N. Shavit and D. Touitou. Software transactional memory. Distributed Computing, 10(2):99--116, 1997.Google ScholarCross Ref
- G. Vossen and G. Weikum. Transactional information systems, , morgan kaufmann, 2001. Google ScholarDigital Library
- R. M. Yoo and H. S. Lee. Adaptive transaction scheduling for transactional memory systems. Georgia Institute of Technology Technical Report GIT-CERCS-07-04, 2007.Google Scholar
Index Terms
- CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory
Recommendations
Advanced contention management for dynamic software transactional memory
PODC '05: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computingThe obstruction-free Dynamic Software Transactional Memory (DSTM) system of Herlihy et al@. allows only one transaction at a time to acquire an object for writing. Should a second require an object currently in use, a contention manager must determine ...
On the impact of serializing contention management on STM performance
Transactional memory (TM) is an emerging concurrent programming abstraction. Numerous software-based transactional memory (STM) implementations have been developed in recent years. STM implementations must guarantee transaction atomicity and isolation. ...
Scheduling support for transactional memory contention management
PPoPP '10Transactional Memory (TM) is considered as one of the most promising paradigms for developing concurrent applications. TM has been shown to scale well on >multiple cores when the data access pattern behaves "well," i.e., when few conflicts are induced. ...
Comments