An average-case analysis of online non-clairvoyant scheduling of independent parallel tasks

We analyze the average-case performance of an online non-clairvoyant scheduling algorithm for independent parallel tasks. The algorithm schedules tasks without prior knowledge of the future tasks and the execution times of the tasks that are not yet completed. By using reasonable assumptions, we find an asymptotic average-case performance bound and develop a method to calculate the bound for arbitrary probability distribution of task sizes. In particular, we show that when task sizes are uniformly distributed in the range [1..C][1..C], an asymptotic average-case performance bound ofMM-(3-(1+1/C)C+1)C-1can be achieved, where M   is the number of processors. The above asymptotic average-case performance bound achieves its maximum value when C=MC=M, which is approximately 1/(e-2)=1.39221121/(e-2)=1.3922112 for large M. We also present extensive numerical and simulation data to demonstrate the accuracy of our analytical bound.