1. Introduction

Data parallelism implements parallel computation by simultaneously applying the same operation to each element of a data collection. This paradigm is considered as a parallel model which can solve many difficulties of parallel programming [2,10,20]. A single stream of program execution guarantees easier programming and better readability. Massive parallelism can be easily obtained by distributing large data collections.

In functional languages, data parallelism is expressed with the following two components.

• parallel data collections
• a set of higher-order parallel functions, skeletons, which capture an algorithmic form common to a range of parallel computations on the parallel data collection.

For example, in NESL[5], parallel data collections are vectors and parallel skeletons are apply-to-each and a set of built-in parallel functions such as scan and permute. In BMF Model[21], parallel data collections are lists and parallel skeletons are map and reduce.

This paradigm enables efficient and portable parallel programming by encouraging programmers to build the parallel programs from ready-made skeletons for which efficient implementations are known to exist. Taking the form of higher-order functions, the parallel skeletons can be very familiar building blocks to functional language programmers.

However, data parallel programming is still not so easy. In functional languages, data collections such as lists or trees are declared recursively and applications on such data structures are naturally understood and specified using recursion. Extracting predefined forms of data parallelism from such applications and integrating them into efficient parallel programs are not simple.

For example, the following is the sequential program which numbers every node of a tree in in-order. Because the size of the left subtree is required to number the right subtree, inorder function returns not only the numbered tree but also the size of the input tree. Because the same function inorder is applied to each node of a tree using recursion, there can be valuable data parallelism in this program. But, because of dependencies among recursions, it is not straightforward to develop an efficient data parallel program for in-order numbering.

          datatype tree = Leaf of int | Node of int * tree * tree 

          inorder (Leaf x, n) = (Leaf n,1) 
          |       (Node(x,lt,rt), n) = 
             let 
                (t1,s1) = inorder(lt,n); 
                (t2,s2) = inorder(rt,1+n+s1) 
             in
                (Node(n+s1,t1,t2),s1+s2+1) 
             end

In this paper, we propose a method to extract data parallelism from recursive functions. Our research has the following aspects.

• We employ polytypic parallel skeletons as our parallel model for object programs[14]. Our parallel skeletons are polytypic in that they can be generically defined for general algebraic data types such as trees and lists. Therefore, we can extract data parallelism for the irregular data structures.
• We define a classification of subexpressions in a recursive function based on their parallelism using static slicing[23]. Subexpressions of each classification can be executed in parallel using an appropriate skeleton. Using analytical approach, we can parallelize recursive functions with complex data flow.

Our research is presented as follows. In Section 2, we formally define the form of recursive functions to be parallelized. In Section 3, parallel skeletons which are used in object parallel programs are defined. In Section 4, we present an analysis method to classify subexpressions of a function body based on their conditions of parallel execution. In section 5, the form of object parallel program is presented and the parallelization process is sketched with an example. Finally we discuss related works and conclude in Section 6.