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. 30 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 34th 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 12th 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 33rd
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 12th 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 10th 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 20th 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 22nd
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 11th 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 11th 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 33rd 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 14th
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 34th
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 12th 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 12th 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 32nd
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 39th 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 11th 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 14th 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 34th 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 ( larus@microsoft.com) 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.