×

Nebelung: Execution environment for transactional openmp. (English) Zbl 1147.68438

Summary: Future generations of chip multiprocessors will provide dozens or even hundreds of cores inside the chip. Writing applications that benefit from the massive computational power offered by these chips is not going to be an easy task for mainstream programmers who are used to sequential algorithms rather than parallel ones. This paper explores the possibility of using Transactional Memory (TM) in OpenMP, the industrial standard for writing parallel programs on shared-memory architectures, for C, C++ and Fortran. One of the major complexities in writing OpenMP applications is the use of critical regions (locks), atomic regions and barriers to synchronize the execution of parallel activities in threads. TM has been proposed as a mechanism that abstracts some of the complexities associated with concurrent access to shared data while enabling scalable performance. The paper presents a first proof-of-concept implementation of OpenMP with TM. Some language extensions to OpenMP are proposed to express transactions. These extensions are implemented in our source-to-source OpenMP Mercurium compiler and our Software Transactional Memory (STM) runtime system Nebelung that supports the code generated by Mercurium. Hardware transactional memory or hardware-assisted STM are seen as possible paths to make the tandem TM-OpenMP more scalable. In the evaluation section we show the preliminary results. The paper finishes with a set of open issues that still need to be addressed, either in OpenMP or in the hardware/software implementations of TM.

MSC:

68N20 Theory of compilers and interpreters

Software:

Nebelung; Fortress
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Larus, J., Rajwar, R.: Transactional Memory. Morgan Claypool (2006)
[2] OpenMP Architecture Review Board, OpenMP Application Program Interface, May 2005
[3] Harris, T., Plesko, M., Shinnar, A., Tarditi, D.: Optimizing memory transactions. In: PLDI ’06: ACM SIGPLAN 2006 Conference on Programming Language Design and Implementation, June 2006
[4] Allen, E., Chase, D., Luchangco, V., Maessen, J.-W., Ryu, S., Steele, Jr. G.L., Tobin-Hochstadt, S.: The Fortress Language Specification. Sun Microsystems (2005)
[5] Charles, P., Grothoff, C., Saraswat, V., Donawa, C., Kielstra, A., Ebcioglu, K., von Praun, C., Sarkar, V.: X10: an object-oriented approach to non-uniform cluster computing. In: Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-oriented Programming Systems Languages and Applications (OOPSLA), pp. 519–538. New York, USA (2005)
[6] Cray. Chapel Specification, February 2005
[7] Shavit, N., Touitou, D.: Software Transactional Memory. In: Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing, pp. 204–213 (1995) · Zbl 1373.68178
[8] Herlihy, M., Eliot, J., Moss, B.: Transactional memory: architectural support for lock-free data structures. In: Proceedings of the 20th International Symposium on Computer Architecture (ISCA’93), pp. 289–300, May 1993
[9] Damron, P., Fedorova, A., Lev, Y., Luchangco, V., Moir, M., Nussbaum, D.: Hybid transactional memory. In: Proceedings of the Twelfth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), October 2006
[10] Kumar, S., Chu, M., Hughes, C.J., Kundu, P., Nguyen, A.: Hybrid transactional memory. In: The Proceedings of ACM Symposium on Principles and Practice of Parallel Programming, March 2006
[11] Saha, B., Adl-Tabatabai, A., Jacobson, Q.: Architectural support for software transactional memory. In: 39th International Symposium on Microarchitecture (MICRO) (2006)
[12] Shriraman, A., Marathe, V.J., Dwarkadas, S., Scott, M.L., Eisenstat, D., Heriot, C., Scherer, III. W.N., Spear, M.F.: Hardware acceleration of Software Transactional Memory. TRANSACT (2006)
[13] Balart, J., Duran, A., Gonzàlez, M., Martorell, X., Ayguadé, E., Labarta, J.: Nanos Mercurium: a research compiler for OpenMP. European Workshop on OpenMP (EWOMP’04). pp. 103–109. Stockholm, Sweden, October 2004
[14] Martorell, X., Ayguadé, E., Navarro, N., Corbalan, J., Gonzalez, M., Labarta, J.: Thread Fork/join Techniques for Multi-level Parallelism Exploitation in NUMA Multiprocessors. 13th International Conference on Supercomputing (ICS’99), Rhodes (Greece), June 1999
[15] Milovanoviæ, M., Unsal, O.S., Cristal, A., Stipiæ, S., Zyulkyarov, F., Valero, M.: Compile time support for using transactional memory in C/C++ applications. In: 11th Annual Workshop on the Interaction between Compilers and Computer Architecture INTERACT-11 in conjunction with HPCA-13, Phoenix, Arizona, February 2007
[16] Milovanoviæ, M., Ferrer, R., Gajinov, V., Unsal, O.S., Cristal, A., Ayguadé, E., Valero, M.: Multithreaded software transactional memory and OpenMP. In: Proceedings Of 8th MEDEA Workshop in Conjunction with the PACT 2007, Romania, September 2007 · Zbl 1147.68438
[17] McDonald, A., Chung, J., Carlstrom, B., Minh, C., Chafi, H., Kozyrakis, C., Olukotun, K.: Architectural semantics for practical transactional memory. In: Proceedings 33th Annual International Symposium on Computer Architecture, pp. 53–65 (2006) · Zbl 1119.68041
[18] Gauss-Seidel finite difference method for solving the linear system of equations. Online material available at: http://www-unix.mcs.anl.gov/dbpp/text/node17.html#SECTION02330000000000000000 , 27 August 2007
[19] Blundell, C., Lewis, C., Martin, M.M.K.: Subtleties of transactional memory atomicity Semantics. IEEE Computer Architecture Letters 5(2) (2006)
[20] Baek, W., Minh, C.-C., Trautmann, M., Kozyrakis, C., Olukotun, K.: The OpenTM transactional application programming interface. In: Proceedings 16th International Conference on Parallel Architectures and Compilation Techniques (PACT’07), Romania, September 2007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.