Optimization of the parallel black-box fast multipole method on CUDA
Optimization of the parallel black-box fast multipole method on CUDA
复制标题
DOI：
10.1109/inpar.2012.6339607
复制
发表时间：
2012-05
期刊：
影响因子：
--
通讯作者：
T. Takahashi;C. Cecka;Eric F Darve
中科院分区：
文献类型：
--
作者：
T. Takahashi;C. Cecka;Eric F Darve
快速多极子方法是计算科学和工程中广泛使用的一种数值算法。最近的一个研究趋势是在多核处理器上执行FMM，包括图形处理单元(GPU)。在本文中，我们讨论了在GPU上优化黑盒FMM(BbFMM)的方法，它是FMM的一个变体，可以接受用户指定的任何非振荡内核。使用支持CUDA的图形处理器，我们重点分析了bbFMM中最耗时的两个阶段：多极到局部(M2L)运算和短距离直接核计算。在高桥等人之前发表的一篇论文之后。(2011)，我们将针对GPU的M2L操作的最佳实现整合到一个完整的bbFMM代码中。我们创建了高度优化的CPU版本的代码以及CUDA代码。虽然GPU在M2L阶段提供了显著的加速，但在直接短程计算部分的加速更温和。结果发现，在该计算阶段，12核CPU的性能接近峰值(使用所有核心)。在CPU和GPU之间提供了广泛的算法和性能分析，并与以前发表的工作进行了比较，这表明当前的实现是这类FMM最有效的实现之一。
The fast multipole method (FMM) is a widely used numerical algorithm in computational science and engineering. A recent research trend is to perform the FMM on many-core processors, including Graphical Processing Units (GPUs). In this paper, we discuss methods to optimize the black-box FMM (bbFMM), which is a variant of the FMM that can accept any non-oscillatory kernel as specified by the user, on GPUs. Using CUDA-capable GPUs, we focused our analysis on the two most time-consuming phases in the bbFMM: the multipole-to-local (M2L) operation and the short-range direct kernel computation. Following a previously published paper by Takahashi et al. (2011), we incorporated the best implementation of the M2L operation for the GPU in a complete bbFMM code. We created a highly optimized CPU version of the code along with the CUDA code. Although the GPU provides a significant speed-up during the M2L phase, the speed up was more moderate in the direct short-range calculation part. It was found that the 12-core CPU is close to peak performance (using all cores) during that phase of the calculation. Extensive algorithmic and performance analysis is provided between the CPU and GPU, along with comparisons with previously published work, which suggests that the current implementation is one of the most efficient for this class of FMM.