Reconciling transactional conflicts with compiler's help

ABSTRACT

Software transactional memory(STM) is a promising programming paradigm for shared memory multithreaded programs. While STM offers the promise of being less error-prone and more programmer friendly compared to traditional lock-based synchronization, it also needs to be competitive in performance in order for it to be adopted in mainstream software. A major source of performance overheads in STM is transactional aborts. Conflict resolution and aborting a transaction typically happens at the transaction level which has the advantage that it is automatic and application agnostic. However it has a substantial disadvantage in that STM declares the entire transaction as conflicting and hence aborts it and re-executes it fully, instead of partially re-executing only those part(s) of the transaction, which have been affected due to the conflict. This "Re-execute Everything" approach has a significant adverse impact on STM performance.

In order to mitigate the abort overheads, we propose a compiler aided Selective Reconciliation STM (SR-STM) scheme, wherein certain transactional conflicts can be reconciled by performing partial re-execution of the transaction. Ours is a selective hybrid approach which uses compiler analysis to identify those data accesses which are legal and profitable candidates for reconciliation and applies partial re-execution only to these candidates selectively while other conflicting data accesses are handled by the default STM approach of abort and full re-execution. We describe the compiler analysis and code transformations required for supporting selective reconciliation. We find that SR-STM is effective in reducing the transactional abort overheads by improving the performance for a set of five STAMP benchmarks by 12.58% on an average and up to 22.34%.

References

1. Y. Afek, A. Morrison, and M. Tzafrir. Brief announcement: view transactions: transactional model with relaxed consistency checks. In Proceeding of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing, PODC '10, pages 65--66, New York, NY, USA, 2010. ACM.
2. C. Blundell, A. Raghavan, and M. M. Martin. Retcon: transactional repair without replay. In Proceedings of the 37th annual international symposium on Computer architecture, ISCA '10, pages 258--269, New York, NY, USA, 2010.
3. J. Bobba, K. E. Moore, H. Volos, L. Yen, M. D. Hill, M. M. Swift, and D. A. Wood. Performance pathologies in hardware transactional memory. SIGARCH Comput. Archit. News, 35:81--91, June 2007.
4. C. Cao Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford transactional applications for multi-processing. In IISWC '08: Proceedings of The IEEE International Symposium on Workload Characterization, September 2008.
5. S. C. Chan, G. R. Gao, B. Chapman, T. Linthicum, and A. Dasgupta. Open64 tutorial. In IPDPS, page 1, 2008.
6. D. Dice, O. Shalev, and N. Shavit. Transactional locking II. In DISC '06: Proc. 20th International Symposium on Distributed Computing, pages 194--208, September 2006.
7. D. Dice and N. Shavit. Understanding tradeoffs in software transactional memory. In CGO '07: Proceedings of the International Symposium on Code Generation and Optimization, pages 21--33, March 2007.
8. S. Dolev, D. Hendler, and A. Suissa. Car-stm: scheduling-based collision avoidance and resolution for software transactional memory. In Proceedings of PODC, pages 125--134. August 2008.
9. A. Dragojević, R. Guerraoui, and M. Kapalka. Stretching transactional memory. SIGPLAN Not., 44:155--165, June 2009.
10. A. Dragojević, R. Guerraoui, A. V. Singh, and V. Singh. Preventing versus curing: Avoiding conflicts in transactional memories. In PODC '09: Proc. 28th ACM Symposium on Principles of Distributed Computing, August 2009.
11. P. Felber, V. Gramoli, and R. Guerraoui. Elastic transactions. In Proceedings of the 23rd international conference on Distributed computing, DISC'09, pages 93--107, Berlin, 2009.
12. T. Harris and S. Stipic. Abstract nested transactions. In TRANSACT '07, August 2007.
13. M. Herlihy and E. Koskinen. Transactional boosting: a methodology for highly-concurrent transactional objects. In PPoPP '08, pages 207--216, New York, NY, USA, 2008. ACM.
14. M. Herlihy, V. Luchangco, M. Moir, and William Scherer. Software transactional memory for dynamic-sized data structures. In PODC '03, pages 92--101, July 2003.
15. G. Kestor, V. Karakostas, O. S. Unsal, A. Cristal, I. Hur, and M. Valero. Rms-tm: a comprehensive benchmark suite for transactional memory systems. SIGSOFT Software Engineering Notes, 36:42--43, Sept. 2011.
16. E. Koskinen and M. Herlihy. Checkpoints and continuations instead of nested transactions. In Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, SPAA '08, pages 160--168, 2008.
17. J. R. Larus and R. Rajwar. Transactional Memory. Morgan and Claypool, 2006.
18. J. E. B. Moss. Open nested transactions: Semantics and support (poster). In Workshop on Memory Performance Issues, February 2006.
19. J. E. B. Moss and A. L. Hosking. Nested transactional memory: model and architecture sketches. Sci. Comput. Program., 63:186--201, December 2006.
20. Y. Ni, V. S. Menon, A.-R. Adl-Tabatabai, A. L. Hosking, R. L. Hudson, J. E. B. Moss, B. Saha, and T. Shpeisman. Open nesting in software transactional memory. In PPoPP '07, pages 68--78, New York, NY, USA, 2007. ACM.
21. L. Schaelicke and E. DeLano. Intel itanium quad-core architecture for the enterprise. In EPIC '08: Proceedings of the Eighth Workshop on Explicitly Parallel Instruction Computing Architectures and Compiler Technology, pages 21--33, April 2010.
22. W. N. Scherer III and M. L. Scott. Advanced contention management for dynamic software transactional memory. In Proceedings of the 24th ACM Symposium on Principles of Distributed Computing, Las Vegas, NV, July 2005.
23. Y. Wu and J. R. Larus. Static branch frequency and program profile analysis. In Proceedings of the 27th annual international symposium on Microarchitecture, MICRO 27, pages 1--11, New York, NY, USA, 1994. ACM.
24. R. M. Yoo and H.-H. S. Lee. Adaptive transaction scheduling for transactional memory systems. In SPAA '08, pages 169--178, June 2008.
25. R. M. Yoo, Y. Ni, A. Welc, B. Saha, A.-R. Adl-Tabatabai, and H.-H. S. Lee. Kicking the tires of software transactional memory: why the going gets tough. In SPAA '08, pages 265--274, June 2008.
26. F. Zyulkyarov, S. Stipic, T. Harris, O. S. Unsal, A. Cristal, I. Hur, and M. Valero. Discovering and understanding performance bottlenecks in transactional applications. In Proceedings of the 19th international conference on Parallel architectures and compilation techniques, PACT '10, pages 285--294, New York, NY, USA, 2010. ACM.

Index Terms

• Computing methodologies

  • Concurrent computing methodologies

    • Concurrent programming languages

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language types

        • Concurrent programming languages