分散処理の効率化のための実行時間予測手法

書誌事項

タイトル別名
  • ブンサン ショリ ノ コウリツカ ノ タメ ノ ジッコウ ジカン ヨソク シュホウ
  • Run Times Prediction for Load Balancing Efficiently

この論文をさがす

説明

並列処理環境の利用効率を向上させるためには,効率的なタスクスケジューリングや負荷分散システム等が必要である.しかしそれらの中には,システムに投入されるプロセスの実行完了時間が既知であるという前提のもとで構築されている手法が多々存在する.よって,それらを実際にシステムに導入する際,投入されるプロセスの実行時間予測が必要となる.過去の実行履歴から予測対象プロセスに類似したプロセスを発見し,その情報を用いることで実行時間予測が可能である.ここで,プロセス間の類似性をどのように規定するかという問題が生じる.本論文で提案する予測手法では,プロセス間の類似性を判定するために有用なプロセス情報を,相互情報量を用いて選択する.それによって得られる複数の類似判定用テンプレートを用いて複数回の仮予測を行い,t分布によって定義される信頼度とプロセス情報数に基づく予測選択を行う.予測実験の結果,提案手法が従来手法よりも高い予測精度を示すことを確認した.

Task runtime prediction is often required for task scheduling algorithms and load balancing methods because some scheduling methods exploit execution time of tasks. Task runtime can be predicted by using historical information of “similar” task runs. That is because the execution time of similar task tends to be more similar than execution time of tasks that have no same task property. In this strategy, an important problem is how we can define similarity between task runs. In this paper, we propose a runtime prediction method which uses mutual information to define similarity measure and predictor selection based on confidence index and the number of task property in the set for measuring similarity. Experimental results indicate that the proposed method can predict task runtimes more accurately than previous methods.

収録刊行物

キーワード

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

問題の指摘

ページトップへ