3. Polytypic Parallel Skeletons

We use polytypic parallel skeletons as our parallel model. It provides us a set of parallel structures to capture data parallelism of sequential programs.

Our model is composed of map, reduce, upward accumulation, downward accumulation and zip skeletons. The skeletons are polytypic[14] in that they are generically defined for general algebraic data types.

Our model does not force that argument functions for reduce and accumulation to be associative as in [14]. With this freedom, we can fully extract data parallelism from the divide-and-conquer nature of computations on tree-like structures. The associativity of functions can be fully utilized for the efficient implementation of parallel skeletons.

Given a recursive data structure as is defined in the previous section, parallel skeleton functions are generically defined as follows :

• $map$ simultaneously applies one of argument functions to each element.
  
  $$\begin{array}{c} map~\bar{f}~C_i(a,x_{1},\ldots,x_{r_i}) = C... ...{f}=(f_1,\ldots,f_m)%~\mbox{and}~(1 \le i \le m) \end{array}$$
  
  

• $reduce$ applies one of argument functions to each element in bottom-up order propagating results upwards.
  
  $$\begin{array}{c} reduce~\bar{f}~C_i(a,x_{1},\ldots,x_{r_i}) ... ...{f}=(f_1,\ldots,f_m)%~\mbox{and}~(1 \le i \le m) \end{array}$$
  
  

• Upward accumulation function $scan_{up}$ applies one of argument functions to each element in bottom-up order propagating results upwards and keeping the intermediate results for each recursive part in the same structure.
  
  $$\begin{array}{c} scan_{up}~\bar{f}~C_i(a,x_{1},\ldots,x_{r_i... ...,\ldots,x_{r_i}) = a ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \end{array}$$
  
  

• Downward accumulation function $scan_{down}$ applies one of argument functions to each element in top-down order propagating values downwards via accumulation parameters and keeping the intermediate results in the same structure.
  
  $$\begin{array}{l} scan_{down}~\bar{f}~C_i(a,x_{1},\ldots,x_{r... ...~ \mbox{and} ~f_i~a~ap = (v,ap_1,\ldots,ap_{r_i}) \end{array}$$
  
  

• $zip$ merges two algebraic values of the same structure by making tuples pair-wisely.
  
  $$\begin{array}{c} zip~C_i(a,x_{1},\ldots,x_{r_i})~ C_i(b,y_{1... ...(a,b),zip~x_{1}~y_{1},\ldots,zip~x_{r_i}~y_{r_i}) \end{array}$$
  
  

Because the implementation of parallel skeletons is not within the scope of our research, we only summarize well-known results. The parallel time complexity of $map~\bar{f}$ is given by $O(max(T(f_i))_{i=1}^m)$ with enough processors where $T(f_i)$ denotes the computing time for $f_i$. Reduce and accumulation are not so simple to implement, and many researchers applied the tree contraction algorithm for efficient implementation. The naive implementations of $reduce~\bar{f}$, $scan_{up}~\bar{f}$ and $scan_{down}~\bar{f}$ have the parallel time complexity of $O(max(T(f_i))_{i=1}^m \times ht)$ with enough processors where $ht$ is the height of the tree-like structure. The tree contraction algorithm can be applied if each argument function $f_i$ for each node type can be replaced with a set of functions on the binary tree representation with no additional time complexity where partial compositions of the new functions require constant time and space. Using the tree contraction algorithm, $reduce~\bar{f}$, $scan_{up}~\bar{f}$ and $scan_{down}~\bar{f}$ can be computed in $O(log~n \times max(T(f_i))_{i=1}^m)$ parallel time[22].