ヘテロ型大規模並列環境の階層型タスクスケジューリングの提案と評価

• Item type: Trans(1)
• 公開日: 2009-01-27
• タイトル: ヘテロ型大規模並列環境の階層型タスクスケジューリングの提案と評価
• タイトル / 言語: en
• タイトル: A Hierarchical Scheduling Scheme for Large Scale Heterogeneous Environments
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 三重大学大学院工学研究科
• 著者所属: 三重大学大学院工学研究科 現在，株式会社デンソー
• 著者所属: 三重大学大学院工学研究科
• 著者所属: 三重大学大学院工学研究科
• 著者所属: 三重大学大学院工学研究科
• 著者所属: 京都大学学術情報メディアセンター
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Mie University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Mie University,Presently with Denso Co., Ltd
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Mie University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Mie University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Mie University
• 著者所属(英): en
• 著者所属(英): Academic Center for Computing and Media Studies, Kyoto University
• 著者名: 松本, 真樹; 片野, 聡; 佐々木, 敬泰; 大野, 和彦; 近藤, 利夫; 中島, 浩
• 著者名(英): Masaki, Matsumoto; Satoshi, Katano; Takahiro, Sasaki; Kazuhiko, Ohno; Toshio, Kondo; Hiroshi, Nakashima
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 我々は大規模な広域分散環境における並列処理を目的とした，タスク並列スクリプト言語MegaScriptを開発している．本言語による並列処理で高性能を達成するには，依存のあるタスク群を非均質環境に効率良くスケジューリングする手法が必要である．しかし，高精度な静的スケジューリングは計算コストが非常に高く，タスクが完全独立でないため単純な動的スケジューリングでは高性能が期待できない．そこで，階層型にスケジューラを配置し，複数の方式を併用するハイブリッド型のスケジューリング方式を提案する．本手法では実行環境のホスト群およびスケジューリング対象であるタスクネットワークを階層モデル化し，階層型スケジューラによる段階的なスケジューリングを行う．上位スケジューラでは抽象モデルによる高速な大域スケジューリングを行い，下位スケジューラでは個々のタスク・ホストに対する詳細な局所スケジューリングを行うことで，大規模なスケジューリングを効率良く扱うことができる．また，動的スケジューリングを併用することで，実行環境の性能変動などによる影響を補正する．抽象シミュレーションにより本手法の評価を行った結果，均質環境用の詳細スケジューリングと比べ，階層型スケジューリングでは7-10倍程度の速度向上が得られ，タスク数/ホスト数が10 000/1 000規模の場合，約1/44の時間でスケジューリングを行うことができた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We are developing a task parallel script language MegaScript for parallel processing on large-scale widely-distributed environments. To achieve high performance, MegaScript requires a scheduling scheme, which efficiently schedules dependent tasks to a heterogeneous environment. However, the scheduling overhead of existing static schemes are too large, and dependency among tasks reduces efficiency of simple dynamic scheduling schemes. Therefore, we propose a hybrid scheduling scheme, which uses multiple schemes. To reduce the overhead of static scheduling, we use multi-layered schedulers: the upper layer makes rough global scheduling, and the lower layer makes precise local scheduling. We also use dynamic scheduling scheme to compensate the effect of dynamic change of the system performance. The evaluation of our scheme using abstract simulation achieved 7-10 times speedup using multi-layered schedulers. The scheduling time of 10,000 tasks/1,000 hosts was approximately 1/44 compared to a precise single scheduler.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 2, 号 1, p. 1-17, 発行日 2009-01-27
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会