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

摘要

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