多项式—PCG并行算法研究

摘要

计算机网络的高速发展和微机处理芯片性能的不断提高,为并行计算提供了一个很好的网络平台.同时由于商业化的硬件和软件的不断发展,也为计算机网络提供了高性价比、高可用性的计算.这种高性能计算系统一般被称为机群计算系统.近年来,机群计算系统已经成为学术界、商业界和其它行业界研究的热点.PVM(Parallel Virtual Machine)并行虚拟机,是能使一群松散连接的计算机用来作为一台并行计算资源的软件系统.这就使大规模计算问题可以通过使用众多计算机聚集来的计算能力和内存来降低低成本地解决,PVM可移植性好、低性价比、编程环境的兼容性和运行平台的广泛性,使PVM拥有着大量的用户,现已成为世界上分布式计算事实上的标准.该文是将并行机群计算系统应用到解决电法勘探中,在使用有限元方法(FEM)时所产生的大型线性方程组求解问题上.有限元方法是工程学科的重要工具,被证明为在许多科学和工程领域中连续物理系统模拟的一种普遍方法,但缺点是随着工程结构分析问题越来越复杂,在结构分析中,为保证数值解的精度,在使用有限元方法离散处理时,往往要用大量的高阶单元将结构剖分得很密,这时相应的代数方程组的系数矩阵的阶数很高,即使用目前速度最快的串行机来进行求解,费时仍然太多且问题的规模受到内存容量的限制.FEM处理结构分析问题的最基本思想是需要对域进行离散化(一个网格或者模型),这和机群分而治之的思想相似.因此,有限元节点代码可以被并行化、并能在基于不同的PVM机群结点上运行.可用C++编写程序,通过调用PVM库函数提供对并行虚拟机的访问.有限元法产生的线性方程组使用多项式预处理共轭梯度(P-PCG)算法求解,多项式预处理共轭梯度(P-PCG)法与有限元法联系的十分自然,因为两者都是采用相似的最小化过程.多项式预处理共轭梯度算法的高度向量化,且不需要构造全局矩阵,它在大规模并行结构中能被有效地实现.

目录

文摘

英文文摘

第一章绪论

1.1论题提出的背景

1.2目前国内外的研究现状

1.3研究目的及意义

第二章网络机群并行计算系统

2.1高性能计算机与网络机群并行计算系统

2.1.1高性能计算机的应用需求

2.1.2典型并行计算系统简介

2.2机群并行计算系统的组成

2.2.1机群并行系统的结构

2.2.2机群并行系统的结点

2.2.3机群并行系统的通信环境——互连网络

2.2.4机群行系统的编程环境

2.3机群并行系统的特点

2.4机群并行系统的可扩展性

2.4.1可扩展性并行系统结构

2.4.2可扩展性编程

2.5机群并行系统设计中的关键技术

2.5.1可用性支持

2.5.2单一系统映象

2.5.3作业管理

2.5.4高效通信

2.5.5并得编译技术

2.5.6并行调试技术

2.5.7故障恢复与容错

2.5.8其它原因

2.6机群应用前景

第三章基于消息传递的并行计算环境——PVM

3.1消息传递环境

3.1.1引言

3.1.2 基于消息传递的并行程序设计

3.2 PVM概述

3.2.1PVM的产生和发展

3.2.2 PVM系统结构

3.2.3 PVM系统的功能

3.2.4 PVM系统的特征

3.3 PVM系统的通信机制

3.4 PVM系统的程序设计

3.4.1编程模式

3.4.2Hello,World示例

第四章有限元法在电法勘探中的应用

4.1引言

4.2有限元分析

4.2.1产生与发展

4.2.2基本思想

4.3有限元法的三维电阻率算法

4.3.1偏微分方程与与边值问题

4.3.2网格剖分

4.3.3线性插值

4.3.4变分问题离散化

4.3.5合成

4.4线性方程组的分析

第五章多项式预处理共轭梯度法求解线性方程组

5.1引言

5.2 JOHNSON.多项式预处理共轭梯度法

5.3基于LAGRANGE插值多项式的预条件共轭梯度法

5.4基于线性插值多项式的四分预条件共轭梯度法

5.5四分预条件共轭梯度法的改进

5.6 SAAD多项式预处理共轭梯度法

5.7数值试验及分析

5.8两种预处理方法的VC++6.0实现

第六章机群并行计算的实现及算例

6.1机群并行计算环境的系统结构：PC机群

6.2串行程序设计

6.3并行程序设计

6.3.1任务分解

6.3.2 PVM编程模式选择

6.3.3主程序

6.3.4从程序

6.3.5进程同步

6.3.6消息传递方式的选择

6.4工程算例

6.5小结

结论

参考文献

攻读硕士学位期间发表的论文

致谢

独创性声明