5
$\begingroup$

I'm trying to understand how ParallelEvaluate works, considering the two following snippets:

count = 1;  
SetSharedVariable[count];  
ParallelEvaluate[count++]  
Out[320]= {1, 2, 3}

Whereas if I do:

count = 1;  
SetSharedVariable[count];  
ParallelEvaluate[count = count + 1]  
Out[329]= {2, 2, 2}

The output, as seen above, is quite different. The first case is mostly from the docs for SetSharedVariable. My confusion is because in the docs for the increment operator, the statements k++ and k = k+1 are mentioned to be the same.

Therefore, could someone please explain why the parallel kernels treat the two situations differently?

$\endgroup$
1
  • 1
    $\begingroup$ Interesting observation. I think the second case demonstrates a race condition; otherwise it should be the same as the first. Please do not take the statements in the documentation about the equivalence of different programs too seriously. A healthy suspicion of all such claims will save you a lot of headaches in cases like this. $\endgroup$ Jun 20, 2014 at 14:51

1 Answer 1

7
$\begingroup$

SetSharedVariable effectively causes count to be always evaluated on the main kernel. Some of the following description consists of guesses and might not be accurate enough, but I think it illustrates well enough in what way things are going wrong. (As Oleksandr said, it's a race condition.)

There are two ways count may be accessed that will cause a callback to the main kernel: reading or setting its value. count++ causes a single callback: it sets the value. count = count+1 triggers two callbacks: a read and a set. The key point to understand that the order of accesses coming from different subkernels is unpredictable, and their order affects the result.

What seems to happen is that first all three subkernels read the value of count. Accidentally all three reads happen before any of the writes take place, so all three reads result in 1. Now all subkernels compute 1+1 to obtain 2. Finally all of them will set this value to count.

You can see that when there are two kinds of accesses, both reads and writes, then the order of the operations becomes critical. Theoretically count could end up with any value between 2 and 4 in your program, depending on the order of operations, and the result of 2 is just accidental.

You could fix this problem in two ways:

  1. Make sure that all of count = count+1 is evaluated in a single go before allowing another subkernel to access count in any way:

    count = 1;
    SetSharedVariable[count];
    ParallelEvaluate[CriticalSection[{lock}, count = count + 1]]
    
  2. Restrict your accesses to reads only, with no writes. In other words, use functional programming and avoid side effects. This will also eliminate all the extra callbacks to the main kernel for write access and synchronization, which would slow down your program significantly. More info here and here.

$\endgroup$
4
  • $\begingroup$ Two observations: (a) The 2's are NOT accidental, I always get them. (b) In the "lock-case" I have to start with count = 0 to obtain {1,2,3,4} $\endgroup$
    – eldo
    Jun 20, 2014 at 16:10
  • $\begingroup$ @eldo They're accidental in the sense that they depend on evaluation order which is unpredictable. It is true that this specific code when run on an otherwise idle computer is likely to return 2s because the timings are likely to turn out this way. What I meant is that there's no guarantee that it will happen like this. I can imagine that on a computer which is already under heavy load it might turn out differently. Maybe I should have phrased it differently: the point is that the timings should not be relied on because there are no guarantees on how they'll turn out. $\endgroup$
    – Szabolcs
    Jun 20, 2014 at 17:17
  • $\begingroup$ @eldo This is exactly why race condition related bugs are so hard to debug: typically, usually these bugs don't change the result but sometimes they do. They're hard to reproduce. Regarding (b), there's a difference in the return value x++ incerements the value of x, but it returns the value of x from before it has been incremented. The code using CriticalSection is an alternative in the sense thatit change count in the same way as the non-parallelized code would. The return value from x++ or x=x+1 is usually ignored, but you're right the returns values are different. $\endgroup$
    – Szabolcs
    Jun 20, 2014 at 17:20
  • $\begingroup$ @Szabolcs: thanks for your explanation, that makes sense. $\endgroup$
    – MvP
    Jun 21, 2014 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.