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.
2 comments:
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?
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.
Post a Comment