A Divide-and-conquer Parallel Skeleton for Unbalanced and Deep Problems

TítuloA Divide-and-conquer Parallel Skeleton for Unbalanced and Deep Problems
AutoresMillán A. Martı́nez, Basilio B. Fraguela and José C. Cabaleiro
TipoComunicación para congreso
Fonte 13th International Symposium on High-Level Parallel Programming and Applications, Porto (Portugal), pp. 76-95 , 2020.
AbstractThe Divide-and-conquer (D&C) pattern appears in a large number of problems and is highly suitable to exploit parallelism. This has led to much research on its easy and efficient application both in shared and distributed memory parallel systems. One of the most successful approaches explored in this area consists in expressing this pattern by means of parallel skeletons which automate and hide the complexity of the parallelization from the user while trying to provide good performance. In this paper we tackle the development of a skeleton oriented to the efficient parallel resolution of D&C problems with a high degree of unbalance among the subproblems generated and/or a deep level of recurrence. Our evaluation shows good results achieved both in terms of performance and programmability.
Palabras chaveAlgorithmic skeletons, Divide-and-conquer, Template metaprogramming, Load balancing