How to reduce the usage of "broadcast variables" when using parfor

Hi, in a "parfor" loop, a same warning message is put on three variables which I named "el", "ds", and "vmin". The message is: "The entire array or structure 'el' (or 'ds', 'vmin') is a broadcast variable. This might result in unnecessary communication overhead."

This "parfor" loop requires four variables which were calculated before the loop: Variable "el" is 4-by-378 double, "NElem"=27, "ds" is 27-by-27 sparse double, and "vmin" is 1-by-378 double.

Part of this loop is as follows:

el_row1=el(1,:);
parfor e=1:NElem
    k=el_row1-e==0;
    ind=el(4,k);
    ds_e=ds(:,ind);
    vs_e=ds_e*vmin(k)';
    ...
end

Is there a way to avoid this "unnecessary communication overhead", so that this parfor loop can run faster please? I read on the various types of variables in parfor-loops in Matlab documentation, I'm guessing the reason these three variables get the warning message is the form of indexing: "k" or "ind" is not a loop variable, so "el", "ds" or "vmin" cannot be sliced. But I don't know how to turn the variables "el", "ds", and "vmin" into slice variables. Any help is appreciated.

Answer 1

[Walter Roberson]

"Is there a way to avoid this "unnecessary communication overhead", so that this parfor loop can run faster please?"

No. You are accessing the values in random order.

    k=el_row1-e==0;
    ind=el(4,k);

You can build el4=el(4,:); and index that at el_row1==e so that el as a whole does not need to be sent.

You could findgroups el_row1 and splitapply or similar ahead of time to create cell ind{e} so that the index information could be sliced.

But ds and vmin are going to have to be sliced. Unless, that is, it turns out that the information needed for any given e turns out to be consecutive and can be split ahead of time.

Your arrays are not large at all. I would be concerned about whether they are doing enough work to make it worth using parfor.

[Paula]

Hi Walter, thank you very much, two questions on your answer please:

1. Is the purpose of using "findgroups" and "splitapply" to keep the following two lines out of the parfor loop? In other words, to turn the indices "k" and "ind" into "broadcast variables"? Just want to check if I understood correctly.

k=el_row1-e==0;
ind=el(4,k);

2. Sorry what do you mean "ds and vmin are going to have to be sliced"? I know the code will probably be faster if ds and vmin are sliced, but I don't know how to. If I manage to keep the above two lines out of the parfor loop, i.e. obtain the "k" and "ind" values for all "e" ahead of time, then will ds and vmin become sliced variables automatically?

Finally, sorry for the misinformation but the current array sizes correspond to a very coarse mesh of my problem, so the arrays are going to be much larger, just as an example, "el" could be (or more than) 4-by-1515000 double, and "ds" 7500-by-7500 sparse double.

[Paula]

Hi Walter, a quick question please: I tried "G=findgroups(el_row1)". The output G is exactly the same as "el_row1". Does it mean findgroups does not work on this array?

[Walter Roberson]

I meant to say that ds and vmin would need to be broadcast.

If I manage to keep the above two lines out of the parfor loop, i.e. obtain the "k" and "ind" values for all "e" ahead of time, then will ds and vmin become sliced variables automatically?

No. Variables can only be sliced when the indices are constants except for one index that is a simple computation based on the parfor variable. The idea is that the portion of the variable needed must be completely predictable ahead of time, without doing any deep flow analysis.

In order to prevent the variables from being broadcast, you would either have to be naturally indexing through a relatively uncomplicated index based on the parfor variable, or else you would have had to do the slicing "manually" ahead of time before the parfor loop.

For example, since you said that findgroups(el_row1) returns the same as el_row1 itself, then el_row1 is already a suitable grouping that could be used with

inds = splitapply(@(ind) {el(4,ind)}, el_row1);

Now you can

parfor e=1:NElem
    ind = inds{e};
    stuff
end

and you would have avoided having to broadcast el_row1 and el

    ds_e=ds(:,ind);

but with the information you have given us so far we have to assume that those values might be scattered all over the place inside ds.

If you have an array that is being accessed at scattered indices, then that array must be broadcast (unless you can slice it in pre-processing.)

If you have an array that is being accessed at consecutive locations with fixed width, then when practical, reshape and permute that array so that you can use the parfor variable as the last index into the array (because then the memory required for any given iteration is all consecutive, making it efficient to transfer with the automatic slicing.) Using the parfor variable as the first index adds measurable overhead even for a large enough 2D array.

[Paula]

Hi Walter, thank you for the explanation, I understood the idea of using findgroups and splitapply, unfortunately the line of "inds" that you wrote did not work:

inds = splitapply(@(ind) {el(4,ind)}, el_row1);

I think it's because in my case, the input argument of the function @(ind) needs to be the indices/locations of each group inside el_row1, but not the values of each group. For example, if el_row1=[1 2 3 2 1 1], then group 1 (or the input argument of function) returned by findgroups is [1 1 1] (which are just the three values of 1 in "el_row1"). But I want it to be [1 5 6] which are the indices of the value 1 in "el_row1", because I want to find el(4,[1 5 6]). Similarly for group 2, the function input is [2 2], but I need [2 4] (indices) instead.

Is there a Matlab function that finds the indices/locations of each group please? For example for the array el_row1=[1 2 3 2 1 1], it returns something like {[1 5 6], [2 4], [3]}. I realize it's a different question from what I was asking originally, sorry! If I can do this step, then I'll be able to use splitapply and avoid broadcast variable as you suggested. Thanks!

[Bruno Luong]

el_row1=[1 2 3 2 1 1];
[~,~,J] = unique(el_row1);
i = accumarray(J,(1:length(J))',[],@(x){x});
i{:}

ans = 3×1

1 5 6

ans = 2×1

2 4

ans = 3

[Paula]

Hi Bruno, this is very much what I need, thanks a lot for helping! I would never have thought of using accumarray this way..

I'm going to accept this answer, thank you both!

Answer 2

[Bruno Luong]

You can use parallel constant to convert el, el_row1, ds, vmin to constant and reduce the data transfert, if they are not modified (the snipet of code you showed they are not).