Page 86 - 《软件学报》2021年第8期

2368 Journal of Software 软件学报 Vol.32, No.8, August 2021

1.1 宇宙N体模拟
N 体问题又称“多体问题”,兼具数据密集和计算密集的特点,是物理科学高端模拟中 7 个主要问题之一 [17] .
此类问题在天体物理学、分子动力学等领域处于核心的地位.天文学的一些关键现象(如星系成团及演化、暗
物质晕等)需采用大尺度、高解析度的大规模 N 体模拟结果来解释和指导天文观测;宇宙模型和理论也通过计
算结果得以验证和完善.随着先进快速算法和高性能计算技术发展,万亿量级规模 N 体问题的高效大规模并行
计算模拟已成为可能.
基于树遍历的算法如快速多极子方法(fast multipole method,简称 FMM),不仅具有近似线性的复杂度和较
高的精度,而且适合并行.其中短程力的求解具有计算密集的特征,可有效利用高性能异构平台加速器件(如
GPU、MIC 或众核处理器等)的超强计算能力.基于快速傅里叶变换(fast Fourier transform,简称 FFT)的粒子网格
方法(particle-mesh method,简称 PM)虽速度更快,但由于受限于精度,只适用于计算长程力,而且将带来全局通信.
为兼顾计算速度和精度,重叠短程力的计算与长程力的通信,混合算法成为高性能并行 N 体模拟的主流 [18,19] .如
图 2 所示,虚线内为 FMM 计算区域,其中粒子间的短程力相互作用(P2P)占 FMM 计算时间的 90%以上,适合在
加速卡上实现;虚线外的区域采用 PM 计算长程力,可在 CPU 端调用 FFT 实现.

Fig.2 A schematic diagram of FMM-PM algorithm
图 2 FMM-PM 算法示意图
中国科学院国家天文台和计算机网络信息中心团队合作,在国产高性能异构计算平台上采用 FMM 与 PM
耦合算法实现了大规模的 N 体问题高效并行模拟.计算的并行效率达 80%,浮点峰值效率达 30%以上,为实现更
高分辨率的超大规模天文应用模拟奠定了基础.
1.2 大气与地球系统模式

大气与地球系统模式中,Stencil 计算是核心算法,也是物理科学高端模拟中 7 个主要问题之一 [17] 并广泛存
在与科学与工程计算中.Stencil 计算(如图 3 所示)绝大部分是访存密集型计算,计算访存比低,主存带宽受限严
重 [20] .已经有很多 Stencil 计算优化方面的工作:如 Strumpen 等人 [21] 利用时间局部性优化三级存储系统;
Micikevicus 等提出了 GPU 平台上的高阶 Stencil 优化方法.此外,也有一些基于 Stencil 计算的应用在国产机器
上的移植优化工作,如 Fu 等人 [22] 将大气模式 CAM 和大型非线性地震模拟系统移植到“神威·太湖之光”超级计
算机上.
与大气模式 CAM 类似,中国科学院地球系统模式中的有限差分 Stencil 计算的运行时间占比超过 90%,但
是其浮点计算效率仅有不到 5%.而且这些 Stencil 计算包含更多更复杂的数据结构,Stencil 的种类和差分格式、
算法求解过程和特点也各不相同.其主要特点有:通信和同步多、复杂计算多、变量多而计算网格点少、计算
访存比和主存带宽受限问题更突出.这对当前的国产并行计算平台的计算和访存能力提出了新需求.而在高性