OpenMP tasks in IBM XL compilers

ABSTRACT

Tasking is the most significant feature included in the new OpenMP 3.0 standard. It was introduced to handle unstructured parallelism and broaden the range of applications that can be parallelized by OpenMP. This paper presents the design and implementation of the task model in the IBM XL parallelizing compilers. The task construct is significantly different from other OpenMP constructs. This paper discusses some of the unique challenges in implementing the task construct and its associated synchronization constructs in the compiler. We also present a performance evaluation of our implementation on a set of benchmarks and applications. We identify limitations in the current implentation and propose solutions for further improvement.

REFERENCES

• 1: S. G. Akl , N. Santoro, Optimal parallel merging and sorting without memory conflicts, IEEE Transactions on Computers, v.36 n.11, p.1367-1369, Nov. 1987 [doi>10.1109/TC.1987.5009478]
• 2: Architecture Review Board. OpenMP Fortran Application Program Interface v 1.0, October 1997.
• 3: Eduard Ayguadé , Nawal Copty , Alejandro Duran , Jay Hoeflinger , Yuan Lin , Federico Massaioli , Ernesto Su , Priya Unnikrishnan , Guansong Zhang, A Proposal for Task Parallelism in OpenMP, Proceedings of the 3rd international workshop on OpenMP: A Practical Programming Model for the Multi-Core Era, p.1-12, June 03-07, 2007, Beijing, China [doi>10.1007/978-3-540-69303-1_1]
• 4: E. Ayguadé, A. Duran, J. Hoeflinger, F. Massaioli, and X. Teruel. An experimental evaluation of the new openmp tasking model. In Proceedings of the 20th International Workshop on Languages and Compilers for Parallel Computing (LCPC), October 2007.
• 5: J. Balart, A. Duran, M. González, X. Martorell, E. Ayguadé, and J. Labarta. Nanos Mercurium: a Research Compiler for OpenMP. In 6th European Workshop on OpenMP (EWOMP'04), Stockholm, Sweden, October 2004.
• 6: Pieter Bellens , Josep M. Perez , Rosa M. Badia , Jesus Labarta, CellSs: a programming model for the cell BE architecture, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188546]
• 7: A. Bik, M. Girkar, P. Grey, and X. Tian. Efficient exploitation of parallelism on Pentium III and Pentium 4 processor-based systems. In Intel Technology Journal Q1, pages 1--9, March 2001.
• 8: Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.207-216, July 19-21, 1995, Santa Barbara, California, United States
• 9: Architecture Review Board. OpenMP Application Program Interface v 3.0, May 2008.
• 10: Jyh-Herng Chow , Leonard E. Lyon , Vivek Sarkar, Automatic parallelization for symmetric shared-memory multiprocessors, Proceedings of the 1996 conference of the Centre for Advanced Studies on Collaborative research, p.5, November 12-14, 1996, Toronto, Ontario, Canada
• 11: A. Duran, J. Corbalan, and E. Ayguadé. Evaluation of openmp task scheduling strategies. In IWOMP '08: International Workshop on OpenMP (IWOMP), pages 100--110, May 2008.
• 12: A. Duran, J. M. Perez, E. Ayguadé, R. M. Badia, and J. Labarta. Extending the openmp tasking model to allow dependent tasks. In IWOMP '08: International Workshop on OpenMP (IWOMP), pages 111--122, May 2008.
• 13: X. Martorell, J. Labarta, N. Navarro, and E. Ayguadé. Nano-Threads Library Design, Implementation and Evaluation. Technical Report UPC-DAC-1995-33, DAC/UPC, September 1995.
• 14: Robert Sedgewick, Implementing Quicksort programs, Communications of the ACM, v.21 n.10, p.847-857, Oct. 1978 [doi>10.1145/359619.359631]
• 15: S. Shah, G. Haab, P. Petersen, and J. Throop. Flexible control structures for parallelism in openmp. Concurrency - Practice and Experience, 12(12):1219--1239, 2000.
• 16: T. F. Smith and M. S. Waterman. Identification of common molecular subsequences. Journal of Molecular Biology, 147:195--197, 1981.
• 17: Xavier Teruel , Xavier Martorell , Alejandro Duran , Roger Ferrer , Eduard Ayguadé, Support for OpenMP tasks in Nanos v4, Proceedings of the 2007 conference of the center for advanced studies on Collaborative research, October 22-25, 2007, Richmond Hill, Ontario, Canada [doi>10.1145/1321211.1321241]
• 18: X. Tian, A. Bik, M. Girkar, P. Grey, H. Saito, and E. Su. Intel OpenMP C++/Fortran compiler for hyper-threading technology: Implementation and performance. In Intel Technology Journal 6, pages 36--46, 2002.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Design, Experimentation, Performance