For the second lock, if we move the if statement into the lock and let done=true if all threads say the predicate is true, can we remove the second lock then? (This is not for speed-up, just for the question on if we can remove any barriers.)

First barrier: we need to make sure every thread has reset diff before it is updated by any partial sum. Otherwise, diff might be reset after accumulating some partial sums.

Second barrier: we need to make sure all partial sums are accumulated before examining the if statement so that all threads get the same answer using the same diff.

Third barrier: we need to make sure all threads have computed done before it goes to the next cycle. Otherwise, some threads might use the wrong diff value to examine the if statement since diff is reset on the top of each cycle.

To nanoxh: my guess is yes since we have the third barrier there to stop and wait for all threads to finish, but I am not very sure...and it may slow down the process by not letting the if statement to run in parallel...

Couldn't we also move the first barrier to after the for loop but before the lock and accumulating the partial sums in diff? It seems like that should be okay since the for loop doesn't depend on the value of diff, and threads would be able to continue their work sooner.

@jchen I think you're right, the for loop doesn't depend on the global variable diff so removing the barrier will not effect the correctness of the result