appropriate programming model for STM. STM-ME is likely too tedious and error-prone for use in most applications and might instead be appropriate only for smaller applications or performance-critical sections of code. Clearly, an STM compiler is crucial for usability, yet transparent privatization support might not be absolutely needed from STM. It seems that programmers make a conscious decision to privatize a piece of data, rather than let the data be privatized by accident. This might imply that, for the programmer, explicitly marking privatizing transactions would not require much additional effort. Apart from semantic issues, our experiments show that STM-CE offers good performance while scaling well.c

 

Conclusion

We reported on the most exhaustive evaluation to date of the ability of an STM to outperform sequential code, showing it can deliver good performance across a range of workloads and multicore architectures. Though we do not claim STM is a silver bullet for general-purpose concurrent programming, our results contradict Cascaval et al. 3 and suggest STM is usable for a range of applications. They also support the initial hopes about STM performance and should motivate further research in the field.

Many improvements promise to boost STM performance further, making it even more appealing; for example, static segregation of memory locations, depending on whether or not the locations are shared, can minimize compiler instrumentation overhead, partially visible reads can improve privatization performance, and reduction of accesses to shared data can enhance scalability.

 

acknowledgments

We are grateful to Tim Harris for running the Bartok-STM experiments, to Calin Cascaval for providing us with the experimental settings of Cascaval et al., 3 and to Yang Ni for running experi- c Because the experiments reported in Cascaval et al. 3 were conducted with STM variants not supporting transparent privatization, our observation about the programming model does not alter the performance comparisons covered earlier in the article.

ments with McRT-STM, confirming our speculation about the effect of hyper-threading. We also thank Hillel Avni, Derin Harmanci, Michał Kapałka, Patrick Marlier, Maged Michael, and Mark Moir for their comments. This work was funded by the Velox FP7 European Project and the Swiss National Science Foundation grant 200021-116745/1.

 

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. dragojević, a., Felber, P., Gramoli, V., and Guerraoui, r. Why S TM Can Be More Than a Research Toy. Technical Report LPD-REPORT-2009-003. ePFl, lausanne, switzerland, 2009.

7. dragojević, 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. dragojević, 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.

 

Aleksandar Dragojević (aleksandar.dragojevic@epfl. ch) is a Ph.d. student in the distributed Programming laboratory of the École Polytechnique Fédérale de lausanne, lausanne, switzerland.

Pascal Felber ( [e-mail]) is a professor in the computer science department of the université de neuchâtel, neuchâtel, switzerland.

Vincent Gramoli ( [e-mail]) is a postdoctoral researcher in the distributed computing laboratory in the École Polytechnique Fédérale de lausanne, lausanne, switzerland, and a postdoctoral researcher in the computer science department of the université de neuchâtel, neuchâtel, switzerland.

Rachid Guerraoui ( [e-mail]) is a professor in the distributed Programming laboratory in the École Polytechnique Fédérale de lausanne, lausanne, switzerland.

© 2011 acM 0001-0782/11/04 $10.00