两种Krylov子空间算法的并行性能改进研究

摘要

寻求大型稀疏线性方程组的高效并行解法是当前大规模科学计算中亟待解决的热点问题。Krylov子空间算法是求解大型稀疏线性方程组最流行和最有效的迭代方法之一，其并行计算主要考虑矩阵向量乘和内积计算。目前通过适当编码，矩阵向量乘在并行计算时不会造成严重性能降低的通信问题。但内积计算并非如此，由于内积计算需要全局通信，在分布式并行计算环境下其成为高效并行计算的瓶颈。
　　 ORTHOMIN(m)算法和GCR(k)算法是两种Krylov子空间算法，为减少两算法内积计算引起的全局通信以提高并行性能，本文以油藏数值模拟问题为应用背景分别对两算法做了如下工作：
　　 首先利用ORTHOMIN(m)算法的固有性质改变其计算次序，给出了该算法的改进形式，其次对算法进行了并行设计、理论分析，最后通过求解油藏数值模拟问题给出数值实验。同ORTHOMIN(m)算法相比，改进算法与ORTHOMIN(m)算法具有相同的收敛性，在分布式并行计算环境下进行并行计算时改进算法用连续内积计算代替了ORTHOMIN(m)算法分离的内积计算，消除了ORTHOMIN(m)算法两次内积计算的数据相关性，使同步开销次数减少为ORTHOMIN(m)算法的一半进而加大了计算时间相对通信时间的比重，提高了并行效率。理论分析表明当处理机台数较多时改进算法比ORTHOMIN(m)算法的并行计算时间要快，有更好的加速比及可扩展性。数值实验结果也表明改进算法的并行性能要优于ORTHOMIN(m)算法，更利于油藏数值模拟问题的并行求解。
　　 对于GCR(k)算法，利用同样的方法给出了该算法的改进形式，并给出算法的并行设计、理论分析，且通过求解油藏数值模拟问题给出数值实验。与ORTHOMIN(m)算法类似，改进算法与GCR(k)算法具有相同的收敛性，在分布式并行计算环境下进行并行计算时改进算法使同步开销次数减少为GCR(k)算法的一半，提高了并行效率。理论分析同样表明当处理机台数较多时改进算法比GCR(k)算法的并行计算时间要快，有更好的加速比及可扩展性。数值实验结果也同样表明改进算法的并行性能要优于GCR(k)算法，更利于油藏数值模拟问题的并行求解。

目录

文摘

英文文摘

第一章 绪论

1.1 研究背景

1.2 Krylov子空间算法的并行化研究现状

1.3 论文主要工作

1.4 论文结构

第二章 并行计算及Krylov子空间算法

2.1 引言

2.2 并行计算机模型

2.2.1 并行计算机结构模型

2.2.2 并行计算模型

2.2.3 并行编程模型

2.3 并行算法设计

2.3.1 并行算法的定义和分类

2.3.2 并行算法设计方法

2.3.3 并行算法性能度量

2.4 Krylov 子空间的概念及其算法分类

2.4.1 Krylov子空间的概念

2.4.2 Krylov子空间算法的分类

2.5 Krylov子空间算法的并行化策略

2.6 小结

第三章 ORTHOMIN(m)算法的并行计算

3.1 引言

3.2 Krylov子空间方法-GCR 算法

3.3 ORTHOMIN(m)算法及其改进

3.3.1 ORTHOMIN(m)算法的并行设计

3.3.2 改进算法的并行设计

3.4 算法分析与比较

3.5 数值实验-油藏数值模拟问题的求解

3.6 小结

第四章 GCR(k)算法的并行计算

4.1 引言

4.2 GCR(k)算法及其改进

4.2.1 GCR(k)算法的并行设计

4.2.2 改进算法的并行设计

4.3 算法分析与比较

4.4 数值实验-油藏数值模拟问题的求解

4.5 小结

第五章 总结及未来的工作

5.1 总结

5.2 未来的工作

致谢

攻读硕士学位期间从事的科研工作

参考文献