Thread-safety of DART functions

[devreal]

The documentation states the following:

A note on thread safety:
All functions in the DART interface shall be implemented in a thread safe way.

This is problematic for two reasons:

• We cannot guarantee that the underlying communication library supports multi-threaded access (MPI provides MPI_Init_thread to check whether this is supported) neither do we enforce multi-threaded initialization at the moment.
• There are global data-structures in DART that are manipulated, e.g., the team or segment data structures. We could guard them with mutexes by default but that will likely cause some overhead even for single-threaded applications.

I propose to remove this sentence for now until we have support for tasking/multi-threading in DART in a later version. I would favor a relaxed policy, e.g., all communication operations should be thread-safe.

Related to #106

[fuchsto]

Thread-safe by default without any restriction on safe operations whatsoever is a bad idea, that's why the STL doesn't do it.
But I think the issue here is just the missing definition of thread safety.

All functions in the DART interface shall be implemented [...] thread safe

... does not specify if this refers to function calls on shared resources.
Calling dart_group_add_member in parallel is perfectly thread safe! But not on the same dart_group_t object.

I think that is what this spec is about. There must not exist any hidden shared states (global vars etc.)
that lead to data races the caller has no chance knowing about.

This also would correspond to the STL's understanding of thread safety in containers.
Concurrent reads must be safe, and concurrent writes with exactly one thread modifying the state.

Here's the meat:

An object is thread-safe for reading from multiple threads. For example, given an object A, it is safe to > read A from thread 1 and from thread 2 simultaneously.
If an object is being written to by one thread, then all reads and writes to that object on the same or
other threads must be protected. For example, given an object A, if thread 1 is writing to A, then
thread 2 must be prevented from reading from or writing to A.
It is safe to read and write to one instance of a type even if another thread is reading or writing to a
different instance of the same type. For example, given objects A and B of the same type, it is safe
when A is being written in thread 1 and B is being read in thread 2.

Note that the second part

If an object is being written to by one thread, then all reads and writes to that object on the same or
other threads must be protected.

... refers to the responsibility of the programmer, not the STL.

[fuchsto]

@fuerlinger @knuedd @colinglass @jgraciahlrs
What is the stance of the members of the honorable DART Interface Review Board (DIRB) on this?

[fuerlinger]

I'm not particularly worried about locks on group manipulation routines. Team creation will be slow anyhow and if you are doing it too often, then you are doing something wrong.

However, data access operations should certainly be as fast as possible and we should (and can) avoid locks. Similar to STL, DASH datastructures are not concurrent data structures - that's a whole different story that we can look into eventually

I have not looked into this too closely but it looks like the STL allows concurrent access to container elements as long as different threads access different data elements.

http://en.cppreference.com/w/cpp/container

I think a similar approach would be great (and natural) for DASH. However, even this approach requires that we use MPI_Init_thread(THREAD_MULTIPLE), since several threads might concurrently issue MPI_Put and MPI_Get operations.

As far as I know THREAD_MULTIPLE can be significantly slower than THREAD_SINGLE for many MPI implementations and so that might be a bit of a problem.

So maybe the cleanest solution would be to give the user the choice of threading model, i.e., dash_init(THREAD_MULTIPLE) vs. dash_init(THREAD_SINGLE).

[fuchsto]

Yes, concurrent writes to independent container elements are valid, but that's the same thing:
Writes to container elements do not modify the container's state unless specified otherwise by const qualifiers. Adding / removing elements modifies the container and would not be considered safe.
Fortunately since C++11, we can rely on the new, useful semantics of const.

P.S.: @fuerlinger Fixed a funny typo in your link.

[fuchsto]

Hm, it's a bit of a shame, really. This use case is a prime example for STL execution policies:
http://en.cppreference.com/w/cpp/experimental/parallelism
... but enabling or disabling MPI multi-threading support for single operations is not feasible, apparently.

[devreal]

So maybe the cleanest solution would be to give the user the choice of threading model, i.e., dash_init(THREAD_MULTIPLE) vs. dash_init(THREAD_SINGLE).

This is currently the way I'm doing it on my tasking branch, except that the function is called dash_init_threads (of course this split is debatable). If the user requests THREAD_MULTIPLE and the MPI implementation does not support it we have to ensure mutual exclusion ourselves through locks. We could think about returning the actual concurrency level back to the user, just as MPI does.

From what I can see in the code, most functions are re-entrant on the DART level and can be called by multiple threads. However, at the moment there is some global state that is maintained for teams and segments so any function that creates a new team or allocates a segment is not thread-safe. Since these shared objects are not visible to the programmer they cannot be regarded thread-safe with respect to the definition given by @fuchsto. I also don't see a way to get rid of this hidden state without major redesign of the API.

If we want to keep the promise of thread-safety for the upcoming release I can guard these shared objects through locks, which should be easily doable.

[fuchsto]

I don't even see a way to make the state of teams a non-global state even with drastic redesigns.
If team configurations were local, they wouldn't actually achieve anything, the global effect is their actual purpose.
But is it a problem, actually? Why would a thread engange in team organization?
Team operations are collective by nature and must be executed by involved processes.
Delegating, say, a team split to threads appears conceptually broken to me.

Global allocation in DART must be refactored for thread safety, but it should be refactored anyways.

