基于骨架的Apla语言程序到MPI+C++并行程序的自动转换

摘要

从“软件危机”爆发至今，人们提出了很多新方法和新工具，这些方法和工具致力于解决“软件危机”的各个方面。但现有的这些解决方案并没有使人们彻底地从“软件危机”中解脱出来，用形式化方法开发正确，高效的算法程序，被当今计算机界誉为克服“软件危机”，提高软件可靠性和生产效率的革命性途径。 薛锦云教授在国家863和多项国家自然科学基金课题的资助下，根据多年从事算法程序设计理论研究的成果，提出了一种简单实用的设计和证明算法的形式化方法—PAR。在该方法的指导下，定义了Radl算法设计语言来描述算法规约和抽象算法，定义了Apla语言来描述抽象程序。程序的自动转换系统是整个PAR方法理论框架的重要组成部分，是用PAR方法开发高级语言程序的辅助工具。而现有的程序自动转换系统只能将Apla语言程序转换成顺序程序，而在并行程序设计越来越重要的今天将Apla语言程序自动转换成并行程序显得尤其重要。因此本文研究和实现了Apla+到MPI+C++并行程序的自动转换系统。 现有的大多数并行程序设计模型本质上是对并行程序编码的研究，它们为并行程序设计提供一个抽象平台，但缺乏指导程序员在其上有效地进行并行程序开发的方法。基于骨架（skeleton）的并行程序设计方法通过为程序员提供通用的问题并行求解骨架，使得程序员摆脱了琐碎的并行细节，而更关注问题本身，因而是一种更高抽象层次的并行程序设计方法。本文研究的Apla+到MPI+C++程序自动转换系统是基于骨架思想实现的。 本文工作主要涵盖以下几点：（1）深入研究基于骨架的并行编程环境，分析其中骨架的概念、描述语言等方面存在的问题与困难，探索一种适用于PAR平台中程序并行化实现的可行的解决方案。（2）对并行计算中的任务队列骨架进行了深入研究，采用C++模板机制并以一种可以嵌入到现有的自动转换系统的方式对任务队列骨架进行了预实现，并集成为模板库，加入到自动转换系统中。（3）进一步研究PAR方法的思想在此基础上将Apla语言扩充为Apla+，使之可以识别任务队列骨架。（4）实现基于骨架的Apla+到MPI+C++程序自动转换系统。（5）用实例来演示用程序自动转换系统来解决实际问题的方法。

目录

文摘

英文文摘

声明

1绪 论

1.1研究背景

1.2相关研究领域与本文工作比较

1.2.1并行计算模型

1.2.2并行程序开发方法

1.2.3并行编程环境

1.2.4泛型程序设计

1.2.5并行程序设计语言的实现途径

1.3本文研究内容与章节结构

2 PAR方法

2.1 PAR方法概述

2.2 PAR方法开发算法程序的步骤及特点

2.3 Apla语言

2.3.1 Apla语言的基本结构

2.3.2 Apla语言的基本类型

2.3.3 Apla语言过程和函数的定义

2.3.4 Apla语言程序语句

3基于骨架的并行程序设计方法

3.1骨架概述

3.1.1骨架分类

3.1.2骨架复合

3.1.3骨架性能研究

3.2基于骨架的代表性并行编程系统

3.3本文基于骨架的并行编程系统环境

3.3.1 Apla+语言

3.3.2骨架库

3.3.3模板库

3.4与传统并行程序设计模型比较

4任务队列骨架的实现

4.1 Murray I.Cole对任务队列模式的描述

4.2本文对任务队列骨架的描述

4.2.1任务队列骨架描述

4.2.2任务队列骨架的实现

4.3小结

5自动转换系统的实现方法

5.1系统设计思想

5.2系统结构

5.3系统运行和使用

5.3.1运行环境

5.3.2系统使用

5.4小结

6应用实例

6.1单源最短路径问题

6.1.1单源最短路径问题的Apla+抽象程序

6.1.2单源最短路径通过自动转换系统得到的MPI+C++程序

6.2 LU矩阵分解

6.2.1 LU矩阵分解的Apla+抽象程序

6.2.2 LU矩阵分解通过自动转换系统得到的MPI+C++程序

6.3传统并行程序开发方法与本文方法比较

6.4性能评价

6.5小结

结 语

参考文献

后 记

在学期间公开发表论文及著作情况