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（T. Ito（T. Ito）提出的（该项目的负责人）。并发任务的懒惰创建称为“窃取助手评估”（简而言之），它仅在可用的空闲处理器可用时才能创建流程，并且已知比ETC（急切的任务创建）在实现高性能时会创建流程。她使用SST上的一组操作（可偷堆）实现了她。将两个独特的有趣构造“可偷”和“ pdelay”引入了平行语言设计中。此外，我们提出并设计了SST机器，该机器是基于SHE策略的虚拟平行机。用C语言编写的SST机器库是为了支持SHE策略的更简单和标准化的实现。 SST机器库成功地用于实现Pailisp的有效并行系统，这是一个并行方案，具有丰富的并发构造。包括PCALL，PLET，PLETREC，PAR和PAR-OR，FUTURE，可偷车。请注意，该系统基于对功能参数的急切分析和并发任务的懒惰创建。 Pailisp的紧凑核内核，称为Pailisp-Kernel，是根据ETC策略和SHE策略得出的。同样，基于功能系统的平行功能系统的功能参数和懒惰创建并发任务的懒惰评估（即，她）是设计和实施的。根据渴望的评估和她，所得系统具有几个良好的功能和属性。但是，为了实现基于懒惰评估的高性能系统，需要像急切的评估系统一样开发一些有效的实施技术。 Reearch透露，SHE策略确实是实现有效并行系统的一种很好的技术，而新的构造“可窃取”是一种简单有效的结构，具有干净的并发语义，并且对各种并行语言具有广泛的适用性。此外，SST机器及其C库在实现基于SH的并行系统方面也很有用。较少的