Scheduling large task graphs is an important issue in parallel computing. I
n this paper we tackle the two following problems: (I) how to schedule a ta
sk graph, when it is too large to fit into memory? (2) How to build a gener
ic program such that parameter values of a task graph can be given at run-t
ime? Our answers feature the parameterized task graph (PTG), which is a sym
bolic representation of the task graph. We propose a dynamic scheduling alg
orithm which takes a PTG as an entry and allows us to generate a generic pr
ogram. We present a theoretical study which shows that our algorithm finds
good schedules for coarse-grain task graphs, has a low memory cost, and st
low 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. We also provide experimental results that dem
onstrate the feasibility of our approach using several compute-intensive ke
rnels found in numerical scientific applications. (C) 1999 Academic Press.