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

更新时间:2023-05-28

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

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

阅读全文