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

情報処理学会 Web Site 被引用文献1件

書誌事項

タイトル別名
  • ヘテロガタ ダイキボ ヘイレツ カンキョウ ノ カイソウガタ タスクスケジューリング ノ テイアン ト ヒョウカ
  • A Hierarchical Scheduling Scheme for Large Scale Heterogeneous Environments

この論文をさがす

抄録

我々は大規模な広域分散環境における並列処理を目的とした，タスク並列スクリプト言語MegaScriptを開発している．本言語による並列処理で高性能を達成するには，依存のあるタスク群を非均質環境に効率良くスケジューリングする手法が必要である．しかし，高精度な静的スケジューリングは計算コストが非常に高く，タスクが完全独立でないため単純な動的スケジューリングでは高性能が期待できない．そこで，階層型にスケジューラを配置し，複数の方式を併用するハイブリッド型のスケジューリング方式を提案する．本手法では実行環境のホスト群およびスケジューリング対象であるタスクネットワークを階層モデル化し，階層型スケジューラによる段階的なスケジューリングを行う．上位スケジューラでは抽象モデルによる高速な大域スケジューリングを行い，下位スケジューラでは個々のタスク・ホストに対する詳細な局所スケジューリングを行うことで，大規模なスケジューリングを効率良く扱うことができる．また，動的スケジューリングを併用することで，実行環境の性能変動などによる影響を補正する．抽象シミュレーションにより本手法の評価を行った結果，均質環境用の詳細スケジューリングと比べ，階層型スケジューリングでは7-10倍程度の速度向上が得られ，タスク数/ホスト数が10 000/1 000規模の場合，約1/44の時間でスケジューリングを行うことができた．

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.

収録刊行物

被引用文献 (1)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