Scheduling of Random Task Graphs on Parallel Processors Invited paper, presented to honor Edward G. Coffman, Jr. on his 60th Birthday
Zhen Liu · 1995
Task graphs are one of the most used models for representing parallel computations. The structures of these graphs are sometimes obtained when compiling the parallel programs. In many other cases, however, they can be determined only at run time. In this paper, we study the scheduling of parallel computations whose task graphs are generated at Tun time. We obtain a simple optimal scheduling policy for the stochastic minimization of the running time of task graphs when these graphs are generated according to some specific statistical laws.