An Investigation into the Performance of Reduction Algorithms under Load Imbalance
An Investigation into the Performance of Reduction Algorithms under Load Imbalance
复制标题
负载不平衡下约简算法的性能研究
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
P. Schelkens
中科院分区：
文献类型：
--
作者：
P. Marendic;J. Lemeire;Tom Haber;D. Vucinic;P. Schelkens
如今，大多数缩减算法都针对平衡工作负载进行了优化。他们假设所有进程将大约在同一时间开始减少。然而，实际上情况并非总是如此，可能会出现严重的负载不平衡并影响所述算法的性能。在本文中，我们研究了这种不平衡对最常用的归约算法的影响，并提出了一种专门适合当前上下文的新算法。首先，我们分析乐观情况，即我们对所有不平衡有先验知识，并提出接近最优的解决方案。在一般情况下，我们对不平衡没有任何预知，我们提出了一种动态重新平衡的树缩减算法。我们通过实验证明该算法的性能优于默认的 OpenMPI 和 MAPICH2 实现。
Today, most reduction algorithms are optimized for balanced workloads; they assume all processes will start the reduction at about the same time. However, in practice this is not always the case and significant load imbalances may occur and affect the performance of said algorithms. In this paper we investigate the impact of such imbalances on the most commonly employed reduction algorithms and propose a new algorithm specifically adapted to the presented context. Firstly, we analyze the optimistic case where we have a priori knowledge of all imbalances and propose a near-optimal solution. In the general case, where we do not have any foreknowledge of the imbalances, we propose a dynamically rebalanced tree reduction algorithm. We show experimentally that this algorithm performs better than the default OpenMPI and MVAPICH2 implementations.