通信を考慮したタスクスケジューリング問題の解法についての一考察

カテゴリ: 部門大会

論文No: GS14-4

グループ名: 【C】平成16年電気学会電子・情報・システム部門大会講演論文集

発行日: 2004/09/02

タイトル(英語): A Study of Task Scheduling Problem Taking Account of Communication Overhead

著者名: 綾部 翼(成蹊大学),津田 耕治(成蹊大学),甲斐 宗徳(成蹊大学)

著者名(英語): Tsubasa Ayabe(Seikei University),Koji Tsuda(Seikei University),Munenori Kai(Seikei University)

キーワード: タスクスケジューリング|並列処理技術|最適化問題|分枝限定法|ヒューリスティックアルゴリズム|Task scheduling|Parallel Processing Technology|Optimizing problem|Branch and Bound method|Heuristic algorithm

要約(日本語): タスクスケジューリング問題の実用的で有効な解法としてDF/IHS法がある。しかしタスク間の通信時間を考慮するとタスクのプロセッサ割当ての組合せ数は激増することになる。まず我々は通信を含んだタスクグラフのスケジューリング解法を得るために分枝限定法であるDF/IHSを拡張した。その中で探索時間を削減するための経験則として、各タスクについて全タスク終了までの時間の下限値を通信を含めて見積もる手法を考案し、枝刈りに適用した。さらにその下限値をもとに、各タスクのプロセッサに割当てる組合せを経験上効果的に限定するためのタスクのグループ化を新しく考案した。以上のアルゴリズムの提案と評価結果について報告する。

PDFファイルサイズ: 4,914 Kバイト