実用的並列最適化マルチプロセッサスケジューリング アルゴリズムPDF/IHSの性能評価

• Item type: SIG Technical Reports(1)
• 公開日: 1997-11-21
• タイトル: 実用的並列最適化マルチプロセッサスケジューリング アルゴリズムPDF/IHSの性能評価
• タイトル / 言語: en
• タイトル: Performance Evaluation of a Practical Parallel Optimization Multiprocessor Scheduling Algorithm PDF/IHS
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 早稲田大学理工学部電気電子情報工学科
• 著者所属: 早稲田大学理工学部電気電子情報工学科
• 著者所属(英): en
• 著者所属(英): Dept. of Electrical, Electronics and Computer Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): Dept. of Electrical, Electronics and Computer Engineering, Waseda University
• 著者名: 飛田, 高雄; 笠原, 博徳
• 著者名(英): Takao, Tobita; Hironori, Kasahara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，強NP完全な最適化問題である実行時間最小マルチプロセッサスケジューリング問題に対する実用的並列最適化アルゴリズムPDF/IHS (arallelized Depth First/Impricit Heuristic Searc) の性能評価結果について述べる．Sun Microsystems社のマルチプロセッサシステム Ultra Enterprise 3000上でタスク数50から1100の大規模問題に適用した結果，wall?clock timeで600秒以内に最適解を得られた問題の割合は逐次型アルゴリズムDF/IHS (epth First/Implicit Heuristic Searc)で．69．3%だったのに対し，3PEを用いたPDF/IHSでは80．8%，6PEでは82，8%と向上した．また6PEで最適解が得られた問題の平均求解時間はIPEで107．5秒であったのに対し，6PEで5．8秒となっており，6PEを用いてIPEの平均18．5倍の速度向上を得るなど，スーパーリニアスピードアップが有効に引き出せることが確認された．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper describes performance evaluation of a practical parallel optimization algorithm PDF/IHS (Parallelized Depth First / Impricit Heuristic Search) to very large scale problems with more than one thousand tasks. PDF/IHS has been impremented on a shared main memory multi processor system Ultra Enterprise 3000 and applies to 50 - 1l00 tasks problems. Within 600 second wall-clock time, it was confirmed that optimal schedules were found for 69.3% of problems on one processor, 80.8% on 3 processors and 82.8% on 6 processors. An average search time for optimal solution was reduced from 107.5 [s] by sequential DF/IHS to 5.8 [s] (18.5 times speedup) with 6 processors,
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10505667
• 書誌情報: 情報処理学会研究報告数理モデル化と問題解決（MPS）; 巻 1997, 号 113(1997-MPS-016), p. 13-18, 発行日 1997-11-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会