Why STM can be more than a research toy

Abstract

Despite earlier claims, Software Transactional Memory outperforms sequential code.

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, June 10--16). ACM Press, New York, 2006, 26--37.
2. Cao Minh, C., Chung, J., Kozyrakis, C., and Olukotun, K. STAMP: Stanford Transactional Applications for Multiprocessing. In Proceedings of the 2008 IEEE International Symposium on Workload Characterization (Seattle, Sept. 14--16). IEEE Computer Society, Washington, D.C., 2008, 35--46.
3. Cascaval, C., Blundell, C., Michael, M.M., Cain, H.W., Wu, P., Chiras, S., and Chatterjee, S. Software transactional memory: Why is it only a research toy? Commun. ACM 51, 11 (Nov. 2008), 40--46.
4. Dice, D., Lev, Y., Moir, M., and Nussbaum, D. Early experience with a commercial hardware transactional memory implementation. In Proceedings of the 14th International Conference on Architectural Support for Programming Languages and Operating Systems (Washington, D.C., Mar. 7--11). ACM Press, New York, 2009, 157--168.
5. Dice, D., Shalev, O., and Shavit, N. Transactional locking II. In Proceedings of the 20th International Symposium on Distributed Computing (Stockholm, Sept. 18--20). Springer-Verlag, Berlin, 2006, 194--208.
6. Dragojevik, A., Felber, P., Gramoli, V., and Guerraoui, R. Why STM Can Be More Than a Research Toy. Technical Report LPD-REPORT-2009-003. EPFL, Lausanne, Switzerland, 2009.
7. Dragojevic, A., Guerraoui, R., and Kapalka, M. Stretching transactional memory. In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation (Dublin, 2009). ACM Press, New York, 2009, 155--165.
8. Dragojevik, A., Ni, Y., and Adl-Tabatabai, A.-R. Optimizing transactions for captured memory. In Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures (Calgary, Aug. 11--13). ACM Press, New York, 2009, 214--222.
9. Eddon, G. and Herlihy, M. Language support and compiler optimizations for STM and transactional boosting. In Proceedings of the Fourth International Conference on Distributed Computing and Internet Technology (Bangalore, Dec. 17--20). Springer-Verlag, Berlin, 2007, 209--224.
10. Ellen, F., Lev, Y., Luchangco, V., and Moir, M. Snzi: Scalable nonzero indicators. In Proceedings of the 26th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (Portland, OR, Aug. 12--15). ACM Press, New York, 2007, 13--22.
11. Felber, P., Gramoli, V., and Guerraoui, R. Elastic transactions. In Proceedings of the 23rd International Symposium on Distributed Computing (Elche/Elx, Spain, Sept. 23--25). Springer-Verlag, Berlin, 2009, 93--107.
12. Guerraoui, R., Kapalka, M., and Vitek, J. STMBench7: A benchmark for software transactional memory. In Proceedings of the Second ACM SIGOPS/EuroSys European Conference on Computer Systems (Lisbon, Mar. 21--23). ACM Press, New York, 2007, 315--324.
13. Harris, T. and Fraser, K. Language support for lightweight transactions. In Proceedings of the 18th Annual ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (Anaheim, CA, Oct. 26--30). ACM Press, New York, 2003, 388--402.
14. Harris, T., Plesko, M., Shinnar, A., and Tarditi, D. Optimizing memory transactions. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (Ottawa, June 10--16). ACM Press, New York, 2006, 14--25.
15. Herlihy, M., Luchangco, V., Moir, M., and Scherer III, W.N. Software transactional memory for dynamic-sized data structures. In Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (Boston, July 13--16). ACM Press, New York, 2003, 92--101.
16. Lev, Y., Luchangco, V., Marathe, V., Moir, M., Nussbaum, D., and Olszewski, M. Anatomy of a scalable software transactional memory. In Proceedings of the Fourth ACM SIGPLAN Workshop on Transactional Computing (Raleigh, NC, Feb. 15, 2009).
17. Marathe, V.J., Spear, M.F., and Scott, M.L. Scalable techniques for transparent privatization in software transactional memory. In Proceedings of the 37th International Conference on Parallel Processing (Portland, OR, Sept. 8--12). IEEE Computer Society, Washington, D.C., 2008, 67--74.
18. Ni, Y., Welc, A., Adl-Tabatabai, A.-R., Bach, M., Berkowits, S., Cownie, J., Geva, R., Kozhukow, S., Narayanaswamy, R., Olivier, J., Preis, S., Saha, B., Tal, A., and Tian, X. Design and implementation of transactional constructs for C/C++. In Proceedings of the 23rd Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (Nashville, Oct. 19--23). ACM Press, New York, 2008, 195--212.
19. Rajwar, R., Herlihy, M., and Lai, K. Virtualizing transactional memory. In Proceedings of the 32nd Annual International Symposium on Computer Architecture (Madison, WI, June 4--8). IEEE Computer Society, Washington, D.C., 2005, 494--505.
20. Riegel, T., Felber, P., and Fetzer, C. Dynamic performance tuning of word-based software transactional memory. In Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Salt Lake City, Feb. 20--23). ACM Press, New York, 2008, 237--246.
21. Riegel, T., Felber, P., and Fetzer, C. A lazy snapshot algorithm with eager validation. In Proceedings of the 20th International Symposium on Distributed Computing (Stockholm, Sept. 18--20). Springer-Verlag, Berlin, 2006, 284--298.
22. Riegel, T., Fetzer, C., and Felber, P. Automatic data partitioning in software transactional memories. In Proceedings of the 20th ACM Symposium on Parallelism in Algorithms and Architectures (Münich, June 14--16). ACM Press, New York, 2008, 152--159.
23. Shavit, N. and Touitou, D. Software transactional memory. In Proceedings of the 14th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (Ottawa, Aug. 20--23). ACM Press, New York, 1995, 204--213.
24. Spear, M.F., Marathe, V.J., Dalessandro, L., and Scott, M.L. Privatization techniques for software transactional memory. In Proceedings of the 26th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (Portland, OR, Aug. 12--15). ACM Press, New York, 2007, 338--339; extended version available as TR 915, Computer Science Department, University of Rochester, Feb. 2007.
25. Yoo, R.M., Ni, Y., Welc, A., Saha, B., Adl-Tabatabai, A.-R., and Lee, H.H.S. Kicking the tires of software transactional memory: Why the going gets tough. In Proceedings of the 20th ACM Symposium on Parallelism in Algorithms and Architectures (Münich, June 14--16). ACM Press, New York, 2008, 265--274.

Index Terms

• Hardware

• Information systems

  • Information storage systems

    • Storage management

• Software and its engineering

  • Software creation and management

    • Software development techniques

  • Software notations and tools

    • General programming languages

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • File systems management

        • Memory management

• Theory of computation