Our research is related with studies of parallel programming with parallel skeletons and calculational approach to parallelization.
Skeleton based parallel programming originates from the parallel implementation of BMF model[1,21], where the parallel data collection is parallel list and parallel skeletons are mainly map and reduce. Based on the constructive algorithmics, BMF model was extended to general algebraic data types such as trees, and parallel implementations of tree skeletons on wide range of parallel systems have been presented[7,17,22]. With these results, skeleton based programming becomes an efficient programming model which can extend the scope of data parallel execution to irregular data structures. This is advocated to be very useful by many researchers[18,19].
But data parallel programming using predefined skeletons is not easy. Therefore many researches have tried to build skeleton based parallel programs from sequential recursive programs. Most of the researches are based on the program transformation in calculation form. In these approaches, parallelization schemes start from the homomorphism lemma[1][9]. Because the lemma can be applied to restricted recursive programs, there have been many researches to expand the scope of parallelization to almost homomorphisms[16,12], functions on sequential lists[3,6,8,13], functions with accumulation parameters[13,14], functions on general recursive structures[14] and so on. However the calculational method for parallelization is still not so strong that they can parallelize recursive functions with complex data flow like the inorder function.
We propose an alternative approach to build skeleton based parallel programs from recursive functions. We analyze the data parallelism of subexpressions in recursive functions. Based on the analysis, we can generate skeleton based parallel programs. In this way, we can parallelize recursive functions with complex data flow which are often originated from let expressions with tuple bindings.
Our approach is inspired by the loop parallelization technique based on dependency analysis. But functional programs on recursive data structures have irregular iteration structures. We present an analysis and parallelization method for such programs using polytypic parallel skeletons as the parallel model for object programs.