Stochastic prediction of execution time for dynamic bulk synchronous computations

We consider the problem of execution time prediction for non-deterministic bulk synchronous computations on multiprocessors. We formulate the evolution of the execution time of a processor as two random workload change models: additive and multiplicative. These two models reflect parallel commutations in which the workload change of a processor is independent of its workload and proportional to its workload, respectively. We take advantage of their salient features and show that approaches based a central limiting theorem in statistics are viable to approximate the execution time after a certain transient time interval. By an elegant coordination of some results from order statistics and convergence rates in the central limiting theorem, we derive explicit bounds on the execution time under some mild assumptions on distributions. The accuracy of the prediction is analyzed rigorously and verified by simulations.