核外并行求解线性方程组的设计与实现

摘要

由于大型线性方程组在化学工程、天气预报、数值方法等领域中都有广泛应用,使得对其求解的研究一直是个热点。随着科学技术的迅猛发展,人们所需要处理的数据量迅速增长。虽然近些年来计算机硬件迅猛发展,但是内存容量常常不能满足涉及到大数据量计算问题的存储需求。目前各种类型的并行处理系统已成为科研或求解重大规模问题的主流计算环境。为了适应新的计算环境、追求更高的求解速度和更大的求解容量,集群系统因其是具有良好性价比的并行处理机系统已被广泛用于科研和应用中。因此在集群环境下对大型线性方程组的并行求解方法的研究和设计,就具有非常重要的理论和实际意义。求解线性方程组的方法有很多,由于本文求解的线性方程组的系数矩阵是对称的,采用Cholesky分解的方法求解。本文对基于集群系统下线性方程组的串并行算法进行了细致的研究和分析,主要内容包括:
　　 (1)实现了MPI编程环境下求解线性方程组的Cholesky分解的串并行核内算法。
　　 (2)通过分析串并行Cholesky分解核内算法,给出了存在的问题及优化方法。
　　 (3)在核内并行算法的基础上,提出了核外预取算法的并行方案；不仅成功的解决了内存容量小的问题,而且还有效的缩短了I／O与CPU速度间的差距,提高了Cholesky分解的效率。
　　 (4)在核外并行算法的基础上,提出了数据重用的方法；通过将当前已经读入内存而下一次仍需用到的数据继续的留在内存,来降低I／O操作的时间,实现了对核外数组的合理调度与高效访问。
　　 本文搭建了基于Linux的并行计算平台,构建了此平台下的MPI并行程序设计环境。同时将本文提出的核外预取和数据重用算法在此平台上进行了测试,并对实验结果进行了性能分析。结果表明,本文设计的算法能够很好的在小内存的集群上运行大规模线性方程组的Cholesky求解程序。

目录

文摘

英文文摘

1 绪论

1.1 线性方程组的研究背景及意义

1.2 研究现状

1.3 本文工作及内容安排

2 并行处理

2.1 并行体系结构

2.2 并行软件环境

2.3 并行算法及其评价

2.4 环境的搭建

2.4.1 硬件环境

2.4.2 软件环境

3 基于Cholesky的线性方程组求解算法

3.1 串行处理

3.1.1 处理流程

3.1.2 问题与改造

3.2 并行处理

3.2.1 处理流程

3.2.2 算法优化

3.2.3 算法优化分析

3.3 现存问题及解决方法

4 基于预取的方法并行求解线性方程组的设计与实现

4.1 算法思想与策略

4.2 算法描述

4.3 复杂度分析

4.4 实验测试与结果分析

5 基于数据重用的方法并行求解线性方程组的设计与实现

5.1 算法思想与策略

5.2 算法描述

5.3 复杂度分析

5.4 实验测试与结果分析

6 结论

参考文献

攻读硕士学位期间发表学术论文情况

致谢