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

新的骨架并行编程系统的理论基础和实际实现的发展

• 批准号: 15500020
• 负责人: IWASAKI Hideya
• 金额: $ 2.11万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2003
• 资助国家: 日本
• 起止时间: 2003 至 2004
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-15500020/
• 关键词: Parallel Programming; Parallel Skeleton Library; Constructive Algorithmics; Fusion Transformation; C++; MPI; スケルトン並列プログラミング; プログラム変換; 並列スケルトン; スケルトンプログラミング

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++.

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

项目成果

Kakehi, K., Hu, Z., Takeichi, M.: "List Homomorphism with Accumulation"Proc.4th International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing. 250-259 (2003)

Kakehi, K.、Hu, Z.、Takeichi, M.：“List Homomorphism with Accumulation”Proc.第四届软件工程、人工智能、网络和并行/分布式计算国际会议。

PType System : A Featherweight Parallelizability Detector

PType 系统：轻量级并行性检测器

• 发表时间: 2004
• 期刊: Proc.2nd ASIAN Symposium on Programming Languages and Systems(APLAS2004)
• 作者: Xu;D.N.;Khoo;S.C.;Hu;Z.
• 通讯作者: Z.

A Parallel Skeleton Library in C++ with Optimization Mechanism

具有优化机制的C并行骨架库

• 期刊: Computer Software (to appear)
• 作者: Akashi;Y.;Matsuzaki;K.;Iwasaki;H.;Kakehi;K.;Hu;Z
• 通讯作者: Z

最適化機構を持つ C++ 並列スケルトンライブラリ

具有优化机制的C++并行骨架库

• 发表时间: 2005
• 期刊: コンピュータソフトウエア Vol.22, No.3
• 作者: 明石 良樹 松崎 公紀;岩崎 英哉;筧 一彦;胡 振江
• 通讯作者: 胡 振江

Systematic Derivation of Tree Contraction Algorithms

树收缩算法的系统推导

• 发表时间: 2004
• 期刊: Proc. 4th International workshop on Constructive Methods for Parallel Programming (CMPP2004)
• 作者: Matsuzaki;K.;Hu;Z.;Kakehi;K.;Takeichi;M.
• 通讯作者: M.