適応型手法の改良による大規模な実ワークフローの高速スケジューリング

• 松本 真樹

• 大野 和彦

• 佐々木 敬泰

• 近藤 利夫

書誌事項

タイトル別名

• A Fast Adaptive Scheduling Scheme for Large-scale Workflows

抄録

近年，コストパフォーマンスやスケーラビリティの面から，PC クラスタを利用した大規模並列処理への需要が高まっている．特にワークフロー型の大規模並列処理システムにおいて高いスループットを得るには，静的スケジューリング処理が重要になってくる．しかし，高精度な静的スケジューリング手法は計算コストが非常に高い．一方，実アプリケーションはワークフロー内に類似したサブワークフローを複数持つ場合など，ある程度規則的なワークフローとなることが多い．そこで本論文では，このようなサブワークフローに着目しスケジューリングの計算量を削減する手法を提案する．本手法では，個々のサブワークフローを疑似タスクとして扱い，全体のワークフローや個々のサブワークフローに対して個別に我々が開発した適応型スケジューリング手法を用いる．これにより一回の静的スケジューリング手法で扱うタスク数を減らすことができ，高速なスケジューリングが可能となる．抽象シミュレーションにより本手法を評価した結果，タスク数が 10,000 規模の場合に適応型スケジューリング手法の約 1/100 の時間でスケジューリングを行うことができた．Task scheduling is very important for efficient execution of large-scale workflows. However, scheduling large-scale workflows using existing scheduling schemes is not practical because of the huge computational costs. To solve this problem, we have proposed an adaptive scheduling scheme with low computational cost. However, many practical workflows are collections of sub-workflows and the scheme may not schedule them efficiently. Therefore, we propose a new scheme that improves adaptive scheduling. In our scheme, sub-workflows are replaced to pseudo tasks and an adaptive scheme schedules the workflow which contains pseudo tasks and each sub-workflows separately. The evaluation using an abstract simulation shows the scheduling time of our scheme is approximately 1/100 compared to the adaptive scheme.

収録刊行物

• 研究報告ハイパフォーマンスコンピューティング（HPC）

  研究報告ハイパフォーマンスコンピューティング（HPC） 2011 (60), 1-8, 2011-07-20

詳細情報

• CRID: 1572261551916550784
• NII論文ID: 110008583416
• NII書誌ID: AN10463942
• 本文言語コード: ja
• データソース種別:
  • CiNii Articles