R3Qによる進化型計算の中粒度Grid スケジューリング

• Item type: Trans(1)
• 公開日: 2006-09-15
• タイトル: R3Qによる進化型計算の中粒度Grid スケジューリング
• タイトル / 言語: en
• タイトル: A Grid Scheduling for an Evolutionary Computation Using R3Q
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: グリッド
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 神戸大学大学院自然科学研究科
• 著者所属: 広島大学大学院工学研究科
• 著者所属: 信州大学繊維学部
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Technology, Kobe University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Faculty of Textile Science and Technology, Shinshu University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者名: 松浦, 芳樹; 大倉, 和博; 松村, 嘉之; 藤本, 典幸; 萩原, 兼一
• 著者名(英): Yoshiki, Matsuura; Kazuhiro, Ohkura; Yoshiyuki, Matsumura; Noriyuki, Fujimoto; Kenichi, Hagihara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，進化型計算の隔世代交替モデルをGrid Computing に実装することを試みる．隔世代交替モデルでは，世代交替の際に各計算機の同期を世代ごとに行う必要がある．しかし，Grid は動的かつヘテロな計算機環境であるため，低速計算機がボトルネックとなり，同期処理が効率良く行えない．さらに，分散可能なタスクが中粒度タスクゆえに，ネットワーク環境における通信遅延が問題となり，分散計算の効果が低下してしまう．本稿では，これらの問題に対し，Grid スケジューリングの立場から対処する．まず，同期処理に対し，タスクスケジューリングアルゴリズムRR（list scheduling with Round-robin order Replication）を適用する．さらに，通信遅延に対し，RR における強制終了の効率を考慮したスケジューリング手法RWQ（Remote Work Queue）を提案し，RR とRWQ を併用するR3Q を提案する．いくつかの手法を比較した計算機実験の結果より，R3Qにより通信遅延時間に左右されず高い並列化効率が得られることを確認した．これより，R3Q によりEC の隔世代交替モデルにおいても，進化ダイナミクスを変えることなく，効率良くGrid に実装できることを示した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A computational method for implementation of Evolutionary Computation (EC) optimization methods in grid computing environments is discussed. In general, EC methods implemented in a grid environment need jobs to be synchronized each generation. In addition, EC problems incur a significant communication overhead, because of the fact that they are what we refer to as “medium-grained” tasks. We deal with these problems by using a dynamic grid scheduling method without prediction. In this paper, list scheduling with Round-robin order Replication (RR) is adopted to reduce waiting times due to synchronisation. However, RR is suitable only for coarse-grained tasks. For medium-grained tasks, we propose a new technique for reducing the communication overhead, called the Remote Work Queue (RWQ) method. This is able both to reduce communication time and obtain efficient forced termination of tasks. We then define R3Q (Round-robin Replication Remote Work Queue) as RWQ with RR like task replication. In order to evaluate R Q, computer simulations are conducted by using a test problem that requires a constant number of computations, but where varying computer resources in the grid nodes result in varying execution times. Our results show that R3Q can reduce both synchronous waiting time and communication time, and provides efficient forced termination of tasks in comparison with other methods.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11833852
• 書誌情報: 情報処理学会論文誌コンピューティングシステム（ACS）; 巻 47, 号 SIG12(ACS15), p. 240-249, 発行日 2006-09-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7829
• 出版者 / 言語: ja
• 出版者: 情報処理学会