| 講演名 | 1999/6/18 マルチプセッサスケジューリング問題のためのメタヒューリスティック解法RMLSの提案と評価 田中 貴文, 藤田 聡, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では,自動並列化コンパイラを実現するための重要な問題の一つであるマルチプロセッサスケジューリング問題(MSP)に注目し,MSPを解くためのメターヒューリスティック解法としてRMLSという手法を提案する.ランダムに生成されたインスタンスを用いた計算機実験の結果,RMLSはインスタンスのもつ並列性がプロセッサ数よりも十分大きい場合に特に有効に働くことがわかった.具体的には,枝密度が20%のとき,通常のリストスケジューリングによって生成される解が最大で14%改良されることがわかった. |
| 抄録(英) | In this paper, we propose a new metaheuristic method RMLS (Romdomized Multiple Local Search) for obtaining a near-optimal solution to multipocessor scheduling problem that has been recognized as a key problem for realizing efficient parallelizing compilers. As a result of computational experiments we show that if the given instance has enough parallelism with respect to the given number of processors, then RMLS outputs a better solution than conventional list scheduling algorithms. In particular, when the density of edges is around 20% and the number of procssors is 2, RMLS gives 14% better solution than the (currently) best list scheduling algorithm. |
| キーワード(和) | マルチプロセッサスケジューリング問題 / メタヒューリスティック |
| キーワード(英) | multiprocessor scheduling problem / metaheuristic |
| 資料番号 | COMP99-20 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1999/6/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | マルチプセッサスケジューリング問題のためのメタヒューリスティック解法RMLSの提案と評価 |
| サブタイトル（和） | |
| タイトル（英） | RMLS : A metaheuristic method for the multiprocessorr scheduling problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | マルチプロセッサスケジューリング問題 / multiprocessor scheduling problem |
| キーワード(2)（和/英） | メタヒューリスティック / metaheuristic |
| 第 1 著者 氏名（和/英） | 田中 貴文 / Takahumi TANAKA |
| 第 1 著者 所属（和/英） | 広島大学大学院工学研究科 Graduate School of Information Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 藤田 聡 / Satoshi FUJITA |
| 第 2 著者 所属（和/英） | 広島大学工学部 Electrical Engineering, Faculty of Engineering, Hiroshima University |
| 発表年月日 | 1999/6/18 |
| 資料番号 | COMP99-20 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 130 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |