並列度を考慮した標準タスクグラフセットを用いた実行時間最小マルチプロセッサスケジューリングアルゴリズムの性能評価(分岐予測アーキテクチャ及びスケジューリング, SHINING 2005「アーキテクチャとコンパイラの協調および一般」)

概要

論文の詳細を見る
本論文では, 実行時間最小化ノンプリエンプティブマルチプロセッサスケジューリングの公平な性能評価を可能とするために開発中のベンチマークタスクグラフを用いたヒューリスティックアルゴリズム, 実用的逐次型最適化アルゴリズム及び並列最適化アルゴリズムの性能評価について述べる.本論文で用いる標準タスクグラフセット(STG)では, タスクグラフの並列度とスケジューリング対象プロセッサ台数の関係が, 最適解求解率へ影響を与えることに注目し, タスク数規模は50, 100, 300, 500, 700, 1000, タスクグラフの並列度paraは1.5≤para<20.5の範囲で, 3078例のタスクグラフを生成した.このSTGを用いて, 2∿16台のプロセッサに割り当てる際のヒューリスティックスアルゴリズムFIFO(First In First Out), RTRS (Ready Task Random Selection), CP(Critical Path), CP/MISF (CP/Most Immediate Successor First), 実用的逐次型最適化スケジューリングアルゴリズムDF/IHS (Depth First/Implicit Heuristic Search)及び, その並列化アルゴリズムPDF/IHS (Parallelized DF/IHS)の性能評価を行った.この結果, 全12312例において, FIFOで15.14%, RTRSで14.63%, CPで65.80%, CP/MISFで65.85%, DF/IHSで87.79%, PDF/IHSで91.62%の最適解求解率が得られた.また, 探索上限時間を6時間とした場合, SUN 4PE WS Ultra80上で, PDF/IHSはDF/IHSに比ベタスク割り当て対象プロセッサ台数2の時平均554.6倍, 4の時平均461.8倍と非常に高い加速率を得ることができた.さらに, paraとプロセッサ台数が近い時, 各アルゴリズムにおいて求解率が急激に低下し, プロセッサ台数4の時においては, CPなどのヒューリスティックアルゴリズムでは"para>プロセッサ台数"の時においても求解率が低下し, 最適解求解率が約60%であるが, DF/IHSでは約90%, PDF/IHSでは約100%という高い求解率が得られることが確認された.
2005-01-21

スポンサーリンク

概要

著者

関連論文

スポンサーリンク