7
$\begingroup$

A friend of mine observed that when running ParallelMap or ParallelTable that he would get different results than when running Map or Table, respectively. This because, according to him, the Parallel were returning matrices that were not respecting the original ordering. According to him, the returned matrices were more dependent on the speed at which the CPUs were finishing their computations. An example would be:

m=Map[f,Range@10]
p=ParallelMap[f,Range@10]
(*that would return, for example:*)
(*m*) {1,2,3,4,5,6,7,8,9,10}
(*p*) {1,2,3,4,9,10,5,6,7,8}

Note that the above is only an example for you to understand the sort of problem that he is facing.

My question is the following: is any of you able to corroborate or deny this sort of behavior?

I am seriously worried that this is happening in my own code because it may be a serious problem for my data. Sorry if I can't give you a real working example, but I couldn't ask him for a snippet of his code.

|improve this question
$\endgroup$
  • $\begingroup$ Tangentially related: (473) $\endgroup$ – Mr.Wizard♦ Jun 24 '15 at 12:22
  • $\begingroup$ What version are you using? Also, on the surface (ignoring MrW's post), out of order results from a parallel calculation is the norm. It is likely that ParallelMap and ParallelTable are supposed to do some post-processing to hide this from the user, but otherwise order is never guaranteed across multiple processes. $\endgroup$ – rcollyer Jun 24 '15 at 12:28
  • $\begingroup$ @rcollyer he sees this behavior in v10 and 10.1. When we (me and my friend) were discussing this issue, we also mentioned that the ordering should not be kept, but that the reassembled result likely would re-order everything back. $\endgroup$ – Sosi Jun 24 '15 at 12:53
  • $\begingroup$ I can't reproduce the problem, either. But, that is only on my local machine. By any chance, is this on a cluster of machines? $\endgroup$ – rcollyer Jun 24 '15 at 13:03
  • $\begingroup$ @rcollyer nope. He is running this on his laptop and possibly on a desktop too. $\endgroup$ – Sosi Jun 24 '15 at 13:11
4
$\begingroup$

I cannot reproduce this behavior. With the following code I tested whether two very long series of random numbers when processed serially or in parallel ever yield different results:

c = 0; (* counter to count the number of times the two results differ *)
Do[
 m = RandomInteger[1000, 10^6];
 If[Map[#^2 &, m] =!= ParallelMap[#^2 &, m], c++]
 , {1000}
 ]
c

result: 0. So never in 1000 evaluations did the results arrive out of order.

I assume this may be dependent on the function f. If, for instance, this function uses and changes global variables all bets are off:

f[x_] := (If[x == 1, c = 0]; (c++))

c = 0;
Map[f, Range@10]
ParallelMap[f, Range@10]

(* {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} *)

(* {0, 1, 10, 11, 10, 10, 2, 12, 11, 11} *)

Without knowing any details about f answering this question is impossible. But the above example shows it is pretty easy to make mistakes resulting in the described behavior.

|improve this answer
$\endgroup$
3
$\begingroup$

It is important to understand that in Mathematica, semi-automatic parallelization, such as the one provided by ParallelTable or ParallelMap works only if the chunks of code executed in parallel have no side effects.

What does it really mean to say that f has no side effect? Another way to say it is that the output of f depends only on it's input and nothing else. In other words, f has no internal state that influences its result.

Here's a function that does have side effects:

c=0;
f[x_] := x + (c++)

Evaluating f twice with the same input gives different results:

f[2]
(* 2 *)

f[2]
(* 3 *)

The output does not only depend on the input, but also on some (possibly private-to-f) state that is preserved between subsequent calls to f, in this case c.

Functions like f above are simply not suitable for parallelization in Mathematica. Yes, this is a limitation in some sense, but it's also a great advantage in that side-effect-less functions are really easy to parallelize.

A comment on the order of evaluations:

As your colleague notes, the order of evaluations may affect the results for functions with side effects:

c = 0;
KeySort@AssociationMap[f, {1, 2, 3}]
(* <|1 -> 1, 2 -> 3, 3 -> 5|> *)

c = 0;
KeySort@AssociationMap[f, {3, 2, 1}]
(* <|1 -> 3, 2 -> 3, 3 -> 3|> *)

It also goes the other way: if the order of evaluations does affect the result, that tells me that his function must have had side effects.

He believed that parallelization fails because the order of evaluations is unpredictable. This is not correct. Parallelization fails much worse than that because f's internal state (the variable c) exists as a separate and independent copy for each parallel thread. The different threads are not al modifying a global c, they're instead modifying their own private local c. To put it plainly: the results will be rubbish.

The golden rule to keep in mind: code evaluated in parallel must never have any side effects, i.e. it must not maintain an internal state between subsequent evaluations.

|improve this answer
$\endgroup$
  • $\begingroup$ A naive question about this: I've faced a warning saying that parallelization was not possible and that the evaluation would proceed sequentially sometimes. Could the issue that you raise (of the internal state between evaluations having to be maintained) be detected by that sort of warnings, or does it bypass it? $\endgroup$ – Sosi Jun 24 '15 at 13:12
  • 1
    $\begingroup$ @Sosi I don't think it can ever be detected, perhaps in very rare cases with Parallelize. It could be that there were no subkernels available. E.g. LaunchKernels[]; CloseKernels[]; ParallelMap[f, Range[10]] would say No parallel kernels available; proceeding with sequential evaluation. $\endgroup$ – Szabolcs Jun 24 '15 at 13:15
  • 1
    $\begingroup$ Parallelize[f[1, 2, 3]] will say "f[1,2,3] cannot be parallelized; proceeding with sequential evaluation." That's because Parallelize doesn't know what to do with this, not because it is examining f's definition. $\endgroup$ – Szabolcs Jun 24 '15 at 13:15
  • $\begingroup$ I see, thanks! +1 $\endgroup$ – Sosi Jun 24 '15 at 15:40
1
$\begingroup$

The documentation for ParallelMap and ParallelTable specifically state:

  • ParallelMap will give the same results as Map, except for side effects during the computation.

  • ParallelTable will give the same results as Table, except for side effects during the computation.

If you actually experience out-of-order results you have encountered a bug. Most of the parallel functionality is implemented in top-level code that can be "spelunked" so it would be possible to bug-check it if sufficiently determined.

Of course the warning about side-effects stand; mutable programming and parallelism don't usually mix well.

|improve this answer
$\endgroup$

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.