How MATLAB divide the number of iterations of "parfor" on the workers of one computer?

Dear all,

Please, I have a question, how MATLAB divide the number of iterations of "parfor" on the workers of the computer?

In the following example of Mathworks in the picture, as I understood, they mentioned when the number of iteration is 10 and the number of workers is 4, the first three workers take the 2 iterations equally then the remaining four iterations divide into the four. That is mean the first three workers take 3 iterations and the last worker take just one iteration.

Please, could anyone correct me if I am wrong ! And please, explain to me how MATLAB divide the number of iterations, i.e. even or odd ?

Lease, if I have this case how MATLAB divide the iterations ? 1. If the number of iteration is 40 and we have 4 workers. 2. If the number of iteration is 40 and we have 5 workers. 3. If the number of iteration is 40 and we have 8 workers. 4. If the number of iteration is 40 and we have 12 workers.

Kind regards Ammar

[Steven Lord]

Are you asking out of curiosity, or because you're going to try to use this information somehow? If you are planning to try to use this information, how are you planning to use it and for what purpose? Ideally, you shouldn't need to care on which workers the iterations are executed (or in which order they are executed.) All you should need to care about is that they were executed.

[Ammar]

Dear Steven, I would like to thank you for your comments. Yes, actually, I was just puzzle when I saw the diagram. Then, I start to think how MATLAB do the division of iterations? Please, if you have any idea how MATLAB divide the number of iterations could you help me. As I said if I have 4 workers and 40 iteration does MATLAB divide the 40/4 and give each worker 10 iteration to execute ? Or how it does done ? Regards, Ammar

[Walter Roberson]

"As I said if I have 4 workers and 40 iteration does MATLAB divide the 40/4 and give each worker 10 iteration to execute ?"

No. It does an initial division of work, but after that it allocates according to whichever worker is ready first.

[Ammar]

Yes Walter, thanks for this comment. Please, do you know what is the formula for initial division ? Regards

Answer 1

[Walter Roberson]

a = zeros(10,1);
parfor i = 1 : 10; t = getCurrentTask(); a(i) = t.ID; end;
a'

ans =
     4     4     3     3     2     2     1     3     1     2

a = zeros(1,40);
parfor i = 1 : 40; t = getCurrentTask(); a(i) = t.ID; end
mat2str(a)

ans = 
   [4 4 4 4 4 4 4 3 3 3 3 3 3 3 2 2 2 2 2 2 2 1 1 1 1 1 4 4 4 4 2 2 2 3 3 1 1 4 2 3]

a = zeros(1,40); parfor i = 1 : 40; t = getCurrentTask(); a(i) = t.ID; end; mat2str(a)

ans =
  [4 4 4 4 4 4 4 3 3 3 3 3 3 3 2 2 2 2 2 2 2 1 1 1 1 1 3 3 3 3 4 4 4 2 2 1 1 3 4 1]

So MATLAB does some initial estimation of the work requirements, but the order is not completely fixed: after the initial work is done, the remaining work is broken up and handed to whichever worker is ready first.

Work is not broken up into strict blocks because it can happen that some iterations take more or less time than others. For example if the task were to determine whether the loop counter is prime, then the iterations where the loop counter was even would return quickly. So parfor just estimates. It looks like it might perhaps be something like ceil(number_of_iterations/(number of workers minus 1)) as the initial allocation to the first (number of workers minus 1) workers.

[Ammar]

Dear Walter, I would like to thank you for this answer. Really, it is helpful. From yesterday till now I am thinking for a general formula to guess how MATLAB is doing this division but I could not find such a formula. Please, if you have any further idea to find out how it is work it will be helpful.

Kind regards Ammar

[Walter Roberson]

Code attached. It runs tests at up to 8 workers, and from 1 to 100 tasks to do.

(Note: if you have fewer than 8 physical cores, either change the first line of the code or edit your local cluster to have a higher limit. I happen to have 4 physical cores with hyperthreading available, so I edited my cluster profile to permit up to 8.)

It might be easier to look at the transpose of the output,

initial_counts .'

With 2 workers, you can see that the initial allotment stays the same for groups of 3 -- e.g., upper limit 40, 41, 42 all give 14 initial tasks to the first group.

With 3 workers, it alternates bunches of width 5 and 4 -- e.g., 41, 42, 43, 44, 45 all get 10 tasks, 46, 47, 48, 49 all get given 11 tasks, the next group of width 5 (50, 51, 52, 53, 54) get 12 tasks, etc.

With 4 workers, groups of 6 get allocated the same initial length

With 5 workers, the groups alternate between width 8 and width 7

With 6 workers, groups of 9 get allocated the same initial length

With 7 workers, the groups alternate width 11 and width 10

With 8 workers, groups of 12 get allocated the same initial length

So... this works out as grouping chunks of

[floor(workers*1.5), ceil(workers*1.5])

The formula appears to be close to:

initial_allotment = ceil( 2/3 * number_of_iterations / number_of_workers )

Answer 2

[Sean de Wolski]

The slide is just an illustration to demonstrate the load balancing idea.

Check out this blog post:

http://blogs.mathworks.com/pick/2014/08/01/time-parallel-for-parfor-loops/

[Ammar]

Dear Sean, I would like to thank you for your comment. Yes, I agree the slide just an illustration.

I read the link you mentioned. Please, do know how they get that figure ? Because they did no explain that.

Please, do know exactly how MATLAB divide the load to the all workers when we use parfor?

[Walter Roberson]

Notice the top,

"Sean's pick this week is Par Tic Toc by Sarah Wait Zaranek"

That "Par Tic Toc" is a link to http://www.mathworks.com/matlabcentral/fileexchange/27472-partictoc . So the figures they got were by measurements using that program.

"Please, do know exactly how MATLAB divide the load to the all workers when we use parfor?"

Please see this link for information on obtaining that level of detail with certainty.

Or you could just test it yourself with the code I posted, the short form of which is that just short of 2/3 of the total iterations are handled out initially.

[Ammar]

Dear Walter, Thank you very much for these details. I will keep trying to find the solution. Regards, Ammar