迭代方法中基于渐近规模的通信与计算比分析

摘要

迭代方法是科学计算中求解大规模稀疏线性代数方程组最常用的方法.大量实际应用表明,迭代方法通常具有较高的通信与计算比,只有在粗粒度并行下才能取得较好的并行可扩展性能.而实际应用大规模计算的需求和当前多核/众核体系结构的发展趋势要求迭代方法具备细粒度并行可扩展能力.文中引入渐近规模,即满足加速条件的计算规模下界,来反映并行迭代方法适应细粒度并行的能力,并由此刻画通信与计算比.基于矩阵的稀疏模式及其通信模式、机器的通信参数和迭代方法的基本运算,给出了渐近规模的理论预测公式.在一台包含128个双路4核计算节点的并行机上,分别基于纯进程并行(MPI)和进程/线程混合并行(MPI/OpenMP),以实际应用中3种常用迭代方法Jacobi、CG、BiCGSTAB为例,分析其渐近规模.并行可扩展性测试表明了渐近规模用于刻画迭代方法通信与计算比的准确性.对于纯进程情形,给出了渐近规模的理论预测与实际测试的对比,表明了理论预测结果的正确性.最后,基于这些结果,从迭代方法的算法设计和并行实现等方面讨论了面向未来更大规模的计算系统,降低通信与计算比的途径.