4
$\begingroup$

I am testing out some optimization algorithms. I have written the code with a Do loop inside a Do loop. The inner loop is the algorithm itself and the order the steps are executed is very important. The outer loop simply generates runs of the algorithm and the order is not important. In order to save time I thought I'd parallelize the outer loop. However, it doesn't return the correct number of iterations.

Here is a simple code with the same idea.

d = 5;
SetSharedVariable[re];
re = {};
ParallelDo[
 x = RandomReal[];
 y = x;
 ser = {};
 Do[y = y + 1; ser = {ser, y}, {d}];
 re = Append[re, Partition[Flatten[ser], d]]
 ,
 {d}
]; 
re

While the values in "re" are correct, "re" only has length 2, but it clearly should be 5 and it works correctly if the "Parallel" part is removed. Why is this?

The length of the result depends on the variable "d". If we table the length of "re" returned for values of "d" from 1 to 20, we get values

{1, 1, 1, 1, 2, 2, 2, 2, 4, 4, 4, 3, 4, 4, 4, 4, 6, 6, 6, 5}.
$\endgroup$
  • $\begingroup$ Is there a good reason why you are not using ParallelTable here? $\endgroup$ – Szabolcs Oct 19 '15 at 14:51
  • $\begingroup$ The reason it is as it is is basically historical. I wrote these algorithms over a couple of months and they just grew "organically" through small changes. So there probably is no good reason to do it the way I have done it. I'll look at the answers given and attempt to improve it. $\endgroup$ – Valtteri Oct 19 '15 at 19:36
  • $\begingroup$ Generally it's best to avoid functions with side-effects, and avoid SetSharedVariable. It tends to kill performance. $\endgroup$ – Szabolcs Oct 19 '15 at 19:37
7
$\begingroup$

As Emilio pointed out in his answer the problem is the way you store the results of your computation. This presents a sort of race condition. The canonical way of dealing with such a case is to introduce a CriticalSection (see below) although it's probably not the best way to go for your problem.

Emilio already presented a couple of ways to rewrite your code. Generally it is a good idea to use side-effect free functions if you plan to parallelize them. In your case this could be achieved by something like this:

d=5;
f[x_] := Module[{y = x}, {Table[y = y + 1, {d}]}]
ParallelTable[f@RandomReal[], {d}]

(Note that f could definitely be written in many different better ways, this is just to stay close to the code you posted.) The point here is that every time you call f for a certain value x you will get the same result. In this way parallel application of f is trivial.

The CriticalSection solution looks something like this, but I wouldn't recommend it unless you really need it!

d = 5;
SetSharedVariable[re]; re = {};
ParallelDo[x = RandomReal[]; y = x; ser = {}; 
  Do[y = y + 1; ser = {ser, y}, {d}];
  CriticalSection[{relock}, 
   re = Append[re, Partition[Flatten[ser], d]]], {d}];
$\endgroup$
  • $\begingroup$ should that just be {re} in CriticalSection? $\endgroup$ – george2079 Oct 19 '15 at 16:50
  • $\begingroup$ @george2079 No, CriticalSection is a bit counter-intuitive, see man page. $\endgroup$ – sebhofer Oct 19 '15 at 17:43
  • $\begingroup$ Now I get it ,thanks. $\endgroup$ – george2079 Oct 19 '15 at 17:54
7
$\begingroup$

As a naive guess, the double call to re in re=Append[re,...] seems to be causing some form of cross-talk trouble between the different kernels, with kernel 1 trying to write to re while kernel 2 is reading from it. Changing the Append call for an equivalent AppendTo call returns the expected results:

d = 6;
SetSharedVariable[re];
re = {};
ParallelDo[
  x = RandomReal[];
  y = x;
  ser = {};
  Do[
   y = y + 1;
   ser = {ser, y}, {d}
   ];
  AppendTo[re, Partition[Flatten[ser], d]]
  , {d}];
re

Alternatively, you can switch your reporting to a Sow+Reap scheme, which also returns the expected results.

d = 5;
SetSharedFunction[Sow]
Reap[
 ParallelDo[
  x = RandomReal[];
  y = x;
  ser = {};
  Do[
   y = y + 1;
   ser = {ser, y}, {d}
   ];
  Sow[
   Partition[Flatten[ser], d]
   ];
  , {d}];
 re
 ]

As to why the explicit Set+Append call fails to work, I'm not really sure. But hopefully these workarounds are useful, and they do shed some light on the mechanisms.

$\endgroup$
  • $\begingroup$ I really like the AppendTo solution, it seems to work perfectly and it requires the minimal change to the the original code. $\endgroup$ – Valtteri Oct 19 '15 at 19:33
  • $\begingroup$ @Valtteri Yeah, but AppendTo is maybe just a little bit too much of a functional-programming holdover. See in particular tip 7 of this list - it works as long as your lists are not too long, but at some point you should start using Sow. $\endgroup$ – Emilio Pisanty Oct 19 '15 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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