Parallel Expression Evaluation using Tree Contraction

Recently I wrote on Sequential Expression Evaluation in its stack-based recursive form. As a part of my course work, I wrote a parallel version for it referencing this. My implementation was in OpenMP using shared memory on SHARCNET.

Parallel implementation is done using Tree Contraction technique. The important operation of this technique is raking, that involves removing of many leaves of the binary expression tree in parallel. Tree Contraction and Raking is explained as under:

For a vertex u in tree having v and w as its left and right children. The vertex v ( and every other node) is associated with label .The initial value of this label id (1,0). At every iteration new value for this labels are evaluated until the the tree is reduced to 3 vertices. The value of the parent node v is given by:

The value of the parent of u, denoted by p(u) is given by:

When we rake v, labels of w are updated. Thus, on applying rake operation repeatedly we get a three-vertex tree T with root r, having the operator, and its children as and .

The value at the root, and hence the expression is given by:

Parallel Expression Evaluation is about applying raking operation in parallel. Here is a glimpse of raking operation.

The raking operation has to be done with a small strategy. Consider this tree.

We clearly cannot rake node 1 and 8, whose parents are consecutive, at the same time. So we apply raking to non-consecutive leaves as they appear from left to right. The algorithm for the raking operation is as:

1. Label the leaves consecutively in order from left to right, excluding the left-most and right-most nodes (since we need then for final evaluation), and store this in an array A of size n. Create a subarray A_odd and A_even that consist of odd- and even-indexed elements of A.

2.for(lg(n+1)) iteration do

1. Apply rake operation that modifies the siblings labels concurrently to all the elements of A_odd that are left children,

2. Apply rake operation that modifies the siblings labels concurrently to all the rest of the elements of A_odd .

3. Make A = A_even.

3.Compute the value of arithmetic expression from the three-vertex binary tree.

A glimpse of this operation in action is here:

The OpenMP implementation of this algorithm gave significant results when applied on a Full Binary Tree with height = 30.

The complexity of sequential arithmetic evaluation, for an n node tree is O(n), while for parallel version it is reduced to O(lg(n)).

All figures, excluding chart, are from here.