Flat a tree using parallel programming

I’m pursuing a Master’s degree in computer science and as part of the algorithm analysis class we had to solve a problem using parallel programming.

The problem says as follows:

We have a set of trees that can be represented as an array (A), each entry of this array points to its father in the tree. The roots of each tree points to zero. Example:

Image taken from problem description

The challenge was to flat the trees (meaning that each node should point to its tree’s root) writing a parallel algorithm that runs in O(log2 n) and using n processors. The final result should looks like the image below:

Image taken from problem description

Step by step solution

1. Assume that each reading instruction happens before the writing instructions.
2. Create a new array C of size n (this is to use C as an auxiliar array to send the result. If we prefer we can avoid the use of C and directly modify A).
3. Define a loop that will iterates ⌈log n⌉ times, the instructions inside this loop will be executed in parallel according the number of processors (n).
4. If A[i] is equals to zero then C[i] = A[i], that’s because we dealing with a root node.
5. If A[i] is different to zero, we have to check that A[A[i]] (A[i]’s parent) is different to zero. Two things could happen here:

a. A[A[i]] is equal to zero, this means that A[i]’s parent is a root, so we should assign C[i] = A[i] to keep the flat level.

b. A[A[i]] is different to zero meaning we need to flat more levels, so we do C[i] = A[A[i]] (we do the same thing in A, A[i] = A[A[i]]).

Pseudocode solution

The solution I gave to the problem