Fill This Form To Receive Instant Help
Homework answers / question archive / [a] Consider an n-element list in an n-processor EREW parallel random-access machine, where some elements of the list are marked as being blue
[a] Consider an n-element list in an n-processor EREW parallel random-access machine, where some elements of the list are marked as being blue. Describe an efficient parallel algorithm to form a new list consisting of all the blue elements.
[b] Suppose that some nodes in an n-node binary tree are marked blue. Describe an efficient EREW algorithm to form a list consisting of the blue nodes that do not have a blue ancestor.
[a] sharedvar values : array[1..n] of elements;
blues : array[1..n] of elements;
flags : array[1..n] of boolean;
mapping : array[1..n] of words;
var i : word;
numblues : word;
Step 1:
par i := 1 to n sync do
if (values[i] is blue)
flags[i] := true;
else
flags[i] := false;
end;
end;
This step will take O(1) time and at the end of it flags array will indicate the blue marked elements.
Step 2:
We need to generate a new list that holds only the blue elements, i.e. all the blue elements should be packed towards one end of this list.
We could easily do this in O(n) even with one processor in a modified first step, as shown below -
numblues := 0
i := 1 to n do
if (values[i] is blue)
numblues := numblues + 1;
blues[numblues] := values[i];
end;
end;
However, if we can find out the index in blues list, for each i corresponding to a blue element in values array (a one-to-one mapping wrt blue elements), we can take advantage of n processors at our disposal and populate the blues list in parallel in O(1) time.
One of the ways in which this mapping can be generated is given below, considering true=1 and false=0. Assuming that n is greater than zero.
mapping[1] := flags[1];
i := 2 to n do
mapping[i] := mapping[i-1] + flags[i];
end;
numblues := mapping[n];
But this method takes O(n) time, and doesn't take any advantage of having n processors to work with.
Notice that all we are doing in the mapping process, is nothing but add scan of flags array.
Can we use divide-and-conquer logic here? Yes. If we divide flags into two parts - first n/2 and remaining (n - n/2). The mapped-to index for first blue element in second half will be 1 more than the mapped-to index for the last blue element in first half, in other words it will be equal to (number of blue elements in first half + 1). Same can be said about two further parts of each part, and so on.
Looking at above in another way, we can also say that
- first we compute the mapped-to index values for two parts separately, which can be done in parallel.
- then we add last mapped-to index in first part to each mapped-to index in second part to get the mappings wrt both these parts put together in this order. This can also be done in parallel.
For obvious reasons, we will prefer not to adjust the mappings again and again (to reduce number of addition operations), which we can do by careful implementation of above idea.
Basically what we need is a parallel implementation of scans, that computes the number of blue elements in one pass from leaves to the root and in another pass it uses this information downwards to leaves for computing the mappings.
First pass (leaves to root)
For each internal node on the path, do
bluesinleft = value of left child
subtreesum = sum of values from left and right child
// subtreesum will be passed as the value of this node to parent.
end
Second pass (root to leaves)
For each node on the path, do
parval = bluesinleft value of parent (for root node, it will be 0), will be passed as the value of this node to left child.
(parval + bluesinleft value of this node) will be passed as the value of this node to right child.
end
At the leaves, we can either collect values to be pushed down to left child or right child, but uniformly across. This will control how mapping values are to be used as indices, and also the computation of the value of numblues. Please see the example below for details.
Computations at each level can be done in parallel. Thus Each of the passes will be accomplished in O(lg(n)) time - at each level value set to be processed gets halved in first pass (n to 1), and other way round in second pass (1 to n).
So best case running time of this step would be O(lg(n)).
Step 3:
par i := 1 to n sync do
if (flags[i] is true)
blues[mapping[i]] := values[i];
end;
end;
Clearly this is O(1) step.
So, overall running time of this algorithm will be
O(1) + O(lg(n)) + O(1)
= O(lg(n))
Let us work it out (step 2 onwards) with example flags array [1,0,0,1,1,0,1,1], corresponding value set being [v1,v2,v3,v4,v5,v6,v7,v8].
First pass (leaves to root) :
comma pairs denote (bluesinleft,subtreesum).
[2,5]
|
[(1,2) (1,3)]
|
[(1,1) (0,1)] [(1,1) (1,2)]
|
[1 0] [0 1] [1 0] [1 1]
|
Leaves: [1] [0] [0] [1] [1] [0] [1] [1]
Second pass (root to leaves) :
comma pairs denote (parval for left child, parval for right child).
(0,2)
|
[(0,1) (2,3)]
|
[(0,1) (1,1)] [(2,3) (3,4)]
|
Leaves: [(0,1)] [(1,1)] [(1,1)] [(1,2)] [(2,3)] [(3,3)] [(3,4)] [(4,5)]
If we collect the first value of pair at leaves, we get the mappings as [0,1,1,1,2,3,3,4] - actual indices from which can be computed by adding 1 to selected value, as we are indexing the array 1 onwards.
numblues := mapping[n] + 1 = mapping[8] + 1 = 4 + 1 = 5
If we choose second member of pair at leaves, we get the mappings as [1,1,1,2,3,3,4,5] - these values can directly be used as indices.
numblues := mapping[n] = mapping[8] = 5
Combining above information with flags array, we get blues array as [v1,v4,v5,v7,v8].
[b] In this case performance of algorithm will depend upon the nature of input binary tree.
If it is the worst case of binary tree i.e. a chain of n nodes, finding the required nodes itself will take O(n) time.
If it is best case i.e. as completely balanced as possible with n nodes, then finding the required nodes will take O(lg(n)) time.
It is assumed that the nodes of binary tree are stored in values array and tree is implemented using indices as links to children and parent nodes. Parent of root node is NULL.
sharedvar values : array[1..n] of nodes;
blues : array[1..n] of nodes;
flags : array[1..n] of boolean;
mapping : array[1..n] of words;
var i : word;
numblues : word;
parent : node;
Step 1:
par i := 1 to n sync do
if (node values[i] is blue)
// Check whether it has a blue ancestor.
flags[i] := true;
parent := parent of values[i];
while (parent is not NULL) do
if (parent is blue)
flags[i] := false;
break out of while loop
end
parent := parent of parent;
end
else
flags[i] := false;
end;
end;
This step can take O(lg(n)) to O(n) time depending on input tree, as discussed earlier. Packing the desired nodes into new list will require same effort as in problem(a) i.e. O(lg(n)). Hence solution to this problem can take O(lg(n)) to O(n) time depending upon nature of input tree.