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

在函数式程序设计中，函数式参数的求值一般采用“渴望求值”或“惰性求值”，而在并行函数式程序的并行求值中，则有并行处理中常用的“渴望任务创建”和T.伊藤（本项目首席研究员）。并发任务的惰性创建被称为“Steal-Help Evaluation”（简称SHE），它只在空闲处理器可用时才创建进程，并且在实现高性能方面比ETC（渴望任务创建）更好。SHE是使用SST（Stealable Stack）上的一组操作来实现的。引入了两个独特的有趣的结构“stealable”和“pdelay”，将SHE引入到并行语言设计中。提出并设计了一种基于SHE策略的虚拟并行机SST Machine。实现了用C语言编写的SST机器库， 关于我们 安全、健康和环境战略的简单和标准化实施。SST机器库被成功地用于实现PaiLisp的高效并行系统，PaiLisp是一个具有丰富并发结构集的并行Scheme。包括pcall、plet、pletrec、par-and、par-or、future、stealable。请注意，该系统是基于函数参数的积极评估和并发任务的惰性创建。在ETC策略和SHE策略下，导出了PaiLisp的一个紧凑核，称为PaiLisp-Kernel。设计并实现了一个基于函数参数惰性求值和并发任务惰性创建的并行函数式语言系统（SHE）。该系统与基于渴望评价和SHE的系统相比，具有许多优良的特性。然而，为了实现一个高性能的系统的基础上懒惰的评价，一些有效的实现技术需要开发的渴望评价系统。结果表明，SHE策略是实现高效并行系统的一种有效技术，而新构造“stealable”是一种简单有效的构造，具有清晰的并发语义，广泛适用于各种并行语言。此外，SST机和它的C库是有用的，在实现一个基于SHE的并行系统。少

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