CPU/GPU异构平台下并行保结构算法的研究

With the aim to make the structure-preserving algorithm accommodate the requirements of solving large scale problems, this project investigates the equations obtained by the structure-preserving algorithms and presents a series of CPU/GPU heterogeneous parallel algorithms, which is efficient, stable and accurate, with the principle of preserving the original characteristic of problems as many as possible. The content of this project includes the following aspects. Firstly, several representatives of structure-preserving algorithms, such as local structure-preserving algorithm, multi--symplectic algorithm, discrete variational derivative method, splitting method etc., are chosen, and then are studied how to spread them to solve Maxwell's equations; Secondly, on the basis of analyzing the characteristic of the discrete equations by the above chosen structure-preserving algorithm, CPU/GPU heterogeneous parallel algorithms are suggested to solve them; Thirdly, in order to speed up the convergence of our proposed algorithms, we will study the effective parallel preconditioners which can preserve the original characteristic of problems as many as possible, and is easy to be parallelized on the CPU/GPU heterogeneous platform; Finally, we will do research on the heterogeneous programming model, effectively cooperative methods, optimization strategies and performance evaluation methods etc.. This project will establish a relatively perfective CPU/GPU heterogeneous parallel solver for making structure-preserving algorithms accommodate the requirements of solving large scale problems, which will not only be helpful for establishing the basic theory of the structure-preserving algorithms and extending its applied fields, but also be meaningful for the development of promoting CPU/GPU heterogeneous parallel computing.

本项目目标是通过分析保结构算法离散得到的系统方程组的结构特征，遵循尽可能保持和体现保结构算法原有保某种结构特征的原则，研究CPU/GPU异构并行的高效、稳定、精确求解的并行算法，使其适合大规模科学工程计算问题的需要。基于此，本项目选择以解决电磁波问题为例，重点考虑选择局部保结构算法、多辛算法、离散变分积分方法、分裂方法等方法，研究推广构建电磁波方程的保结构算法；分析离散得到的方程组系数矩阵特征，研究CPU/GPU异构的高效并行求解算法；研究保持某种结构特征，并适宜于CPU/GPU异构的高效并行预条件子；研究异构并行程序设计的异构编程模式、高效的协同方式、优化策略及性能评价方法等。本项目将形成一套相对完善的适宜于保结构算法解决大规模问题的CPU/GPU异构并行求解器，对完善保结构算法的基本理论、拓宽其应用领域，以及推动CPU/GPU异构并行计算的发展都有着重要的价值和意义。

保结构算法作为当前流行的数值方法之一，是上世纪80年代由我国科学家冯康先生首先提出的。通过它离散偏微分方程得到的数值格式，有着保某守恒量，并能够保证随着时间演化格式一直保持稳定的特性，因此一直受研究者们的关注。然而，由于保结构算法离散得到的数值格式，都是隐格式，为了发挥其在大尺度问题上的优势，与并行计算结合必不可少。. 项目围绕保结构算法离散电磁波方程得到的线性系统，基于CPU/GPU异构框架，展开建立一系列高效并行求解算法的研究。主要的研究内容包括并行预条件子、并行稀疏矩阵矢量乘、并行迭代算法以及性能优化和评价策略等方面，取得了一系列研究成果。首先，探索突破了不完全Cholesky分解 (MIC) 预条件子强串行性，不易并行的特性，提出了一种新颖的GPU并行MIC 预条件子算法；基于诺依曼多项式分解技术，提出了一种GPU加速的SSOR(Symmetric successive over-relaxation) 稀疏近似逆预条件子；其次，提出了矢量运算决策树、矢量内积决策树，通过这些决策树，可以自动获得高效并行的矢量运算和内积算法；提出了若干高效的GPU并行稀疏矩阵矢量乘（SpMV）算法；进一步，提出了一种新颖的GPU并行MIC 预条件共轭梯度 (PCG) 算法、一种面向GPU的PCG并行优化模型、一种高效并行的GMRES算法；最后，在CPU/GPU异构平台上，针对对称正定的稀疏矩阵，研究构建了一种与具体问题无关的SpMV并行优化框架。任给一个稀疏矩阵，通过我们提出的优化框架，能够自动、快速和精确地为分配到每一个GPU上的矩阵块选择出最合适的稀疏压缩存储格式和实现方法。通过应用去解实际的电磁场问题方程，取得不错的应用效果。总结起来，本项目研究不仅为推动大尺度的电磁波问题的研究发展有着重要意义，而且对推动并行计算的发展也有着重要的实际应用价值。