基于三对角线性方程组的混合并行算法研究

摘要

许多大型科学与工程计算问题等应用领域都有涉及对于典型结构大型线性代数方程组的求解，且大型线性方程组的求解可以作为解决相应领域重大问题的基础。现今大型工程项目与科学研究中出现的计算问题越来越复杂，故对计算环境的要求越来越高，要想省时有效地解决大型或超大型复杂计算问题，就需要依靠并行计算技术的实现。近年，大型并行计算机或超级计算机的进一步发展为有效地求解大型或超大型复杂计算问题提供了可靠的保证。
　　本文基于OpenMP并行编程环境，研究三对角线性方程组的并行解法。对于该典型结构的线性方程组的并行解法，目前已有块划分算法、循环递减算法以及这些算法的改进算法等。划分算法和循环递减算法都是基于分治法思路，在近年兴起的的并行环境中也取得了显著的研究成果。
　　鉴于求解三对角线性方程组时循环递减算法的复杂回代求解过程，本文提出了一种新的优化并行算法来求解三对角线性方程组。采用混合并行模型，该算法结合了循环递减和划分算法。在并行机上，相比循环递减算法，该混合算法有更简洁的回代求解过程。本文中，操作数和算法执行时间被用于文中这些算法的性能分析与比较。基于这些衡量参数的结果，混合并行算法以混合方式采用多线程实现技术成功取得了比其他并行算法（循环递减和划分算法等）更好的性能效率。尤其，本文中提出的新算法有最少的标量操作数，且在多核计算机上求解规模大于一定数量的三对角线性方程组时有最短的算法执行时间。在求解大规模三对角方程组时，混合并行算法提高了循环递减和划分算法的性能分别为19.2％和13.2%。此外，为了进一步探索混合并行算法的性能，本文增加了混合算法中递减消元过程的次数，分析并实现了多次递减过程的混合并行算法的性能。通过比较单次递减过程混合算法和多次递减过程混合并行算法，得出一个结论，即增加循环递减算法的递减过程次数对混合并行算法的性能并没有有效的影响。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪 论

1.1课题研究背景及意义

1.2国内外的研究现状

1.3本文的主要工作及结构组织

第2章 OPENMP多线程介绍

2.1并行计算

2.2 OpenMP简介

2.3 OpenMP编程模型

2.4本章小结

第3章 三对角线性方程组的相关算法分析

3.1 Thomas算法

3.2 CR算法

3.3 PM算法

3.4本章小结

第4章 混合并行算法设计与分析

4.1混合算法设计

4.2 Single-Iteration算法分析

4.3 Multi-Iterations算法分析

4.4本章小结

第5章 算法性能分析与实验

5.1性能分析

5.2实验环境

5.3实验设计与结果分析

5.4本章小结

结论

参考文献

致谢

附录A 攻读硕士学位期间所发表的学术论文

附录B 攻读硕士学位期间所参与的项目