多核体系结构上迭代方法的通信与计算比分析

摘要

迭代方法是科学计算中求解大规模稀疏线性代数方程组最常用的方法.迭代方法的并行可扩展性能取决于迭代过程中通信与计算开销之比.稀疏矩阵与向量的乘积(SpMV)、向量与向量的内积(Dot)是迭代方法的两个基本运算,分别需要局部点对点通信和全局规约通信,是影响迭代方法并行可扩展性能的主要瓶颈.多核体系结构需要并行迭代方法适应更细粒度的并行计算,通信与计算比对并行性能的影响更为突出.针对多核体系结构特征,本文分析并行迭代方法的通信与计算比.具体地,引入渐近规模,即满足加速条件的计算规模下界,来反映并行迭代方法适应细粒度计算的能力,并由此刻画通信与计算比.基于此,在一台包含128 个双路四核计算节点的并行机上(共1024 个CPU 核),分别基于纯进程并行(MPI)和进程/线程混合并行(MPI/OpenMP),分析了几类常用迭代方法的通信与计算比.数值结果表明,基于MPI 的纯进程并行性能受限于内积计算的渐近规模,难以适应多核体系结构上的大规模计算.基于MPI/OpenMP 的进程/线程混合并行可缓解进程间的MPI 通信开销,降低渐近规模,改善并行可扩展性能.基于这些结果,从迭代方法的算法设计和并行实现等方面讨论了面向更大规模的多核系统,降低通信与计算比的途径和方法.