Communications - August 2008

Investigating the complex trade-offs in this design space is the subject of current research. ¹^{, 16}

Whether or not one believes in transactions, it does seem likely that some combination of effect systems and/or ownership types will play an increasingly important role in concurrent programming languages, and these may contribute to the guarantees desirable for memory transactions.

Our main claim is that transactional memory qualitatively raises the level of abstraction offered to programmers. Just as high-level languages free programmers from worrying about register allocation, so transactional memory frees the programmer from concerns about locks and lock acquisition order in designing shared-memory data structures. More fundamentally, one can combine such abstractions without knowing their implementations, a property that is the key to constructing large programs.

References

1. Abadi, M., Birrell, A., Harris, T., and Isard, M. Semantics of transactional memory and automatic mutual exclusion. POPL’08: Proceedings of the 35th ACM SIGPLAn-SIGACT Symposium on Principles of Programming Languages, pp. 63–74, ACM, Jan. 2008.

2. Blelloch, G.E., Hardwick, J.C., Sipelstein, J., Zagha, M., and Chatterjee, S. Implementation of a portable nested data-parallel language. J. Parallel Distrib. Comput., 21 ( 1): 4–14, 1994.

3. Carlstrom, B.D., McDonald, A., Chafi, H., Chung, J., Minh, C. C., Kozyrakis, C., and Olukotun, K. The Atomos transactional programming language. PLDI’06: Proceedings of the 2006 ACM SIGPLAn Conference on Programming Language Design and Implementation, pp. 1–13, ACM, June 2006.

4. Chung, J., Minh, C. C., McDonald,

A., Skare, T., Chafi, H., Carlstrom,

B. D., Kozyrakis, C., and Olukotun,

K. Tradeoffs in transactional memory virtualization. ASPLOS’06: Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 371–381, ACM, Oct. 2006.

5. Damron, P., Fedorova, A., Lev,

Y., Luchangco, V., Moir, M., and Nussbaum, D. Hybrid transactional memory. ASPLOS’06: Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 336–346, ACM, Oct. 2006.

6. Daume III, H. Yet another Haskell tutorial. http://www.cs.utah.edu/~hal/

docs/daume02yaht.pdf, 2006.

7. Gray, J., and Reuter, A. Transaction Processing: Concepts and Techniques. Morgan Kaufmann Publishers, Inc., 1992.

8. Harris, T., and Fraser, K. Language support for lightweight transactions. OOPSLA’03: Proceedings of the 18th ACM SIGPLAn Conference on Object-Oriented Programming, Systems, Languages, and Applications, pp. 388–402, ACM, Oct. 2003.

9. Harris, T., Marlow, S., Peyton Jones, S., and Herlihy, M. Composable memory transactions. PPoPP’05: Proceedings of the 10th ACM SIGPLAn Symposium on Principles and Practice of Parallel Programming, pp. 48–60, ACM, June 2005.

10. Harris, T., and Peyton Jones,

S. Transactional memory with data invariants. TRAnSACT’06: Proceedings of the 1st ACM SIGPLAn Workshop on Languages, Compilers, and Hardware Support for Transactional Computing, June 2006.

11. Herlihy, M., Luchangco, V., Moir, M., and Scherer, III, W.N. Software transactional memory for dynamic-sized data structures. PODC’03: Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing, pp. 92–101, ACM, July 2003.

12. Herlihy, M. and Moss, J.E. B. Transactional memory: Architectural support for lock-free data structures. ISCA’93: Proceedings of the 20th International Symposium on Computer Architecture, pp. 289–300, ACM, May 1993.

13. Kumar, S., Chu, M., J. Hughes, C., Kundu, P., and Nguyen, A. Hybrid transactional memory. PPoPP’06: Proceedings of the 11th ACM

Like high-level languages, transactional memory does not banish bugs altogether; for example, two threads can easily deadlock if each awaits some communication from the other. But the gain is very substantial: transactions provide a programming platform for concurrency that eliminates whole classes of concurrency errors, and allows the programmer to concentrate on the really interesting bits.

acknowledgments

We would like to thank Byron Cook, Austin Donnelly, Matthew Flatt, Jim Gray, Dan Grossman, Andres Löh, Jon Howell, Jan-Willem Maessen, Jayadev Misra, Norman Ramsey, Michael Ringenburg, David Tarditi, and especially Tony Hoare, for their helpful feedback on earlier versions of this paper, and Guy Steele for his meticulous suggestions in preparing this revised version.

SIGPLAn Symposium on Principles and Practice of Parallel Programming, pp. 209–220, ACM, Mar 2006.

14. Larus, J., and Rajwar, R. Transactional Memory (Synthesis Lectures on Computer Architecture). Morgan & Claypool Publishers, 2007.

15. Martin, M., Blundell, C., and Lewis, E. Subtleties of transactional memory atomicity semantics. IEEE Comput. Archit. Lett. 5( 2): 17, 2006.

16. Moore, K.F. and Grossman, D. High-level small-step operational semantics for transactions. POPL’08: Proceedings of the 35th ACM SIGPLAn-SIGACT Symposium on Principles of Programming Languages, pp. 51–62, ACM, Jan. 2008.

17. Moss, E.B. Nested transactions: An approach to reliable distributed computing. Tech. Rep. MIT/LCS/ TR-260, Massachusetts Institute of Technology, Apr. 1981.

18. Peyton Jones, S. Tackling the awkward squad: Monadic input/ output, concurrency, exceptions, and foreign-language calls in Haskell. Engineering Theories of Software Construction, Marktoberdorf Summer School 2000.

19. Peyton Jones, S. Beautiful concurrency. In Beautiful Code (2007), A. Oran and G. Wilson, Eds., O’Reilly.

Tim harris ( tharris@microsoft.com) Microsoft Research

Simon Marlow (simonmar@microsoft. com) Microsoft Research

20. Peyton Jones, S., Gordon, A., and Finne, S. Concurrent Haskell. POPL’96: Proceedings of the 23rd ACM SIGPLAn-SIGACT Symposium on Principles of Programming Languages, pp. 295–308, ACM, Jan. 1996.

21. Peyton Jones, S. and Wadler, P. Imperative functional programming. POPL’93: Proceedings of the 20th ACM SIGPLAn-SIGACT Symposium on Principles of Programming Languages, pp. 71–84, ACM, Jan. 1993.

22. Rajwar, R., Herlihy, M., and Lai, K. Virtualizing transactional memory. ISCA’05: Proceedings of the 32nd International Symposium on Computer Architecture, pp. 494–505, IEEE Computer Society, June 2005.

23. Shavit, N., and Touitou, D. Software transactional memory. PODC’95: Proceedings of the 14th ACM Symposium on Principles of Distributed Computing, pp. 204–213, ACM, Aug. 1995.

24. Stone, J. M., Stone, H.S., Heidelberger, P., and Turek, J. Multiple reservations and the Oklahoma update. IEEE Parallel and Distributed Technology 1( 4): 58–71, 1993.