How do you break out of parallel loops? ParallelBreak

Question

Hi, in the following snippet, if you replace Do by ParallelDo, it will evaluate by a factor of 3 SLOWER, because now the loop will be broken in only ONE of the two kernels.

ParallelEvaluate[NN = 10070];
SetSharedVariable[res]
Module[{a, b, c},
  Do[
   c = NN - a - b;  
   If[a a + b b == c c, res = a b c; Break[]]
   , {a, 1, NN}, {b, a + 1, NN}
   ];
  res
  ] // AbsoluteTiming

Calling ParallelAbort would solve the issue, but it's forbidden. What else is there?

Answer 1

You need to have a way for each iteration to tell all other iterations that the answer has been found. I modelled this with a "quit" flag, intially set to false, that is set to true when any iteration decides to finish. Each iteration likewise has to check the exit condition.

My Mathematica is 15 years rusty, and I haven't seen the Parallelxxx forms before, but a good guess at how the loop should change is the following variation on your code:

ParallelEvaluate[NN = 10070];
SetSharedVariable[res,quit]
Module[{a, b, c},
    quit=false;
   Do[ c = NN - a - b;  
       If[quit, Break[]];
       If[ a a + b b == c c, quit=true; res = a b c; Break[]],
       {a, 1, NN}, {b, a + 1, NN}
     ];
     res
   ] // AbsoluteTiming

The extra If slows down the loop somewhat, but thats the price of synchronization.

I suspect that the amount of work you are doing in each iteration is already pretty small compared to the cost of executing each iteration in parallel, so this loop is probably inefficient and you may not get any real value from the Do Parallel. If you dont, then you can make each Do iteration operate on several values of a and b (e.g., use {a, 1, NN, 10} and similarly for b for each iteration and handle the 10-wide subrange as a subloop inside each parallel iteration).to keep the quit-test exit overhead small in comparison to the work done in each loop body. Recode exercise left for the reader.

Your code has another problem: there's a race condition in setting res. Under ceratin circumstances, two iterations could both decide to set res. If you don't care which answer is produced, and the store to res is "atomic", this is fine. If res were a more complicated data structure, and updating it took multiple Mathematica statements, you'd surely have a data race and your loop would produce bad results once in a great while and it would be very hard to debug. You ideally need some kind of atomic test to protect the exit condition. I don't know what that is in MMa, so you'll have to look it up, but I imagine an "atomic[...]" form that insists its body is executged by only one of the many parallel threads. (Perhaps MMa has a semaphore that you can use to implement atomic]. If so, your code should then look like this:

ParallelEvaluate[NN = 10070];
SetSharedVariable[res,quit]
Module[{a, b, c},
    quit=false;
   Do[ c = NN - a - b;  
       If[quit, Break[]];
       If[ a a + b b == c c, 
           atomic[If[not[quit]; quit=true; res = a b c;]; Break[]],
       {a, 1, NN}, {b, a + 1, NN}
     ];
     res
   ] // AbsoluteTiming