基于计算与通信重叠的稀疏矩阵-向量乘积及其在AMG中的应用  

SPARSE MATRIX-VECTOR MULTIPLY ALGORITHM BASED ON OVERLAPPING COMPUTATION AND COMMUNICATION AND APPLICATION IN AMG

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

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

出　　处：《数值计算与计算机应用》2015年第3期197-214,共18页Journal on Numerical Methods and Computer Applications

基　　金：国家自然科学基金重大研究计划(No.91430214);国家重点基础研究发展计划(973)(No.2011CB309702);国家高技术研究发展计划(863)(No.2012AA01A309);数学工程与先进计算国家重点实验室开放基金(No.2014A03)资助

摘　　要：本文针对代数多重网格(algebraic multigrid,AMG)并行实现中的稀疏矩阵-向量乘,建立了稀疏矩阵新的分布和数据存储模式,提出了一类具有最小通信量以及隐藏通信的新稀疏矩阵-向量乘并行算法,并实现了基于K-循环迭代的求解阶段并行算法.针对现代多核处理器,结合细粒度的并行编程模型,实现了MPI+OpenMP混合编程并行算法.通过同hypre软件包测试比较,在深腾7000集群上求解三维Laplace方程并行规模达到512核心时,并行求解阶段运行时间较hypre(high performance preconditioners)软件包提高了56%,在元集群上提高了39%,验证了算法的有效性.This paper shows the study on sparse matrix-vector multiplication in AMG,this paper establishes a new sparse matrix distribution and data storage mode,and propose a new sparse matrix-vector parallel algorithm with minimum traffic and hidden communication,and implements the parallel algorithm of the solution phase with K-cycle iteration.For modern multi-core processors,combine with the fine-grained parallel programming model to achieve a hybrid MPI＋OpenMP parallel programming algorithm.Numerical experiment indicates that compare with the hypre（high performance preconditioners）software,in Deepcomp 7000 cluster when MPI process reaches 512 cores to solve the three-dimensional Laplace equation,the run time of solve phase using K-cycle obtains 56%faster than hypre software with V-cycle and in Era cluster obtains 39%faster than hypre with V-cycle.

关 键 词：代数多重网格 预处理过程 数据存储格式 计算与通信重叠 

分 类 号：O241.6[理学—计算数学]