论文部分内容阅读
多重网格算法是一类非常有效的求解稀疏线性系统的迭代方法。多重网格算法主要包含两种算法，即几何多重网格和代数多重网格。对于几何多重网格方法，需要知晓应用问题的几何背景构造网格层，对于几何背景复杂的问题并不适用，而代数多重网格算法是利用几何多重网格方法的思想建立起来的一种自动求解方程的迭代方法。近些年随着计算机硬件以及求解数值方法的快速发展，代数多重网格突破了几何多重网格对物理背景的限制，在求解稀疏线性问题上发挥了重要的作用。但是随着应用问题的复杂化，计算问题的规模也与日俱增，这对代数多重网格的计算时间以及效率提出了更高的要求。 随着并行计算机以及高性能计算的发展，对大规模科学计算应用问题设计高效的并行算法成为必不可少的重要手段。在计算流体力学以及电磁学等科学与工程计算领域中，往往都需要对稀疏线性代数方程组进行求解。而且随着方程组系数矩阵规模的不断增大，在并行机上设计并行算法高效求解大规模稀疏线性方程组成为了科学计算领域的一项重要任务。采用直接算法求解大规模稀疏线性方程组受到了内存和计算复杂度的限制，不能满足对计算时间的需求。所以采用迭代方法，在有限步数内收敛于方程的精确解。代数多重网格方法现已成为数值计算领域一种重要的加速迭代收敛技术，但由于算法的串行性，不能得到很好的可扩展性，所以近年来，在大规模集群上实现AMG算法成为研究热点。本文的研究内容包括: 1)设计代数多重网格并行算法的预处理过程。首先结合近似最小度排序算法对稀疏系数矩阵进行重排序提高并行算法的性能。其次结合数据的稀疏性以及数据在进程间的分块策略，提出了并行分块CSR存储格式。最后通过预处理通信模块算法建立具有最小通信量的通信关系。 2)研究了代数多重网格算法以及作为Krylov子空间预条件子。研究代数多重网格的五个分量，并在建立阶段提出了aggregation+PMIS混合粗化算法，降低建立阶段的计算复杂度，增加算法的并行度，提高建立阶段运行时间。在求解阶段实现V-循环和K-循环迭代模式。基于预处理阶段的存储结构以及通信信息实现了高效的计算与通信重叠模式的稀疏矩阵-向量乘并行算法。最后通过分析进程内部的计算操作，结合共享存储编程模型，设计MPI+OpenMP混合编程算法，实现混合并行AMG算法。 3)异构环境下代数多重网格混合编程算法实现。通过分析算法中并行度较高的部分，研究了适合新型CPU+MIC异构并行计算平台的并行实现策略，将数据传输到MIC卡上进行多线程计算。总体分析模块之间的关联度，对CPU-MIC数据拷贝、MIC计算进行优化，减少CPU端向MIC端传输数据的次数并且调用多块MIC卡进行并行计算，在MIC端采用OpenMP细粒度编程，提高程序整体性能。 4)基于以上研究内容设计并实现AMG并行算法代码架构。该架构在设计上采用自底向上的形式，通过分析算法的并行性并基于新的数据结构，使用MPI、OpenMP以及MIC并行化方法实现。耦合了预处理过程通信优化模块、计算与通信重叠算法、以及建立阶段求解阶段的功能函数，可以对大规模稀疏线性方程组进行求解。