Abstract: Current analytic solutions to the execution time distribution of an N-ary parallel composition of tasks having independent and identically distributed execution times are computationally complex, except for a limited number of distributions. In this paper we introduce an analytical solution based on approximating the execution time distributions in terms of a limited number of statistical moments. This approach allows the parallel execution time to be approximated with O(1) solution complexity for a wide range of execution time distributions, while the approximation ac-curacy outperforms comparable techniques known to date. Experiments show that the error of the predicted mean value of the parallel execution time is even less than 4% for parallel loops comprising up to 10,000 tasks whose execution times are normally distributed. Measurements on real programs (NAS-EP benchmark, PSRS sorter, and WATOR simulator) confirm these results provided the task execution distributions are independent and unimodal.
Citation:
Hasyim Gautama, Arjan J. C. Van Gemund, "Low-Cost Performance Prediction of Data-Dependent Data Parallel Programs," mascots, pp.0173, Ninth IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS'01), 2001
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb