Justin E. Gottschlich
Jeremy G. Siek
Manish Vachharajani
ABSTRACT
Transactional memory (TM) is an emerging concurrency control mechanism that provides a simple and composable programming model. Unfortunately, transactions violate the semantics of mutual exclusion locks when they execute concurrently. Due to the prevalence of locks, transactions must be made lock-aware enabling them to correctly interoperate with locks.
We present a lock-aware transactional memory (LATM) system that employs a unique communication method using local knowledge of locks coupled with granularity-based policies. Our system allows higher concurrent throughput than prior systems because it only prevents truly conflicting critical sections from executing concurrently. Furthermore, our system relaxes the prior requirement of transaction isolation when executing conflicting transactional critical sections and instead runs these transactions as irrevocable, improving transaction concurrency. We demonstrate our performance improvements mathematically and empirically.
Our system also advances LATM research in terms of program consistency. This is achieved by detecting potential deadlocks at run-time and aborting the programs that contain them. Prior systems break deadlocks, which reveal partially executed critical sections to other threads, thereby violating mutual exclusion. Because our system disallows deadlocks, it does not suffer from mutual exclusion violations, improving program consistency.
- A.-R. Adl-Tabatabai, D. Dice, M. Herlihy, N. Shavit, C. Kozyrakis, C. von Praun, and M. Scott. Potential show-stoppers for transactional synchronization. In PPOPP, page 55, 2007. Google Scholar
Digital Library
- E. W. Dijkstra. Solution of a problem in concurrent programming control. Commun. ACM, 8(9):569, 1965. Google ScholarDigital Library
- J. E. Gottschlich and D. A. Connors. DracoSTM: A practical C++ approach to software transactional memory. In ACM SIGPLAN Library-Centric Software Design (LCSD), Oct. 2007. Google ScholarDigital Library
- J. E. Gottschlich and D. A. Connors. Optimizing consistency checking for memory-intensive transactions. In ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Aug. 2008. Google ScholarDigital Library
- J. E. Gottschlich, J. G. Siek, P. J. Rogers, and M. Vachharajani. Toward simplified parallel support in C++. In Proceedings of the Fourth International Conference on Boost Libraries (BoostCon). May 2009.Google Scholar
- T. Harris, S. Marlow, S. L. P. Jones, and M. Herlihy. Composable memory transactions. In K. Pingali, K. A. Yelick, and A. S. Grimshaw, editors, PPoPP, pages 48--60. ACM, 2005. Google ScholarDigital Library
- M. Herlihy and E. Koskinen. Transactional boosting: a methodology for highly-concurrent transactional objects. In PPoPP. ACM, 2008. Google ScholarDigital Library
- M. Herlihy and J. E. B. Moss. Transactional memory: Architectural support for lock-free data structures. In Proceedings of the International Symposium on Computer Architecture. May 1993. Google ScholarDigital Library
- M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Elsevier, Inc., 2008. Google ScholarDigital Library
- J. R. Larus and R. Rajwar. Transactional Memory. Morgan and Claypool, 2006.Google ScholarCross Ref
- V. J. Marathe and M. Moir. Toward high performance nonblocking software transactional memory. In PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, pages 227--236, New York, NY, USA, 2008. ACM. Google ScholarDigital Library
- 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 Symposium on High-Performance Computer Architecture, pages 254--265. IEEE Computer Society, Feb. 2006.Google ScholarDigital Library
- J. E. B. Moss and A. L. Hosking. Nested transactional memory: model and architecture sketches. Sci. Comput. Program., 63(2), 2006. Google ScholarDigital Library
- R. Rajwar and P. A. Bernstein. Atomic transactional execution in hardware: A new high performance abstraction for databases. In Workshop on High Performance Transaction Systems, 2003.Google Scholar
- 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 T. C. Bressoud and M. F. Kaashoek, editors, SOSP, pages 87--102. ACM, 2007. Google ScholarDigital Library
- N. Shavit and D. Touitou. Software transactional memory. In Proceedings of the Principles of Distributed Computing. Aug 1995. Google ScholarDigital Library
- M. F. Spear, L. Dalessandro, V. Marathe, and M. L. Scott. A comprehensive strategy for contention management in software transactional memory. In PPoPP, Feb. 2009. Google ScholarDigital Library
- M. F. Spear, M. M. Michael, and M. L. Scott. Inevitability mechanisms for software transactional memory. In Proceedings of the 3rd ACM SIGPLAN Workshop on Transactional Computing. Feb 2008.Google Scholar
- H. Volos, N. Goyal, and M. M. Swift. Pathological interaction of locks with transactional memory. In ACM SIGPLAN Workshop on Transactional Computing, February 2008.Google Scholar
- A. Welc, B. Saha, and A.-R. Adl-Tabatabai. Irrevocable transactions and their applications. In SPAA, 2008. Google ScholarDigital Library
- L. Ziarek, A. Welc, A.-R. Adl-Tabatabai, V. Menon, T. Shpeisman, and S. Jagannathan. A uniform transactional execution environment for Java. In ECOOP, pages 129--154, 2008. Google ScholarDigital Library
- C. Zilles and D. Flint. Challenges to providing performance isolation in transactional memories. In Proceedings of the Fourth Workshop on Duplicating, Deconstructing, and Debunking, pages 48--55, Jun 2005.Google Scholar
Index Terms
- An efficient lock-aware transactional memory implementation
Recommendations
An efficient software transactional memory using commit-time invalidation
CGO '10: Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimizationTo improve the performance of transactional memory (TM), researchers have found many eager and lazy optimizations for conflict detection, the process of determining if transactions can commit. Despite these optimizations, nearly all TMs perform one ...
Safe privatization in transactional memory
PPoPP '18Transactional memory (TM) facilitates the development of concurrent applications by letting the programmer designate certain code blocks as atomic. Programmers using a TM often would like to access the same data both inside and outside transactions, ...
Safe privatization in transactional memory
PPoPP '18: Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel ProgrammingTransactional memory (TM) facilitates the development of concurrent applications by letting the programmer designate certain code blocks as atomic. Programmers using a TM often would like to access the same data both inside and outside transactions, ...
Comments