A low‐communication, parallel algorithm for solving PDEs based on range decomposition
A low‐communication, parallel algorithm for solving PDEs based on range decomposition
复制标题
DOI：
10.1002/nla.2041
复制
发表时间：
2017-05
影响因子：
4.3
通讯作者：
D. Appelhans;T. Manteuffel;S. McCormick;J. Ruge
中科院分区：
文献类型：
--
作者：
D. Appelhans;T. Manteuffel;S. McCormick;J. Ruge
本文提出了一种新的，低通信算法，用于在大规模并行计算机上求解偏微分方程。范围分解（RD）算法通过在执行全局通信步骤之前应用嵌套迭代和自适应网格细化来暴露粗粒度并行性。只需几个这样的步骤被观察到是足够的，以获得一个小的离散化误差的倍数内的精度。目标应用是千万亿次和亿次机器，其中需要分层并行，并且由于消息延迟，传统的并行数值PDE通信模式是昂贵的。RD算法使用单位分割来平均分配误差，从而平均分配工作。这种方法的计算优势是，分解的问题可以并行解决，没有任何通信，直到分区的解决方案被求和。这在昂贵的通信但非常便宜的计算的范例中提供了潜在的优势。本文介绍了该方法，并详细说明了通信步骤。两个性能模型的开发，表明与传统的并行实现嵌套迭代的延迟成本是成比例的log（P）2，而RD方法减少了通信延迟log（P），同时保持类似的带宽成本。两个问题，拉普拉斯和平流扩散的数值结果，证明了增强的性能，和启发式的论点解释了为什么该方法收敛速度快。版权所有© 2016约翰威利父子有限公司.
This paper proposes a new, low‐communication algorithm for solving PDEs on massively parallel computers. The range decomposition (RD) algorithm exposes coarse‐grain parallelism by applying nested iteration and adaptive mesh refinement locally before performing a global communication step. Just a few such steps are observed to be sufficient to obtain accuracy within a small multiple of discretization error. The target applications are petascale and exascale machines, where hierarchical parallelism is required and traditional parallel numerical PDE communication patterns are costly because of message latency. The RD algorithm uses a partition of unity to equally distribute the error, and thus, the work. The computational advantages of this approach are that the decomposed problems can be solved in parallel without any communication until the partitioned solutions are summed. This offers potential advantages in the paradigm of expensive communication but very cheap computation. This paper introduces the method and explains the details of the communication step. Two performance models are developed, showing that the latency cost associated with a traditional parallel implementation of nested iteration is proportional to log(P)2, whereas the RD method reduces the communication latency to log(P), while maintaining similar bandwidth costs. Numerical results for two problems, Laplace and advection diffusion, demonstrate the enhanced performance, and a heuristic argument explains why the method converges quickly. Copyright © 2016 John Wiley & Sons, Ltd.