The Runtime Abort Graph and its Application to Software Transactional Memory Optimization
Chakrabarti, Dhruva R.; Banerjee, Prithviraj; Boehm, Hans-J.; Joisha, Pramod G., Schreiber, Robert S.
Keyword(s): No keywords available.
Abstract: Programming with atomic sections is a promising alternative to locks since it raises the abstraction and removes deadlocks at the programmer level. However, implementations of atomic sections using software transactional memory (STM) support have significant bookkeeping overheads. STM programmers therefore need tools that provide insights and means to improve performance. This paper attempts to identify the source of an abort at the granularity of a transactional memory reference. The resulting abort patterns are captured in the form of a runtime abort graph (RAG). We show how to build this graph efficiently using compiler instrumentation and discuss its qualitative semantics. We then describe a technique that works on the RAG and automatically recommends STM policy changes to improve performance. Significant performance improvements, upto 90% individually, have been obtained. We present detailed experimental results showing the tradeoffs in building the RAG and its use in reducing aborts and improving performance.
Additional Publication Information: Parts of this work will appear in the International Symposium on Code Generation and Optimization (CGO), 2011.
External Posting Date: February 16, 2011 [Fulltext]. Approved for External Publication
Internal Posting Date: October 21, 2010 [Fulltext]