面向异构系统的可扩展的迭代方法并行优化模型及其应用研究

With the rapid improvement of the computation capacity of computers and the increasing depth and scale of the problems，researchers focus on the GPU computing to improve the performance of iterative methods for solving the large-scale sparse linear system Ax = b over the recent years. Given that there is not any GPU-accelerated iterative method that is always highly efficient for all sparse linear systems, and constructing it is expensive and time-consuming, based on the heterogeneous multi-GPU platform, we take several popular preconditioned iterative methods for example in this project, analyze the main ingredients influencing the performance of iterative methods, and thus construct the parallel optimization models of the vector operation, inner product, sparse matrix-vector multiplication, and preconditioner. My target is to present an adaptive parallel optimization model and the corresponding theoretical system for iterative methods on any multi-GPU platform. Using the proposed optimization model of iterative methods, we can automatically and rapidly construct the optimal parallel iterative method on multi-GPUs for any given sparse linear system. We validate our models by applying them to the electromagnetic field. This project presents a new idea of how to automatically and rapidly construct the optimal multi-GPU parallel iterative method, which is meaningful for the development of promoting the parallel computing.

随着计算机计算能力的提高，人们探讨问题的深度和规模也随着增大，为适应求解大规模稀疏线性系统Ax=b的需要，近些年通过GPU计算提高迭代求解算法性能的研究已得到广泛的关注。考虑不存在普遍适用的基于GPU的异构并行迭代方法，而且构造它是繁重且耗时的，为此，本研究面向CPU+多GPU异构系统，基于CUDA编程模型，针对流行的预条件迭代方法，分析影响其性能的关键成分，深入研究构建与具体问题无关的矢量运算、内积和稀疏矩阵矢量乘的并行优化模型、并行预条件子算法及迭代方法并行优化框架，建立一整套可扩展的迭代方法并行优化模型和理论体系，以达到任意给定稀疏线性系统，能够自动快速地构建求解此稀疏线性系统的最优化多GPU并行迭代方法。通过在电磁计算中的应用，验证模型有效性和实用性。本项目为如何自动快速地建立最优性能的多GPU并行迭代方法提供了一个新的思路，对推动并行计算的发展有着重要的理论意义和实际应用价值。

在计算流体力学、电磁计算等诸多领域实际应用中，将描述自然现象的偏微分方程离散后，通常会得到一个稀疏的线性系统Ax=b，求解稀疏线性系统对整个应用问题的解决至关重要。求解的算法主要有两种：直接法和迭代法。相对于直接法，迭代法因运算量和存储量小而备受研究者们的青睐。随着计算机计算能力的提高，人们探讨问题的深度和广度也逐渐增大，要求必须提高线性系统的迭代求解效率，并行计算自然成为提高迭代法性能的有效手段首选。. 项目围绕建立高效的CPU/GPU异构并行迭代算法，面向CPU/GPU异构平台，基于CUDA编程模型，展开建立一系列高效并行求解算法的研究。主要的研究内容包括并行稀疏矩阵矢量乘、并行预条件子、并行迭代算法及性能优化等方面，取得了一系列研究成果。首先针对有散点和长零段的稀疏对角矩阵，提出了一种新的存储格式，克服了流行对角存储格式大量零填充的缺陷；进一步，对对角矩阵分类，针对每一类矩阵提出一种高效的存储格式和核函数，并通过设计的搜索引擎，使得任给一个对角稀疏矩阵，能自动识别其类别，从而选择最优的存储格式和核函数；其次，针对基于F范数的稀疏近似逆，提出了一种自适应线程分配的高并行静态稀疏近似逆预条件算法；一种排序的多GPU并行静态稀疏近似逆预条件算法；进一步，针对现有基于F范数的动态稀疏近似逆预条件子算法面对大规模问题出现内存溢出异常错误这一共性问题，以一种最流行的其算法为例，分析其错误原因，并给出了解决方法，且以此为基础，提出了一种面向GPU高并行动态稀疏近似逆预条件子算法；最后，在CPU/GPU异构平台上，构建了高性能迭代算法库，并针对对称正定的稀疏矩阵，研究构建了一个自动生成预条件共轭梯度算法系统。应用本研究提出的算法去解实际的应用问题，取得不错的效果。总结起来，本研究不仅为建立最优性能的GPU并行迭代方法提供了一个新的思路，而且对推动并行计算的发展也有着重要的实际应用价值。