Development of Theoretical Basis and Practical Implementation of a new Skeletal Parallel Programming System

并行编程已被证明是困难的，需要并行算法和硬件体系结构的专业知识才能获得良好的结果。骨架式并行程序设计使程序员能够从已有的已知有效实现的组件(并行骨架)中构建并行程序，从而使并行程序开发和并行化过程变得更加容易。通过本文的研究，我们取得了以下成果：1)我们开发了一种新的骨架，它为列表和二叉树等递归数据结构抽象了原始并行骨架的良好组合。2)我们基于构造性算法的思想，开发了一种融合两个连续骨架调用的优化规则。3)我们开发了一个实用的C++和MPI骨架库，该库可以在通用并行环境下使用。A)该库提供了抽象典型形式的递归函数的累积框架。B)库实现了融合变换，避免了不必要的中间数据结构。C)该库没有牺牲C++通用性的语法扩展。

Parallel programming has proved to be difficult, requiring expert knowledge of both parallel algorithms and hardware architectures to achieve good results. Skeletal parallel programming enables programmers to build a parallel program from ready-made components (parallel skeletons) for which efficient implementations are known to exist, making both the parallel program development and the parallelization process easier.This research aims to develop both theoretical basis and practical programming environment system for skeletal parallel programming. Through this research, we have achieved the following results.1)We have developed a new skeleton that abstracts a good combination of primitive parallel skeletons for recursive data structures such as lists and binary trees.2)We have developed an optimization rules that fuses two successive calls of skeletons, based on the idea of constructive algorthmics.3)We have developed a practical skeletal library in C++ and MPI that can be used in general parallel environments.Our library has the following characteristic features that have not implemented in existing libraries. a)The library provides accumulate skeleton that abstracts typical form of recursive functions. b)The library implements fusion transformation that avoids unnecessary intermediate data structures. c) The library has no syntactic extensions that sacrifice generality of C++.