- 1、本文档共21页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
Footer Text Footer Text 大规模稀疏矩阵并行计算 李修宇 QQ:295553381 * * 主流求解方法 直接法 GAUSS消去法 波前法 多波前法 迭代法 经典迭代法 Jacobi、SOR、SSOR 投影方法 CG、GMRES 预处理技术 不完全分解预处理条件 代数多重网格技术 * 大规模稀疏矩阵并行计算 * 矩阵性质对求解的影响 性质 影响 * 大规模稀疏矩阵并行计算 * 非零元的分布 带状分布 按块分布 …… 正定性 对称性 矩阵的存储方式 求解方法的选择 求解速度 …… 直接法 矩阵图重排:一般分为两大类,带宽缩减算法(也常称为外形缩减)和区域分解算法,应用较多的带宽缩减算法CM,RCM,GPS,Rosen算法。一般建议多重方法结合使用:全局方法的全局平衡性、局部方法的局部最优特性。 符号分解:确定非零元结构以及相应的消元索引,以便在实际数值分解前确定所需存储资源大小,避免数值分解中动态分配存储空间和复杂的索引策略。 构建消去树(elimination tree):确定分解节点之间的分解依赖,即确定分解的顺序并构成并行分解的层次结构。 * 大规模稀疏矩阵并行计算 * 直接法 数值分解:利用符号分解得到的非零元结构和索引沿消去树路径进行分解。 回代求解:包括前向(forward)和后向(backward)回代,可先构建消去依赖树或顶点着色技术实现并行回代求解。 在有限元领域应用最广的直接求解方法常使用带宽缩减或多区域分解的多波前法(multifrontal)。 * 大规模稀疏矩阵并行计算 * 对称正定矩阵的求解 * 大规模稀疏矩阵并行计算 * 对称矩阵的不完全分解 * 大规模稀疏矩阵并行计算 * 代数多重网格法 V-Cycle AMG(V循环多重网格法) W-Cycle AMG(W循环多重网格法) FMG(完全多重网格法:嵌套网格与V循环或者W循环结合) * 大规模稀疏矩阵并行计算 * 代数多重网格法 * 大规模稀疏矩阵并行计算 * 代数多重网格法 在粗网格上对残差方程进行求解(可用迭代法或直接解法)。 延拓或插值(interpolation):将细网格节点上的值通过分片插值延拓到细网格节点上。 通过光滑的残差对解进行修正。 后光滑(post-smooth),类似于前光滑。 * 大规模稀疏矩阵并行计算 * 代数多重网格法方法选择 对于非结构化网格形成的矩阵,SGS,SSOR方法不易并行,即使使用顶点着色技术,因其粗粒度的并行更适合于传统的多核处理器,并不非常适合GPU这样的细粒度并行的架构。 Jacobi方法不具有低通滤波性,因此推荐使用damp-Jacobi和PCG方法作为迭代子,其中damp-Jacobi方法的权值一般取为2/3。 在最粗网格上的计算推荐使用直接解法。 通常对于二阶椭圆边值问题,几何多重网格法具有更好的计算效率以及收敛速度。 * 大规模稀疏矩阵并行计算 * 代数多重网格法方法选择 一般遵循两个原则: 对于某个顶点,其邻接顶点要么属于粗网格顶点,要么至少连接到一个粗网格顶点。 粗网格顶点集应是任意两个粗网格节点不相邻的极大独立集。 有时很难同时满足两个条件,优先满足第一个条件时尽量满足第二个条件。 * 大规模稀疏矩阵并行计算 * 代数多重网格法方法选择 * 大规模稀疏矩阵并行计算 * 代数多重网格法的局限性 任意几何网格不适用于所有问题。 需要高质量的网格划分。 不便于编写通用的程序。 重点要解决的问题:网格粗化(对应于粗水平方程组)。 常用的网格粗化方法复杂:RS,RS2,RS3,Falgout,HIPS,CLJP。 * 大规模稀疏矩阵并行计算 * 大规模稀疏矩阵GPU计算程序优化设计探索 内核执行的优化 在大循环中具有大量入口参数的内核,其不变的参数在循环开始前放入常量内存。避免多余的内存操作 合理的网格布局。 有时将一个大grid拆分成多个阶段小的grid将有助于提高网格利用率,提高计算效率,例如对称矩阵的分解以及三角方程组的计算。 寄存器优化 一个线程中计算输出多个变量,用寄存器内存替换共享内存。 在Fermi上,如果程序中存取操作占多数,则对于大于32bit的数据, 以字节流的形式访问,因为对于例如双精度数据,这时只有一个warp调度器可以工作。 * 大规模稀疏矩阵并行计算 * 大规模稀疏矩阵GPU计算程序优化设计探索 合并访问 存取操作以half-warp(计算能力=1.3的硬件上)或者warp为单位(Fermi架构上)。 例如,在Fermi架构之前的硬件上,用Vector-CSR方法计算稀疏矩阵乘法,使用half-warp相对于使用warp有很高的性能提升。 提高线程网格的利用率,减少了线程块的开销。 *
您可能关注的文档
最近下载
- 2024首届全国红旗杯班组长大赛题库及答案(2)(2001-4000题).docx VIP
- 河南省漯河市郾城区2023-2024学年八年级上学期期末数学试题(含答案).doc
- 软件资格考试信息系统管理工程师(基础知识、应用技术)合卷(中级)试题与参考答案.docx VIP
- 东南大学《信号与系统》期末试卷及习题集合集_wrapper.pdf
- 2025年软件资格考试信息系统管理工程师(中级)(基础知识、应用技术)合卷试题及解答参考.docx VIP
- 南京邮电大学2021学年度第一学期《概率论与数理统计》期末考试试卷(A卷)及参考答案.docx
- 2024年上海市中考数学试题(含答案).docx VIP
- 信息系统管理工程师(基础知识、应用技术)合卷软件资格考试(中级)试题与参考答案(2025年).docx VIP
- 员工心态培训态度与能力积极的工作态度课件PPT.pptx VIP
- 王艳艳《工程招投标与合同管理》3第三章 工程项目投标2014.ppt VIP
文档评论(0)