(74)专利代理机构无锡知之火专利代理事务所(特殊普通合伙)32318专利代理师朱爱进

　　本发明提供的面向异构众核架构的PCG预条件子方法,涉及异构众核架构计算的优化方法,对原矩阵A直接进行变换,获得了从矩阵范数或条件数而言具有更高的相似度对角块矩阵M1,同时利用每个从核分别负责一个对角块矩阵M1的子块矩阵求逆计算,保证了预条件子的并行性,减少通信带宽受限所导致的性能下降,提高了整体线性方程组求解的收敛性。

　　1.一种面向异构众核架构的PCG预条件子方法,包括诺依曼多项式,zn+1,(r‑(A‑D)*zn)*D‑1(z0)D‑1r,其中,A表示原系数矩阵,D为原矩阵对应对角矩阵,其特征在于,包括,

　　将对角矩阵D进行分块变形,沿原系数矩阵A进行采样,将主对角线核计算核心,生成块对角矩阵M,块对角矩阵M的子块矩阵为{C0(C1)C2,…C63},

　　对每个小矩阵块可通过cholesky法则进行不完全分解,生成新的块对角矩阵M1,即

　　对M1求逆即对M1中每一个子块矩阵求逆,求逆过程使用从核阵列的64核进行并行求逆,最终得到变换后的诺依曼多项式,

　　[0001]本发明涉及一种异构众核架构计算的优化方法,尤其涉及一种面向异构众核架构的PCG预条件子方法。

　　[0002]随着高性能计算的发展,研究基于传统数值计算方法的并行性显得越来越重要,大规模数值算法的设计和性能优化需在并行架构上得到有效利用。然而简单的数值算法在进行并行化实现过程中通常变得非常复杂。尽管使用迭代法求解大型线性方程组可以显著提高在高度并行架构上的并行性,但该方法不适用于所有问题。线性系统上的迭代收敛速度太慢,因此传统的迭代法在高性能并行系统上进行大规模并行化改造时收敛性难以保证,这使得迭代法在高性能并行系统上的难以得到有效发展。

　　[0003]CG方法求解大型稀疏线性方程组的常用方法之一,同时也是经典的krylov子空间迭代法之一。Krylov子空间法根据原系数矩阵构造关于解空间的投影从而得到一个更低维度的线性子空间,并从子空间中寻找近似解。构造后的子空间求解算法计算复杂度理论在O(n),也就是说理论上通过n次迭代(n表示解向量长度)后即可找到精确解。CG法利用了krylov子空间迭代法的思想通过对特殊矩阵(对称正定矩阵,SymmetricPositiveDefinite,SPD)解向量两两共轭性建立了与系数矩阵相关的二次泛函模型,同时利用该模型存在唯一极小值点的性质,再结合梯度下降算法找到原线性方程组解也就是对应二次泛函的极小值点。但是上述的CG发在系数矩阵的条件数较大时求解依然困难。因此数学家们又引入了PCG算法,即基于系数矩阵预处理的共轭梯度算法,一般称之为预条件子共轭梯度算法。这里的预条件子即为选取的预处理矩阵,构造预处理矩阵通常满足两个性质,一是矩阵形状接近原系数矩阵,相似越高收敛性越强,二是尽可能容易求逆,若求逆过程过于复杂则与矩阵预处理目的背道而驰。

　　[0004]PCG方法是大型稀疏线性方程求解算法中最常用的方法之一,也是提高迭代法收敛性的krylov子空间法最常用的方法之一。使用PCG算法求解线性代数系统时预条件子地选取通常对整体线性系统求解的收敛性起到决定性作用。现有的预条件方法可分为两大类,一类是以矩阵求逆过程作为基础PG中国电子技术有限公司的消元法。通过对选取的条件矩阵进行不完全因式分解,使其更容易进行矩阵求逆,经不完全因式分解后,原条件矩阵将变成上、下、对角矩阵(或上、下矩阵组合)相乘方式再对解元素逐次消元。另一类是使用迭代方法替代条件矩阵求逆过程直接对原共轭梯度向量进行预处理。基于矩阵分裂原理对矩阵预处理过程重新设计算法,将原有对条件矩阵求逆形式转化为对预处理梯度向量迭代逼近真实解的形式进行少量的迭代以近似求得所求预处理后的梯度向量。上述这两种方式是现阶段解决大型系数线性系统问题的最主要手段,同时上述两类方式的结合运用也是大规模并行化最有效的策略。

　　[0005]使用不完全因式分解法对系数矩阵求逆已经很早之前就被提出,其主要原因在于不完全因式分解法可以减少对原系数矩阵求逆的运行时间,同时减少矩阵预处理过程中可

　　能参与的SpMV操作。不完全因式分解方法在求解非对称系数矩阵问题非常有效,因此该方法也被广泛的运用在PCG算法的预条件子中。但是在解决对称正定的系数矩阵问题时由于矩阵的特殊性使其优越性并不明显。在大型超算系统上进行并行化改造过程中,由于消元法的数据依赖性使得单纯使用不完全因式分解求系数矩阵近似逆的并行化变得极为困难。因此基于Neumann系列的迭代技术在大型稀疏线性系统中,尤其是在对称正定线性系统中的并行化方法将逐渐成为超算系统上针对系数线性系统求解的有效重要方法之一。虽然现阶段在处理对称正定线性系统的PCG预条件算法中,根据非零元邻接图结构对系数矩阵进行按行(或列)着色重排序可以使不完全Cholesky分解之后的系数矩求逆的并行性得以提升,但是经验证测试可知该方法的并行度不高。

