基于聚集混合粗化的代数多重网格并行算法  

Parallel algebraic multigrid method based on aggregation hybrid coarsening

作　　者：赵莲[1,2] 赵永华[1] 迟学斌[1] 

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

出　　处：《计算机工程与设计》2017年第1期81-85,共5页Computer Engineering and Design

基　　金：国家自然科学基金重大研究计划基金项目(91430214);国家973重点基础研究发展计划基金项目(2011CB309702);国家863高技术研究发展计划基金项目(2015AA01A303);数学工程与先进计算国家重点实验室开放基金项目(2014A03);北京高等学校青年英才计划基金项目(YETP0706);中央高校基本科研业务费专项资金基金项目(2014MS21)

摘　　要：为提高代数多重网格(algebraic multigrid,AMG)并行算法的可扩展性能,提出一种基于聚集粗化和最大独立集算法的混合并行粗化算法。在每个进程内部独立实现聚集粗化,在此基础上,进程间采用PMIS(parallel maximum independent set)算法对边界点进行修正。针对现代多核处理器,结合细粒度的并行编程模型,实现MPI+OpenMP混合编程并行算法。数值实验结果验证了该算法的有效性,对于求解二维五点Laplace方程在集群"元"上并行规模达到256核,相对于AGMG软件包求解总时间提高了74%,测试结果优于hypre软件包,可扩展到128核心。To increase the parallel scalability of algebraic multigrid algorithm, a hybrid coarsening algorithm based on aggregation algorithm and maximum independent set was implemented. Aggregation coarsening for local points was done in every process, and PMIS algorithm was used to correct boundary points. For modern multi-core processors, the fine-grained parallel program- ming model was combined to achieve a hybrid MPI-r-OpenMP parallel programming algorithm. The validity of the algorithm was verified by numerical experiments. In Era cluster when MPI process reaches 256 cores to solve the two-dimensional Laplace equa- tion, the total time cost of AMG algorithm is 74% less than AGMG software. With other matrixes, the total time cost of AMG is better than hypre （high performance preconditioners） software and can be extended to 128 cores.

关 键 词：代数多重网格 数据存储格式 PMIS粗化 聚集粗化 混合编程 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]