バルク同期スケジューリング問題の近似アルゴリズムの開発

点击翻译按钮获取中文摘要

バルク同期スケジューリング問題(以降BSP問題)に対する近似アルゴリズム開発のための研究を行った。その結果,タスクの実行時間がすべて単位時間であり,かつ,通信遅延が一定の場合に(BSP問題でない)通常の通信遅延を考慮したタスクスケジューリング問題(以降SP問題)のスケジュールを効率よくバルク同期スケジュールに変換する手法を開発した.この手法はSP問題のα-近似スケジュールを対応するBSP問題の2α-近似のバルク同期スケジュールに変換するものである.この手法をSP問題の既存の近似アルゴリズムと組み合わせれば,BSP問題の近似アルゴリズムが得られる.SP問題は古くからよく研究されており,効率の良い近似アルゴリズムが多数知られているため,本研究で開発した変換手法は,BSP問題に対する効率のよい近似アルゴリズムを多数与える有益なものである.さらに本研究では,この提案する変換手法が最適な変換手法である(SP問題のα-近似スケジュールからBSP問題の2α-近似スケジュールより良い近似精度を持つバルク同期スケジュールを生成するアルゴリズムは一般には存在しない)ことの証明も与えた.これらの結果は以下のIEEEの論文誌に採録された:Noriyuki Fujimoto and Kenichi Hagihara,"On Approximation of the Bulk Synchronous Task Scheduling Problem",IEEE Transactions on Parallel and Distributed Systems, Vol.14,No.11,pp.1191-1199,2003