　　[0006]经典的KS(Krylov‑Schwarz)算法将krylov子空间法与Schwarz相结合,krylov能够利用迭代求解方式求出形如Au,f的近似解。本身算法易于并行,但对于大型线性系统而言其收敛性难以保证,因此添加条件矩阵的方式可提高子空间迭代的收敛性,同时结合Schwarz算法思想将整体求解域切分成相互独立的子区域集,从而实现算法高度并行性,同时也提高了原来稀疏线性系统并行化算法的鲁棒性。KS算法是通过基于便于求解近似逆的本地jacobian迭代法将子区域进一步切分称小子区域,在大区域内使用jacobian迭代法,而小子区域内则可以使用其他算法求解,通常是使用ILU分解的消元法或者迭代法(如Gauss‑Seidel,SOR)作为小区域内的求解算法。通过这种子区域再分技术极大增强了算法在不同体系架构上的普适性,尤其在现如今发展迅猛的异构众核架构上,这种天然混合并行层次结构将计算过程完美的映射到同样具有层次结构的异构众核架构的硬件计算部件上。因此现如今基于KS算法在面向大型超算并行系统上的研究愈加成为热点,然而现如今在大型异构众核架构研究基于KS思想的解决大型稀疏线性系统问题仍没有一个明确的,同时具备高度并行能力和收敛性的普适性算法。因此充分挖掘KS算法研究如何兼顾大型稀疏线性系统在异构体系架构的超算系统上高度并行能力和良好收敛性已成为主要挑战和机遇之一。

　　[0007] 针对上述无法同时兼顾高度并行能力和收敛性的问题,本发明提供的一种面向异构众核架构的PCG预条件子方法,能够有效解决基于国产申威异构众核体系架构的PCG预条件子迭代法并行性与收敛性难以兼顾的问题,在保证预条件子并行性的同时,与传统的迭代法相比具有更强的收敛性。

　　[0010] 将对角矩阵D进行分块变形,沿原系数矩阵A进行采样,将主对角线核计算核心,生成块对角矩阵M,块对角矩阵M的子块矩阵为{C0(C1 )C2,…C63} ,

　　[001 1] 对每个小矩阵块可通过cholesky法则进行不完全分解,生成新的块对角矩阵M1 ,即

　　[0012] 对M1求逆即对M1中每一个子块矩阵求逆,求逆过程使用从核阵列的64核进行并行

　　[0017] 本发明提供的面向异构众核架构的PCG预条件子方法,对原矩阵A直接进行变换,获得了从矩阵范数或条件数而言具有更高的相似度对角块矩阵M1 ,同时利用每个从核分别负责一个对角块矩阵M1的子块矩阵求逆计算,保证了预条件子的并行性,减少通信带宽受限所导致的性能下降,提高了整体线性方程组求解的收敛性。

　　[0018] 通过阅读参照以下附图对非限制性实施例所作的详细描述,本发明及其特征、外形和优点将会变得更加明显。在全部附图中相同的标记指示相同的部分。并未刻意按照比例绘制附图,重点在于示出本发明的主旨。

　　[0020] 下面结合本发明实施例中的附图,对本发明实施例中的技术方案进行说明,显然所描述的实施例仅仅是本发明的一部分实施例,而不是全部的实施例。因此,以下对附图中提供的本发明实施例中的详细描述并非旨在限制要求保护的本发明的范围,而是仅仅表示本发明的选定实施例。基于本发明的实施例,本领域技术人员在没有作出创造性劳动的前提下所获得的所有其他实施例,都属于本发明的保护范围。

　　[0022] 原始的诺依曼多项式,zn+1,(r‑ (A‑D)*zn)*D‑1 (z0)D‑1r,其中,A表示原系数矩阵,D为原矩阵对应对角矩阵,使用原始一阶多项式迭代法可充分提高对梯度向量预处理算法的并行行,但是鲁棒性较差,对于复杂度较高的系数矩阵而言收敛性也较差,因此,本发明实施例1中

　　[0023] S101 ,将对角矩阵D进行分块变形,沿原系数矩阵A进行采样,将主对角线核计算核心,生成分块对角矩阵M,分块对角矩阵M的子块矩阵为{C0(C1 )C2,…C63} ,如图1所示,黑色方块表示子块矩阵,

　　[0024] S102,对每个小矩阵块可通过cholesky法则进行不完全分解,生成新的块对角矩阵M1,即

　　[0025] 对M1求逆即对M1中每一个子块矩阵求逆,求逆过程使用从核阵列的64核进行并行求逆,

　　[0029] 由于M1的子矩阵块之间不存在数据依赖性,因此各从核在计算 时无需核间数据交互,可大大减少由于片上通信带宽受限所导致的性能下降。

　　[0030] 共轭梯度法的收敛速度受制于原矩阵A的条件数,同时浮点运算的舍入误差也会影响共轭梯度法的向量的正交性,预处理技术的采用能有效改善线性代数方程组稀疏矩阵的条件数,以极小代价构造与A足够接近的预处理矩阵M,使得M‑1A或AM‑1 ,LAL‑T的特征值更加集中,达到加速收敛的效果。但对于不完全Cholesky分解而言其近似矩阵M与A仍然存在差异,因此收敛性同样还是会受到制约,因此在本发明实施例1中直接使用了原矩阵A进行变换,与原矩阵A相比其无论从矩阵范数或条件数而言具有更高的相似度,并同时在求梯度向量时增加对全局网格单元边界点的更新过程,加快了全局沿梯度方向的搜索速度,提高了整体线性方程组求解的收敛性。

　　[0031] 以上所述仅为本发明的优选实施例,并非因此限制本发明的专利范围,凡是利用本发明说明书及附图内容所作的等效结构变换,或直接或间接运用在其他相关的技术领域,均同理包括在本发明的专利保护范围内。