Estimating the Parallel Start-Up Overhead for Parallelizing Compilers
by Rizos Sakellariou
Abstract:
A technique for estimating the cost of executing a loop nest in parallel (parallel start-up overhead) is described in this paper. This technique is of utmost importance for parallelizing compilers which take decisions on the basis of predicting performance through the quantification of overheads. Such a model is analyzed and the necessary conditions for computing an estimate for the parallel start-up overhead are presented. Based on this estimate, it is shown how to transform parallelizable loop nests in such a way that the start-up cost for parallel execution does not outweigh the gains. Experimental results demonstrate that this transformation results in performance improvements. Finally, it is also shown that such an estimate is essential to predict the performance of codes whose parallelization is based on the multiple execution of a small parallelized program fragment.
Keywords: theory
Source:
R. Sakellariou, Estimating the Parallel Start-Up Overhead for Parallelizing Compilers. In V. Malyshkin (ed.),
Parallel Computing Technologies: Proceedings of the 4th International Conference,
Lect. Notes in Comp. Sci., Vol. 1277, Springer, 1997, pp. 83-93