Development of a Parallel Skeleton Library for rich set of data types withoptimization mechanism

本研究旨在开发一种新的实用并行骨架库，帮助程序员编写一个高效的并行程序，就像它是一个顺序程序一样。在骨架并行程序设计中，并行处理的典型模式被抽象为并行骨架。并行骨架的示例包括将相同函数应用于列表中的每个元素的MAP、使用关联二元运算符将给定列表折叠成单个值的REDUTE、以及将REDUTE的所有中间结果累加到列表中的SCAN。在本研究中，我们开发了一个新的骨架库，称为SkeTo(东京的骨架库)。SkeTo现在可以通过http://www.页面作为自由软件获得IPL.T.U-tokvo.ac.JP/Sketa。SkeTo的主要功能是在其他库中看不到的。1)SkeTo支持丰富的数据类型集，包括列表、矩阵、二叉树和玫瑰树。2)SkeTo是用C++实现的，没有对并行骨架进行语法扩展。因此，熟悉C++的程序员在使用SkeTo库时没有问题。3)基于构造性算法理论，SkeTo提供了将连续的骨架调用融合到单个调用中的优化机制。

This research aims to develop a new practical parallel skeleton library that helps programmers write an efficient parallel program as if it were a sequential one. In skeletal parallel programming, typical patterns of parallel processing are abstracted in parallel skeletons. Examples of parallel skeletons includes map that applies the same function to each element in a list, reduce that collapses a given list into a single value using an associative binary operator, and scan that accumulates all intermediate results of reduce in a list. Each parallel skeleton hides parallel behavior in its implementation, thus programmers need not be involved in the details of parallelization.In this research, we have developed a new skeleton library called SkeTo (Skeleton library in Tokyo).SkeTo is now available as a free software via the page http://www. ipl. t.u-tokvo.ac. jp/sketa. Main features of SkeTo that cannot be seen in other libraries are as follows.1)SkeTo supports rich set of data types including list, matrix, binary tree and rose tree.2)SkeTo is implemented in C++ without syntactic extensions for parallel skeletons. Thus programmers who are familiar with C++ have no problem in using the SkeTo library.3)Based on the theory of Constructive Algorithmics, SkeTo provides optimization mechanism that fuses successive skeleton calls into a single call.