通信遅延を考慮したタスクスケジューリング問題の並列解法 : サブタスクグラフ最適スケジューリングによる探索効率の改善

Abstract

In order to implement high performance parallel processing, task scheduling is a very important key technology. However, task scheduling problems belong to very difficult optimizing problem and are not be able to solve in practical time. So, it is required to detect sub task graphs, which can be partially optimized independently, as soon as possible. Each sub task graph can be recognized as a macro task, therefore, total number of tasks will be reduced, and this results in reducing the time to solve scheduling problems. In this paper, we propose a new sub task graph detection mechanism which can find more sub task graphs. We show that some scheduling problems, which were impossible to solve by the conventional methods, can be solved.