WEKO3
アイテム
並列度・タスク実行時間の偏りを考慮した標準タスクグラフセット STG Ver3 を用いたスケジューリングアルゴリズムの評価
https://ipsj.ixsq.nii.ac.jp/records/61274
https://ipsj.ixsq.nii.ac.jp/records/612740937c4dc-4099-4432-8a0f-61425c8650cb
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-ARC09182022 (1.0 MB)
|
Copyright (c) 2009 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2009-02-19 | |||||||
| タイトル | ||||||||
| タイトル | 並列度・タスク実行時間の偏りを考慮した標準タスクグラフセット STG Ver3 を用いたスケジューリングアルゴリズムの評価 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Performance Evaluation of Minimum Execution Time Multiprocessor Scheduling Algorithms Using Standard Task Graph Set Ver3 Consider Parallelism of Task Graphs and Deviation of Task Execution Time | |||||||
| 言語 | ||||||||
| 言語 | 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 | ||||||||
| Dept. of Computer Science, Waseda University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Dept. of Computer Science, Waseda University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Dept. of Computer Science, Waseda University | ||||||||
| 著者名 |
島岡, 護
今泉, 和浩
鷹野, 芙美代
木村, 啓二
笠原, 博徳
× 島岡, 護 今泉, 和浩 鷹野, 芙美代 木村, 啓二 笠原, 博徳
|
|||||||
| 著者名(英) |
Mamoru, Shimaoka
Kazuhiro, Imaizumi
Fumiyo, Takano
Keiji, Kimura
Hironori, Kasahara
× Mamoru, Shimaoka Kazuhiro, Imaizumi Fumiyo, Takano Keiji, Kimura Hironori, Kasahara
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 本稿では強 NP 困難な組み合わせ最適化問題である実行時間最小マルチプロセッサスケジューリング問題のための標準タスクグラフセット STG Ver3 を提案するとともに，それを用いたアルゴリズムの性能評価について述べる． STG Ver2 はタスク実行時間生成乱数，先行制約形状生成乱数により生成されたタスクグラフセットである． STG Ver3 は STG Ver2 にタスクの並列度，タスク実行時間の偏差に考慮を加えることにより生成した “並列度セット” ， “正規化偏差セット” により構成される．評価の結果，最適化アルゴリズム DF/IHS (Depth First/ ImplicitHeuristic Search) では 87.25% ， PDF/IHS (Parallelized DF/IHS) では 92.25% の問題で 10 分以内に最適解を得られることを確認した． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | This paper proposes the “Standard Task Graph Set Ver3” (STG Ver3) to evaluate performance of heuristic and optimization algorithms for the minimum execution time multiprocessor scheduling problem. The minimum execution time multiprocessor scheduling problem is known as a strong NP-hard combinational optimization problem to the public. The STG Ver2 was created by random task execution times and random predecessors. In addition, the STG Ver3 considers parallelism of task graphs and deviation of task execution times to let us understand characteristics of algrithms. This paper describes evaluation results by applying the STG Ver3 to several algorithms. Performance evaluation show that DF/IHS can give us optimal solutions for 87.25%, and PDF/IHS 92.25% within 600 seconds. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN10096105 | |||||||
| 書誌情報 |
研究報告計算機アーキテクチャ（ARC） 巻 2009, 号 14(2009-ARC-182), p. 127-132, 発行日 2009-02-19 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
