In the first class, we had an exercise where 4 students added numbers.
For the incorrect code, imagine we had a 5th person who would tell each student the current sum and they reply with the sum after they added their current element. This has a race condition if the 5th student tells multiple others the same sum.
For the correct code, imagine that the 4 students all do their sums independently, then tell the 5th person their partial sums. Which, in fact, is what happened in the class demo.
khans
Prof. Kayvon prefers there not to be a 5th person - the reduce-add is really more like the 4 students adding their numbers together by a predefined order.
Cake
A point that was mentioned in lecture: reduce_add may be "called" once in each program instance, but it only "returns" once, since it stores the final return value in sum, a uniform variable.
BestBunny
It was mentioned during class that although the code on the left generates a compile-time error due to sharing a uniform value across different instances, once the programmer indicates parallelism with a foreach loop, the compiler does not confirm the accuracy of the statement. It simply assigns the various iterations to the gang in any way which thereby creates race conditions in the program on the left (if it compiled).
haoala
A race condition might arise if multiple instances load the same value of sum, add to it and write the result back. The instance which does the later write "overwrites" the value of sum computed by an instance which wrote earlier.
ask
The code on the right is a simple implementation of sum reduction using partial sums which gives a decent performance for a small number of elements. However, when operating on very large arrays, we can achieve a better performance by some sort of tree reduction of partial sums as discussed in the subsequent lectures.
In the first class, we had an exercise where 4 students added numbers. For the incorrect code, imagine we had a 5th person who would tell each student the current sum and they reply with the sum after they added their current element. This has a race condition if the 5th student tells multiple others the same sum. For the correct code, imagine that the 4 students all do their sums independently, then tell the 5th person their partial sums. Which, in fact, is what happened in the class demo.
Prof. Kayvon prefers there not to be a 5th person - the reduce-add is really more like the 4 students adding their numbers together by a predefined order.
A point that was mentioned in lecture: reduce_add may be "called" once in each program instance, but it only "returns" once, since it stores the final return value in sum, a uniform variable.
It was mentioned during class that although the code on the left generates a compile-time error due to sharing a uniform value across different instances, once the programmer indicates parallelism with a foreach loop, the compiler does not confirm the accuracy of the statement. It simply assigns the various iterations to the gang in any way which thereby creates race conditions in the program on the left (if it compiled).
A race condition might arise if multiple instances load the same value of sum, add to it and write the result back. The instance which does the later write "overwrites" the value of sum computed by an instance which wrote earlier.
The code on the right is a simple implementation of sum reduction using partial sums which gives a decent performance for a small number of elements. However, when operating on very large arrays, we can achieve a better performance by some sort of tree reduction of partial sums as discussed in the subsequent lectures.