Multithreaded software transactional memory and OpenMP

ABSTRACT

Transactional Memory (TM) is a key future technology for emerging many-cores. On the other hand, OpenMP provides a vast established base for writing parallel programs, especially for scientific applications. Combining TM with OpenMP provides a rich, enhanced programming environment and an attractive solution to the many-core software productivity problem.

In this paper, we discuss the first multithreaded runtime environment for supporting our combined TM and OpenMP framework. We present the extensions of OpenMP for using Transactional Memory. We then present the novel multithreaded STM design with a dedicated thread for eager asynchronous conflict detection. Conflict detection will be executed in a separate thread so the transaction will not waste time on that. On the other hand, eager conflict detection is asynchronous which will increase speculative parallel execution. We also include an initial performance analysis of the runtime system and possible gains which can be achieved.

REFERENCES

• 1: J. Larus and R. Rajwar, "Transactional Memory", Morgan Claypool, 2006.
• 2: OpenMP Architecture Review Board, OpenMP Application Program Interface, May 2005.
• 3: Tim Harris , Mark Plesko , Avraham Shinnar , David Tarditi, Optimizing memory transactions, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 4: E. Allen, D. Chase, V. Luchangco, J.-W. Maessen, S. Ryu, G. L. Steele Jr. and S. Tobin-Hochstadt. The Fortress Language Specification. Sun Microsystems, 2005.
• 5: Philippe Charles , Christian Grothoff , Vijay Saraswat , Christopher Donawa , Allan Kielstra , Kemal Ebcioglu , Christoph von Praun , Vivek Sarkar, X10: an object-oriented approach to non-uniform cluster computing, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 6: Cray. Chapel Specification. February 2005.
• 7: Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224987]
• 8: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 9: Peter Damron , Alexandra Fedorova , Yossi Lev , Victor Luchangco , Mark Moir , Daniel Nussbaum, Hybrid transactional memory, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 10: Sanjeev Kumar , Michael Chu , Christopher J. Hughes , Partha Kundu , Anthony Nguyen, Hybrid transactional memory, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1123003]
• 11: Bratin Saha , Ali-Reza Adl-Tabatabai , Quinn Jacobson, Architectural Support for Software Transactional Memory, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.185-196, December 09-13, 2006 [doi>10.1109/MICRO.2006.9]
• 12: A. Shriraman, V. J. Marathe, S. Dwarkadas, M. L. Scott, D. Eisenstat, C. Heriot, W. N. Scherer III, and M. F. Spear. "Hardware Acceleration of Software Transactional Memory", TRANSACT 2006.
• 13: J. Balart, A. Duran, M. Gonzàlez, X. Martorell, E. Ayguadé and J. Labarta. "Nanos Mercurium: A Research Compiler for OpenMP". European Workshop on OpenMP (EWOMP'04). Pp. 103--109. Stockholm, Sweden. October 2004
• 14: Xavier Martorell , Eduard Ayguadé , Nacho Navarro , Julita Corbalán , Marc González , Jesús Labarta, Thread fork/join techniques for multi-level parallelism exploitation in NUMA multiprocessors, Proceedings of the 13th international conference on Supercomputing, p.294-301, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305206]
• 15: M. Milovanović, O. S. Unsal, A. Cristal, S. Stipić, F. Zyulkyarov and M. Valero, "Compile time support for using Transactional Memory in C/C++ applications", 11th Annual Workshop on the Interaction between Compilers and Computer Architecture INTERACT-11, Phoenix, Arizona, February 2007.
• 16: Austen McDonald , JaeWoong Chung , Brian D. Carlstrom , Chi Cao Minh , Hassan Chafi , Christos Kozyrakis , Kunle Olukotun, Architectural Semantics for Practical Transactional Memory, Proceedings of the 33rd annual international symposium on Computer Architecture, p.53-65, June 17-21, 2006
• 17: Woongki Baek , Chi Cao Minh , Martin Trautmann , Christos Kozyrakis , Kunle Olukotun, The OpenTM Transactional Application Programming Interface, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.376-387, September 15-19, 2007 [doi>10.1109/PACT.2007.74]
• 18: M. Milovanović, R. Ferrer, O. Unsal, A. Cristal, E. Ayguadé, J. Labarta and M. Valero, "Transactional Memory and OpenMP". In the Proceedings of the Intl. Workshop on OpenMP, Beijing/China, June 2007.
• 19: N. Sonmez, C. Perfumo, S. Stipic, A. Cristal, O. Unsal and M. Valero, "unreadTVar: Extending Haskell Software transactional Memory for Performance". In the Proceedings of the Eight Symposium on Trends in Functional Programming, New York/USA, April 2007.
• 20: Gauss-Seidel Finite Difference Method for solving the linear system of equations. Online material available at: http://wwwunix.mcs.anl.gov/dbpp/text/node17.html#SECTION02330000000000000000, August 27, 2007.
• 21: K. Fraser, Practical lock freedom. PhD thesis, University of Cambridge Computer Laboratory, 2003.

INDEX TERMS

Keywords:
OpenMP, runtime environment, transactional memory