EREW parallel random-access machine algorithms

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