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

概要

論文の詳細を見る
本論文では,強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%に最適解が得られることが確かめられ,提案する標準タスクグラフセットがヒューリスティックおよび逐次・並列最適化アルゴリズムの評価に有効であることが確認された.
一般社団法人情報処理学会の論文
2002-04-15

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

スポンサーリンク

概要

著者

関連論文

スポンサーリンク