RT Journal Article
T1 A Parallel Skeleton for Divide-and-conquer Unbalanced and Deep Problems
A1 Martínez, Millán A.
A1 Fraguela, Basilio B.
A1 Cabaleiro Domínguez, José Carlos
K1 Algorithmic skeletons
K1 Divide-and-conquer
K1 Template metaprogramming
K1 Load balancing
AB The 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 of 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 imbalance among the subproblems generated and/or a deep level of recurrence. The skeleton achieves in our experiments average speedups between 11 and 18% higher than those of other solutions, reaching a maximum speedup of 78% in some tests. Nevertheless, the new proposal requires an average of between 13 and 29% less programming effort than the usual alternatives.
PB Springer Nature
YR 2021
FD 2021-05-14
LK https://hdl.handle.net/10347/42119
UL https://hdl.handle.net/10347/42119
LA eng
NO Martínez, M.A., Fraguela, B.B. & Cabaleiro, J.C. A Parallel Skeleton for Divide-and-conquer Unbalanced and Deep Problems. Int J Parallel Prog 49, 820–845 (2021). https://doi.org/10.1007/s10766-021-00709-y
NO This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/s10766-021-00709-y
NO This research was supported by the Ministry of Science and Innovation of Spain (TIN2016-75845-P, PID2019-104184RB-I00 and PID2019-104834GB-I00, AEI/FEDER/EU, 10.13039/501100011033) and the predoctoral Grant of Millán Álvarez Ref. BES-2017-081320), and by the Xunta de Galicia co-founded by the European Regional Development Fund (ERDF) under the Consolidation Programme of Competitive Reference Groups (ED431C 2017/04 and ED431C 2018/19). We acknowledge also the support from the Centro Singular de Investigación de Galicia “CITIC” and the Centro Singular de Investigación en Tecnoloxías Intelixentes “CiTIUS”, funded by Xunta de Galicia and the European Union (European Regional Development Fund- Galicia 2014-2020 Program), by grants ED431G 2019/01 and ED431G 2019/04. We also acknowledge the Centro de Supercomputación de Galicia (CESGA) for the use of their computers.
DS Minerva
RD 29 abr 2026