Why parfor is slower than for in my algorithm?

Why this:

...
parfor i=1:k
  if M(:,:,i)*A*M(:,:,i)'==B
      iz(1,i)=1;   
  end
end
...

is slower than the same algorithm with non-parallel for? A and B are n*n matrices, M is array of all n*n permutation matrices, k=n!. I can use only 2 workers.

• n=4 - 250 times slower than non-parallel for
• n=5 - 40 times slower
• n=6 - 10 times slower
• n=7 - 4 times slower (0.16 sec vs 0.04 sec)
• n=8 - 2 times slower (0.8 sec vs 0.4 sec)
• n=9 (9!=362880) - 2.5 times slower (?) (10 sec vs 4 sec)
• n=10 - error in parfor vs 55 sec in for

Answer 1

[Edric Ellis]

parfor is only faster than for when the overheads are lower than the computation time. In this case, there is a relatively large amount of data transfer (from client to workers) compared to computation since the matrix multiplications are relatively small. As n increases, there is more computation per data transfer, and so the "speedup" improves. On my machine, I see positive speedup with 2 workers when n is about 8.

If you have a compatible GPU, then pagefun on the GPU is ideally suited to this sort of computation, and you could proceed without any loops like so:

t1 = pagefun(@mtimes, M, A);
t2 = pagefun(@transpose, M);
t3 = pagefun(@mtimes, t1, t2);
t4 = pagefun(@eq, t3, B);
iz = all(all(t4,1),2);

On my Tesla K20c, this completes in 0.25 seconds for n = 9 (and runs out of memory for n = 10 - you'd have to partition M for that case).

[Petr Karas]

Thanks for your answer. I tried it and it writes error "Undefined function 'pagefun' for input arguments of type 'function_handle'." When I write "help pagefun", answer is "pagefun not found." Can I download it somehow?

I found some information about function arrayfun, which also uses GPU, here: http://www.mathworks.com/help/distcomp/run-element-wise-matlab-code-on-a-gpu.html and tried the example and it is ok, but pagefun is not.

And if I copy pagefun example from http://www.mathworks.com/help/distcomp/pagefun.html I get error:

Error using rand
Output class must be 'single' or 'double'.
Error in skriptpagefun (line 8)
A = rand(M,K,P1,1,P3,'gpuArray');

[Edric Ellis]

Which version of MATLAB/PCT are you using? pagefun was added in R2013b, and that build syntax for rand was also added relatively recently (not quite sure when).

[Petr Karas]

I use older version than R2013b. But I can get licence for newer version from my school.