How to optimize embeded loop index for parallelization in Matlab?

Question

Currently I'm working on a project and I want to improve the execution speed. I'm completely new to parallel coding. My program initially had six loops and I managed to optimize it to three loops and the execution time reduced 300%. From what I studied I believe that the problem is in the indexing. I used already parfor in a previous loop but there the index was i = 1:vs_max-1.

In the following code:

for i = 1:vs_max-1
 for j = i+1:vs_max-1
  d = max(abs(X(i,:)-X(j,:)));
  DD = exp(-(d/r)^n);
  D(i,j) = DD;
  D(j,i) = DD;
  while (i~=vs_max)
    d2 = max(abs(X2(i,:)-X2(j,:)));
    DD2 = exp(-(d2/r)^n);
    D2(i,j) = DD2;
    D2(j,i) = DD2;
    break;
  end

 end
end

I believe the problem is in second loop indexing where j requires also the i value and when we have more than one thread we have multiple access to these values.

Can anyone help me in re-indexing this loop in order the parfor not to prompt or provide another type of code optimization in order the above code to become more faster?

Thank you in advance for your kindness reading and answering my post.

score 2 · Answer 1 · edited May 23 '17 at 12:12

You are basically generating indices in an upper-triangular matrix. As the value of i progresses towards vs_max-1, lines are getting shorter and shorter. This doesn't distribute well among multiple threads unless some dynamic work scheduling is being performed (e.g. similar to schedule(dynamic), should you happen to be familiar with OpenMP).

You can "flatten" things out and run a single loop and use some math to convert iteration number to an (i,j) pair, e.g. see this question for a possible solution. If you have plenty of memory, you may also use a prepopulated list of all possible (i,j) pairs and then use it to quickly compute i and j from the iteration number.

BTW: the the second part of the computation looks weird. Why put it in a while loop that always executes and besides executes exactly once (i ~= vs_max is always true since i never reaches vs_max and break terminates it after the first iteration)?

How to optimize embeded loop index for parallelization in Matlab?

1 Answers1