reduction variables and evaluation order

This the doc on can read

"A reduction variable accumulates a value that depends on all the iterations together, but is independent of the iteration order. MATLAB allows reduction variables in parfor-loops."

Among the operations one have

% X = X * expr

And we all know for matrix, multiplcation order matters. So why X itcan be considered as valid reduction variable using "*"?

However when I test it it looks like parfor magically multiply in the right order as showed in this code:

A=rand(2,2,10);

% B = A(:,:,1)*A(:,:,2)*...A(:,:,10)
B=1;
for k=1:size(A,3)
    B = B*A(:,:,k);
end
B

B = 2×2

0.1810 0.3914 0.1442 0.3118

C=1;
parfor k=1:size(A,3)
    pause(0.1*rand()); % This will make the order of each worker more or less random
    C = C*A(:,:,k);
end

Starting parallel pool (parpool) using the 'local' profile ...
Connected to the parallel pool (number of workers: 2).

C

C = 2×2

0.1810 0.3914 0.1442 0.3118

norm(B-C)/norm(B)

ans = 3.3254e-16

Do I missread the doc? There is a descrption in the doc about what works are done by worker and what by client and it is not totally clear to me. Is there any joint+fork occurs when such variable is updated? Order matter or not? Can someone shed a light?

Answer 1

[Matt J]

First remember that each worker is assigned some consecutive subset of loop iterations. The worker will execute the iterations within its assigned subset in the original, consecutive order. Therefore, each partial sequence of reduction operations will have a predictable result.

Then, once all iterations are complete, the partial reductions are post-consolidated. I suspect that the order in which reduction variables are post-consolidated is also done to preserve the original ordering (and why not, since the processing is sequential anyway at this point).

Note therefore that concatenation works, too, even though we can clearly see that the timing of each iteration's execution is all over the place:

C=[];
parfor k=1:10
    pause(0.1*rand());
    disp("k="+k)
    C=[C,k];
end

Starting parallel pool (parpool) using the 'local' profile ...
Connected to the parallel pool (number of workers: 2).
k=1
k=3
k=4
k=7
k=10
k=2
k=5
k=6
k=8
k=9

C

C = 1×10

1 2 3 4 5 6 7 8 9 10

[Bruno Luong]

So this statement from the document "...but is independent of the iteration order..." is wrong?

Does that mean that all tasks must wait each other (joint) before the statement

C = C*A(:,:,k);

are carried out sequentially and in order k=1:10?

The the next code will be run in parallel again (fork)?

[Matt J]

So this statement from the document "...but is independent of the iteration order..." is wrong?

I don't know about wrong, but certainly over-conservative (if slightly). There are definitely some situations where the order will affect reduction like this:

C=[];

t1=clock;
parfor k=1:10
    pause(0.1*rand());

    C=[C,etime(clock,t1)];
end

Starting parallel pool (parpool) using the 'local' profile ...
Connected to the parallel pool (number of workers: 2).

C

C = 1×10

19.2053 19.2533 19.2818 19.3751 19.3155 19.3297 19.4344 19.4007 19.4373 19.4543

issorted(C)

ans = logical
   0

[Bruno Luong]

Let assume I have 2 workers; does it mean

• worker1 computes TmpC_1_5 = A(:,:,1)*...A(:,:,5)
• worker2 computes TmpC_6_10 = A(:,:,6)*...A(:,:,10)
• Client computes C = 1*TmpC_1_5*TmpC_6_10, (when? after all for_loop body "finishes"?)

[Matt J]

Client computes C = 1*TmpC_1_5*TmpC_6_10, (when? after all for_loop body "finishes"?)

Yes.

[Bruno Luong]

That means the reduction variables required the operator to be associative, which is more relax than commutative (order)?

[Bruno Luong]

FWIW, this is a strange feature, used precautiously

fun = @(a,b) a-b;

x = 1;
for k=1:4
    x = fun(x,k);
end
x

x = -9

x = 1;
parfor k=1:4
    x = x-k;
end
x

x = -9

x = 1;
parfor k=1:4
    x = fun(x,k);
end
x

x = 9

[Matt J]

That means the reduction variables required the operator to be associative, which is more relax than commutative (order)?

It is recommended here that the operation be associative,

https://www.mathworks.com/help/parallel-computing/reduction-variable.html#bragj2e-1

[Raymond Norris]

When the client sends the instructions/data out, it recalls the order for assignment back to the variable on the lefthand side. This doesn't mean the values will be sorted (as in the case of the clock example). It means that MATLAB knew when the 4th value returned, where to put it. Even if it was assigned after the 5th (which could have been the 1st iteration to evaluate in the 2nd group).