B-010
通信遅延を考慮したタスクスケジューリング問題のための階層的最適化による高速解法

◎長谷川幹・澁谷知則・甲斐宗徳（成蹊大）

強NP困難な計算複雑度を持つタスクスケジューリング問題は、現実の並列実行時にプロセッサ間で生じる通信遅延を考慮した上に大規模なタスク集合に対しては実用的な時間内に最適解を求めることが益々困難になっている。筆者らはこれまでに、実際のソースコードに基づいたタスク集合に対して通信遅延を考慮した並列化分枝限定法によるタスクスケジューリング手法を開発してきた。今回の研究では、タスクグラフの部分最適化を行うことにより、従来の分枝限定法に用いる下限値計算の改良を行った。また、部分最適化したタスク群と全体のタスクグラフを階層的にタスクスケジューリングすることにより解法の高速化を図った。