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

IPSJ Web Site

Bibliographic Information

Other Title
  • 静的情報を用いた動的再スケジューリングのオーバヘッド削減手法
  • セイテキ ジョウホウ オ モチイタ ドウテキ サイスケジューリング ノ オーバ エ ッド サクゲン シュホウ
  • A Dynamic Rescheduling Scheme for Reducing Scheduling Overhead Using Static Information

Search this article

Abstract

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

Task scheduling is very important for efficient execution of large-scale workflows in distributed computing environments. Static scheduling schemes achieve high performance when executing workflows in stable environments. However, the scheduling costs are very high for large-scale workflows and they may perform poorly if the system performance is changed dynamically. Demand-driven scheduling schemes achieve high performance for independent tasks, but they may perform poorly for workflows. Dynamic rescheduling schemes have the advantages of these two types of schemes, because tasks are rescheduled using algorithms from static scheduling schemes when the performance is changed. Thus, better performance can be achieved in workflow applications, although the scheduling costs are increased if the system performance is frequently changed. Therefore, we propose a new dynamic scheduling scheme to reduce the number of reschedulings. The rescheduling trigger of this scheme is based on task terminations. Moreover, the scheme reduces the number of reschedulings compared to a scheme using a simple task termination trigger by checking dependencies between tasks. Evaluation using an abstract simulation demonstrated that the number of reschedulings was reduced to approximately 1/4 to 1/100 of that without, and with a 5% increase of the execution time.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top