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

摘要：

对称稠密矩阵特征问题的求解通常转化为三对角矩阵特征问题的求解,基于对称三对角矩阵特征求解的分而治之方法,提出了一种基于消息传递接口(message passing interface,MPI)+Cilk多任务并行模型的混合求解算法,采用进程间数据并行和进程内多线程任务并行的方法,实现了对分而治之算法中分治阶段和合并阶段的多任务划分和动态调度.进程内利用Cilk任务执行的有向无环图模型,解决了线程级并行的数据依赖和饥饿等待等问题,提高了程序的并行性;进程间通过粗粒度计算任务的划分,优化了MPI部分的数据通信流程和负载均衡问题.数值实验表明,混合并行算法在计算性能和可扩展性方面都要优于纯MPI并行算法.

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

所属期刊栏目：52

分类号：TP391(计算技术、计算机技术)

资助基金：国家重点研发计划项目;国家自然科学基金重点项目;中国科学院"十三五"信息化建设专项项目

在线出版日期：2020-03-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：33-38