2
$\begingroup$

I am trying to solve many different linear systems in parallel in matlab. The problem is, each linear system has entirely different parts and are fairly large, so passing the information to each of the workers is taking significantly longer than solving the each one normally.

My current setup is very crude, I precompute cells for each matrix, right hand side, and preconditioner, then solve using GMRES. I am also using function handles to evaluate the preconditioner backsolve.

Essentially

parfor i=1:N
X{i} = gmres(A{i}, b{i}, maxit, tol, @(x) mfun(x,M{i}))
end

The matrices are all sparse and memory isn't an issue. How should I speed this up?

$\endgroup$
2
$\begingroup$

It seems like you have $N$ systems of linear equations that you need to solve. Let's say that you have $P$ cores available to you and unlimited memory. Now, you have two options:

  1. You can try solving $P$ systems in parallel, while each system is solved using 1 core.
  2. You can solve one system using $P$ cores, solving all $N$ systems one-by-one.

The choice will depend on many factors: used computer architecture, amount and bandwidth of memory, memory locality, size of the systems, chosen solver procedure.

I assume, that some of your performance problems are coming from:

  • memory locality problems. The necessity of solving many systems at once makes it hard to fit the required data into the caches; thus, increasing cache misses penalties.
  • while parfor is supposed to dynamically distribute tasks, you are still bounded by the slowest worker. For example, consider you need to solve $N_1=5$ or $N_2=8$ systems and you have $P=4$ cores available (with an assumption that each system takes exactly the same time to be solved). Both $N_1$ and $N_2$ will take exactly the same time if you use approach 1.
  • too many workers that Matlab decides to use with this "slightly unexpected" parallelization pattern.

Suggestions:

  • Try approach 2 with solving only one system at a time using all the cores. Make sure that it is solved in parallel. maxNumCompThreads should give you the # threads that are available to Matlab.
  • Try approach 1 and make sure that you are not using hyperthreading so that the number of workers is equal or less than the number of physical cores on your machine.

If the size of each system is large enough, the second approach of using $P$ threads to solve one system at a time is preferred. However, I can see that for a large number of relatively small systems the approach 1 (the one you are using) might offer more benefits.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.