基于Charm++的并行FMM实现  

Implementation of Parallel FMM Based on Charm++

作　　者：丁磊[1,2] 王武 姜金荣[1] 赵莲[1] Ding Lei;Wang Wu;Jiang Jinrong;Zhao Lian(Computer Network Information Center,Chinese Academy of Sciences,Beijing 100190,China;University of Chinese Academy of Sciences,Beijing 100049,China)

机构地区：[1]中国科学院计算机网络信息中心,北京100190 [2]中国科学院大学,北京100049

出　　处：《数据与计算发展前沿》2020年第3期101-112,共12页Frontiers of Data & Computing

基　　金：国家重点研发计划“地球系统模式的改进、应用开发和高性能计算”(2016YFB0200800);中国科学院科研信息化应用工程:高性能应用软件(XXH13506-405);中国科学院战略性先导科技专项(C):国产安全可控先进计算系统研制(XDC01040100)。

摘　　要：【目的】为了利用Charm++的过分解与运行时迁移特性,提高FMM的并行执行效率,本文在Charm++上完成了FMM的并行实现。【方法】通过分析通信、并行任务分解、异步调用转化,采用SDAG实现了基本通信函数,并利用LPT近似策略达到了负载均衡,最终实现了并行FMM。【结果】测试结果表明,FMM的Charm++实现的计算精度与MPI实现完全相同,在千核规模上的执行速度优于MPI实现。过分解与负载均衡策略在粒子分布不均的情况下减少了10%的运行时间。【局限】目前的实现没有利用Charm++共享内存的结构,仍有优化的空间,负载均衡策略较为简单。【结论】本文给出了一个较为通用的MPI风格程序向Charm++转化的策略,并证明了Charm++的过分解与负载均衡策略对FMM有加速效果。[Objective]This paper has implemented a parallel FMM based on Charm++to take advantage of its over-decomposition and migratability.[Methods]It is achieved by analyzing communication,separating parallel tasks,and converting synchronous communication to asynchronous communication.Also,the SDAG was used to implement the basic communication calls and the LPT approximation strategy was adopted for dynamic load balancing.[Results]The results show that the implementation of parallel FMM based on Charm++has the same accuracy as that of MPI implementation,and its execution speed on the thousand-core scale is better than that of MPI implementation.Over-decomposition and load-balancing strategy contribute to the execution time reduction by 10%in the unbalance particle distribution.[Limitations]The current implementation does not use the shared memory structure of Charm++and needs further optimizations.Besides,the load balancing strategy is simple.[Conclusions]This paper gives a relatively general method to convert the MPI style programs to Charm++style ones and proves that over-decomposition and load-balancing strategy can accelerate FMM execution.

关 键 词：Charm++ FMM 负载均衡 过分解 

分 类 号：TP332[自动化与计算机技术—计算机系统结构] O241[自动化与计算机技术—计算机科学与技术]