《最新大规模稀疏矩阵并行计算ppt课件PPT课件》由会员分享，可在线阅读，更多相关《最新大规模稀疏矩阵并行计算ppt课件PPT课件（22页珍藏版）》请在金锄头文库上搜索。
1、大规模稀疏矩阵并行计算大规模稀疏矩阵并行计算pptppt课件课件主流求解方法直接法oGAUSS消去法o波前法o多波前法迭代法o经典迭代法Jacobi、SOR、SSORo投影方法CG、GMRESo预处理技术不完全分解预处理条件o代数多重网格技术8/7/20242大规模稀疏矩阵并行计算代数多重网格法8/7/20249大规模稀疏矩阵并行计算代数多重网格法在粗网格上对残差方程进行求解（可用迭代法或直接解法）。延拓或插值（interpolation）：将细网格节点上的值通过分片插值延拓到细网格节点上。通过光滑的残差对解进行修正。后光滑（post-smooth），类似于前光滑。8/7/202410大规模稀
2、疏矩阵并行计算代数多重网格法方法选择对于非结构化网格形成的矩阵，SGS，SSOR方法不易并行，即使使用顶点着色技术，因其粗粒度的并行更适合于传统的多核处理器，并不非常适合GPU这样的细粒度并行的架构。Jacobi方法不具有低通滤波性，因此推荐使用damp-Jacobi和PCG方法作为迭代子，其中damp-Jacobi方法的权值一般取为2/3。在最粗网格上的计算推荐使用直接解法。通常对于二阶椭圆边值问题，几何多重网格法具有更好的计算效率以及收敛速度。8/7/202411大规模稀疏矩阵并行计算代数多重网格法方法选择一般遵循两个原则：o对于某个顶点，其邻接顶点要么属于粗网格顶点，要么至少连接到一个粗
3、网格顶点。o粗网格顶点集应是任意两个粗网格节点不相邻的极大独立集。有时很难同时满足两个条件，优先满足第一个条件时尽量满足第二个条件。8/7/202412大规模稀疏矩阵并行计算代数多重网格法方法选择8/7/202413大规模稀疏矩阵并行计算代数多重网格法的局限性任意几何网格不适用于所有问题。需要高质量的网格划分。不便于编写通用的程序。重点要解决的问题：网格粗化（对应于粗水平方程组）。常用的网格粗化方法复杂：RS，RS2，RS3，Falgout，HIPS，CLJP。8/7/202414大规模稀疏矩阵并行计算大规模稀疏矩阵GPU计算程序优化设计探索内核执行的优化o在大循环中具有大量入口参数的内核，其
4、不变的参数在循环开始前放入常量内存。避免多余的内存操作o合理的网格布局。o有时将一个大grid拆分成多个阶段小的grid将有助于提高网格利用率，提高计算效率，例如对称矩阵的分解以及三角方程组的计算。寄存器优化o一个线程中计算输出多个变量，用寄存器内存替换共享内存。o在Fermi上，如果程序中存取操作占多数，则对于大于32bit的数据， 以字节流的形式访问，因为对于例如双精度数据，这时只有一个warp调度器可以工作。8/7/202415大规模稀疏矩阵并行计算大规模稀疏矩阵GPU计算程序优化设计探索合并访问存取操作以half-warp（计算能力b )a=c; else a=0; 可以替换为：a=(
5、 ab )*c;8/7/202417大规模稀疏矩阵并行计算大规模稀疏矩阵GPU计算程序优化设计探索指令按照half-warp（计算能力=1.3）或者warp对齐。例如：每个线程计算输出7个变量，每个变量的计算差别很大。这时可以让block的第一个warp的所有线程计算第一个变量，第二个warp计算第二个变量，可以利用函数指针（在计算能力=1.3的硬件上可以使用对齐到warp边界的控制语句，这时并不会在warp内造成路径分支（uniform divergence），通过warp编号来选择；但是对于相近的计算则不建议使用函数指针反而会降低效率。8/7/202418Footer Text大规模稀疏矩
6、阵GPU计算程序优化设计探索对于矢量类型数据，使用SOA（Structure of Array）格式代替例如，float4可使用 xxxx yyyy zzzz wwww的存储结构代替，一般更有效。在Fermi硬件上，读float4类型的数据，虽然显存带宽可以被充分利用，但是会有部分CUDA Core暂时闲置，并且必须等待两次的存储请求完成才开始计算，而如果使用SOA，则在其后的各分量独立的计算中可以更有效隐藏延迟。8/7/202419大规模稀疏矩阵并行计算大规模稀疏矩阵GPU计算程序优化设计探索如果按照显式的warp模式进行操作，则尽量将每个warp对应操作的存储器起始地址对齐。如果每个warp的活动线程数小于75%左右时，则不建议使用。数据结构应该和网格布局相互适应来有效利用存储控制器的带宽。例如矩阵的转置。8/7/202420大规模稀疏矩阵并行计算谢谢！8/7/202421大规模稀疏矩阵并行计算
