THE STATIC PARALLELIZATION OF LOOPS AND RECURSIONS

We demonstrate approaches to the static parallelization of loops and r ecursions on the example of the polynomial product. Phrased as a loop nest, the polynomial product can be parallelized by applying a space-t ime mapping technique based on linear algebra and linear-programming. One can choose a parallel program that is optimal with respect to some objective function like the number of execution steps, processors, ch annels, etc. However, at best, linear execution time complexity can be attained. Through phrasing the polynomial product as a divide-and-con quer recursion, one can obtain a parallel program with sublinear execu tion time. In this case, the target program is not derived by an autom atic search but given as a program skeleton, which can be deduced by a sequence of equational program transformations. We discuss the use of such skeletons, compare and assess the models in which loops and divi de-and-conquer recursions are parallelized and comment on the performa nce properties of the resulting parallel implementations.