標準タスクグラフセットを用いた実行時間最小マルチプロセッサスケジューリングアルゴリズムの性能評価

情報処理学会 Web Site 被引用文献2件 参考文献18件

書誌事項

タイトル別名
  • ヒョウジュン タスクグラフセット オ モチイタ ジッコウ ジカン サイショウ マルチプロセッサスケジューリング アルゴリズム ノ セイノウ ヒョウカ
  • Performance Evaluation of Minimum Execution Time Multiprocessor Scheduling Algorithms Using Standard Task Graph Set
  • 並列化コンパイラ

この論文をさがす

抄録

本論文では，強NP困難な組合せ最適化問題である実行時間最小マルチプロセッサスケジューリング問題に対するヒューリスティックアルゴリズム，逐次および並列最適化アルゴリズムの性能評価のための``標準タスクグラフセット''と名付けたランダムタスクグラフ集を提案するとともに，それを用いたアルゴリズムの評価について述べる．従来のマルチプロセッサスケジューリングアルゴリズムの研究においては，評価に使われたランダムグラフが提案アルゴリズムに都合のよいランダムグラフである，あるいは他の研究者が検証しようとしても使われたグラフが手に入らずどのアルゴリズムが真に良いのかを比較できないという問題があった．提案する標準タスクグラフセットはこの問題を解決するため，従来の論文で使用された種々のランダムグラフ生成法を用い多種のランダムタスクグラフを生成するとともにタスクグラフとその解などの情報をWebサイトで公開しており，これを用いることで今後スケジューリングアルゴリズム研究者が各種アルゴリズムも同一条件下で公平に評価し，アルゴリズムの性能を比較することが可能となる．また本論文ではこの標準タスクグラフセットのタスク数50から5 000までのタスクグラフ2 700例を用いてアルゴリズムの評価を行い，標準タスクグラフセットの有効性の評価も行う．この評価ではヒューリスティックアルゴリズムCP，CP/MISFではそれぞれ全問題の68.22%，68.46%に，逐次最適化アルゴリズムDF/IHSでは600秒の探索上限時間内に85.79%，並列最適化アルゴリズムPDF/IHSでは4プロセッサSMP上で89.60%に最適解が得られることが確かめられ，提案する標準タスクグラフセットがヒューリスティックおよび逐次・並列最適化アルゴリズムの評価に有効であることが確認された．

This paper proposes a ``Standard Task Graph Set'' (STG) to evaluate performance of heuristic and optimization algorithms for the minimum execution time multiprocessor scheduling problem, which is known as a strong NP-hard combinational optimization problem, and describes evaluation results by applying them to several algorithms. In the previous researches on multiprocessor scheduling algorithms, there exists a problem that it is not able to compare the performance to decide which algorithm is better, because the task graphs fit for the algorithm proposed in each paper or were not available to the other researchers. To cope with this problem, STG makes possible the fair evaluation and comparison of the algorithms under the same conditions for every researchers by giving many kinds of random task graphs based on various task graph generation methods used in the literature with their scheduling results, and making them available from Website.This paper evaluates several algorithms using 2,700 task graphs with 50 to 5,000 tasks from STG and evaluates its effectiveness.The performance evaluation confirms that heuristic algorithms CP and CP/MISF could obtain optimal schedules 68.22% and 68.46% of tested cases, 85.79% by a sequential optimization algorithm DF/IHS, and 89.60% by a parallel optimization algorithm PDF/IHS on a SMP with 4 processor elements within 600 seconds upper limit.It was also confirmed that the proposed STG is useful for evaluation of the heuristic and the optimization scheduling algorithms.

収録刊行物

被引用文献 (2)*注記

もっと見る

参考文献 (18)*注記

もっと見る

キーワード

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

問題の指摘

ページトップへ