遅延タスク生成の反復計算向け拡張

• Item type: Journal(1)
• 公開日: 2002-04-15
• タイトル: 遅延タスク生成の反復計算向け拡張
• タイトル / 言語: en
• タイトル: Extending Lazy Task Creation for Iterative Computation
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 特集：並列処理
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 並列化コンパイラ
• 著者所属: 京都大学大学院情報学研究科通信情報システム専攻
• 著者所属: 京都大学大学院情報学研究科通信情報システム専攻
• 著者所属: 京都大学大学院情報学研究科通信情報システム専攻
• 著者所属: 京都大学大学院情報学研究科通信情報システム専攻
• 著者所属(英): en
• 著者所属(英): Department of Communications and Computer Engineering, Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Department of Communications and Computer Engineering, Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Department of Communications and Computer Engineering, Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Department of Communications and Computer Engineering, Graduate School of Informatics, Kyoto University
• 著者名: 馬谷, 誠二; 八杉, 昌宏; 小宮, 常康; 湯淺, 太一
• 著者名(英): Seiji, Umatani; Masahiro, Yasugi; Tsuneyasu, Komiya; Taiichi, Yuasa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 不規則な問題を並列処理するのには，実行時のスレッド生成が可能なプログラミング言語が適している．そのような言語のなかには，スレッド生成時に他のプロセッサに授受可能なタスクの生成を行うように実装されていることも多い．しかし，この方法では実行時間のうちタスク生成にかかるオーバヘッドの占める割合が高くなってしまう．これに対し，Lazy Task Creation（LTC）を用いた実装ではアイドルなプロセッサが現れたときにはじめて，新しいタスクを生成することで必要のないタスク生成にかかるオーバヘッドを減らしている．さらに，タスクの分割を根本で行うことによりほぼ最小限のタスクの授受で各プロセッサに仕事（work）が十分に割り当てられる．本研究では，実行時スレッド生成を行う並列言語OPAにLTCを導入する．また，OPAには明示的なループ構文が存在しており，そのような反復コードの実行中にスレッド生成を行うことも可能であるが，これを通常のLTCにより実行させた場合，仕事を均等に分けることができず，そのためにタスク生成・授受の回数も抑えられない．本研究では，反復コード実行中には通常と異なる方法でLTCを行わせることにより，そのような状況においても効率の良い負荷分散を行えるようにした．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Programming languages which feature runtime thread creation are quitesuitable for parallel processing of irregular problems. In theirimplementations, the creation of a thread often means the creation ofa task which is a piece of work transferable to other processors.Such implementations, however, often incur a large overhead of taskcreation in the overall execution.In contrast,implementations using Lazy Task Creation (LTC) reduce the overhead bycreating a new task only when some other processor become idle.The new task is extracted by dividing the present running task.Furthermore, by dividing it around the root, each processor can have sufficient amount of work with the almost minimum number of task transfers.In this study, we introduce LTC in parallel language OPA which features runtime thread creation. OPA has explicit loop syntax, and enablesthread creation during a loop execution. If we use the usual LTC for such loop, we cannot divide work equally and the number of taskcreations and task transfers will become large.In order to obtain the LTC's efficient load-balancing even in such cases,we propose an extension of LTC to support iterative thread creation.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 43, 号 4, p. 948-957, 発行日 2002-04-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764