Design and Implementation of a Data-Parallel Language based on Recusively Defined Data

Data-parallelism is considered as a paradigm that can solve many difficulties of parallel programming such as portability and readability. But the scope of parallelism is restricted to regular arrays because irregular data lead to irregular communications and their implementation often requires particular effort for balanced data distribution. We propose a data-parallel functional language that handles irregular data structures with recursive types. The language expresses the distribution of recursive data with parallel variables in formal parameter patterns. The parallel executions on distributed data are represented by recursive calls which use parallel variables as parameters. We implement the language based on the vector model. We represent the recursive data structures with a set of vectors and transform operations on each node to vector operations. To transform the parallel recursion to vector operations, we must classify computations of a parallel function based on the condition..