静的情報を用いた動的再スケジューリングのオーバヘッド削減手法

概要

論文の詳細を見る
ワークフロー型の大規模並列処理において実行効率を高めるにはタスクスケジューリングが重要であり,様々な手法が提案されている.静的スケジューリング手法は良いスケジューリング長を得ることができるが,計算ホストの負荷等による性能変動が発生した場合,ワークフローの実行効率が低下する可能性がある.一方デマンドドリブン型の動的スケジューリング手法は,ワークフローの依存関係によって良いスケジューリング長を得られない場合がある.そこで,実行環境の性能変動が発生するごとに静的スケジューリング・アルゴリズムを用いて再スケジューリングを行う動的再スケジューリング手法が提案されている.しかし,静的スケジューリング・アルゴリズムの計算コストは非常に高いため,アルゴリズムの実行回数が多い場合,現実的な時間でスケジューリングを行えない.そこで本発表では,スケジューリングの計算コストを削減することを目的とした動的再スケジューリング手法を提案する.従来の手法は性能変動を条件に再スケジューリングを行っているため,無駄な再スケジューリング処理が行われる可能性がある.そこで本手法は,再スケジューリングの実行回数を削減するために,特定タスクの終了を実行条件として用いている.本手法を抽象シミュレーションを用いて評価した結果,タスク数が 1,000 規模のワークフローの場合,5% 程度のワークフローのスケジューリング長の増加で,再スケジューリングの実行回数を約 1/4〜1/100 に減らすことができた.
2011-06-29

静的情報を用いた動的再スケジューリングのオーバヘッド削減手法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク