Optimal parallel processing of random task graphs

We consider scheduling of tasks of parallel programs on multiprocessor syst ems where tasks have precedence relations and synchronization points. The t ask graph structures are random variables in the sense that successors to a task do not become known until the task is executed. Thus, as is often the case with parallel processing, scheduling must occur at run time rather th an compile time. We prove that a simple scheduling policy stochastically mi nimizes the processes of task completions and job (i.e. set of parallel tas ks) completions for several classes of task graph structures. Copyright (C) 2001 John Wiley & Sons, Ltd.