A simple puzzle

A short post after a loong pause. This means that I'm very busy with other stuff.

I am attending a course about formal verification of systems. The book we use in the course gives an example of the "best" (as claimed by the author) way to parallelize a simple task on 2 CPUs: finding the maximum element in a vector of n elements. The problem with their proposed solution is that it is, IMO, far from the "best". I took me only few moments to think up a solution simpler than the one in the book.

The puzzle for my readers: suggest a way to parallelize the above-mentioned task to 2 CPUs. If you want a bigger challenge, generalize to k CPUs.


Anonymous said...

Okay, I'll bite. One CPU looks for the maximum value between in the [1, n/2] range, and the other in the [n/2+1, n] range. The maximum is the larger value of the two.

What did the author recommend? What was your better (or was it just simpler?) solution?

zvrba said...

The solution you gave is what I had in mind. I don't want to transcribe the algorithm from the book, suffice it to say that it used a SHARED variable to keep the current maximum. With all locking complications stemming from using a single shared variable.