[devreal]

I agree that team management operations are not required to be thread-safe although one might think about initializing different parts of the code in parallel using threads (we all know this kind of users, right?). We need to specify which parts are meant to be thread-safe and which are not. In the future, global allocations need to be thread-safe since they can be easily hidden in some DASH functionality (e.g., dash::algorithm) that is called from within a thread-parallel region. However, we should postpone that to the next release as it will be invasive.

For this release though, my main issue is the underlying MPI layer and with that the communication operations. Since we currently have no way of signaling whether the underlying MPI supports thread-multiple I see three options for the upcoming release:

1. Document that at the moment thread-parallel access is not possible in general. This is the most strict and least invasive solution.
2. Extend the DART and DASH interfaces to allow the user to request thread-multiple and:
   a) Pass back the actual support for concurrency and leave it to the user to adhere to it, or
   b) Ensure mutual exclusion ourselves if the underlying MPI does not support thread-multiple but the user requested it.

Personally I am slightly in favor of 2a but I have code in place to implement 2b as well.

[fuchsto]

Yes, totally aggree. For the upcoming release, I'd just add documentation of thread-safe/-unsafe functions and not change anything in implementation for now.

[devreal]

Agreed. RFC:

A note on thread safety:

At the moment, the DART API specification does not guarantee the correctness
of thread-parallel access. It is thus erroneous to use DART or DASH functionality
from within a multi-threaded context.
The specification of thread-safety will be added in the next release.

I will also open a ticket to track the implementation of thread-safe global allocation after this release.

[fuchsto]

That would work, but we can elaborate some more already.

• include the definition for Thread Safety and its compliance to the STL.
• define Doxygen tags for DART types:
  • \thread_safe_read - safe for concurrent reads
  • \thread_safe_single_write - safe if at most one thread is writing/modifying
  • \thread_safe - safe without restrictions

Example: dart_team_t

dart_team_create : \thread_safe_single_write
dart_team_myid : \thread_safe_read
dart_team_size : \thread_safe_read

[fuchsto]

@devreal Off-topic remark: we use the "compact" format in Doxygen instead of \brief.
The first paragraph is used as \brief, the following paragraphs (separated by first empty line) is the full
documentation.

Example:

/**
 *  Whether the communication sub-system is self-aware.
 * 
 *  Falsification test if the communication sub-system reached singularity.
 * 
 *  \returns   \c 1   if the sub-system is self-aware and open about it or
 *             \c 0   if the sub-system is either not self-aware or decided to lie about it 
 */
int dart_is_self_aware();

[devreal]

Thanks for the hint, will fix it within branch sup-109-dart-threadsafety.
I will also annotate the DART functions with thread-safety information.

[fuchsto]

@devreal No need for a fix, \brief still works.
The thread-safety doxygen tags are just a suggestion, let us know if you find something better.

[devreal]

Having given it more thought, I think it does not make sense to distinguish between read and write access in DART. You either call a DART function from multiple threads or you don't. The STL definition of thread-safety does not apply to the DART API, although it does apply to DASH of course.

For DART, I think we should specify the following three:

• \threadsafe: safe to call from multiple threads concurrently.
• \threadsafe_serial: safe to call from different threads within a multi-threaded context but access has to be serialized by the user.
• \threadsafe_none: Not thread-safe whatsoever, do not call from within a multithreaded context.

Note that the MPI standard mandates that a normal MPI_Init has the same effect as calling MPI_Init_thread with MPI_THREAD_SINGLE (which actually mandates that the process is not multi-threaded at all, which is graciously ignored when doing classical MPI+OpenMP). So \threadsafe_none should be the default for all DART functionality that involves MPI unless we initialize the MPI thread environment.

Also note, that we might have to apply this scheme to groups of functions, i.e., even with MPI_THREAD_MULTIPLE you cannot issue collective operations in parallel due to the required matching of collectives but you can issue a get or put in parallel with a collective operation on another thread. So inside the group CollectiveOperations it would be \threadsafe_none but across function groups it's \threadsafe. We have to think about a way to express that when we work on the thread-safety improvements.

[fuerlinger]

@devreal sounds good to me.

In the cautionary note on thread safety we should also note that local-view access to DASH data structures does not involve DART calls and can thus be safely be performed in a thread parallel way.

dash::Array<int> arr(...);
#pragma omp parallel for // OK to parallelize since we're working on .local 
for( auto i=0; i<arr.local.size(); i++ ) [
 arr.local[i]=foo(i);
}

@fuchsto The above is true for dash::Matrix too, right? I.e., dash::LocalMatrixRef etc. are tread-safe out of the box?

[fuchsto]

@fuerlinger Yes, we could even specify this as a general constraint:

Operations on local view accessors like Container.local or Container.lbegin do not
involve communication.

However, dart_put is not an atomic write operation, right? So RDMA could lead to
data races at the target unit, if I'm not mistaken. Otherwise, we could add:

... and do not depend on any non-local process.

[devreal]

Correct, dart_put is not atomic, only compare_and_swap and fetch_and_op are. It is up to the user to prevent data races, just like the definition of thread-safety in the STL states.

[fuchsto]

With the documentation updates by @devreal we can safely consider this issue resolved.