Improvement of CRCW-COMBINED-PRAM over CRCW-COMMON-PRAM

Question

In problem 2 of 2016, September.

The algorithm can be that:

1) in one parallel for loop y[i] = abs(a[i]-a[i-1]) where y is an array.

2) apply the algorithm of page 39 on array y with slight changes to return maximum ( with O(n) processors and O(1) time.

This can be done in Combined to answer part a and b of the question.

What optimization can be done in case of Common?

The only optimization I could think of (for this algorithm) was changing the 'if' statement with an 'and' associative function.

Answer 1

First of all, you are right that one can first compute the array y you mention using O(n) processors in one step. Then, we apply the algorithm for computing the maximum in O(1) steps using again O(n²) processors (not O(n) as you wrote), so that this PRAM algorithm is not work-efficient. This algorithm can be run on a CRCW-COMMON PRAM machine, since all common writes write the same value (the maximum). 

Part c) asks for an optimization for a CRCW-Combined PRAM machine. In contrast to CRCW-COMMON, this machine allows concurrent writes with different values to a variable that are resolved by application of a commutative and associative binary function. The idea in part c) is to use the maximum of two values as such function so that after having computing your array y, the algorithm simply assigns all y[i] in parallel to a variable m. Since these writes are resolved by the maximum function, the final result in m is the maximum of array y.

Comments

Wouldn't it be possible to use the algorithm "Another Parallel Computation of Maximum" on page 39 to use O(N), processors? Because it also calls FirstOnePar and since we have CRCW in both cases we can use it.
Are we using the algorithm on page 34 because of CRCW being (Common) in the first part, hence the need for O(n^2) processors?

---

Right, you can also use that algorithm for computing the maximum of an array with only O(n) processors in time O(1).

---

to be precise this other maximum-algorithm is written down as Minimum.
But Maximum would be the same by replacing FristOneOpt by LastOneOpt.

Is it ok for the exam to use LastOneOpt with the comment to replace the 2 lines 'next y[j]=false' to 'next y[i]=false' and 'next x[yindex+j]=false' to 'next x[yindex+i]=false'

---

Yes, that algorithm was formulated as computation of the minimum, but it can be adapted (as said above) to compute the maximum as well using a function LastOne instead of FirstOne with the intended meaning. As far as I can see, the above mentioned modifications in the algorithms for FirstOnePar and FirstOneParOpt would be sufficient to obtain a corresponding algorithm for LastOne.

It is sufficient to note that plan in the mentioned exercise, it is not needed to list the detailed code.

However, the above mentioned algorithm to compute the minimum/maximum is a bad one that cannot be recommended. Note that for an array of size N with integers in the range {-R,..,R-1}, we would need a local array of size R. For 32-bit integers, this is already a challenge. BTW, I see that the algorithm is broken, since a[i] has type int{R} and can be negative, so that occ[a[i]] would fail. Hence, the type of array a should be better nat{R}.