非均質環境における適応型スケジューリング手法の提案と評価

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

誌名
電子情報通信学会論文誌 D   Vol.J93-D   No.6   pp.693-704
発行日: 2010/06/01
Online ISSN: 1881-0225
Print ISSN: 1880-4535
論文種別: 特集論文 (情報爆発論文特集)
専門分野: 並列分散処理
キーワード: 
スケジューリング,  並列処理,  分散計算,  高性能計算,  

本文: PDF(442.9KB)
>>論文を購入


あらまし: 
近年,広域ネットワーク上に分散したクラスタを利用した大規模並列処理への需要が高まっている.特にワークフロー型の大規模並列処理システムにおいて高いスループットを得るには,静的スケジューリング処理が重要になってくる.しかし,高精度な静的スケジューリング手法は計算コストが非常に高い.そこで実行環境を階層モデル化し階層ごとに異なるスケジューリング方式を使い分ける,階層型スケジューリング手法を提案し,計算コストの大幅な削減を実現している.しかしタスク数が非常に多い場合,同手法の局所スケジューラがボトルネックになる.そこで本論文では適応型スケジューリング手法を提案する.これは互いに依存関係を含まないタスク群に対して,依存関係を考慮せず計算コストの低い独立タスクのスケジューリング手法を用いることで,スケジューリング処理の高速化を行う.抽象シミュレーションにより本手法を評価した結果,タスク数が10000規模の場合に本手法単独ではHEFTの約1/1000,階層型スケジューリング手法に組み込んだ場合に約1/50~1/100の時間でスケジューリングを行うことができた.