Parallel execution time prediction of the multitask parallel programs

A critical problem of predicting the execution time of parallel programs is computing the maximum execution time of tasks involved in the parallel computation. For a parallel composition of nn tasks, distribution information of execution time of the constituent task is crucial to accurately predicting mean, variance and even distribution of execution time of the composition of tasks when the execution time of them is stochastic. This paper presents a method of predicting the maximum parallel execution time of nn constituent tasks, each of which has independent, identically distributed random execution time. First, execution time of any constituent task as a random variable is transformed into standard normal variable, or approximately so, by using Johnson distributions. Then the distribution and moments of the maximum parallel execution time are obtained after appropriate Johnson transformation is chosen and its corresponding parameters are determined. The experiment on synthetic distributions such as exponential distribution shows that most relative errors of the first four moments are near the 0.1%. And the experiment on some practical applications shows that the relative errors of the first four moments are below 0.1%. The computing complexity of our algorithm, as a function of the number nn of the tasks or processors, is O(n)O(n), and even O(1)O(1) while using approximate distribution, such as Gumbel distribution.