Title :
Low memory cost dynamic scheduling of large coarse grain task graphs
Author :
Cosnard, Michel ; Jeannot, Emmanuel ; Rougeot, Laurence
Author_Institution :
INRIA Lorraine, Villiers les Nancy, France
fDate :
30 Mar-3 Apr 1998
Abstract :
Scheduling large task graphs is an important issue in parallel computing since it allows the treatment of large size problems. We tackle the following problem: 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 task graph. We propose a dynamic scheduling algorithm which takes the PTG as an entry and allows to generate a generic program. The performance of the method is studied as well as its limitations. We show that our algorithm finds a 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
Keywords :
computational complexity; directed graphs; parallel algorithms; performance evaluation; scheduling; coarse grain task graphs; computational complexity; compute-intensive kernels; generic program; large coarse grain task graphs; low memory cost dynamic scheduling; makespan; numerical scientific applications; parallel computing; parameterized task graph; performance; scheduling overhead; symbolic representation; task graph scheduling; Application software; Computational complexity; Costs; Distributed computing; Dynamic scheduling; Heuristic algorithms; Kernel; Parallel processing; Processor scheduling; Scheduling algorithm;
Conference_Titel :
Parallel Processing Symposium, 1998. IPPS/SPDP 1998. Proceedings of the First Merged International ... and Symposium on Parallel and Distributed Processing 1998
Conference_Location :
Orlando, FL
Print_ISBN :
0-8186-8404-6
DOI :
10.1109/IPPS.1998.669966