新しい計算モデルキューマシンとその並列関数型言語への応用

• Item type: Journal(1)
• 公開日: 1997-03-15
• タイトル: 新しい計算モデルキューマシンとその並列関数型言語への応用
• タイトル / 言語: en
• タイトル: New Computation Model Queue Machine and Its Application to Parallel Functional Programming Languages
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: ソフトウェア
• 著者所属: 慶應義塾大学大学院理工学研究科
• 著者所属: 慶應義塾大学大学院理工学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Technology, Keio University
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Technology, Keio University
• 著者名: 前田, 敦司; 中西, 正和
• 著者名(英): Atusi, Maeda; Masakazu, Nakanishi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，幅優先で式の評価を行う新たな計算機アーキテクチャであるキューマシンを提案し，その実行モデルを用いて関数型言語を特殊なハードウェアのサポートのない密結合並列計算機上で効率良く自動並列実行する言語処理系の構築法を述べる．関数型言語においては複数の関数呼び出しを並列に処理することが可能であるが，すべての関数呼び出しの実行が終了するまで待って実行を再開するための同期オーバヘッドが問題となる．また，通常スタックに保持する局所的な実行の文脈をヒープ上に保持する必要があるため，メモリ管理のオーバヘッドも増大する．本論文では，キューマシンの実行モデルを模倣してスタックをキューに置き換えることにより上記のオーバヘッドを大幅に削減することができ，既存の計算機上で並列関数呼び出しが効率良く実現できることを示す．この手法を用いたプロトタイプ言語処理系の実行時間を密結合並列計算機で測定した結果，逐次実行ではCなどの他の（逐次）言語処理系に劣るものの，2CPU以上では他の処理系を上回り，高い台数効果が得られている．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We present a new evaluation scheme for expressions called queue machine model of execution which enables automatic (implicit) parallel execution of functional programming languages with very small synchronization overhead without special hardware support.In purely functional languages,multiple function call can be evaluated parallely without changing semantics of the program.But when implemented naively,synchronization overhead to wait for termination of all subcomputations becomes prohibitive.Moreover,local context information usually stored in stack must be maintained in garbage-collected heap.So overhead of memory management also increases when compared to sequential implementations.In this paper,we show that by emulating execution model of queue machines and by replacing stacks with queues,the overhead can be drastically reduced and parallel function invocation can be implemented efficiently on stock hardware.Preliminary measurement of prototype implementation based on this technique is presented.The measurement shows that,although programs compiled with our prototype compiler run slower than other implementations on sequential machines,they show good scalability and run faster than sequential implementations when executed with two or more processors.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 38, 号 3, p. 574-583, 発行日 1997-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764