High Performance Evaluation of Helmholtz Potentials using the Multi-Level Fast Multipole Algorithm
High Performance Evaluation of Helmholtz Potentials using the Multi-Level Fast Multipole Algorithm
复制标题
DOI：
10.1109/tpds.2022.3165649
复制
发表时间：
2020-06
影响因子：
5.3
通讯作者：
Michael P. Lingg;S. Hughey;H. Aktulga;B. Shanker
中科院分区：
文献类型：
--
作者：
Michael P. Lingg;S. Hughey;H. Aktulga;B. Shanker
对势的评估在物理学的许多领域中是至关重要的。经典的N体问题的根源在于计算拉普拉斯势，并产生了树算法，快速多极方法（FMM），以及核独立的方法。多年来，FMM的拉普拉斯潜力已经产生了深远的影响，对一些学科，因为它已经有可能开发高度可扩展的并行版本的这些算法。这是在鲜明的对比，如亥姆霍兹潜在的振荡电位的并行算法。可扩展并行的主要瓶颈是向上、跨树和向下遍历树所需的操作的计算和通信成本。在本文中，我们分析了并行实现中的计算和通信的渐近成本，并描述了克服瓶颈和实现不同粒子分布的亥姆霍兹势的高性能评估的技术。我们证明，由此产生的实施具有负载平衡的效果，显着减少了解决方案的时间，并提高了规模的问题，可以使用全波物理处理。
Evaluation of pair potentials is critical in a number of areas of physics. The classical N-body problem has its root in evaluating the Laplace potential, and has spawned tree-algorithms, the fast multipole method (FMM), as well as kernel independent approaches. Over the years, FMM for Laplace potential has had a profound impact on a number of disciplines as it has been possible to develop highly scalable parallel versions of these algorithms. This is in stark contrast to parallel algorithms for oscillatory potentials such as the Helmholtz potential. The principal bottlenecks to scalable parallelism are the computation and communication costs of operations necessary to traverse up, across, and down the tree. In this paper, we analyze asymptotic costs for both computation and communication in a parallel implementation, and describe techniques to overcome bottlenecks and achieve high performance evaluation of the Helmholtz potential for different distributions of particles. We demonstrate that the resulting implementation has a load balancing effect that significantly reduces the time-to-solution and enhances the scale of problems that can be treated using full wave physics.