{"id":4006,"date":"2021-04-15T08:19:42","date_gmt":"2021-04-15T12:19:42","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/?p=4006"},"modified":"2021-04-15T14:31:57","modified_gmt":"2021-04-15T18:31:57","slug":"preparing-to-run-code-in-parallel","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2021\/04\/15\/preparing-to-run-code-in-parallel\/","title":{"rendered":"Preparing to Run Code in Parallel"},"content":{"rendered":"
In a <\/span>recent post<\/span><\/a>, I talked about <\/span>for<\/span>-loops in MATLAB and how to optimize their use knowing how MATLAB stores arrays in memory. Today I want to talk about getting ready for parallel computation, specifically using parallel <\/span>for<\/span>-loops, via <\/span>parfor<\/span><\/a>. <\/span><\/div>
En route to creating code suitable for running in parallel, sometimes we take code with a <\/span>for<\/span>-loop and simply replace it with a parallel loop, using <\/span>parfor<\/span>. That is, if we can't vectorize the code well first. This transformation from <\/span>for->parfor<\/span> works really well sometimes, but does not always work, and for very good reasons. <\/span><\/div>
For example, you can't simply replace <\/span>for<\/span> with <\/span>parfor<\/span> if loop iterations are not completely independent. You can find out more conditions <\/span>here<\/span><\/a>. There is a notable exception to this rule, <\/span>reduction variables<\/span><\/a>, (a <\/span>reduction variable<\/span> accumulates a value that depends on all the iterations together, but is independent of the iteration order). The documentation for this is great. Here's a quick pseudo-code that would parallelize just fine, even though we reuse the variable <\/span>s<\/span> on both the right and left-hand sides. As long as the result is not numerically sensitive to the order in which the accumulation occurs, you will get the \"right\" answer here whether you use a <\/span>for<\/span> or a <\/span>parfor<\/span> loop.<\/span><\/div>
s = 0;<\/span><\/span><\/div>
parfor <\/span>ind = 1:100<\/span><\/span><\/div>
s = s + fun(data(ind));<\/span><\/span><\/div>
end<\/span><\/span><\/div><\/div>

Testing for Parallelizability<\/span><\/h2>
I doubt parallelizability is word, but I think you know what I mean! <\/span><\/div>
One simple way to see if your loop might be suitable for parallelization is to try running the loop in another order to see if you get the same result. If so, it is a candidate for <\/span>parfor<\/span>. The easiest version of this might be running the loop backwards. If you get the same results as the standard sweep, you should be good to go. Instead of backwards, you can also try replacing the loop with the counter in random order; this can be achieved easily using <\/span>randperm<\/span><\/a>. <\/span><\/div>
Note: clearly this calculation can be vectorized easily. That's not my focus here.<\/span><\/div>
k = randn(100,1);<\/span><\/span><\/div><\/div>
meank = mean(k);<\/span><\/span><\/div><\/div>
tol = sqrt(eps);<\/span><\/span><\/div><\/div>
<\/div><\/div>
qforward = zeros(size(k));<\/span><\/span><\/div><\/div>
for <\/span>ind = 1:100<\/span><\/span><\/div><\/div>
qforward(ind) = k(ind) - meank;<\/span><\/span><\/div><\/div>
end<\/span><\/span><\/div><\/div>
<\/div><\/div>
meank = mean(k);<\/span><\/span><\/div><\/div>
qbackward = zeros(size(k));<\/span><\/span><\/div><\/div>
for <\/span>ind = 100:-1:1<\/span><\/span><\/div><\/div>
qbackward(ind) = k(ind) - meank;<\/span><\/span><\/div><\/div>
end<\/span><\/span><\/div><\/div>
<\/div><\/div>
meank = mean(k);<\/span><\/span><\/div><\/div>
qrandom = zeros(size(k));<\/span><\/span><\/div><\/div>
for <\/span>ind = randperm(100)<\/span><\/span><\/div><\/div>
qrandom(ind) = k(ind) - meank;<\/span><\/span><\/div><\/div>
end<\/span><\/span><\/div><\/div>
<\/div><\/div>
<\/div><\/div>
aretheyequal = isequal(qforward, qbackward, qrandom) <\/span><\/span><\/div>
aretheyequal = logical<\/span><\/span>\r\n 1<\/div><\/div><\/div><\/div><\/div><\/div>
In case the answers aren't exactly equal, you could compare them in a way similar to this.<\/span><\/div>
nearlyfb = norm(qforward-qbackward) < tol<\/span><\/span><\/div>
nearlyfb = logical<\/span><\/span>\r\n 1<\/div><\/div><\/div><\/div><\/div>
nearlyfr = norm(qforward-qrandom) < tol<\/span><\/span><\/div>
nearlyfr = logical<\/span><\/span>\r\n 1<\/div><\/div><\/div><\/div><\/div>
nearlybr = norm(qbackward-qrandom) < tol<\/span><\/span><\/div>
nearlybr = logical<\/span><\/span>\r\n 1<\/div><\/div><\/div><\/div><\/div><\/div>
So this calculation is ready to try with <\/span>parfor<\/span>.<\/span><\/div>
qpar = zeros(size(k));<\/span><\/span><\/div><\/div>
for <\/span>ind = 1:100<\/span><\/span><\/div><\/div>
qpar(ind) = k(ind) - meank;<\/span><\/span><\/div><\/div>
end<\/span><\/span><\/div><\/div>
<\/div><\/div>
aretheyequal = isequal(qpar, qforward)<\/span><\/span><\/div>
aretheyequal = logical<\/span><\/span>\r\n 1<\/div><\/div><\/div><\/div><\/div><\/div>

What if I Have an Expression with Iteration Dependency<\/span><\/h2>
You may not always be able to parallelize your code. However, there are some conditions under which you can convert your code to take advantage of parallelization by refactoring your calculations a little Let me show you an example. In this case, I will do some of the accumulation after the loop is complete.<\/span><\/div>
%% The Code Analyzer gives this first chunk of code two red error messages.<\/span><\/span><\/div>
x = [17 zeros(1,99)];<\/span><\/span><\/div>
k = [0 randn(1,99)];<\/span><\/span><\/div>
<\/div>
parfor <\/span>ind = 2:100 <\/span><\/span><\/div>
x(ind) = x(ind-1) + k(ind)^2;<\/span><\/span><\/div>
end<\/span><\/span><\/div>
<\/div>
%% the error messages from above code:<\/span><\/span><\/div>
The <\/span>PARFOR loop cannot run due to the way variable 'x' is used.<\/span><\/span><\/div>
In <\/span>a PARFOR loop<\/span>, variable <\/span>'x' is indexed in different ways<\/span>, potentially <\/span><\/span><\/div>
causing <\/span>dependencies between iterations.<\/span><\/span><\/div><\/div>
Here's the <\/span>for<\/span> loop equivalent, no warning.<\/span><\/div>
x = [17 zeros(1,99)];<\/span><\/span><\/div><\/div>
k = [0 randn(1,99)];<\/span><\/span><\/div><\/div>
for <\/span>ind = 2:100 <\/span><\/span><\/div><\/div>
x(ind) = x(ind-1) + k(ind)^2;<\/span><\/span><\/div><\/div>
end<\/span><\/span><\/div><\/div>
xx = x;<\/span><\/span><\/div><\/div>
<\/div><\/div><\/div>
And here's how you might parallelize it<\/span><\/div>
x = [17 zeros(1,99)];<\/span><\/span><\/div><\/div>
tmp = zeros(1,100);<\/span><\/span><\/div><\/div>
parfor <\/span>ind = 2:100<\/span><\/span><\/div><\/div>
tmp(ind) = k(ind)^2;<\/span><\/span><\/div><\/div>
end<\/span><\/span><\/div><\/div>
x = cumsum(x+tmp);<\/span><\/span><\/div><\/div>
<\/div><\/div>
aretheyequal = isequal(x,xx)<\/span><\/span><\/div>
aretheyequal = logical<\/span><\/span>\r\n 1<\/div><\/div><\/div><\/div><\/div><\/div>

Thoughts?<\/span><\/h2>
Do you often work with large datasets or simulations where getting access to hardware suitable for running code in parallel helps your work scale? Did your code fall into any of the simple categories I mentioned in this post? I would love to hear from you about any issues you have wrangling your code into a form suitable for parallelization. Post your thoughts <\/span>here<\/span><\/a>.<\/span><\/div>\r\n<\/div>