Critical code section inside parfor

With C++ one can define critical code section inside a parallel for.

Is there a similar construct that can be used with Matlab?

e.g. suppose that a shared variabe has to be infrequently updated, but must be shared.

With C/C++ we might use a typical construct such as this:

#pragma omp for

for (...) {

// Do something with elements indexed by loop control variable

// and use some shared resource in calculations

if (update_required) {

#pragma omp critical

// Critical block can only be entered by 1 thread at a time

{

// update shared resource

}

}

}

For instance, insert a new key-value pair into a shared hashtable inside the loop; a rare event, but nevertheless the update must be safely shared by all executing threads.

Answer 1

[Walter Roberson]

parfor does not share variables with other threads.

Unless you are calling an external function such as https://www.mathworks.com/matlabcentral/fileexchange/28572-sharedmatrix or you are updating a memory mapped file https://www.mathworks.com/help/matlab/ref/memmapfile.html then the only way you can update a variable in another worker is to use a parfor data queue to send the value to the client, and have the client send the value to the other workers.

"global" variables are not shared. graphic objects are not shared.

[Walter Roberson]

Oh yes, another possible mechanism: if the workers are all using matFile() on the same file, then in theory the next time they happen to read the variable they would get the new value. However I do not see any documentation that promises that in practice -- the lack of discussion of cache effects suggests that either their is no cache (seems unlikely for performance reasons) or else that the facility was not designed for multiple update (seems more likely.)

[Shlomo Geva]

Thanks.

Answer 2

[Edric Ellis]

Further to Walter's response, the closest analogy in parfor is a reduction variable. These may appear to be updated by multiple loop iterations concurrently, but the parfor machinery (and language constraints) ensure that the result is computed deterministically with no race conditions. I.e. the following is supported, and completely deterministic.

list = [];
parfor i = 1:100
    list = [list, i];
end

[Shlomo Geva]

Thanks.

It works of course, but on the other hand the following example fails.

If you run it with for, the hashtable size after the loop is 100 as expected.

If you run it with parfor the hashtable is empty when the loop is done.

Both run happily in Matlab, but the parfor does not produce the desired result.

There is no reduction step in the loop to combine the local copies.

(PS - if you time it, the parfor is a lot faster, so it is run in parallel)

h = java.util.Hashtable;

parfor i = 1:100

h.put(i,i^2);

end

disp(h.size);

[Shlomo Geva]

The list example is conceptually processed something like this:

#pragma omp parallel {

#pragma omp for

for (...) {

// Do something with local list elements indexed by loop control variable

end

#pragma omp critical

// Critical block can only be entered by 1 thread at a time

{

// collect lists from threads

}

}

This is not what I need. I need threads to share a central resource (hashtable) for lookup, to achieve significant saving in computation. Most times threads access it in read-only mode, so it can be shared. However, occasionally threads 'discover' new savings and have to share it via the table. So the table has to be locked while updated. The cost of the rare lock is much lower than the cost of the savings gained down the the track by all trheads.

I guess Matalb is not as fancy as omp... I was not sure how far it goes.

[Walter Roberson]

You should consider using SPMD instead of parfor. spmd can send data between threads, including query to find out if information is queued. It uses MPI2 underneath if I recall correctly. Maybe MPI3 these days, not sure.

There is evidence that it does not use OMP underneath: namely that MATLAB Compiler, which can handle Parallel Processing Toolbox, does not require an OMP compliant compiler, and has been supported on compilers that do not support omp.

[Shlomo Geva]

Thanks, that's useful.

[Edric Ellis]

As Walter points out, the spmd communication methods labSend and labReceive etc. are MPI based. These are two-sided communication primitives - this means that both parties in any communication need to cooperate to get messages delivered. This can be challenging for what sounds like a less structured communication pattern (i.e. the updates can be required at unpredictable points in your algorithm). Normally, in spmd, the general pattern is each worker performs a bunch of work purely locally, then all workers together collaborate using communication.

[Walter Roberson]

A valid spmd pattern is

otherlabs = setdiff(1:numlabs,labIndex);

while true
  while labProbe
    newkv = labRecieve;
    update local hash using newkv{1} key and newkv{2} value
  end
  compute the next thing 
  if the computation required a new hash key 
    labSend({newkey, newvalue}, otherlabs) 
  end
end

This would have to be enhanced to handle shutting down labs gracefully when end of calculating is reached. For example instead of sending a cell a lab could send its own lab index with a tag marking a shut down. The labSend would first labProbe checking for that tag and if it finds it, labRecieve the tag and remove the received lab number from the list otherlabs before going ahead with the labSend to update the others.

[Edric Ellis]

I would not recommend that pattern, as it can lead to deadlock. labSend does not necessarily complete until the corresponding labReceive has started. Therefore, you can easily end up with all workers stuck trying to call labSend simultaneously (e.g. if they all wish to send on the first iteration). In practice, small messages get sent immediately by labSend using underlying buffering, but it is definitely not a good idea to rely on that. The "safe" version of that pattern unfortunately loses efficiency because it requires a synchronisation point after each "compute the next thing". Something like

spmd
    while ~done
        compute the next thing
        % all-to-all communication to disseminate values
        if the computation required a new hash key
            toCommunicate = {newkey, newvalue};
        else
            toCommunicate = {};
        end
        allNewKeysAndValues = gcat(toCommunicate);
        updateCache(allNewKeysAndValues);
        done = % some other collective decision
    end
end