スティール評価法のための仮想並列マシンの設計と実現

• Item type: Journal(1)
• 公開日: 2003-04-15
• タイトル: スティール評価法のための仮想並列マシンの設計と実現
• タイトル / 言語: en
• タイトル: A Virtual Parallel Machine for the Steal-Help Evaluation Strategy
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: プログラミング言語の実装技術
• 著者所属: 東北大学大学院情報科学研究科
• 著者所属: 東北大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Department of Computer and Mathematical Sciences, Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Department of Computer and Mathematical Sciences, Graduate School of Information Sciences, Tohoku University
• 著者名: 伊藤貴康; 宮川伸也
• 著者名(英): Takayasu, Ito; Shinya, Miyakawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: スティール評価法は実行効率の良い並列Scheme処理系の実現のために提案された並列評価法である．並列処理系の実現によく用いられるETCは並列実行するタスクをすべて生成してから実行を開始するため，タスク過剰生成問題が発生し，逐次実行よりも遅くなることが多い．スティール評価法では，並列評価したい式はいったんSSTと呼ばれるスタックに入れられ，空きプロセッサが発生したときのみSSTから式がスティール操作によって取り出されるタスク遅延生成法に基づいている．このため，スティール評価法は，タスク過剰生成問題が発生しない効率の良い並列評価法となる．スティール評価法におけるタスク生成がSSTに対する操作によって行われることに着目して設計したのが，仮想並列マシン---SSTマシン---である．SSTマシンは，SSTに対するpush，pop，stealの基本命令に加えて，SSTのflush-outやコピー操作などを行う命令を備えた，スティール評価法のためのタスク生成を行うタスク生成系である．スティール評価法に基づく並列処理系を，タスク生成を行うSSTマシンとタスクの実行を行うタスク実行系に分離して実現することができる．SSTマシンをUNIX環境において移植性の高い形で提供できるようにするため，C言語を用いたSSTマシンライブラリとして実現した．共有メモリ型並列計算機上で実現したSSTマシンライブラリの性能について報告するとともに，その応用例として実現した並列Scheme処理系の実験結果についても述べる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Steal-Help Evaluation (SHE) has been proposed to implement anefficient parallel Scheme system. Eager Task Creation (ETC) is usuallyused as a parallel evaluation strategy to implement parallel systems,but ETC is not necessarily efficient, since it incurs the problem ofexcessive process creation. In SHE, expressions to be evaluated inparallel are pushed into a stack called ``SST''. Under a sharedparallel architecture a processor called ``home processor'' evaluatesan expression, obtaining it from the top of the SST, and when someidle processor is available, it steals an expression in the SST fromits bottom for parallel evaluation. SHE is known to be an efficientparallel evaluation strategy that suppresses excessive processcreation, based on lazy creation of concurrent tasks. We propose avirtual parallel machine called ``SST machine'' with operations on theSST to implement SHE. It is designed to equip ``push'', ``pop'', and``steal'' instructions, together with additional instructions such as``copy'', ``save'', ``flush-out'' and others. The SST machine can be used torealize SHE-based parallel systems, together with use of evaluatorsfor expressions that reside in tasks created by SST machineoperations. The SST machine instructions are implemented as Clibraries to allow their use in various platforms. Then, we reporttheir experimental results, including their use in implementing aparallel Scheme system.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 44, 号 4, p. 1056-1069, 発行日 2003-04-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764