单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Footer Text,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Footer Text,*,大规模稀疏矩阵并行计算,李修宇,QQ,：,295553381,10/27/2024,1,主流求解方法,直接法,GAUSS,消去法,波前法,多波前法,迭代法,经典迭代法,Jacobi,、,SOR,、,SSOR,投影方法,CG,、,GMRES,预处理技术,不完全分解预处理条件,代数多重网格技术,10/27/2024,大规模稀疏矩阵并行计算,2,矩阵性质对求解的影响,性质,影响,10/27/2024,大规模稀疏矩阵并行计算,3,非零元的分布,带状分布,按块分布,正定性,对称性,矩阵的存储方式,求解方法的选择,求解速度,直接法,矩阵图重排：一般分为两大类，带宽缩减算法（也常称为外形缩减）和区域分解算法，应用较多的带宽缩减算法,CM,，,RCM,，,GPS,，,Rosen,算法一般建议多重方法结合使用：全局方法的全局平衡性、局部方法的局部最优特性符号分解：确定非零元结构以及相应的消元索引，以便在实际数值分解前确定所需存储资源大小，避免数值分解中动态分配存储空间和复杂的索引策略。
构建消去树,(elimination tree),：确定分解节点之间的分解依赖，即确定分解的顺序并构成并行分解的层次结构10/27/2024,大规模稀疏矩阵并行计算,4,直接法,数值分解：利用符号分解得到的非零元结构和索引沿消去树路径进行分解回代求解：包括前向（,forward,）和后向（,backward,）回代，可先构建消去依赖树或顶点着色技术实现并行回代求解在有限元领域应用最广的直接求解方法常使用带宽缩减或多区域分解的多波前法（,multifrontal,）10/27/2024,大规模稀疏矩阵并行计算,5,对称正定矩阵的求解,10/27/2024,大规模稀疏矩阵并行计算,6,对称矩阵的不完全分解,10/27/2024,大规模稀疏矩阵并行计算,7,代数多重网格法,V-Cycle AMG,（,V,循环多重网格法）,W-Cycle AMG,（,W,循环多重网格法）,FMG,（完全多重网格法：嵌套网格与,V,循环或者,W,循环结合）,10/27/2024,大规模稀疏矩阵并行计算,8,代数多重网格法,10/27/2024,大规模稀疏矩阵并行计算,9,代数多重网格法,在粗网格上对残差方程进行求解（可用迭代法或直接解法）。
延拓或插值（,interpolation,）：将细网格节点上的值通过分片插值延拓到细网格节点上通过光滑的残差对解进行修正后光滑（,post-smooth,），类似于前光滑10/27/2024,大规模稀疏矩阵并行计算,10,代数多重网格法方法选择,对于非结构化网格形成的矩阵，,SGS,，,SSOR,方法不易并行，即使使用顶点着色技术，因其粗粒度的并行更适合于传统的多核处理器，并不非常适合,GPU,这样的细粒度并行的架构Jacobi,方法不具有低通滤波性，因此推荐使用,damp-Jacobi,和,PCG,方法作为迭代子，其中,damp-Jacobi,方法的权值一般取为,2/3,在最粗网格上的计算推荐使用直接解法通常对于二阶椭圆边值问题，几何多重网格法具有更好的计算效率以及收敛速度10/27/2024,大规模稀疏矩阵并行计算,11,代数多重网格法方法选择,一般遵循两个原则：,对于某个顶点，其邻接顶点要么属于粗网格顶点，要么至少连接到一个粗网格顶点粗网格顶点集应是任意两个粗网格节点不相邻的极大独立集有时很难同时满足两个条件，优先满足第一个条件时尽量满足第二个条件10/27/2024,大规模稀疏矩阵并行计算,12,代数多重网格法方法选择,10/27/2024,大规模稀疏矩阵并行计算,13,代数多重网格法的局限性,任意几何网格不适用于所有问题。
需要高质量的网格划分不便于编写通用的程序重点要解决的问题：网格粗化（对应于粗水平方程组）常用的网格粗化方法复杂：,RS,，,RS2,，,RS3,，,Falgout,，,HIPS,，,CLJP,10/27/2024,大规模稀疏矩阵并行计算,14,大规模稀疏矩阵,GPU,计算程序优化设计探索,内核执行的优化,在大循环中具有大量入口参数的内核，其不变的参数在循环开始前放入常量内存避免多余的内存操作,合理的网格布局有时将一个大,grid,拆分成多个阶段小的,grid,将有助于提高网格利用率，提高计算效率，例如对称矩阵的分解以及三角方程组的计算寄存器优化,一个线程中计算输出多个变量，用寄存器内存替换共享内存在,Fermi,上，如果程序中存取操作占多数，则对于大于,32bit,的数据，以字节流的形式访问，因为对于例如双精度数据，这时只有一个,warp,调度器可以工作10/27/2024,大规模稀疏矩阵并行计算,15,大规模稀疏矩阵,GPU,计算程序优化设计探索,合并访问,存取操作以,half-warp,（计算能力,b),a=c;,else,a=0;,可以替换为：,a=(ab)*c;,10/27/2024,大规模稀疏矩阵并行计算,17,大规模稀疏矩阵,GPU,计算程序优化设计探索,指令按照,half-warp,（计算能力,=1.3,）或者,warp,对齐。
例如：每个线程计算输出,7,个变量，每个变量的计算差别很大这时可以让,block,的第一个,warp,的所有线程计算第一个变量，第二个,warp,计算第二个变量，,可以利用函数指针（在计算能力,=1.3,的硬件上可以使用对齐到,warp,边界的控制语句，这时并不会在,warp,内造成路径分支（,uniform divergence,），通过,warp,编号来选择；但是对于相近的计算则不建议使用函数指针反而会降低效率10/27/2024,Footer Text,18,大规模稀疏矩阵,GPU,计算程序优化设计探索,对于矢量类型数据，使用,SOA,（,Structure of Array,）格式代替,例如，,float4,可使用,xxxx yyyy zzzz wwww,的存储结构代替，一般更有效在,Fermi,硬件上，读,float4,类型的数据，虽然显存带宽可以被充分利用，但是会有部分,CUDA Core,暂时闲置，并且必须等待两次的存储请求完成才开始计算，而如果使用,SOA,，则在其后的各分量独立的计算中可以更有效隐藏延迟10/27/2024,大规模稀疏矩阵并行计算,19,大规模稀疏矩阵,GPU,计算程序优化设计探索,如果按照显式的,warp,模式进行操作，则尽量将每个,warp,对应操作的存储器起始地址对齐。
如果每个,warp,的活动线程数小于,75%,左右时，则不建议使用数据结构应该和网格布局相互适应来有效利用存储控制器的带宽例如矩阵的转置10/27/2024,大规模稀疏矩阵并行计算,20,谢谢！,10/27/2024,21,大规模稀疏矩阵并行计算,。
