Stealing work with the Parallel Computing Toolbox

Question

I implemented a combinatorial search algorithm (for comparison with a more efficient optimization method) and tried to improve its runtime using parfor .

Unfortunately, work assignments look very unbalanced.

Each subelement i has a complexity of approximately nCr(N - i, 3) . As you can see, tasks i < N/4 involve significantly more work than i > 3*N/4 , but it seems that MATLAB assigns all i < N/4 one worker.

Is it true that MATLAB divides the work based on the same subsets of the range of loops?

No, this question cites documentation saying that it is not.

Is there a convenient way to rebalance this without hard coding the number of workers (for example, if I need exactly 4 employees in the pool, then I can exchange the two lower bits i for two higher bits to ensure that each employee receives some combination of simple and complex tasks )?

I don’t think that a complete “theft treatment” is needed, perhaps just assigning workers 1 , 2 , 3 , 4 , and then, when 4 completed first, the worker begins with element 5 , etc. The size of each element is large enough than the number of iterations that do not bother me too much about the increased communication costs.

Answer 1

If the iterations of the loop are really distributed in advance (this will mean that in the end there is one worker who will have to perform several iterations while the other workers are idle - is that really so?), The easiest way to make sure that the mix is ​​random permutation loop iterations:

 permutedIterations = randperm(nIterations); permutedResults = cell(nIterations,1); %# or whatever else you use for storing results %# run the parfor loop, completing iterations in permuted order parfor iIter = 1:nIterations permutedResults(iIter) = f(permutedIterations(iIter)); end %# reorder results for easier subsequent analysis results = permutedResults(permutedIterations);