扶月月，王武，王乔

1.中国科学院计算机网络信息中心，北京 100190

2.中国科学院大学，北京 100049

3.中国科学院国家天文台，北京 100101

引言

N体问题计算相互作用的N个粒子的相互作用和运动，是高性能计算中具有代表性和挑战性的问题之一，在天体物理、分子动力学、磁流体动力学等领域具有广泛的应用。模拟N体问题的数值方法包括直接法（Particle-Particle，PP）、树方法（Tree Method）和粒子网格方法(Particle Mesh，PM)等，其中树方法有BH 方法(Barnes-Hut)[1]和快速多极子方法 (Fast Multipole Method，FMM)[2]。PP方法的复杂度为O(N2)，其中N为粒子规模，这限制了模拟问题的规模；BH 方法的复杂度为O(NlogN)，且计算精度可控；FMM的复杂度为O(N)，兼具精度和速度优势，被IEEE 计算机协会和美国计算物理学会列为20世纪十大算法之一[3]；基于快傅里叶变换（Fast Fourier Transform，FFT）的PM 方法[4]复杂度为O(NlogN)，虽然计算速度较快，但计算短程力时不精确，只适用于长程力计算。为了弥补PM方法计算精度不足的缺点，PM 混合算法应运而生，PM 方法结合直接法和树方法的混合算法（P3M[5]、TreePM[6]）应用广泛。

随着高性能计算技术的发展，以及天文学和分子动力学等领域对大规模计算需求的增长，仅从算法上降低计算复杂度或者增加CPU 核数量并不足以满足领域科学家的计算需求。采用硬件加速来加快计算速度，从而扩大计算规模也是较为可行的途径。GPU的最新发展已经能够以低廉的成本提供高性能的通用计算，基于CPU+GPU的并行异构架构也已成为当今大型超级计算机的主流体系结构之一。例如，2019年11月全球TOP500 排行榜前10名的超级计算机中，有5台使用了CPU+GPU的异构体系结构。……