Gemund, Low-cost static performance prediction of stochastic parallel task compositions

Abstract—Current analytic solutions to the execution time distribution of a parallel composition of tasks having stochastic execution times are computationally complex, except for a limited number of distributions. In this paper, we present an analytical solution based on approximating execution time distributions in terms of the first four statistical moments. This low-cost approach allows the parallel execution time distribution to be approximated at ultra-low solution complexity for a wide range of execution time distributions. The accuracy of our method is experimentally evaluated for synthetic distributions as well as for task execution time distributions found i