4.1. Parallelism of Recursive Functions

Functions of Definition 1 apply the same function to each recursive element of a data collection using recursion. Therefore, by distributing elements of the data collection to multiprocessors, we can compute the function applications in parallel by simultaneously applying the function to every recursive element.

But, simultaneous application of the function body to all elements is restrained by the data dependence among recursions. In the beginning, the value of the accumulation parameter is available only for the root node and the accumulation parameters for other recursions must be propagated along recursive calls. If recursive calls are in a function body, their results must be obtained along the return of recursive calls. For example, subexpression 1+n of the inorder function includes the accumulation parameter n. To evaluate 1+n in parallel, the values of n must be available on all processors. But the value of n is available only for the function application on the root node and the value of n for other recursions must be propagated along recursive calls. For another example, the value of s1 is obtained from the first recursive call. Results of the recursive calls can only be obtained along the return of recursive calls.

Observing the inorder function a little closer, there exist dependencies between recursive calls. The second recursive call uses s1, which is the result of the first recursive call, in its accumulation parameter 1+n+s1. If this dependency forces the recursive calls to be evaluated sequentially, parallel execution time of the function application becomes linear to the number of elements. But, in case of the inorder function, because any value of the accumulation parameter is not used to compute the second element of the result, we can get the values of s1 and s2 in bottom-up order without dependencies between sibling recursions. With the values of s1 and s2 first, we can execute the recursive calls of the function body in parallel.

To classify subexpressions of a function body based on their condition of data parallel execution, we divide results of recursive calls into ${\mathit Red}$ results and ${\mathit Black}$ results. ${\mathit Red}$ results do not use any value of the accumulation parameters and ${\mathit Black}$ results may use values of the accumulation parameters. In the inorder function, s1 and s2 are ${\mathit Red}$ results, and t1 and t2 are ${\mathit Black}$ results.

Considering above observations, we classify subexpressions in a function body as follows. For convenience, we use colors to name them. They are classified along the written order.

• White expressions do not use the accumulation parameters and the results of recursive calls. Because White expressions can be evaluated using constants or non-recursive fields of the recursive parameter allocated to each processor, they can be evaluated simultaneously for all matching elements. Therefore White expressions are evaluated in parallel using map skeleton.
• Red expressions do not use the accumulation parameters and are used to evaluate ${\mathit Red}$ results. Because Red expressions can also use Red results, they must be evaluated along the return of recursions propagating ${\mathit Red}$ results upwards. Therefore they can be evaluated in parallel using $scan_{up}$ skeleton.
• Blue expressions do not use the accumulation parameters like Red expressions and are not used to evaluate Red results. They can be evaluated simultaneously for all matching elements after White and Red expressions have been evaluated. Therefore ${\mathit Blue}$ expressions are evaluated using map skeleton after ${\mathit White}$ and ${\mathit Red}$ expressions are evaluated for all elements.
• Yellow expressions are those used to evaluate the accumulation parameters. Because the accumulation parameters can be used to generate the accumulation parameters for recursive calls on connected elements, the accumulation parameters for each element must be evaluated along the recursive call. Therefore $scan_{\mathit dowm}$ skeleton is used to evaluate every accumulation parameter in parallel.
• Green expressions do not use ${\mathit Black}$ results. They can be evaluated simultaneously for all matching elements after White, Red, Blue and Yellow expressions have been evaluated. Therefore they are evaluated in parallel using map skeleton.
• Black expressions are the remaining expressions. Because they are used to evaluate the overall result, they are evaluated along the return of recursions using reduce skeleton.

If some Yellow expression uses any Black expression, it means that there are multiple recursive calls in a function body and a ${\mathit Black}$ result of a recursive call is used to evaluate an accumulation parameter for another recursive call. In this case, the recursive calls cannot be evaluated in parallel and the virtue of parallelization disappears because the parallel execution time becomes linear to the number of elements.