Predicting the execution times of parallel-independent programs using Pearson distributions

摘要

Predicting the execution time of parallel programs involves computing the maximum or minimum of the execution times of the tasks involved in the parallel computation. We present a method to accurately compute the distribution of the largest (Max) and the smallest (Min) execution time of the composite of a number of parallel programming tasks, each having an independent, stochastic, arbitrary workload. The Max function applies to the general case that the composite task completes at the time its longest constituent task terminates. The Min function applies when the completion of its shortest task terminates the whole parallel process, such as in a parallel searching program. Both the Min and Max density function of a constituent task are characterized in terms of a Pearson distribution. Due to its accuracy, the presented method is especially of interest when the performance of time critical parallel applications must be derived. Both prediction methods are tested against three well-known distributions. Furthermore, the Max prediction method is also tested against a number of measured real-life data parallel programs with different degree of parallelism. The results show excellent accuracy of better than 1% with a very few exceptions in extreme situations.