5. Object Parallel Program

Object parallel programs have the form of Figure 6. Parallel skeletons in let bindings compute intermediate results from ${\mathit White}$, ${\mathit Red}$, ${\mathit Blue}$, ${\mathit Yellow}$ and ${\mathit Green}$ expressions in that order. Their results are combined with previous results for next computations using zip skeleton. Each parallel operation can be omitted unless expressions of the corresponding color exist. The overall result is obtained by evaluating ${\mathit Black}$ expressions in bottom-up order of the input recursive data structure.

Figure 6: Form of Object Parallel Programs

Because ${\mathit White}$, ${\mathit Blue}$ and ${\mathit Green}$ expressions only use values already available on all processors, they are transformed to the argument functions for map skeletons. ${\mathit Red}$ expressions are evaluated along the returns of recursive calls and the intermediate results for calculating Red results can be used for the following computations. So, ${\mathit Red}$ expressions are transformed to the argument functions for $scan_{up}$ operation. ${\mathit Yellow}$ expressions evaluates the accumulation parameters for all recursive calls. Because they are evaluated propagating the accumulation parameters along recursive calls and their intermediate results can be also used in next computations, they are transformed to the argument functions for $scan_{down}$ operation. ${\mathit Black}$ expressions compute the overall result using the results of recursive calls and the intermediate results from previous computations. So, they are transformed to the argument functions for reduce.

Figure 7: Parallel Program for In-order Numbering

Argument functions for parallel skeletons are generated in three steps. At first, recursive calls are replaced with variable tuples so that their results can be propagated through the formal parameters of the argument functions for ${\mathit scan_{up}}$ and ${\mathit reduce}$ skeletons. And then, expressions of each color are extracted from the input program in a form of assignments to new variables and the extracted places are replaced with the new variables. Using these extracted expressions for each color, the argument functions for each skeleton are generated. When generating argument functions, new variables from the previous colors are added to the formal parameters so that previous intermediate results can be used.

Resulting parallel program from the inorder function is given in Figure 7. Because there is neither ${\mathit White}$ nor ${\mathit Blue}$ computation, the first and second $map$ operations are omitted. Argument functions for each color are composed of two functions for Leaf and Node constructors. inorder_R1 and inorder_R2 evaluate the size of each subtree. Sizes of subtrees are propagated through Rtemp221 and Rtemp222 variables, and intermediate results are tupled with the current tree size. inorder_Y1 and inorder_Y2 evaluate the accumulation parameters for all recursions using computed values from ${\mathit Red}$ expressions and the accumulation parameter from the upper node. inorder_G1 and inorder_G2 functions are used as the argument functions of map skeletons and inorder_Bk1 and inorder_Bk2 functions evaluate overall results. The execution time of our parallel program is $O(ht)$ with enough processors where $ht$ is the height of the input tree.