The least common denominator is the weak model, but erroneous programs will produce divergent results on different systems. An alternative viewpoint is that unsynchronized data accesses between two threads is generally an error, and if only one thread is executing a transaction, then there is insufficient synchronization between the threads. Therefore, the programming language, tools, runtime system, or hardware should prevent or detect unsynchronized sharing between transactional and non-transactional code, and a programmer should fix the defect.

Weakly atomic systems also face difficulties when an object is shared between transactional and non-transactional code. ³⁰ Publication occurs when a thread makes an object visible to other threads (for example, by adding it to a global queue) and privatiza-tion occurs when a thread removes an object from the global shared space. Private data should be manipulatable outside of a transaction without synchronization, but an object’s transition between public and private must be coordinated with the TM system, lest it attempt to roll back an object’s state while another thread assumes it has sole, private access to the data.

Finally, TM must coexist and interoperate with existing programs and libraries. It is not practical to require programmers to start afresh and acquire a brand new set of transactional libraries to enjoy the benefits of TM. Existing sequential code should be able to execute correctly in a transaction, perhaps with a small amount of annotation and recompilation. Existing parallel code that uses locks and other forms of synchronization, must continue to operate properly, even if some threads are executing transactions.

conclusion

Transactional memory by itself is unlikely to make Multicore computers readily programmable. Many other improvements to programming languages, tools, runtime systems, and computer architecture are also necessary. TM, however, does provide a time-tested model for isolating concurrent computations from each other. This model raises the level of abstraction for reasoning about concurrent tasks and helps avoid many insidious parallel

programming errors. However, many aspects of the semantics and implementation of TM are still the subject of active research. If these difficulties can be resolved in a timely fashion, TM will likely become a central pillar of parallel programming.

 

References

1. Adl- Tabatabai, A. R., Lewis, B. T., Menon, V., Murphy, B.R., Saha, B., and Shpeisman, T. Compiler and runtime support for efficient software transactional memory. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation (Ottawa, Ontario, Canada, 2006). ACM, NY 26– 37.

2. Blundell, C., Lewis, E.C., and Martin, M.M.K . Subtleties of transactional memory atomicity semantics. IEEE Computer Architecture Letters 5 (Nov. 2006).

3. Bobba, J., Moore, K.E., Volos, H., Yen, L., Hill, M.D., Swift, M.M., and Wood, D.A. Performance pathologies in hardware transactional memory. In Proceedings of the 34^th International Symposium on Computer Architecture (San Diego, CA, 2007). ACM, N Y, 81– 91.

4. Carlstrom, B. D., McDonald, A., Carbin, M., Kozyrakis, C., and Olukotun, K. Transactional collection classes. In Proceedings of the 12^th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (San Jose, CA, 2007). ACM, N Y, 56– 67.

5. Carlstrom, B. D., McDonald, A., Chafi, H., Chung, J., Minh, C. C., Kozyrakis, C., and Olukotun, K. The Atomos transactional programming language. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation (Ottawa, Ontario, Canada, 2006). ACM, NY, 1– 13.

6. Ceze, L., Tuck, J., Torrellas, J., and Cascaval, C. Bulk disambiguation of speculative threads in multiprocessors. In Proceedings of the 33^rd International Symposium on Computer Architecture (Boston, MA, 2006). ACM, N Y, 227–238.

7. Damron, P., Fedorova, A., Lev, Y., Luchangco, V., Moir, M., and Nussbaum, D. Hybrid transactional memory. In Proceedings of the 12^th International Conference on Architectural Support for Programming Languages and Operating Systems (San Jose, CA, 2006). ACM, NY, 336–346.

8. Gray, J. and Reuter, A. Transaction Processing: Concepts and Techniques. Morgan Kaufmann Publishers, San Francisco, CA, 1992.

9. Grossman, D. The transactional memory / garbage collection analogy. In Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (Montreal, Canada, 2007). ACM, NY, 695–706.

10. Guerraoui, R., Herlihy, M., and Pochon, B. Polymorphic contention management. In Proceedings of the 19th International Symposium on Distributed Computing (Krakow, Poland, 2005). Springer Verlag, 303–323.

11. Harris, T., Marlow, S., Peyton-Jones, S., and Herlihy, M. Composable memory transactions. In Proceedings of the 10^th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Chicago, IL, 2005), ACM, NY, 48– 60.

12. Harris, T., Plesko, M., Shinnar, A., and Tarditi, D. Optimizing memory transactions. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation (Ottawa, Ontario, Canada, 2006). ACM, NY, 14– 25.

13. Herlihy, M. and Moss, J.E.B. Transactional memory: Architectural support for lock-free data structures. In Proceedings of the 20^th International Symposium on Computer Architecture. ACM, 1993, 289–300.

14. Herlihy, M., Luchangco, V., Moir, M., and Scherer III, W.N. Software transactional memory for dynamic-sized data structures. In Proceedings of the 22^nd Annual Symposium on Principles of Distributed Computing (Boston, MA, 2003), 92– 101

