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

• Item type: SIG Technical Reports(1)
• 公開日: 2005-01-21
• タイトル: 並列度を考慮した標準タスクグラフセットを用いた実行時間最小マルチプロセッサスケジューリングアルゴリズムの性能評価
• タイトル / 言語: en
• タイトル: Performance Evaluation of Minimum Execution Time Multiprocessor Scheduling Algorithms Using Standard Task Graph Set Which Takes into Account Parallelism of Task Graphs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 早稲田大学理工学部 コンピュータ・ネットワーク工学科
• 著者所属: 早稲田大学理工学部 コンピュータ・ネットワーク工学科
• 著者所属: （株）ソニー・コンピュータエンタテインメント
• 著者所属: 早稲田大学理工学部 コンピュータ・ネットワーク工学科
• 著者所属(英): en
• 著者所属(英): Dept. of Computer science, Waseda University
• 著者所属(英): en
• 著者所属(英): Dept. of Computer science, Waseda University
• 著者所属(英): en
• 著者所属(英): Sony Computer Entertainment Inc.
• 著者所属(英): en
• 著者所属(英): Dept. of Computer science, Waseda University
• 著者名: 松澤, 能成; 坂井田, 真也; 飛田, 高雄; 笠原, 博徳
• 著者名(英): Takanari, Matsuzawa; Shinya, Sakaida; Takao, Tobita; Kasahara, Hironori
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，実行時間最小化ノンプリエンプティブマルチプロセッサスケジューリングの公平な性能評価を可能とするために開発中のベンチマークタスクグラフを用いたヒューリスティックアルゴリズム，実用的逐次型最適化アルゴリズム及び並列最適化アルゴリズムの性能評価について述べる．本論文で用いる標準タスクグラフセット (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 % という高い求解率が得られることが確認された．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper evaluates performance of heuristic and optimization algorithms using benchmark task graphs named Standard TaskGraph Set (STG) for the minimum execution time nonpreemptive multiprocessor scheduling problem. In the standard task graph set used in this paper, in addition to the relationship between parallelism of task graphs and ``the number of processors'' which is the number of processors used in the scheduling problem, the scale of task graphs like 50, 100, 300, 500, 700, 1000 tasks, and parallelism ``para'' of 1.5 ≦ para<20.5 affects optimal solution rate. This paper evaluates perfomance of heuristic algorithms, practical sequential optimization algorithm DF/IHS (Depth First / Implicit Heuristic Search) and practical parallel optimization algorithm (Parallelized DF/IHS) using this STG also for 2 to 16 processors. The evaluation shows for the total 12312 tested problems, FIFO gives us optimal solutions for 15.14 % of the problems, RTRS for 14.63 %, CP for 65.80 %, CP/MISF for 65.85 %, DF/IHS for 87.79 % and PDF/IHS for 91.62 %. Also, it was confirmed that the parallel algorithm PDF/IHS gave us 554.6 times speed up against the sequential algorithm DF/IHS for 2 processors scheduling problems and 461.8 times for 4 processors scheduling problems. When para is close to the number of processors, each algorithm gives us low optimal solution rate, in addition to that, when the number of processors is 4 and ``para > the number of processors'', heuristic algorithms like CP gives us low optimal solution rate (60 %) and however, DF/IHS and PDF/IHS give us high optimal solution rate such as 90 % and 100 % respectively.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10096105
• 書誌情報: 情報処理学会研究報告計算機アーキテクチャ（ARC）; 巻 2005, 号 7(2004-ARC-161), p. 45-50, 発行日 2005-01-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会