大规模稀疏矩阵并行计算

《大规模稀疏矩阵并行计算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、大规模稀疏矩阵并行计算李修宇QQ：2955533816/17/20211主流求解方法直接法GAUSS消去法波前法多波前法迭代法经典迭代法Jacobi、SOR、SSOR投影方法CG、GMRES预处理技术不完全分解预处理条件代数多重网格技术6/17/2021大规模稀疏矩阵并行计算2矩阵性质对求解的影响性质影响6/17/2021大规模稀疏矩阵并行计算3非零元的分布带状分布按块分布……正定性对称性矩阵的存储方式求解方法的选择求解速度……直接法矩阵图重排：一般分为两大类，带宽缩减算法（也常称为外形缩减）和区域分解算法，应用较多的带宽缩减算法CM，RCM，GPS，Rosen算法。

2、一般建议多重方法结合使用：全局方法的全局平衡性、局部方法的局部最优特性。符号分解：确定非零元结构以及相应的消元索引，以便在实际数值分解前确定所需存储资源大小，避免数值分解中动态分配存储空间和复杂的索引策略。构建消去树(eliminationtree)：确定分解节点之间的分解依赖，即确定分解的顺序并构成并行分解的层次结构。6/17/2021大规模稀疏矩阵并行计算4直接法数值分解：利用符号分解得到的非零元结构和索引沿消去树路径进行分解。回代求解：包括前向（forward）和后向（backward）回代，可先构建消去依赖树或顶点着色技术实现并行回代求解。在有限元领域应用最广

3、的直接求解方法常使用带宽缩减或多区域分解的多波前法（multifrontal）。6/17/2021大规模稀疏矩阵并行计算5对称正定矩阵的求解6/17/2021大规模稀疏矩阵并行计算6对称矩阵的不完全分解6/17/2021大规模稀疏矩阵并行计算7代数多重网格法V-CycleAMG（V循环多重网格法）W-CycleAMG（W循环多重网格法）FMG（完全多重网格法：嵌套网格与V循环或者W循环结合）6/17/2021大规模稀疏矩阵并行计算8代数多重网格法6/17/2021大规模稀疏矩阵并行计算9代数多重网格法在粗网格上对残差方程进行求解（可用迭代法或直接解法）。延拓或插值（i

4、nterpolation）：将细网格节点上的值通过分片插值延拓到细网格节点上。通过光滑的残差对解进行修正。后光滑（post-smooth），类似于前光滑。6/17/2021大规模稀疏矩阵并行计算10代数多重网格法方法选择对于非结构化网格形成的矩阵，SGS，SSOR方法不易并行，即使使用顶点着色技术，因其粗粒度的并行更适合于传统的多核处理器，并不非常适合GPU这样的细粒度并行的架构。Jacobi方法不具有低通滤波性，因此推荐使用damp-Jacobi和PCG方法作为迭代子，其中damp-Jacobi方法的权值一般取为2/3。在最粗网格上的计算推荐使用直接解法。通常对于二

5、阶椭圆边值问题，几何多重网格法具有更好的计算效率以及收敛速度。6/17/2021大规模稀疏矩阵并行计算11代数多重网格法方法选择一般遵循两个原则：对于某个顶点，其邻接顶点要么属于粗网格顶点，要么至少连接到一个粗网格顶点。粗网格顶点集应是任意两个粗网格节点不相邻的极大独立集。有时很难同时满足两个条件，优先满足第一个条件时尽量满足第二个条件。6/17/2021大规模稀疏矩阵并行计算12代数多重网格法方法选择6/17/2021大规模稀疏矩阵并行计算13代数多重网格法的局限性任意几何网格不适用于所有问题。需要高质量的网格划分。不便于编写通用的程序。重点要解决的问题：网格粗化（

6、对应于粗水平方程组）。常用的网格粗化方法复杂：RS，RS2，RS3，Falgout，HIPS，CLJP。6/17/2021大规模稀疏矩阵并行计算14大规模稀疏矩阵GPU计算程序优化设计探索内核执行的优化在大循环中具有大量入口参数的内核，其不变的参数在循环开始前放入常量内存。避免多余的内存操作合理的网格布局。有时将一个大grid拆分成多个阶段小的grid将有助于提高网格利用率，提高计算效率，例如对称矩阵的分解以及三角方程组的计算。寄存器优化一个线程中计算输出多个变量，用寄存器内存替换共享内存。在Fermi上，如果程序中存取操作占多数，则对于大于32bit的数据，以字节流

7、的形式访问，因为对于例如双精度数据，这时只有一个warp调度器可以工作。6/17/2021大规模稀疏矩阵并行计算15大规模稀疏矩阵GPU计算程序优化设计探索合并访问存取操作以half-warp（计算能力<=1.3的硬件上）或者warp为单位（Fermi架构上）。例如，在Fermi架构之前的硬件上，用Vector-CSR方法计算稀疏矩阵乘法，使用half-warp相对于使用warp有很高的性能提升。提高线程网格的利用率，减少了线程块的开销。6/17/2021大规模稀疏矩阵并行计算16大规模稀疏矩阵GPU计算程序优化设计探索分支优化消除分支结构的小技巧例