非同期通信に基づく並列言語の静的解析とそれに基づく最適化

基于异步通信的并行语言的静态分析及基于其的优化

• 批准号: 08780242
• 负责人: 小林 直樹
• 金额: $ 0.7万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1996
• 资助国家: 日本
• 起止时间: 1996 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-08780242/
• 关键词: 並列言語; 静的解析; 型システム; プロセス計算

本研究の目的は、並列オブジェクト指向言語をはじめとする非同期通信に基づく並列言語の静的解析とそれに基づく最適化の技法を、プロセス計算のモデルに基づく型つき並列言語HALCをとおして、確立・改良することにあった。研究成果としては、静的解析手法として(1)通信チャネルの使用順序の解析のための型システム、および(2)通信チャネルの使用回数の解析のための型システムの開発・改良が、最適化に関しては(3)並列言語における部分計算の定式化、(4)型情報を利用した分散環境における通信の高速化、が挙げられる。以下各々についてもう少し詳細に述べる。(1)通信チャネルの使用順序の情報を含んだ型システムを開発することによって、従来困難とされてきたプロセス間のデッドロックの静的な検出や、通信のための効率のよいコードの生成が可能となった。(2)並列プログラムにおける、通信チャネルや関数の使用回数の情報を含んだ型システムを開発することによって使用回数の静的解析を可能とし、その情報が冗長な通信の除去、通信の高速化、GCの負担軽減に有用であることを示した。(3)並列言語における部分計算を定式化しさらにその正当性を証明した。これによって、部分計算による並列プログラムの最適化の手法および最適化の正当性の基準の確立に貢献した。(4)型つき並列言語において、実行時型情報を用いて分散環境における通信の際のデータ量およびデータの変換のコストが削減する手法を提案し、HACLの分散処理系dHACLをとおしてその有効性を検証した。

The purpose of this study is to analyze and optimize the basic and parallel speech patterns in asynchronous communication, establish and improve the basic and parallel speech patterns in HALC. The research results include: (1) Analysis of the order of use of communication clusters;(2) Development, improvement and optimization of the order of use of communication clusters;(3) Formulation of partial calculation of parallel speech;(4) High-speed communication in distributed environment by using type information. The following is a detailed description of each item. (1)The information of the order of use of the communication includes the possibility of generating the information of the type of the system, the difficulty of the system and the possibility of generating the information of the system of the communication. (2)In parallel with the platform, a structured system is developed that includes information on the number of usage cycles of communication clicks and related numbers, which makes it possible to analyze the static number of usage cycles, and the lengthy information is useful for eliminating communication, speeding up communication, and reducing the burden on GC. (3)Paratactic speech is formalized and justified. The optimization method of the optimization and the establishment of the criterion of the legitimacy of the optimization are all contributed to the optimization of the system. (4)The distributed processing system dHACL is used to demonstrate the effectiveness of the distributed processing system dHACL.

项目成果

Naoki Kobayashi and Akinori Yonezawa: "Toward Foundations of Concurrent Object-Oriented Programming-Types and Language Design" Theory and Practice of Object Systems,John-Wiley & Sone. 1(4). 243-268 (1996)

Naoki Kobayashi 和 Akinori Yonezawa：“面向并发对象编程类型和语言设计的基础”对象系统的理论与实践，John-Wiley

清水智弘、小林直樹: "並列言語の高レベルなデータの通信における型を利用した最適化について" コンピュータソフトウェア. 14(2). (1997)

Tomohiro Shimizu、Naoki Kobayashi：“在并行语言中使用高级数据通信中的类型进行优化”计算机软件 14(2)。

Haruo Hosoya,Naoki Kobayashi,and Akinori Yonezawa: "Partial Evaluation Scheme for Concurrent Languages and Its Correctness" Euro-Par'96 Parallel Processing,Springer-Verlag LNCS. 1123. 625-632 (1996)

Haruo Hosoya、Naoki Kobayashi 和 Akinori Yonezawa：“并发语言的部分评估方案及其正确性”Euro-Par96 并行处理，Springer-Verlag LNCS。

Naoki Kobayashi: "A Partially Deadlock-free Typed Process Calculus (I) -A Simple System-" Technical Report,Department of Informaiton Science,University of Tokyo. 96-02. 1-32 (1996)

小林直树：“部分无死锁类型化过程演算（I）-简单系统-”技术报告，东京大学信息科学系。