Cheng Wang
ABSTRACT
Transactional memory solves many problems in lock-based parallel programs. Unfortunately, the semantics of transactions are different from those of critical sections defined by locks. The semantic differences make it difficult to correctly port existing lock-based programs to transaction-based programs. Experienced programmers accustomed to lock-based programming can easily make mistakes in transaction-based programming as parallel programs running correctly using locks can run incorrectly when converted to using transactions. This problem becomes even more severe in the efficient software transactional memory implementing weak isolation, optimistic read concurrency management and eager version management.
In this paper, we first identify three necessary properties in a program for the program execution using transactions to be equivalent to the program execution using locks. Assuming that the input lock-based program satisfies the necessary properties (i.e. well-behaved parallel programs), we next present a correctness condition for the program execution using transactions to be equivalent to the program execution using locks. Finally, we develop a correct and efficient software transactional memory implementation that satisfies the correctness condition so that locks in the well behaved parallel programs can be converted to use efficient software transactional memory easily and correctly.
- Wang, C., Chen, W., Wu, Y., Saha, B. and Adl-Tabatabai, A. Code Generation and Optimization for Transactional Memory Constructs in an Unmanaged Language. CGO 2007. Google Scholar
Digital Library
- Adl-Tabatabai, A., Lewis, B. T., Menon, V. S., Murphy, B. M., Saha, B., Shpeisman, T. Compiler and runtime support for efficient software transactional memory. PLDI 2006. Google ScholarDigital Library
- Ananian, C. S., Asanovic, K., Kuszmaul, B. C., Leiserson, C. E., Lie, S. Unbounded Transactional Memory. HPCA 2005. Google ScholarDigital Library
- Dice, Dave, Ori Shalev, Nir Shavit, Transactional Locking II, 20th International Symposium on Distributed Computing (DISC 06), Stockholm, Sweden, September 18--20, 2006. Google ScholarDigital Library
- Hammond, L., Carlstrorm, B. D., Wong, V., Hertzberg, B., Chen, M., Kozyrakis, C., and Olukotun, K. Transactional coherence and consistency. ASPLOS 2004. Google ScholarDigital Library
- Harris, T., Plesko, M., Shinnar, A., and Tarditi, D. Optimizing Memory Transactions. PLDI 2006. Google ScholarDigital Library
- Harris, T. L. and Fraser, K. Language support for lightweight transactions. OOPSLA 2003. Google ScholarDigital Library
- Harris, T. L., Marlow, S., Peyton Jones, S., Herlihy, M. Composable memory transactions. PPoPP 2005. Google ScholarDigital Library
- Herlihy, M. and Moss, J. E. B. Transactional memory: architectural support for lock-free data structures. ISCA 1993 Google ScholarDigital Library
- Herlihy, M., Luchango, V., Moir, M., Scherer III, W. M. Software transactional memory for dynamic sized data structures. PODC 2003. Google ScholarDigital Library
- Hudson, R. L., Saha, B. Adl-Tabatabai, A., and Hertzberg, B. C., McRT-Malloc - A Scalable Transactional Memory Allocator, ISMM '06. Google ScholarDigital Library
- Kumar, S., Chu, M., Hughes, C., Kundu, P., Nguyen, A. Hybrid transactional memory. PPoPP 2006. Google ScholarDigital Library
- McDonald, A., Kozyrakis, C., Olukotun, K. Architectural Semantics for Practical Transactional Memory, ISCA 2006. Google ScholarDigital Library
- Moir, M. Hybrid Transactional Memory. Sun Microsystems Technical Report.Google Scholar
- Moore, K. E., Bobba, J., Moravan, M. J., Hill, M. D., Wood, D. A. LogTM: Log-based Transactional Memory. HPCA-12, 2006.Google ScholarCross Ref
- Rajwar, R., Herlihy, M., and Lai, K. Virtualizing transactional memory. ISCA 2005. Google ScholarDigital Library
- Riegel, T., P. Felber, and C. Fetzer, A Lazy Snapshot Algorithm with Eager Validation, 20th International Symposium on Distributed Computing (DISC 06), Stockholm, Sweden, September 18--20, 2006. Google ScholarDigital Library
- Saha, B., Adl-Tabatabai, A., Hudson, R., Minh, C., Hertzberg, B. McRT-STM: A high performance software transactional memory system for a multi-core runtime. PPoPP 2006. Google ScholarDigital Library
- Shavit, N., and Touitou, D. Software transactional memory. PODC 1995. Google ScholarDigital Library
- Shriraman, A., Marathe, V. J., Dwarkadas, S., Scott, M. L., Eisnstat, D., Heriot, C., Scherer III, W. N., Spear, M. F. Hardware acceleration of software transactional memory. Techical report 887, Computer Science Department, University of Rochester, 2006.Google Scholar
- Wang, C., Ying, V., Wu, Y., Dynamic Binary Translation and Optimization of Legacy Library Code in a STM Compilation Environment, CC2008.Google Scholar
- Blundell, C., Levwis, E. C., and Martin, M. M. K. Deconstructing Transactions: The Subtleties of Atomicity. WDDD 2005.Google Scholar
- Banerjee, U., Bliss, B., Ma, Z., Petersen, P. Unraveling Data Race Detection in the Intel® Tread Checker. STMCS 2006Google Scholar
- Shpeisman, T., Menon, V., Adl-Tabatabai, A., Balensiefer, S., Grossman, D., Hudson, R. L., Moore, K. F., and Saha, B. 2007. Enforcing isolation and ordering in STM. SIGPLAN Not. 42, 6 (Jun. 2007). Google ScholarDigital Library
- Menno, V., Balensiefer, S., Shpeisman, T., Adl-Tabatabai, A., Hudson, Saha, B., and Welc, A., Single Global Lock Semantics in a Weekly Atomic STM, TRANSACT 2008Google Scholar
Index Terms
- From lock to correct and efficient software transactional memory
Recommendations
The semantics of progress in lock-based transactional memory
POPL '09Transactional memory (TM) is a promising paradigm for concurrent programming. Whereas the number of TM implementations is growing, however, little research has been conducted to precisely define TM semantics, especially their progress guarantees. This ...
Lock-free and scalable multi-version software transactional memory
PPoPP '11Software Transactional Memory (STM) was initially proposed as a lock-free mechanism for concurrency control. Early implementations had efficiency limitations, and soon obstruction-free proposals appeared, to tackle this problem, often simplifying STM ...
The semantics of progress in lock-based transactional memory
POPL '09: Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languagesTransactional memory (TM) is a promising paradigm for concurrent programming. Whereas the number of TM implementations is growing, however, little research has been conducted to precisely define TM semantics, especially their progress guarantees. This ...
Comments