Abstract
OpenMP is in the process of adding a tasking model that allows the programmer to specify independent units of work, called tasks, but does not specify how the scheduling of these tasks should be done (although it imposes some restrictions). We have evaluated different scheduling strategies (schedulers and cut-offs) with several applications and we found that work-first schedules seem to have the best performance but because of the restrictions that OpenMP imposes a breadth-first scheduler is a better choice to have as a default for an OpenMP runtime.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Acar, U.A., Blelloch, G.E., Blumofe, R.D.: The data locality of work stealing. In: SPAA 2000: Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, pp. 1–12. ACM, New York (2000)
Ayguadé, E., Copty, N., Duran, A., Hoeflinger, J., Lin, Y., Massaioli, F., Su, E., Unnikrishnan, P., Zhang, G.: A proposal for task parallelism in OpenMP. In: Proceedings of the 3rd International Workshop on OpenMP, Beijing, China (June 2007)
Ayguadé, E., Duran, A., Hoeflinger, J., Massaioli, F., Teruel, X.: An Experimental Evaluation of the New OpenMP Tasking Model. In: Proceedings of the 20th International Workshop on Languages and Compilers for Parallel Computing (October 2007)
Balart, J., Duran, A., Gonzàlez, M., Martorell, X., Ayguadé, E., Labarta, J.: Nanos Mercurium: a Research Compiler for OpenMP. In: Proceedings of the European Workshop on OpenMP 2004 (October 2004)
Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex fourier series. Mathematics of Computation 19, 297–301 (1965)
Fischer, P.C., Probert, R.L.: Efficient procedures for using matrix algorithms. In: Proceedings of the 2nd Colloquium on Automata, Languages and Programming, London, UK, pp. 413–427. Springer, Heidelberg (1974)
Frigo, M., Leiserson, C.E., Randall, K.H.: The implementation of the Cilk-5 multithreaded language. In: PLDI 1998: Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, pp. 212–223. ACM Press, New York (1998)
Huelsbergen, L., Larus, J.R., Aiken, A.: Using the run-time sizes of data structures to guide parallel-thread creation. In: LFP 1994: Proceedings of the 1994 ACM conference on LISP and functional programming, pp. 79–90. ACM, New York (1994)
Korch, M., Rauber, T.: A comparison of task pools for dynamic load balancing of irregular algorithms: Research articles. Concurr. Comput. Pract. Exper. 16(1), 1–47 (2004)
Loidl, H.-W., Hammond, K.: On the Granularity of Divide-and-Conquer Parallelism. In: Glasgow Workshop on Functional Programming, Ullapool, Scotland, July 8–10, 1995, Springer, Heidelberg (1995)
Mohr, J. E., Kranz, D.A., Halstead, R.H.: Lazy task creation: a technique for increasing the granularity of parallel programs. In: LFP 1990: Proceedings of the 1990 ACM conference on LISP and functional programming, pp. 185–197. ACM, New York (1990)
Narlikar, G.J.: Scheduling threads for low space requirement and good locality. In: SPAA 1999: Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, pp. 83–95. ACM, New York (1999)
OpenMP Architecture Review Board. OpenMP Application Program Interface, Version 3.0 (Draft) (October 2007)
Shah, S., Haab, G., Petersen, P., Throop, J.: Flexible control structures for parallellism in OpenMP. In: 1st European Workshop on OpenMP (September 1999)
Teruel, X., Martorell, X., Duran, A., Ferrer, R., Ayguadé, E.: Support for OpenMP tasks in Nanos v4. In: CAS Conference 2007 (October 2007)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Duran, A., Corbalán, J., Ayguadé, E. (2008). Evaluation of OpenMP Task Scheduling Strategies. In: Eigenmann, R., de Supinski, B.R. (eds) OpenMP in a New Era of Parallelism. IWOMP 2008. Lecture Notes in Computer Science, vol 5004. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-79561-2_9
Download citation
DOI: https://doi.org/10.1007/978-3-540-79561-2_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-79560-5
Online ISBN: 978-3-540-79561-2
eBook Packages: Computer ScienceComputer Science (R0)