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

本研究旨在开发一种新的实用并行骨架库，帮助程序员编写高效的并行程序，就像它是一个顺序程序一样。在框架并行编程中，典型的并行处理模式被抽象到并行框架中。并行骨架的例子包括map（对列表中的每个元素应用相同的函数）、reduce（使用关联二进制操作符将给定列表折叠为单个值）和scan（累加列表中reduce的所有中间结果）。每个并行框架在其实现中隐藏并行行为，因此程序员不需要参与并行化的细节。在这项研究中，我们开发了一个新的骨架图书馆，名为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.