大规模矩阵的MPI并行求逆算法设计与分析.docxVIP

第 34 卷第5 期 2 0 1 4 年 1 0 月 大 地 测 量 与 地 球 动 力 学 JOUＲNAL OF GEODESY AND GEODYNAMICS Vol． 34 No． 5 Oct． ，2014 文章编号: 1671-5942( 2014) 05-0120-05 *大规模矩阵的 MPI 并行求逆算法设计与分析 * 周 浩1) 罗志才1，2) 钟 波1，2) 1) 武汉大学测绘学院，武汉 430079 ?2) 地球空间环境与大地测量教育部重点实验室，武汉 430079 ? 摘 要 针对最小二乘解算中的大规模矩阵求逆问题，基于 MPI 实现了高阶稠密对称正定矩阵的 Gauss-Jordan 并行求逆算法，减少了计算耗时; 通过优化矩阵读写、存储等方式降低了单个计算节点的内存耗用量，拓展了算法 的可移植性。通过并行读写效率、单节点进程数、加速比和相对效率等因素评价算法的计算效率，计算结果表明: 通过引入并行读写、减小单个计算节点的负荷等方式，并行求逆的相对效率峰值可达 60% 。以卫星重力场反演为 例，采用曙光集群上的 8 个计算节点分别恢复截断阶次为 120、240 的地球重力场模型，求逆耗时为 229 s、7 395 s， 单个节点的内存耗用峰值为 205 MB、1． 57 GB，反演精度可达 10 － 18 量级，表明该算法能够快速稳定地获取最小二乘 问题的最优估值。 关键词 MPI; 对称正定矩阵; 矩阵求逆; Gauss-Jordan 算法; 最小二乘法 中图分类号: P209 文献标识码: A DESIGN AND ANALYSIS OF MPI PAＲALLEL ALGOＲITHM FOＲ LAＲGE-SCALE MATＲIX INVEＲSION Zhou Hao1) ，Luo Zhicai1，2) and Zhong Bo1，2) 1) School of Geodesy and Geomatics，Wuhan University，Wuhan 430079 ?2) Key Lab of Geospace Environment and Geodesy，Ministry of Education，Wuhan University，Wuhan 430079 ? Abstract In order to solve the problem in large scale matrix inversion with least square solving，the parallel al- gorithm to inverse the high-order dense symmetrical positive define matrix with Gauss-Jordan method on the basis of MPI was proposed． Considering the high memory demand on single processor for this algorithm，the MPI I / O inter- face was introduced，which can reduce communicational time between each node simultaneously． Introducing the parallel I / O efficiency，memory demand on single processor，acceleration ratio and relative efficiency，the efficiency of the parallel algorithm can be estimated comprehensively． The simulation result indicates that this parallel algo- rithm can improve the efficiency significantly，ant its relative efficiency can reach to 60% ． Eventually，the earth gravity field complete to degree and order 120 and 240 are recovered on the Sugon Cluster，and the relative inver- sion time is only 229 s and 7 395 s respectively． In a