Share
Explore BrainMass

EREW parallel random-access machine algorithms

Analyze your algorithm in each of the following cases.

[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.

Solution Preview

[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 ...

Solution Summary

Algorithms are explained in a mix of EREW code and pseudocode, along with verbal explanations, example and execution time analysis.

$2.19