非均質環境における選択型スケジューリング手法

松本, 真樹, 片野, 聡, 大野, 和彦, 佐々木, 敬泰, 近藤, 利夫, 中島, 浩

我々は大規模な広域分散環境における並列処理を目的とした，タスク並列スクリプト言語 MegaScript を開発している．本言語による並列処理で高性能を達成するためには，依存のあるタスク群を非均質環境に効率良くスケジューリングする必要がある．しかし，非均質環境に対する高精度な静的スケジューリングは計算コストが非常に高い．そこで我々は階層型スケジューリング手法を提案し，均質環境用スケジューラと比べ，スケジューリング精度と計算コストの両方で高い性能を得ている．本手法は実行環境のホスト群およびスケジューリング対象であるタスク群を階層モデル化し，段階的なスケジューリングを行う．上位層では抽象モデルによる高速な大域スケジューリングを行い，下位層では個々のタスク・ホストに対する詳細な局所スケジューリングを行う．これにより大規模なスケジューリングを効率良く扱うことができる．しかし，現在用いている局所スケジューリング手法では精度や計算コストが十分とはいえない．そこで本発表では，選択型スケジューリングによる改良手法を提案する．選択型スケジューリング手法を提案する．これは局所スケジューラが扱うタスク間に依存性があるかないかを調べ，各々の場合に適したスケジューラを選択する手法である．また，抽象シミュレーションを用いて，本手法と従来手法との比較評価を行った．

We are developing a task parallel script language MegaScript for parallel processing on large-scale widely-distributed environment. To achieve high performance, MegaScript requires a scheduling scheme that efficiently schedules dependent tasks to a heterogeneous environment. However, the scheduling overheads of existing static schemes are too large. Therefore, we proposed the hierarchical scheduling scheme, and it outperforms the one for homogeneous environments. It uses a couple of different scheduling schemes, the one is used to make rough global scheduling in the upper layer, the other is used to make precise local scheduling in the lower layer. However, the performance of current scheme used in the lower layer is insufficient for large-scale heterogeneous environments. Therefore we propose an adaptive scheduling scheme. In this scheme, a local scheduler switches schemes whether if the assigned tasks are independent or not. We made evaluation of the scheme using abstract simulations.

非均質環境における選択型スケジューリング手法

書誌事項

この論文をさがす

抄録

収録刊行物

キーワード

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

書き出し

問題の指摘

非均質環境における選択型スケジューリング手法

書誌事項

この論文をさがす

抄録

収録刊行物

キーワード

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

書き出し

問題の指摘

参加プロジェクトリスト

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