Research on New Parallel Functional Languages and Their High-Performance Processors

新型并行函数语言及其高性能处理器的研究

基本信息

批准号：
13480073
负责人：
ITO Takayasu
金额：
$ 9.28万
依托单位：
Tohoku University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2002
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-13480073/
关键词：
parallel functional language Steal-Help Evaluation lazy evaluation lazy creation of tasks PaiLisp PaiLisp-kernel SST machine stealable 共有メモリ型並列計算機仮想並列マシン並列Scheme 関数遅延評価

项目摘要

In functional programming, evaluations of functional arguments are evaluated by eager evaluation or lazy evaluation, while in parallel evaluation of parallel functional programs there are "eager task creation" which is commonly used in parallel processing, and "lazy creation of concurrent tasks" which has been proposed by T. Ito (Head investigator of this project). The lazy creation of concurrent tasks is called "Steal-Help Evaluation" (SHE, in short), which creates processes only when idle processors are available and is known to be better than ETC (eager task creation) in achieving high-performance. The SHE is realized using a set of operations on the SST (Stealable Stack). Two unique interesting constructs "stealable" and "pdelay" are introduced incorporate the SHE into parallel language design. Moreover, we proposed and designed the SST Machine, which is a virtual parallel machine based on the SHE strategy. The SST machine library written in the C language is implemented to support … More easy and standardized implementation of the SHE strategy. The SST machine library is successfully used to realize an efficient parallel system of PaiLisp, which is a parallel Scheme with a rich set of concurrency constructs. including pcall, plet, pletrec, par-and, par-or, future, stealable. Note that the system is based on eager eavaluation of functional arguments and lazy creation of concurrent tasks. A compact kernel of PaiLisp, called PaiLisp-Kernel is derived under the ETC strategy and the SHE strategy. Also, a parallel functional language system based lazy evaluation of functional arguments and lazy creation of concurrent tasks (that is, SHE) has been designed and implemented. The resultant system has several good features and properties over the one based on eager evaluation and SHE. However, in order to realize a high-performance system based on lazy evaluation some efficient implementation techniques need to be developed as in eager evaluation systems. The reaearch revealed that the SHE strategy is reaally a nice technique to implement an efficient parallel system and the new construct "stealable" is a simple and efficient construct with a clean concurrency semantics and a wide applicability to various parallel languages. Also, the SST machine and its C library are useful in implementing an SHE-based parallel system. Less

在函数式编程中，函数参数的求值通过急切求值或惰性求值进行求值，而在并行函数程序的并行求值中，有并行处理中常用的“急切任务创建”和具有并行处理功能的“延迟创建并发任务”。 T. Ito（该项目的首席研究员）提出了并发任务的惰性创建称为“Steal-Help Evaluation”（简称SHE），它仅在空闲处理器可用且已知时才创建进程。比ETC（渴望任务SHE 是通过使用 SST（Stealable Stack）上的一组操作来实现的，并且引入了两个独特的有趣结构“stealable”和“pdelay”，并将 SHE 纳入并行语言设计中。并设计了SST机器，这是一个基于SHE策略的虚拟并行机。用C语言编写的SST机器库被成功地用于支持SHE策略的简单和标准化实施。实现一个PaiLisp 的高效并行系统，它是一个具有丰富并发结构的并行方案，包括 pcall、plet、pletrec、par-and、par-or、future、stealable。请注意，该系统基于函数参数的急切求值。 PaiLisp 的紧凑内核（称为 PaiLisp-Kernel）是在 ETC 策略和 SHE 策略下衍生的。此外，还基于函数参数的延迟计算和并行函数语言系统。并发任务的惰性创建（即SHE）已经被设计和实现，与基于急切求值和SHE的系统相比，所得系统具有一些良好的特性和属性，但是为了实现基于惰性任务的高性能系统。评估需要开发一些实现高效的技术，例如在急切的评估系统中。研究表明，SHE 策略确实是实现高效并行系统的好技术，并且新构造“stealable”是一种简单而高效的构造，具有干净的并发性。语义和广泛此外，SST 机器及其 C 库对于实现基于 SHE 的并行系统很有用。