ory Cost Dynamic Scheduling of Large Coarse G
Michel Cosnard, Emmanuel Jeannot, Laurence Rougeot · 1998
Scheduling large task graphs is an important issue inparallel computing since it allows the treatment of big sizeproblems. In this paper we tackle the followingproblem: how to schedule a task graph, when it is too large to fit into memory? Our answer features the parameterized task graph (PTG), which is a symbolic representation of the taskgraph. We propose a dynamic scheduling algorithm which takes the PTG as an entry and allows to generate a generic program. The pevormances of the method are studied as well as its limitations. We show that our algorithmfinds good schedule for coarse grain task graphs, has a very low memory cost, and has a good computational complexity. When the average number of operations of each task is large enough, we prove that the scheduling overhead is negligible with respect to the makespan. The feasibility of our approach is studied on several compute-intensive kernels found in numerical scientific applications.