Why parfor is slower than for in my algorithm?
1 view (last 30 days)
Show older comments
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
0 Comments
Accepted Answer
Edric Ellis
on 16 Apr 2015
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).
3 Comments
Edric Ellis
on 16 Apr 2015
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).
More Answers (0)
See Also
Categories
Find more on Parallel Computing Fundamentals in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!