基于分治法求解对称三对角矩阵特征问题的MPI/Cilk混合并行算法  

A Hybrid Parallel Algorithm Based on Divided and Conquer Method Using MPI/Cilk for the Symmetric Tridiagonal Eigenproblem

作　　者：朱京乔 赵永华[1] ZHU Jingqiao;ZHAO Yonghua(Department of High Performance Computing,Computer Network Information Center,Chinese Academy of Sciences,Beijing 100190,China;School of Computer Science and Technology,University of Chinese Academy of Sciences,Beijing 100049,China)

机构地区：[1]中国科学院计算机网络信息中心高性能部,北京100190 [2]中国科学院大学计算与控制学院,北京100049

出　　处：《郑州大学学报（理学版）》2020年第1期33-38,共6页Journal of Zhengzhou University:Natural Science Edition

基　　金：国家重点研发计划项目(2017YFB0202202,2016YFB0201302);国家自然科学基金重点项目(91430214);中国科学院“十三五”信息化建设专项项目(XXH13506-405)

摘　　要：对称稠密矩阵特征问题的求解通常转化为三对角矩阵特征问题的求解,基于对称三对角矩阵特征求解的分而治之方法,提出了一种基于消息传递接口(message passing interface,MPI)+Cilk多任务并行模型的混合求解算法,采用进程间数据并行和进程内多线程任务并行的方法,实现了对分而治之算法中分治阶段和合并阶段的多任务划分和动态调度。进程内利用Cilk任务执行的有向无环图模型,解决了线程级并行的数据依赖和饥饿等待等问题,提高了程序的并行性;进程间通过粗粒度计算任务的划分,优化了MPI部分的数据通信流程和负载均衡问题。数值实验表明,混合并行算法在计算性能和可扩展性方面都要优于纯MPI并行算法。Divide and conquer method was a good algorithm with high performance used for solving tridiagonal matrix eigenproblems,while with the enlargement of the scale,computing efficiency and storage limitation became the bottleneck.A new eigenproblem solver algorithm based on a hybrid parallel paradigm with MPI/Cilk was proposed to optimize the divide and conquer algorithm both at data and task levels.In order to take good advantage of multi-core CPU,task-based parallelization mechanism was introduced inside computing nodes,which solved the problem in data dependence and thread starvation by directed acyclic graph model.The overhead of data communication among MPI nodes was optimized by coarse-grained partition of tasks,which also improved load balance.The numerical test was carried out and the result was compared with the pure MPI and MPI/openMP parallel algorithm,which showed the performance and efficiency of the algorithm.

关 键 词：三对角矩阵 对称特征问题 并行计算 分治算法 Cilk MPI 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]