文献

J-GLOBAL ID：201302287135891527   整理番号：13A1089345

通信遅延を含むタスクスケジューリング問題の並列分枝限定法に基づく探索解法

A Parallelized Branch-and-Bound Search Method for Task Scheduling Problem with Consideration of Communication Overhead

著者 (2件)： 栗田浩一 (成蹊大) ,  甲斐宗徳 (成蹊大)
資料名： 成蹊大学理工学研究報告  (成けい大学理工学研究報告)
巻： 50  号： 1  ページ： 17-27  発行年： 2013年06月01日 
JST資料番号： F0423A  ISSN： 1880-2265  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 著者らはノード/プロセッサ間の通信遅延を考慮したタスクスケジューリング手法として,分枝限定法による逐次最適化アルゴリズムDF/HIS(Depth First/Implicit Heuristic Search)法に通信遅延の組合せを足し合わせた並列最適化解法を研究している。本論文では,スケジューリング手法における下限値としてタスクの処理時間と互いに結ばれたエッジの通信遅延だけを考慮するREDIC(Remaining Distance Including Communication Overhead)法を改良し,探索効率の向上を図った。具体的には,1)プロセッサ数を考慮した下限値の生成,2)後続タスクの処理時間を考慮した下限値の生成,3)探索中の下限値の更新といったアルゴリズムを提案した。その結果,1)はREDIC法よりも最適解に近い下限値を生成でき,2)によって通信遅延時間が高い場合の下限値の最適解との差を縮められ,3)によってスケジューリング効率を向上できることが確かめられた。そこで,1)~3)を追加した最適化スケジューラを用いて12コアによる並列探索を行う評価実験を試み,最適解発見までの探索時間削減率及び指定実行時間内での初期解からの暫定解向上率が向上することを示した。

シソーラス用語： *スケジューリング ,  *分枝限定法 ,  *探索問題 ,  *並列処理 ,  最適化問題 ,  遅れ ,  高速化 ,  解 ,  オペレーティングシステム ,  評価試験 ,  時間
準シソーラス用語： スケジューラ ,  *タスクスケジューリング ,  最適解 ,  探索時間 ,  通信遅延

分類 (4件)： オペレーティングシステム  (JD03020J) ,  その他のオペレーションズリサーチの手法  (KA03070E) ,  人工知能  (JE08000Z) ,  ディジタル計算機方式一般  (JC02010O)

タイトルに関連する用語 (6件)： 通信遅延 ,  タスクスケジューリング ,  問題 ,  分枝限定法 ,  探索 ,  解法