Shape optimizing load balancing for MPI-parallel adaptive numerical simulations
Shape optimizing load balancing for MPI-parallel adaptive numerical simulations
复制标题
MPI 并行自适应数值模拟的形状优化负载平衡
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Henning Meyerhenke
中科院分区：
文献类型：
--
作者：
Henning Meyerhenke
负载平衡对于在并行计算机上高效地执行数值模拟是重要的。特别是当仿真域随时间变化时，需要相应地修改计算任务到处理器的映射。大多数解决这个问题的最先进的库是基于图重新分区与Kernighan-Lin（KL）启发式的并行变体。KL方法有许多缺点，包括优化的度量和具有不期望的属性的解决方案。在这里，我们进一步探讨了有前途的基于扩散的多级图划分算法DibaP。我们描述了算法的演变，并报告其MPI实现PDibaP与分布式内存的并行性。PDibaP的目标是几十个处理器的中小规模并行。所呈现的实验使用模仿自适应数值模拟的图形序列。他们证明了PDibaP通过在这种规模上重新分区来实现负载平衡的适用性和质量。与更快的ParMETIS相比，PDibaP的解决方案通常具有更少的外部边缘和更小的通信量的底层数值模拟分区。
Load balancing is important for the efficient execution of numerical simulations on parallel computers. In particular when the simulation domain changes over time, the mapping of computational tasks to processors needs to be modified accordingly. Most state-of-the-art libraries addressing this problem are based on graph repartitioning with a parallel variant of the Kernighan-Lin (KL) heuristic. The KL approach has a number of drawbacks, including the optimized metric and solutions with undesirable properties. Here we further explore the promising diffusion-based multilevel graph partitioning algorithm DibaP. We describe the evolution of the algorithm and report on its MPI implementation PDibaP for parallelism with distributed memory. PDibaP is targeted at small to medium scale parallelism with dozens of processors. The presented experiments use graph sequences that imitate adaptive numerical simulations. They demonstrate the applicability and quality of PDibaP for load balancing by repartitioning on this scale. Compared to the faster ParMETIS, PDibaP’s solutions often have partitions with fewer external edges and a smaller communication volume in an underlying numerical simulation.