Departmental Bulletin Paper 通信遅延を考慮したタスクスケジューリング問題の並列解法 : サブタスクグラフ最適スケジューリングによる探索効率の改善
Development of Parallelized Solver for Task Scheduling Problems with Communication Delays : Improvements of Search Effectiveness using Optimal Scheduling of Sub-task-graphs

澁谷, 知則  ,  甲斐, 宗徳

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.

Number of accesses :  

Other information