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

并行编程已被证明是困难的，需要并行算法和硬件架构的专业知识才能获得良好的结果。框架并行编程使程序员能够从已知存在的有效实现的现成组件（并行框架）构建并行程序，从而使并行程序开发和并行化过程更容易。本研究旨在为骨架并行编程提供理论基础和实用的编程环境系统。通过本研究，我们取得了以下成果。1)我们开发了一种新的框架，它为递归数据结构（如列表和二叉树）抽象了一个很好的原始并行框架组合。2)我们已经开发了一个优化规则，融合了两个连续的骨架调用，基于建设性算法的思想。我们用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++.