基于分治法求解对称三对角矩阵特征问题的混合并行实现  

Hybrid Parallel Algorithm Using MPI/Cilk for Symmetric Tridiagonal Eigenproblems

作　　者：朱京乔 赵永华[1] ZHU Jing-Qiao;ZHAO Yong-Hua(Computer Network Information Center,Chinese Academy of Sciences,Beijing 100190,China;University of Chinese Academy of Sciences,Beijing 100049,China)

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

出　　处：《计算机系统应用》2019年第9期246-250,共5页Computer Systems & Applications

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

摘　　要：基于对称三对角矩阵特征求解的分而治之方法,提出了一种改进的使用MPI/Cilk模型求解的混合并行实现,结合节点间数据并行和节点内多任务并行,实现了对分治算法中分治阶段和合并阶段的多任务划分和动态调度.节点内利用Cilk任务并行模型解决了线程级并行的数据依赖和饥饿等待等问题,提高了并行性;节点间通过改进合并过程中的通信流程,使组内进程间只进行互补的数据交换,降低了通信开销.数值实验体现了该混合并行算法在计算效率和扩展性方面的优势.Divide and conquer algorithm is widely used for tridiagonal matrix eigenproblems while computing efficiency and storage limitation are always bottlenecks for large scale problems.In this study,the proposed eigenproblem algorithm based on hybrid parallel paradigm with MPI/Cilk optimizes the divide and conquer algorithm both at data and task levels.The introduced task-based parallelization mechanism inside computing nodes solves the problem in data dependence and thread starvation by directed acyclic graph model.By coarse-grained partition of tasks the overhead of data communication among MPI nodes is also optimized,which helps to improve load balance.The numerical test is carried out and the result is compared with the pure MPI and MPI/openMP parallel algorithm,which shows the performance and efficiency of the algorithm.

关 键 词：并行计算 对称特征问题 分治算法 Cilk 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]