对称特征问题的并行算法与并行软件
文献类型：学位论文
| 作者 | 赵永华 |
| 学位类别 | 博士 |
| 答辩日期 | 2006-06-02 |
| 授予单位 | 中国科学院软件研究所 |
| 授予地点 | 软件研究所 |
| 关键词 | 对称矩阵 特征值 并行算法 三对角化 分而治之 块算法 块存储 SMP集群 MPI/OpenMP 混合编程模型 |
| 中文摘要 | 大规模对称矩阵特征问题存在于许多科学计算领域与工程设计中，而且在许多科学应用的软件代码中也包含着对称特征问题的求解。然而随着求解问题规模的不断增大，存储空间和计算时间正在限制着这些计算问题的求解。因此对这些代码的并行化已成为必然。而对已有的许多并行代码，如计算量子化学的并行代码和电子结构并行代码MP_Quest，稠密对称特征问题求解占据着整个运行时间的极大部分。因此对称特征问题并行算法和实现技术的研究是非常必要的。 本文工作主要围绕着广义对称特征问题有效并行算法设计和实现技术。并行算法的研究充分考虑了处理器网格结构、数据在处理器的分布以及块算法技术等对算法性能的影响，主要目的是降低并行算法存在的通信开销、改善负载平衡，并尽量开拓算法的并行性。另外，针对现代并行机的多级体系结构，探讨了在这种计算平台上的编程模型和有效的并行算法设计方法。所取得成果包括： 本文给出了将广义对称特征问题转化为标准特征问题的并行算法。从降低已有并行算法的通信开销和增加算法并行性考虑，该并行算法将Cholesky分解结合到广义对称特征问题标准化转换中。新算法可显著改善已有并行算法的性能和可扩展性。另外本文给出了一个有效求解具有多个右端项的三角矩阵方程AX=B的并行算法。在使用块算法技术时设计并行算法时，普遍采用的方法是将块算法和块存储结合在一起。这在LU分解和广义对称特征问题标准化等问题的并行计算中确能带来益处。而对于对称矩阵三对角化并行，算法块和数据块的分离可改善已有并行块算法中的负载平衡和可扩展性。基于这一研究，本文给出了不依赖于存储块的对称矩阵三对角化并行块算法和回转换(backtransformatiom)求解原问题特征向量的并行块算法。并提出了存在于回转换算法中的数据重分配策略。基于秩-2修正+laguerre迭代法求解三对角特征问题的分而治之方法，本文给出了一个并行算法。 针对SMP集群系统讨论了MPI/OpenMP混合并行编程模型及其实现方法，并探讨了SMP集群上的并行算法设计方法。基于该系统所具有通信多级性和并行多级性，本文提出了集群级和节点级两级并行算法设计观点。并且基于前面对称特征问题并行算法的研究，给出了三对角化转换和三对角特征问题求解在SMP集群上的混合并行算法。矩阵三对角化的混合并行算法采用了数据在SMP节点间和节点内的动态和静态两种分布方式。节点内线程间并行采用了粗粒度并行模式，这使得节点内线程并行达到了完全的负载平衡。三对角特征问题的混合并行算法采用了细粒度+粗粒度多粒度模式和任务分配的动态调用方法，改善了原MPI算法中的负载平衡问题、降低了通信开销。 基于本文给出的并行算法，开发了对称特征问题并行求解器PSEPS。PSEPS的运行环境是支持MPI消息传递的多种类型体系结构的并行计算机。PSEPS的运行要求BLAS库和LAPACK库。该求解器使用了二维块-循环数据分布。 |
| 语种 | 中文 |
| 公开日期 | 2011-03-17 |
| 页码 | 160 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/6122]  |
| 专题 | 软件研究所_中科院软件所_中科院软件所 |
| 推荐引用方式 GB/T 7714 | 赵永华. 对称特征问题的并行算法与并行软件[D]. 软件研究所. 中国科学院软件研究所. 2006. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。