Algorithm 967
Algorithm 967
复制标题
算法967
DOI：
--
复制
发表时间：
2016
影响因子：
2.7
通讯作者：
G. Biros
中科院分区：
文献类型：
--
作者：
D. Malhotra;G. Biros
常系数椭圆型偏微分方程（PDE）的解可以使用积分变换来计算：与PDE的基本解的卷积，也称为体积势。我们提出了一种快速多极子方法（FMM）计算体积势，并使用它们来构建泊松，斯托克斯和低频亥姆霍兹问题的空间自适应求解器。传统的N体方法适用于离散粒子相互作用。对于体积势，可以用体积积分代替求和。粒子N体方法可以用来加速这种积分。但开发专用的FMM更有效。在这篇文章中，我们讨论了这样一个FMM的有效实现。我们使用高阶分段切比雪夫多项式和八叉树数据结构来表示输入和输出字段，并使近场和核独立FMM（KIFMM）的远场近似的频谱精确近似。对于分布式内存并行，我们使用空间填充曲线，局部基本树，和超立方体的通信计划以前在我们的小组。我们提出了新的近距离和远距离交互遍历，优化缓存的使用。此外，与粒子N体代码不同，我们需要一个2：1的平衡树来允许预计算。我们提出了一个快速的2：1平衡方案。最后，我们在英特尔桑迪Bridge架构上使用向量化（包括AVX指令集），以获得超过50%的峰值浮点性能。我们使用任务并行性在德克萨斯州高级计算中心（TACC）的Stampede平台上使用Xeon Phi。我们在一个节点上实现了大约600 gflop/s的双精度性能。我们在Stampede上的最大运行在16 K核心上花费了3.5s，用于高度不均匀粒子分布的18 e +9个未知数的问题（对应于超过3e+23个未知数的有效分辨率，因为我们在八叉树中使用了23个级别）。
The solution of a constant-coefficient elliptic Partial Differential Equation (PDE) can be computed using an integral transform: A convolution with the fundamental solution of the PDE, also known as a volume potential. We present a Fast Multipole Method (FMM) for computing volume potentials and use them to construct spatially adaptive solvers for the Poisson, Stokes, and low-frequency Helmholtz problems. Conventional N-body methods apply to discrete particle interactions. With volume potentials, one replaces the sums with volume integrals. Particle N-body methods can be used to accelerate such integrals. but it is more efficient to develop a special FMM. In this article, we discuss the efficient implementation of such an FMM. We use high-order piecewise Chebyshev polynomials and an octree data structure to represent the input and output fields and enable spectrally accurate approximation of the near-field and the Kernel Independent FMM (KIFMM) for the far-field approximation. For distributed-memory parallelism, we use space-filling curves, locally essential trees, and a hypercube-like communication scheme developed previously in our group. We present new near and far interaction traversals that optimize cache usage. Also, unlike particle N-body codes, we need a 2:1 balanced tree to allow for precomputations. We present a fast scheme for 2:1 balancing. Finally, we use vectorization, including the AVX instruction set on the Intel Sandy Bridge architecture to get better than 50% of peak floating-point performance. We use task parallelism to employ the Xeon Phi on the Stampede platform at the Texas Advanced Computing Center (TACC). We achieve about 600gflop/s of double-precision performance on a single node. Our largest run on Stampede took 3.5s on 16K cores for a problem with 18e+9 unknowns for a highly nonuniform particle distribution (corresponding to an effective resolution exceeding 3e+23 unknowns since we used 23 levels in our octree).