基于MPI的并行多层快速多极子算法的设计及其优化

摘要

多层快速多极子算法是解决复杂目标的电磁散射问题最为有效的方法之一，因而得到了广泛的应用。但对一些更为复杂的军用目标电磁散射，由于巨大的计算量和内存消耗量，依然不能得到圆满解决。 与此同时并行计算技术也取得了快速的发展，高速网络、机群以及并行编程环境的出现和发展使得越来越多的科研人员有条件进行相关领域算法的并行化研究。 本文在并行编程环境MPI(MessagePassingInterface)下进行了多层快速多极子算法的并行化研究。重点研究了分布树的建立过程，提出了虚拟盒子的概念及其性质，深入分析和设计了聚合、转移和解聚过程的通信机制，探讨了分布层共享层的划分及其对并行性能的影响。提出了分布树分布层负载均衡的一种衡量方法，并以此为基础提出了分布层的一种新的构造算法，相关的实验证明了新构造算法对于提高程序性能的有效性。 此外本文还对使用MPI期间可能会遇到的一些问题做了分析和总结，对大规模数据的传送、多种数据类型的传送及收发方不明确的通信给出了解决办法。对现有MPI没有组通信的非阻塞版本的情况，提供了一种非常简单的实现方法，对MPI用户有一定的指导作用。

目录

文摘

英文文摘

声明

第一章 绪论

1.1 课题背景

1.2 国内外研究概况

1.3 本文的研究内容

第二章MPI简介

2.1 概述

2.2 基本程序设计框架

2.3 程序基本模式

2.3.1 主从模式

2.3.2 对等模式

2.4 消息结构与通信域

2.5 点对点通信

2.6 集合通信

2.7 小结

第三章MPI通信研究

3.1 大规模数据的传送

3.2 多种数据类型的传送

3.2.1 结构数据类型

3.2.2 打包与解包

3.2.3 统一用MPI_BYTE传送

3.2.4 小结

3.3 收发方不明确的通信

3.4 非阻塞的集合通信

3.5 小结

第四章并行多层快速多极子算法的设计

4.1 多层快速多极子算法简介

4.2 分层分组

4.3 分布树

4.3.1 Morton键

4.3.2 分布树的建立过程

4.4 整个算法过程

4.5 通信方式研究

4.5.1 聚合

4.5.2 解聚

4.5.3 转移

4.6 实验结果

4.6.1 正确性验证

4.6.2 性能评估

4.7 小结

第五章 并行多层快速多极子算法的优化

5.1 分布层原构造算法

5.2 分布层负载均衡的度量

5.3 分布层现构造算法

5.4 两算法比较

5.5 实验结果

5.6 小结

第六章结论与展望

6.1 结论

6.2 展望

参考文献

作者在攻读硕士学位期间公开发表的论文

作者在攻读硕士学位期间所作的项目

致谢