15. Isard, M., and Birrell, A. Automatic mutual exclusion. In Proceeding of the Usenix 11^th Workshop on Hot Topics in Operating Systems (San Diego, CA, 2007).

16. Knight, T.F. An architecture for mostly functional languages. In Proceedings of the 1986 ACM Lisp and Functional Programming Conference. ACM, NY.

17. Kumar, S., Chu, M., Hughes, C.J., Kundu, P., and Nguyen, A. Hybrid transactional memory. In Proceedings of the 11^th ACM SIGPLAN Symposium on

Principles and Practice of Parallel Programming. ACM, NY, 2006, 209–220.

18. Larus, J.R. and Rajwar, R. Transactional Memory. Morgan & Claypool, 2006.

19. Lomet, D.B. Process structuring, synchronization, and recovery using atomic actions. In Proceedings of the ACM Conference on Language Design for Reliable Software (Raleigh, NC, 1977). ACM, NY, 128–137.

20. McDonald, A., Chung, J., Brian, D. C., Minh, C. C., Chafi, H., Kozyrakis, C., and Olukotun, K. Architectural semantics for practical transactional memory. In Proceedings of the 33^rd International Symposium on Computer Architecture. ACM, 2006, 53– 65.

21. McDonald, A., Chung, J., Chafi, H., Cao Minh, C., Carlstrom, B.D., Hammond, L., Kozyrakis, C., and Olukotun, K. Characterization of TCC on chip-multiprocessors. In Proceedings of the 14^th International Conference on Parallel Architectures and Compilation Techniques. (St Louis, MO, 2005). IEEE, 63– 74.

22. Minh, C. C., Trautmann, M., Chung, J., McDonald, A., Bronson, N., Casper, J., Kozyrakis, C., and Olukotun, K. An effective hybrid transactional memory system with strong isolation guarantees. In Proceedings of the 34^th International Symposium on Computer Architecture (San Diego, CA, 2007) ACM, N Y, 69– 80.

23. Moore, K.E., Bobba, J., Moravan, M.J., Hill, M.D., and Wood, D. A. Log TM: Log-based transactional memory. In Proceedings of the 12^th International Symposium on High-Performance Computer Architecture (Austin, Tx, 2006). IEEE, 254–265.

24. Moravan, M.J., Bobba, J., Moore, K.E., Yen, L., Hill, M.D., Liblit, B., Swift, M.M., and Wood, D.A. Supporting Nested Transactional Memory in Log TM. Proceedings of the 12^th International Conference on Architectural Support for Programming Languages and Operating Systems (San Jose, CA, 2006). ACM, NY, 359–370.

25. Rajwar, R., Herlihy, M., and Lai, K. Virtualizing transactional memory. In Proceedings of the 32^nd International Symposium on Computer Architecture (Madison, WI, 2005). ACM. NY, 494–505.

26. Saha, B., Adl-Tabatabai, A. R., and Jacobson, Q. Architectural support for software transactional memory. In Proceedings of the 39^th International Symposium on Microarchitecture (Orlando, FL, 2006). IEEE, 185–196.

27. Saha, B., Adl- Tabatabai, A. R., Hudson, R. L., Minh, C.C., and Hertzberg, B. McRT-STM: A high performance software transactional memory system for a multi-core runtime. In Proceedings of the 11^th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (2006). ACM, NY, 187–197.

28. Scherer III, W.N., and Scott, M.L. Advanced contention management for dynamic software transactional memory. In Proceedings of the Twenty-fourth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (Las Vegas, NV, 2005). ACM Press, 240–248.

29. Shavit, N. and Touitou, D. Software transactional memory. In Proceedings of the 14^th ACM Symposium on Principles of Distributed Computing (Ottawa, Canada, 1995). ACM, NY, 204–213.

30. Shpeisman, T., Menon, V., Adl- Tabatabai, A.-R., Balensiefer, S., Grossman, D., Hudson, R.L., Moore, K.F., and Saha, B. Enforcing isolation and ordering in S TM. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation (San Diego, CA, 2007). ACM, NY, 78–88.

31. Shriraman, A., Spear, M.F., Hossain, H., Marathe, V.J., Dwarkadas, S., and Scott, M.L. An integrated hardware-software approach to flexible transactional memory. In Proceedings of the 34^th International Symposium on Computer Architecture (San Diego, CA, 2007). ACM, NY, 104–115.

32. Zilles, C. and Baugh, L. Extending hardware transactional memory to support nonbusy waiting and nontransactional actions. In Proceedings of the First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (Ottawa, Canada, 2006). ACM, N Y.

 

James Larus ( [e-mail]) is a research area manager at Microsoft Research, Redmond, WA.

Christos Kozyrakis ( christosee.stanford.edu) is an assistant professor of electrical engineering and computer science at Stanford University, Stanford, CA.